6
$\begingroup$

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}$

  • 0
    On 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 2

11

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.

  • 0
    Right you are, sir.2011-07-06
12

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...$

  • 4
    For 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