Prime factorisation of $n!$ as $n \to \infty$

By Pooya Farshim (P2572) on Friday, June 2, 2000 - 01:36 am :

Let:

n! = 2^{a_{1}} . 3^{a_{2}} . 5^{a_{3}} . \dots . p_{m}^{a_{m}}

Show that as $n \to \infty$ :

$a_{i} = a_{1} / (p_{i} - 1)$

By Alex Barnard (Agb21) on Monday, June 12, 2000 - 12:55 pm :

A quick sketch answer:

If you know the formula for the a_i then it is easy. Let d(n,m) be the sum of the digits of n written in base m.

So, d(10,2) = 2 as 10 is 1010 in base 2
d(10,3) = 2 as 10 is 101 in base 3
d(10,4) = 4 as 10 is 22 in base 4

Then it can be shown that a_i = (n-d(n,i))/(i-1).

So, because d(n,m) is very small compared to n, you get the limit you claimed.

AlexB.

PS: There are many other nice results like the one above. For example can you show that the power of p (prime) that divides (n Choose r) is given as follows:

In base p write down the sum r + (n-r) and perform the sum longhand. The power of p is the sum of the carries that occur.

Eg. what power of 2 divides (20 Choose 3)?

3 is 11 in base 2; 17 is 1001 in base 2 so the sum is:

0011
1001 +
----
1100 =
0110 carries

So it is 0+1+1+0 = 2.

This can be obviously generalised to multinomial coefficients if you know what these are.