ルジャンドルの公式
) = ∑ i = 1 l ⌊ n p i ⌋ = ∑ i = 1 l ( n l p l − i + ⋯ + n i + 1 p + n i ) = ∑ i = 1 l ∑ j = i l n j p j − i = ∑ j = 1 l ∑ i = 1 j n j p j − i = ∑ j = 1 l n j ⋅ p j − 1 p − 1 = ∑ j = 0 l n j ⋅ p j − 1 p − 1 = 1 p − 1 ∑ j = 0 l ( n j p j − n j ) = 1 p − 1 ( n − s p ( n ) ) {\displaystyle {\begin{aligned}\nu _{p}(n!)&=\sum _{i=1}^{\ell }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor \\&=\sum _{i=1}^{\ell }\left(n_{\ell }p^{\ell -i}+\cdots +n_{i+1}p+n_{i}\right)\\&=\sum _{i=1}^{\ell }\sum _{j=i}^{\ell }n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }\sum _{i=1}^{j}n_{j}p^{j-i}\\&=\sum _{j=1}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&=\sum _{j=0}^{\ell }n_{j}\cdot {\frac {p^{j}-1}{p-1}}\\&={\frac {1}{p-1}}\sum _{j=0}^{\ell }\left(n_{j}p^{j}-n_{j}\right)\\&={\frac {1}{p-1}}\left(n-s_{p}(n)\right)\end{aligned}}}