De Polignac–Legendre formula

This article page is a stub, please help by expanding it.

The prime factorization of

n!, n   ≥   1,

is given by de Polignac's formula, named after Alphonse de Polignac. L. E. Dickson attributes the formula to Legendre.

Formula

The prime factorization of 

n!

, 

n   ≥   1

, is given by

${\begin{array}{l}\displaystyle {n!=\prod _{\stackrel {\scriptstyle p{\text{ prime}}}{p\leq n}}p^{\operatorname {ord} _{p}\,n!},}\end{array}}$

where

${\begin{array}{l}\displaystyle {\operatorname {ord} _{p}\ n!=\sum _{k=1}^{\lfloor \log _{p}(n)\rfloor }\left\lfloor {\frac {n}{p^{k}}}\right\rfloor ,}\end{array}}$

is the p-adic valuation of

n!

(order of prime

p

in the prime factorization of

n!

) and the brackets represent the floor function.

Examples

Consider

${\begin{array}{l}\displaystyle {5!=1\cdot 2\cdot 3\cdot 4\cdot 5=2^{3}\cdot 3^{1}\cdot 5^{1},}\end{array}}$

for which the

p

-adic valuations for primes

p

up to 5 are

${\begin{array}{l}\displaystyle {\operatorname {ord} _{2}\ 5!=\sum _{k=1}^{\lfloor \log _{2}(5)\rfloor }\left\lfloor {\frac {5}{2^{k}}}\right\rfloor =\left\lfloor {\frac {5}{2^{1}}}\right\rfloor +\left\lfloor {\frac {5}{2^{2}}}\right\rfloor =2+1=3,}\end{array}}$

${\begin{array}{l}\displaystyle {\operatorname {ord} _{3}\ 5!=\sum _{k=1}^{\lfloor \log _{3}(5)\rfloor }\left\lfloor {\frac {5}{3^{k}}}\right\rfloor =\left\lfloor {\frac {5}{3^{1}}}\right\rfloor =1,}\end{array}}$

${\begin{array}{l}\displaystyle {\operatorname {ord} _{5}\ 5!=\sum _{k=1}^{\lfloor \log _{5}(5)\rfloor }\left\lfloor {\frac {5}{5^{k}}}\right\rfloor =\left\lfloor {\frac {5}{5^{1}}}\right\rfloor =1.}\end{array}}$