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
    You'll have to add more information than that to your question. In my opinion, one shouldn't have to know a programming language to understand a question on this math Q&A site.2012-04-26
  • 0
    As Zev is suggesting, this might be appropriate for another SE site. The questions here should be math related. I'm not saying yours isn't, but rather that it is more related to programming than math.2012-04-26
  • 0
    I included the reference to the code to provide some context for my situation. I made a few edits to hopefully clear things up.2012-04-26
  • 1
    1,000,000 factorial has about 5,000,000 digits. Do you actually want to calculate that five million digit number exactly?2012-04-26
  • 0
    @GerryMyerson, yes. I know there are ways to approximate large factorials and I do not think they will work for what I am trying to do.2012-04-26
  • 0
    @john Stirling's approximation is a great one. For very large values of $n$, only the last few digits will be off.2012-04-26
  • 0
    @Gerry: For what it is worth, 1,000,000! has 5,565,709 digits or there about.2012-04-27
  • 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). $$

  • 0
    I understand the notation for primorials, however I am still stuck on how you were able to determine the product of !100 in terms of primorials...2012-04-27
  • 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