# Legendre's Formula

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

\phi(p, n) = \sum_{k=1}\bigg\lfloor \frac{n}{p^k} \bigg\rfloor = \frac {n - S_{p}(n)}{p - 1},

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

(n)_{p} = a_{m}a_{m-1}\ldots a_{1}a_{0}

Note that

\bigg\lfloor\frac{n}{p^k}\bigg\rfloor = a_{m}a_{m-1}\ldots a_{k+1}a_{k}.

Returning to the sum,

\sum_{k=1}\bigg\lfloor \frac{n}{p^k} \bigg\rfloor = \sum_{s=1}{a_{s}}(p^{s-1}+p^{s-2}+\ldots + p + 1) = \sum_{s=1}{a_{s}}\frac{p^{s} - 1}{p - 1} = \frac{\sum_{s=1}{a_s}{p^s} - \sum_{s=1}{a_s}}{p-1}
=\frac{{({n} - a_{0})} - (S_{p}(n) - a_{0})}{p-1} = \frac {n - S_{p}(n)}{p - 1},

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.)