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:
An application of this theorem to factorial numbers is that if a prime p is a divisor of n! then p must be a divisor of at least one of the numbers 1,2,…,n. This immediately implies
Every prime factor of n! is less than or equal to n.
Conversely, every prime number between 2 and n must be a prime factor of n!.
Let us introduce the notation da(b) as the number of times a divides into b. Put more precisely, da(b)=k if and only if b/ak is an integer while b/ak+1 is not.
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
(2)
dp(n!)≥dq(n!)for primes p, q with p<q
and thus
d2(n!)≥d3(n!)≥d5(n!)≥d7(n!)≥d11(n!)≥…
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
d10(m)=min{d2(m),d5(m)}.
But if m=n! then we can use (2) and we have
d10(n!)=d5(n!).
For instance,
d10(42!)=d5(42!)=⌊42/5⌋+⌊42/52⌋=8+1=9,
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