de Polignac’s formula


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

i=1π(n)pij=1logpinnpij,

where pi is the ith prime and π(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<pij, dividing the former by the latter gives a value that floors to zero, and then pi0=1. And when i>π(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 divisionMathworldPlanetmath (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 factorsMathworldPlanetmath have already been divided out of the factorialMathworldPlanetmath.

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 28×34×52×71=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