Factorial numbers, n!=1⋅2⋯n, grow very fast with n. In fact, n!∼2πn(n/e)n according to Stirling's approximation. The prime factors of a factorial number, however, are all relatively small, and the complete factorization of n! is quite easy to obtain.
We will make use of the following fundamental theorem:
and p=3 as an example. How many of the numbers 1, 2, …, 42 are divisible by 3? Exactly ⌊42/3⌋=14 of them. But this is not the total count, because some of them are divisible by 3 multiple times. So how many are divisible by 32? ⌊42/32⌋=4 of them. Similarly, ⌊42/33⌋=1. And ⌊42/34⌋=⌊42/35⌋=…=0. So we have
Notice how the exponents do not increase as the prime numbers increase. This is true in general. Assume that p and q are both primes and p<q. Then logp(n)≥logq(n) and n/pk≥n/qk for all positive integers k. Using this in equation (1) we get
dp(n!)≥dq(n!)for primes p, q with p<q
What about dk(n!) for composite numbers k? Given the factorization of both n! and k, this is easy to compute. But if, e.g., the multiplicity of all prime factors of k are the same, then the relation (2) can be used. Consider d10(m) for a positive integer m. Since 10=2⋅5 then
But if m=n! then we can use (2) and we have
so there are 9 trailing zeros in the decimal representation of 42!.
Commenting is not possible for this post, but feel free to leave a question,
correction or any comment by using the contact page