The formula which is often attributed to de Polignac gives \phi(p, n), the number of factors p in the prime factorization of n!.

where S_{p} is the sum of p-digits of n, i.e., the sum of the digits in the representation of n in base p.

The first equality is straightforward. There are \lfloor n/p\rfloor numbers below n, that are divisible by p. Among these, there are numbers that are divisible by p^{2} and which contribute additional factors of p. There are \lfloor n/p^{2}\rfloor such numbers. Among these there are numbers that are divisible by p^{3} and which contribute an additional factor of p each. There are \lfloor n/p^{3}\rfloor such numbers. The process will continue until we meet the largest power of p that still divides n after which all terms in the sum become 0, so that the sum is in fact finite.

For the second equality we need the expansion of n in base p. Let

Note that

Returning to the sum,

* *

which completes the proof.

Interestingly, Legendre's formula has been recently used to prove the infinitude of primes.

(There is a little more detailed derivation and several application of the theorem.)