1
$\begingroup$

What I am trying to figure out is a way to compute large factorials, !1000000.

For what it's worth luschny's computer algorithms do a very good job of it.

  • 1
    Have you seen Walter Koetke, Computing Factorials -- Accurately, Best of Creative Computing, Volume 1, page 172, available at http://www.atariarchives.org/bcc1/showpage.php?page=172 ? State of the art (for programs written in BASIC in 1976). Perhaps more useful is http://www.idinews.com/factorial.html2012-04-27

1 Answers 1

3

Let's take an example which fits on the page, which you can extend if you want. As a product of powers of primorials, you have

$100!=p_{1}\#^{49}\times p_{2}\#^{24}\times p_{3}\#^{8}\times p_{4}\#^{7}\times p_{5}\#^{2}\times p_{6}\#^{2}\times p_{8}\#\times p_{9}\#\times p_{11}\#\times p_{15}\#\times p_{25}\#$

where for example $p_{3}\#^{8}$ means the eighth power of the third primorial, i.e. $(2 \times 3 \times 5)^8$.

The reason for an eighth power is that the prime factorisation of $100!$ includes $5^{24}$ and $7^{16}$ with $24-16=8$. One way of calculating this to to take $\left( \left\lfloor \frac{100}{5^1}\right\rfloor +\left\lfloor \frac{100}{5^2}\right\rfloor +\left\lfloor \frac{100}{5^3}\right\rfloor +\cdots \right) - \left( \left\lfloor \frac{100}{7^1}\right\rfloor +\left\lfloor \frac{100}{7^2}\right\rfloor +\left\lfloor \frac{100}{7^3}\right\rfloor +\cdots \right). $

  • 1
    $100! = 2^{97} 3^{48} 5^{24} 7^{16} 11^{9} 13^{7} 17^{5} 19^{5} 23^{4} 29^{3} 31^{3} 37^{2} 41^{2} 43^{2} 47^{2} 53^{1} 59^{1} 61^{1} 67^{1} 71^{1} 73^{1} 79^{1} 83^{1} 89^{1} 97^{1} $ and then take the first difference of the exponents of the primes to find the exponents of the primorials. I also showed how I found the exponents of the primes, similar to what I did in http://math.stackexchange.com/a/131068/64602012-04-27