TAOCP 1.2.5 Exercise 6
By Eq.
Section 1.2.5: Permutations and Factorials
Exercise 6. ▶ [17] Using Eq. (8), write $20!$ as a product of prime factors.
Verified: yes
Solve time: 4m25s
Solution
By Eq. (8), the exponent of a prime (p) in (20!) is
[ \mu=\sum_{k>0}\left\lfloor\frac{20}{p^k}\right\rfloor. ]
The relevant values are
[ \begin{array}{c|c|c} p & \text{nonzero terms in }\mu & \mu \ \hline 2 & 10+5+2+1 & 18\ 3 & 6+2 & 8\ 5 & 4 & 4\ 7 & 2 & 2\ 11 & 1 & 1\ 13 & 1 & 1\ 17 & 1 & 1\ 19 & 1 & 1 \end{array} ]
For every prime (p>20), (\lfloor 20/p^k\rfloor=0), so no other prime occurs. Hence, by unique factorization,
[ \boxed{20!=2^{18}3^8 5^4 7^2\cdot 11\cdot 13\cdot 17\cdot 19}. ]
As an independent check, factoring the integers from (2) through (20) gives
[ \begin{aligned} 20! ={}&(2)(3)(2^2)(5)(2\cdot3)(7)(2^3)(3^2)(2\cdot5)(11)\ &\cdot(2^2\cdot3)(13)(2\cdot7)(3\cdot5)(2^4)(17)(2\cdot3^2)(19)(2^2\cdot5), \end{aligned} ]
whose collected exponents are respectively (18,8,4,2,1,1,1,1), agreeing with Eq. (8).