Legendre formula

R(p,n)=∑i=1∞⌊npi⌋R(p,n) = \sum^{\infty}_{i=1}\left\lfloor\frac{n}{p^i}\right\rfloor

where R(p,n)R(p,n) to be n!n!'s a largest exponent of a prime factor pp. and ⌊x⌋\lfloor x\rfloor is the floor function.

Proof

since n!n! is each multiply of {1,2,..,n}\{1, 2, .., n\}, ⌊np⌋\lfloor\frac{n}{p}\rfloor is the number of multiple of p in {1,..,n}\{1, .., n\}. also ⌊np2⌋\lfloor\frac{n}{p^2}\rfloor is a number of multiple of p2p^2 in {1,..,n}\{1, .., n\}. adding all these number take the infinite sum for R(p,n)R(p,n).

Alternate form

R(p,n)=n−sp(n)p−1.R(p,n)={\frac {n-s_{p}(n)}{p-1}}.

where sp(n)s_{p}(n) is sum of nl,nl−1,...,n0n_l,\, n_{l-1},\,...,\,n_0 such that n=nlpl+nl−1pl−1+⋯+n0n = n_lp^l + n_{l-1}p^{l-1} + \cdots + n_0.

Proof

R(p,n)=∑i=1l⌊npi⌋=∑i=1lnlpl−i+⋯+ni=∑i=1l∑j=ilnjpj−i=∑j=1l∑i=1jnjpj−i=∑j=1lnjpj−1p−1=∑j=1lnjpj−1p−1=1p−1∑j=1lnj(pj−1)=1p−1(∑j=1lnjpj−∑j=1lnj+n0−n0)=1p−1(∑j=0lnjpj−∑j=10nj)=1p−1(n−sp(n)){\begin{aligned}R(p,n) &= \sum^{l}_{i=1}\left\lfloor\frac{n}{p^i}\right\rfloor = \sum^{l}_{i=1}n_lp^{l-i} + \cdots + n_i =\sum^{l}_{i=1}\sum^{l}_{j=i} n_jp^{j-i} = \sum^{l}_{j=1}\sum^{j}_{i=1} n_jp^{j-i} \\&=\sum^{l}_{j=1}n_j\frac{p^{j} - 1}{p - 1} =\sum^{l}_{j=1}n_j\frac{p^{j} - 1}{p - 1} \\&=\frac{1}{p-1}\sum^{l}_{j=1}n_j(p^{j} - 1) =\frac{1}{p-1}(\sum^{l}_{j=1}n_jp^{j} - \sum^{l}_{j=1}n_j + n_0 - n_0) \\&=\frac{1}{p-1}(\sum^{l}_{j=0}n_jp^{j} - \sum^{0}_{j=1}n_j) =\frac{1}{p-1}(n - s_{p}(n)) \end{aligned}}

Example

for n=6n=6, 6!=720=24⋅32⋅516!=720=2^{4}\cdot 3^{2}\cdot 5^{1}.

R(2,6)=∑i=1∞⌊62i⌋=⌊62⌋+⌊64⌋=3+1,R(3,6)=∑i=1∞⌊63i⌋=⌊63⌋=2,R(5,6)=∑i=1∞⌊65i⌋=⌊65⌋=1.{\begin{aligned}R(2,6)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor=3+1, \\ R(3,6) &=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2, \\ R(5,6) &=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}