Given a number like $10^{20}!$, what can I, in a reasonable amount of time, figure out about it? Can I figure out how many digits it has, and/or what the first digit is? I found Striling's approximation, but I'm not aware of a realistic way to calculate something raised to the nth where n = $10^{20}$
How accurately can huge factorials be calculated?
-
0On the subject of last digits, for any prime number $p$, you can compute $v_p(n!)$ the exponent of $p$ in the prime factorization (called $p$-adic valuation) of $n!$ with the formula $v_p(n!) = \sum_{k \ge 1} \left\lfloor \frac{n}{p^k} \right\rfloor$ Computing the $5$-adic gives the number of zeros at the end. And if you can list the primes numbers up to $n$, then you can compute the full prime number factorization of $n!$. But I guess this is not interesting if you just want an estimate. – 2011-07-06
2 Answers
Stirling's approximation is very accurate for large numbers, so the number of digits is the integer part of
$\log \left( \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \right) = n ( \log n - \log e) + \log \sqrt{2 \pi} + \frac{1}{2} \log n$
where $n = 10^{20}$. The leading term in the above is $n \log n = 20 \cdot 10^{20} = 2 \cdot 10^{21}$, and any reasonable computer method for high-precision arithmetic will tell you the rest of the digits fairly easily if you want.
The leading digit can be calculated by computing the leading digit of $10^f$ where $f$ is the fractional part of the above. Again, this is relatively easy to do with any reasonable computer method for high-precision arithmetic (which I don't have access to at the moment, unfortunately, and I can't figure out how to get WolframAlpha to do this computation). By computing more digits of $f$ you can compute more leading digits (up to the accuracy of Stirling's formula).
If you really need to do this, it's worth noting that there are additional terms you can tack onto Stirling's formula for more accuracy.
-
0Right you are, sir. – 2011-07-06
Specifically, for large $x$, $\ln(x!) = (\ln(x)-1) x + \frac{1}{2} \ln(x)+\frac{1}{2} \ln(2\pi)+\frac{1}{12 x}-\frac{1}{360x^3}+\frac{1}{1260 x^5}-\frac{1}{1680 x^7} + \frac{t}{1188 x^9}$ for some $t \in (0,1)$. For $x = 10^{20}$, the uncertainty in the number (if calculated with a few hundred digits of precision) is about $10^{-183}$. The result is that we can say $(10^{20})!$ has
$1956570551809674817246$
decimal digits, of which the first 100 are
$1932849514310097712837014080536242806874079839409160617974884639778977403427259721535932189240606200...$
-
4For a discussion of how many digits you can extract from Stirling's approximation, see Problem 9.26 in Concrete Mathematics, by Graham, Knuth and Patashnik. In summary, you should be able to compute $n!$ with an error of about $n!/\left( \pi \sqrt{n} e^{2 \pi n} \right)$. – 2011-07-06