# 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 {\mathrm{log}}_{{p}_{i}}n\rfloor}}\lfloor {\displaystyle \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 $$, 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 |