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. The prime decomposition of n! is given by

n!=\prod _{{\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. The former product only needs to be taken for primes less than or equal to n, so the latter sum only needs to be taken for j ranging from 1 to floor( log_p(n) ), i.e.:

s_{p}(n)=\sum _{j=1}^{\lfloor \log _{p}(n)\rfloor }\left\lfloor {\frac {n}{p^{j}}}\right\rfloor

The small disadvantage of the De Polignac's formula is that we need to know all the primes up to n. In fact,

\displaystyle n!=\prod _{i=1}^{\pi (n)}p_{i}^{s_{p_{i}}(n)}=\prod _{i=1}^{\pi (n)}p_{i}^{\sum _{j=1}^{\lfloor \log _{p_{i}}(n)\rfloor }\left\lfloor {\frac {n}{{p_{i}}^{j}}}\right\rfloor },

where $\pi (n)$ is a prime-counting function counting the number of prime numbers less than or equal to n.

Notes and references

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

This article is issued from Wikipedia - version of the 10/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.