# General formula for this

1. Dec 16, 2005

### 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.

2. Dec 16, 2005

### 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 512.

3. Dec 16, 2005

### twoflower

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

4. Dec 16, 2005

### AKG

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

(a0,k) = (0, 0, ...)
(a1,k) = (0, 0, ...)
(a2,k) = (1, 0, 0, ...)
(a3,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.

5. Dec 16, 2005

### 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:
xp 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 x2 consecutive integers there's one integer that's divisible by x2, for every x3 consecutive integers there's one integer that's divisible by x3,...
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 xp 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$$

Last edited: Dec 16, 2005
6. Dec 25, 2005

### 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.