General formula for this

  • Thread starter twoflower
  • Start date
  • #1
368
0
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.
 

Answers and Replies

  • #2
AKG
Science Advisor
Homework Helper
2,565
4
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
368
0
AKG said:
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.

Yes, this manual approach is clear. But there is also a general formula..
 
  • #4
AKG
Science Advisor
Homework Helper
2,565
4
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
VietDao29
Homework Helper
1,424
3
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: [tex]\rho := \left[ \frac{\ln n}{\ln x} \right][/tex], ie: [tex]\rho[/tex] is the largest positive integer such that: [tex]x ^ \rho \leq n[/tex]
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:
[tex]p := \sum_{i = 1} ^ \rho \left[ \frac{n}{x ^ i} \right][/tex]
---------------------
If x is not prime, then you can prime-factorize it:
[tex]x = \lambda_1 ^ {\alpha_1} \ \lambda_2 ^ {\alpha_2} \ \lambda_3 ^ {\alpha_3} \ ... \lambda_k ^ {\alpha_k}[/tex]
Where: [tex]\lambda_i, \ i = 1..k[/tex] are primes.
Then: [tex]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}[/tex]
If xp divides n! then [tex]\lambda_i ^ {\alpha_i p}, \ i = 1..k[/tex] must also divide n!.
So you can use the same method (as shown above) to find the largest [tex]\rho_i, \ i = 1..k[/tex] such that [tex]\lambda_i ^ {\rho_i}, \ i = 1..k[/tex] divides n!.
Then define: [tex]\beta_i := \left[ \frac{\rho_i}{\alpha_i} \right], \ i = 1..k[/tex].
And the largest p can be found by:
[tex]p = \min (\beta_i), \ i = 1..k[/tex]
 
Last edited:
  • #6
benorin
Homework Helper
Insights Author
Gold Member
1,307
109
The exact power of a prime p dividing n! is alternatively given by

[tex]\frac{n-\mu}{p-1},[/tex]

where [itex]\mu[/itex] is the sum of the digits of the base p representation of n.
 

Related Threads on General formula for this

Replies
4
Views
3K
Replies
2
Views
3K
Replies
4
Views
584
Replies
1
Views
846
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
161
Replies
2
Views
4K
Replies
1
Views
12K
Replies
4
Views
2K
Replies
6
Views
2K
Top