de Polignac’s formula

Given $n$ , the prime factorization of $n!$ can be obtained by applying de Polignac’s formula:

\prod_{i=1}^{\pi(n)}{p_{i}}^{\displaystyle\sum_{j=1}^{\lfloor\log_{p_{i}}n% \rfloor}\lfloor\frac{n}{{p_{i}}^{j}}\rfloor},

where $p_{i}$ is the $i$ th prime and $\pi(n)$ is the prime counting function. For both the product and the summation, the iterator’s end value can be set to infinity and the formula is still correct. When $n<{p_{i}}^{j}$ , dividing the former by the latter gives a value that floors to zero, and then ${p_{i}}^{0}=1$ . And when $i>\pi(n)$ then all $j$ give zero in the summation, and the multiplicand for the product is also 1. It is for the sake of a computer implementation that it is necessary to stop the iterations when they no longer give useful results.

A small disadvantage of de Polignac’s formula is that it is necessary to know all the primes up to $n$ . If the implementation mistakenly iterates through a composite value, the error might not be detected, while even with a dumb implementation of trial division (e.g., one that tries odd composite values) the worst that can happen is that time is wasted by trying to divide by a composite value whose prime factors have already been divided out of the factorial.

Let’s work out an example: factoring 10!. The primes less than 10 are 2, 3, 5 and 7. The base 2 logarithm of 10 is approximately 3.32, meaning we only need to divide and floor up to 2’s cube. Half 10 is 5, a quarter of 10 is 2.5 and an eighth of 10 is 1.25; adding up the integer parts of these gives us 8, so the exponent for 2 in the factorization of 10! is 8. The base 3 logarithm of 10 is approximately 2.0959. A third of 10 is about 3.3333 and a ninth of 10 is about 1.1111; the integer parts of these added up gives 4, so the exponent for 3 in the factorization is 4. For both bases 5 and 7, the logarithm of 10 is more than 1 but less than 2. 10 divided by 5 is 2, so that’s our exponent for 5. 10 divided by 7 is about 1.42857, so 1 is our exponent for 7. Then we verify that indeed $2^{8}\times 3^{4}\times 5^{2}\times 7^{1}=3628800=10!$

Title	de Polignac’s formula
Canonical name	DePolignacsFormula
Date of creation	2013-03-22 17:59:54
Last modified on	2013-03-22 17:59:54
Owner	PrimeFan (13766)
Last modified by	PrimeFan (13766)
Numerical id	6
Author	PrimeFan (13766)
Entry type	Definition
Classification	msc 11A51