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

$\endgroup$
  • $\begingroup$ I can tell you what the last digit is... would you settle for the number of digits in the number of digits? $\endgroup$ – Qiaochu Yuan Jul 6 '11 at 15:10
  • $\begingroup$ @Qiaochu: Um... Zero. $\endgroup$ – Benjamin Lindley Jul 6 '11 at 15:11
  • $\begingroup$ @Qiaochu: If that's the best that can be done, then yeah, I'd accept that. $\endgroup$ – Benjamin Lindley Jul 6 '11 at 15:13
  • $\begingroup$ 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. $\endgroup$ – Joel Cohen Jul 6 '11 at 17:27
11
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ The last term in your sum should be $\log \sqrt{n}$ or ${1 \over 2} \log n$. $\endgroup$ – Michael Lugo Jul 6 '11 at 15:27
  • $\begingroup$ Right you are, sir. $\endgroup$ – Qiaochu Yuan Jul 6 '11 at 15:50
12
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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)$. $\endgroup$ – David E Speyer Jul 6 '11 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.