10
$\begingroup$

Is there any neat way to solve how many digits the number $20!$ have? I'm looking a solution which does not use computers, calculators nor log tables, just pen and paper.

$\endgroup$
4
  • 2
    $\begingroup$ I suspect Stirling's approximation will help. $\endgroup$ Apr 25, 2012 at 15:43
  • 3
    $\begingroup$ The simplest way is just to compute $20!$. $20$ is small enough that this shouldn't take too much time (or paper). $\endgroup$ Apr 25, 2012 at 15:45
  • $\begingroup$ See "D. FACTORIALS OF LARGE NUMBERS" in groups.google.com/group/sci.math/msg/d12962e3af2c74b7 $\endgroup$ Apr 25, 2012 at 15:45
  • $\begingroup$ For anyone who might look at this question in the future: Stirling's approximation gives $\lfloor (x + \frac{1}{2}) \log{x} - 0.4343x + 1.4 \rfloor$ as a fairly decent approximation. This is what I use when I need an approximation (which is, admittedly, rarely). $\endgroup$
    – Samuel Li
    Jan 17, 2018 at 22:45

5 Answers 5

8
$\begingroup$

I come from a background in computers, so here's my two cents. Taking the logarithm to the base 10 of n!. If the log comes out to be x, it is not hard to see that the number of digits must be the lowest integer greater than or equal to x, i.e, $floor(x)+1$. Now the question comes down to approximating the $log(n!)$ It is possible to prove by induction that n! lies between $(\frac{n}{2})^n$ and $(\frac{n}{3})^n$. Thus the log(n!) lies between $nlog(\frac{n}{2})$ and $nlog(\frac{n}{3})$. We can get a pretty tight bound if we used log tables for log(20/3), but as you have disallowed that, using the upper limit(which becomes log(10) = 1) will do quite nicely too. The answer comes to 20*log(10) = 20, which should tell you that the expected number of digit is about 19 or 20.(Since 20 is only the upper bound). And 19 happens to be the answer.

$\endgroup$
3
  • 1
    $\begingroup$ Can you give me a reference to understand It is possible to prove by induction that n! lies between (n/2)^n and(n/3)^n? $\endgroup$ Jul 8, 2016 at 10:43
  • $\begingroup$ I don't see how that is true. Looking at the base case of 1! = 1 not being between 1/2 and 1/3 shows that this is not the case. $\endgroup$ Jul 21, 2017 at 17:57
  • 1
    $\begingroup$ @TheStrangeQuark actually the bound is between $n^n$ and $(n/2)^n$. I'm not sure why I wrote what I wrote. $\endgroup$
    – Guy
    Jul 21, 2017 at 18:11
4
$\begingroup$

There is unclean way of solving it.

Number of digits in a number 'N' is CEILING(log(N)).

So number of digit in N! is CEILING(log(N!)) = CEILING(log(N*(N-1)*(N-2)) ... 2*1)

Thus,

CEILING(log(N!)) = CEILING(log(N) + log(N-1) +log(N-2)+ ... log(2)*log(1))

Which is pretty easy to compute.

Source: http://pitcher.digitalfreehold.ca/code/computeSize

$\endgroup$
3
$\begingroup$

As a rough approximation, multiplying an $n$-digit number by an $m$-digit number yields a result with about $n+m$ digits. So the numbers from 2 to 9 are all 1-digit numbers. From 10 to 20 are all 2-digit numbers. That suggests we should have about 18 digits or so.

Wolfram|Alpha claims that $20! = 2.4 \times 10^{18}$. Not far off! :-D

$\endgroup$
4
  • $\begingroup$ (Exponents of more than one character require {} to render properly) $\endgroup$ Apr 25, 2012 at 16:00
  • $\begingroup$ Apparently I fail basic math. If you actually count 2 for all of the 2-digit numbers, you come up with 28, which is quite a way out. sigh $\endgroup$ Apr 25, 2012 at 20:34
  • $\begingroup$ @TheChaz Thanks for that... $\endgroup$ Apr 25, 2012 at 20:35
  • $\begingroup$ @MathematicalOrchid it's actually -1,0, more than their sum of number of digits. 0 being used only in cases where the product of first digits plus carry exceeds 10 ( or when you get to numbers with a 5 with previous result having even last non-zero digit , or big enough to surpass the next power of 10). So you have 1+1-1+1-1+1-0+1-0+1-1+1-0+1-0+1-0+2-1+2-1+2-1+2-1+2-1+2-0+2-1+2-1+2-1+2-0+2-1= 31-12=19 $\endgroup$
    – user645636
    Dec 19, 2019 at 20:29
1
$\begingroup$

I will use log as the base b logarithm and ln as the natural log.

Then number of digits of x in base b is given by one more than the floor of the log(x).

log(n!)=sum(log(k)) for k=1,2,...,n

We can interpret this as the Riemann sum for the integral from 1 to n of log(x) dx. This integral is actually a lower bound. The upper bound is the same integral from 2 to n+1 rather than 1 to n.

The lower bound integral is given by n log(n)-(n-1)/ln(b). The upper bound gives (n+1) log(n+1)-n/ln(b) -2ln(2)+1/ln(b).

For n=20, working in base 10, we get about 17.8 as the lower bound and 18.9 as the upper bound. One more than the floor gives 18 or 19 digits. Not surprisingly, the answer is 19 as the lower bound is nearly 19 digits and the upper is nearly 20.

The Riemann sum approximations will get better as n increases, but the answer is already quite good by n=20.

$\endgroup$
0
0
$\begingroup$

Note: For small $n$, my answer does use a look-up table for the logs of a few small primes, so may not meet your specification. For large $n$ that's a power of 10, we can dispense with the tiny log table.

The number of digits in an integer $i$ is $\lfloor \log_{10} i \rfloor + 1$, so let's begin an exact asymptotic approximation for $\log_{10} n!$,

$$\log_{10} n! \approx \frac{n \ln n - n +\ln (2 \pi n)}{\ln 10}$$

This is a slightly more accurate approximation that Sterling's approximation, given that you wanted to take the factorial of a relatively small number like 20.

We can express this alternatively as,

$$\log_{10} n! \approx n \log_{10} n - 0.434 n + \log_{10} (2 \pi n)$$

We don't need a full book of log tables here, we can just know that the logs of a few primes.

$$\begin{array}{ll} 2 & 0.301 \\ 3 & 0.477 \\ 5 & 0.699 \\ 7 & 0.845 \\ 11 & 1.041 \end{array}$$

Since $20 = 2^2 \times 5$, $\log_{10} 20 = 2\times 0.301 + 0.699 = 1.301$.

Next, $\pi \approx 22/7$, thus $\log_{10}(\pi) \approx 0.301 + 1.041 - 0.845 = 0.497$

Thus, $\log_{10}(\sqrt{2 \pi n}) \approx 0.5 \times (0.301 + 0.497 + \log_{10} n) = 0.399 + 0.5 \log_{10} n)$. In our case, since $n = 20$, that's $1.050$.

So, our final sum is $20 \times 1.301 - 0.434 \times 20 + 1.050 = 18.390$, thus we can expect 20! to have 19 digits.

In fact, 20! = 2432902008176640000. In fact, $\log_{10} 20! = 18.386$, so our estimate was very accurate.

I feel that all of the above is well within the reach of hand-calculation. If we restrict ourselves to the factorials of powers of ten, it we can even dispense with the log tables, since $\log_{10} 10^x = x$ and our formula just uses a few constants, and for large $n$ we can drop some terms.

Thus, the number of digits in $10^9!$ (i.e., the factorial of a billion) is $$10^9 \times 9 - 0.434 \times 10^9 \approx 8,566,000,000.$$ Is it a number with about 8.566 billion digits? Yes..

$\endgroup$

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.