De Polignac's formula

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

n! = \prod_{\text{prime }p\le 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 the former product can equally well be taken only over primes less than or equal to n, and the latter sum can equally well be taken for j ranging from 1 to logp(n), i.e :

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

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 sp(n).

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[edit]

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