What is the formula for finding the highest power of x that is divisible by n!?

[twoflower]

Hi all,

there is general formula for findind out, "Which highest power of x is divisible n! with?" Eg. Which highest power of 5 is divisable 50! with?

But I forgot it and can't find it now...will somebody help me please?

Thank you.

 

[AKG]

You mean, what is the highest power of x that divides n!? Well if you can prime-factorize x and n!, this is easy. In the case of 5 and 50!, it's hard to prime-factorize 50!, but the solution is still easy. You can see quite easily that 5 will occur 12 times in the prime-factorization of 50! (it will occur once in each of the factors 5, 10, 15, 20, 30, 35, 40, 45, and twice in both 25 and 50), so the highest power of 5 that divides 50! is 5¹².

 

[twoflower]

You mean, what is the highest power of x that divides n!? Well if you can prime-factorize x and n!, this is easy. In the case of 5 and 50!, it's hard to prime-factorize 50!, but the solution is still easy. You can see quite easily that 5 will occur 12 times in the prime-factorization of 50! (it will occur once in each of the factors 5, 10, 15, 20, 30, 35, 40, 45, and twice in both 25 and 50), so the highest power of 5 that divides 50! is 5¹².

Yes, this manual approach is clear. But there is also a general formula..

 

[AKG]

I'm not sure about a general formula just yet, but this might be helpful: if you associate each factorial with a sequence (a_n,k)_{k in N}, where a_n,k is the power of the k^th prime in n!, you get:

(a_0,k) = (0, 0, ...)
(a_1,k) = (0, 0, ...)
(a_2,k) = (1, 0, 0, ...)
(a_3,k) = (1, 1, 0, 0, ...)
(3, 1, 0, 0, ...)
(3, 1, 1, 0, 0, ...)
(4, 2, 1, 0, 0, ...)
(4, 2, 1, 1, 0, 0, ...)
(7, 2, 1, 1, 0, 0, ...)
(7, 4, 1, 1, 0, 0, ...)
(8, 4, 2, 1, 0, 0, ...)
(8, 4, 2, 1, 1, 0, 0, ...)
(10, 5, 2, 1, 1, 0, 0, ...)
(10, 5, 2, 1, 1, 1, 0, 0, ...)
(11, 5, 2, 2, 1, 1, 0, 0, ...)

The exponent of 2 changes every 2 rows, the exponent of 3 changes every 3 rows, the exponent of p will change every p rows. Ignoring repetition, the exponents for 2 go: 0, 1, 3, 4, 7, 8, 10, 11, ...
For 3, they go 0, 1, 2, 4, 5, ...
For 5, they go 0, 1, 2, ...

Some numbers are skipped in the above sequences because powers occur, i.e. in the sequence for 2, it goes from 1 to 3 without going through 2 because the 4 in 4! contributes two 2's, not just 1. I'm very tired right now, but I suppose if you can generalize what's going on here, it might be a helpful step in finding a general formula.

Well I suppose if you just want to know the general formula and aren't trying to figure it out yourself, then the above isn't much help.

 

[VietDao29]

I suppose that this is not a homework problem... So here's my approach.
Let's say that [x] is the function that will return the integer part before the decimal point of the number x, eg: [37.5534] = 37.
Say, you need to find the largest p that satisfies:
x^p divides n!, for some given x (x is prime), and n.
Let: $$\rho := \left[ \frac{\ln n}{\ln x} \right]$$, ie: $$\rho$$ is the largest positive integer such that: $$x ^ \rho \leq n$$
So for every x consecutive integers there's one integer that's divisible by x, for every x² consecutive integers there's one integer that's divisible by x², for every x³ consecutive integers there's one integer that's divisible by x³,...
So the largest p can be obtained by:
$$p := \sum_{i = 1} ^ \rho \left[ \frac{n}{x ^ i} \right]$$
---------------------
If x is not prime, then you can prime-factorize it:
$$x = \lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}$$
Where: $$\lambda_i, \ i = 1..k$$ are primes.
Then: $$x ^ p = (\lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}) ^ p = \lambda_1 ^ {\alpha_1 p} \ \lambda_2 ^ {\alpha_2 p} \ \lambda_3 ^ {\alpha_3 p} \ ... \lambda_k ^ {\alpha_k p}$$
If x^p divides n! then $$\lambda_i ^ {\alpha_i p}, \ i = 1..k$$ must also divide n!.
So you can use the same method (as shown above) to find the largest $$\rho_i, \ i = 1..k$$ such that $$\lambda_i ^ {\rho_i}, \ i = 1..k$$ divides n!.
Then define: $$\beta_i := \left[ \frac{\rho_i}{\alpha_i} \right], \ i = 1..k$$.
And the largest p can be found by:
$$p = \min (\beta_i), \ i = 1..k$$

 

[benorin]

The exact power of a prime p dividing n! is alternatively given by

$$\frac{n-\mu}{p-1},$$

where $\mu$ is the sum of the digits of the base p representation of n.