3
$\begingroup$

How many digits are there in 100 factorial?

How does one calculate the number of digits?

$\endgroup$

closed as off-topic by Grigory M, John Gowers, drhab, Aditya Hase, Mark Fantini Dec 20 '14 at 12:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Grigory M, John Gowers, drhab, Aditya Hase, Mark Fantini
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ Welcome to MSE. To get useful answers please provide some context to your question, including what you tried so far and where you got stuck. $\endgroup$ – Ittay Weiss Dec 20 '14 at 10:48
5
$\begingroup$

If I were writing a computer program to do it:

$$\left\lfloor\log_{10}(100!)\right\rfloor+1=\left\lfloor\sum_{i=1}^{100}\log_{10}(i)\right\rfloor+1 = 158$$

$\lfloor\log_b(x)\rfloor+1$ calculates the smallest integer power of $b$ which is greater than x. i.e. $$b^{\lfloor\log_b(x)\rfloor} \le x < b^{\lfloor\log_b(x)\rfloor+1}.$$ This is the same as the number of digits in a base-$b$ representation of $x$.

$\endgroup$
  • 1
    $\begingroup$ $\log_{10}(10) = 1$ so $\lceil\log_{10}(10)\rceil = 1$ which is not the number of digits in $10$. You want $1+\lfloor\log_{10}(x)\rfloor$. $\endgroup$ – Henrik Dec 20 '14 at 11:16
  • $\begingroup$ You also need to edit the ceilings to floors in the line below the first equation. $\endgroup$ – Henrik Dec 20 '14 at 11:19
  • $\begingroup$ Direct computation of the product with rescaling (no logarithms) can be more efficient. $\endgroup$ – Yves Daoust Dec 20 '14 at 12:12
  • $\begingroup$ +1 Though, if you're going use a computer program, then why not just Length[IntegerDigits[100!]] in Mathematica or WolframAlpha? My answer is similar in that it uses the same sum but then estimates that sum with an integral. $\endgroup$ – Mark McClure Dec 20 '14 at 13:28
  • $\begingroup$ Very true, My brain defaults to C++'s math.h whenever I think about calculation $\endgroup$ – David Peterson Dec 20 '14 at 14:23
5
$\begingroup$

Suppose that $x$ is a positive, $n$-digit integer. Note that, $$n-1=\log_{10}(10^{n-1}) \leq \log_{10}(x) < \log_{10}(10^n) = n.$$ Thus, you might compute, the floor of $\log_{10}(100!)$ and add $1$. But \begin{align} \log_{10}(100!) &= \sum_{k=1}^{100} \log_{10}(k) \approx \int_{1}^{100}\log_{10}(t)dt \\ &= \left.\frac{t\ln(t)-t}{\ln(10)}\right|_1^{100} \approx 157.005 \end{align} Thus, the answer ought to be 158.


The reason this can be expected to work is that the integral can be approximated via Riemann sums. In fact, $$\sum_{i=1}^{n} \log_{10}(i) < \int_1^n \log_{10}(t)dt < \sum_{i=2}^n\log(10,i) = \sum_{i=1}^n\log(10,i),$$ as illustrated for $n=20$ in the following picture:

enter image description here

Thus, $$\sum_{i=1}^{n} \log_{10}(i) - \sum_{i=1}^n\log(10,i) < \int_1^n \log_{10}(t)dt - \sum_{i=1}^n\log(10,i) < 0.$$ But, the term on the left is just $\log_{10}(100)=2$. So, the integral is a lower bound for the sum that cannot be more than two off of the actual value. Accounting for the fact that the integral is nearly mid-way between the sums, the error should less than one, which is why we hit he answer exactly.

$\endgroup$
  • $\begingroup$ Isn't it easier to use the known Stirling formula ? $\endgroup$ – Yves Daoust Dec 20 '14 at 13:23
  • $\begingroup$ Yes, probably so. But, then, I didn't learn Stirling's formula until well after I had learned about Riemann sums. And, as your answer nicely illustrates, it's nice to think about it from a relatively elementary perspective. I think I'll go upvote it! :) $\endgroup$ – Mark McClure Dec 20 '14 at 13:42
  • $\begingroup$ The $n\log n$ approach is extremely efficient, quasi $O(1)$. $\endgroup$ – Yves Daoust Dec 20 '14 at 17:11
  • $\begingroup$ Wow! That's actually the best of all the answers! Thanks. $\endgroup$ – Tanuj Jul 27 '17 at 15:33
3
$\begingroup$

Stirling's formula gives a good approximation: $$n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$
That is messier, but it helps because I can take the logarithm: $$\log(n!)\approx \log(\sqrt{2\pi n})+n\log\left(\frac{n}{e}\right)$$ That was the common base-ten logarithm.
The number of digits in $n!$ equals the next integer above $\log(n!)$.

$\endgroup$
  • $\begingroup$ But this is not a proof; moreover, are you sure? $\endgroup$ – Peter Franek Dec 20 '14 at 11:03
  • $\begingroup$ The approximation is not accurate enough. It gives $159.36873167803296$, whereas direct calculation, as in @David Peterson's answer, gives $157.97000365471575$. This is in 64 bit arithmetic in Java. $\endgroup$ – Thumbnail Dec 20 '14 at 11:41
  • 2
    $\begingroup$ I got 157.9696... Did you square-root $2\pi n$ first? $\endgroup$ – Empy2 Dec 20 '14 at 11:58
  • $\begingroup$ I did not :(. Doing so, I get the same as you. $\endgroup$ – Thumbnail Dec 20 '14 at 12:11
2
$\begingroup$

Using a four-operations calculator, you can work as follows:

  • start from $2$,
  • multiply by increasing integers,
  • every time the product exceeds $10$, shift the comma (divide by $10$) and count the shift.

The number of digits will be the number of shifts plus one.

$$\begin{align} &2&0\\ &6&0\\ &2.4&1\\ &1.20&2\\ &7.20&2\\ &5.040&3\\ &4.0320&4\\ &\dots&\dots\\ &9.3326215\dots&157 \end{align}$$

Actually, you are computing $100!$ in the scientific notation.

$\endgroup$

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