De Polignac's formula

In number theory, de Polignac's formula, named after Alphonse de Polignac, gives the prime decomposition of the factorial n!, where n ≥ 1 is an integer. L. E. Dickson attributes the formula to Legendre.^[1]

The formula

Let n ≥ 1 be an integer. Then the prime decomposition of n! is given by

$\prod_{p\text{ prime},\, p \leq n} p^{s_p(n)}$

where

$s_p(n) = \sum_{j = 1}^\infty \left\lfloor\frac{n}{p^j}\right\rfloor$

and the brackets represent the floor function.

Note that, for any real number x, and any integer n, we have:

$\left\lfloor\frac{x}{n}\right\rfloor = \left\lfloor\frac{\lfloor x \rfloor}{n}\right\rfloor$

which allows one to more easily compute the terms s_p(n).

Notes and references

1. ^ Leonard Eugene Dickson, History of the Theory of Numbers, Volume 1, Carnegie Institution of Washington, 1919, page 263.