20
$\begingroup$

Here is a riddle someone has been asked in a job interview: How many zero digits are there in $100!$?

Well, I found the first $24$ quite fast by counting how many times five divides $100!$ ($5$ divides $20$ times and $25$ divides it $4$ times).

However, there are more zero digits in the middle of the number (these can be found by hand, by typing factorial(100) in sage).

My question is whether there is a smart way to determine the number of zero digits in $100!$, and more generally in $n!$.

By the way, this will not affect the job interview as it was finished some time ago.

$\endgroup$
6
  • 3
    $\begingroup$ Note to all: This question is asking about all $0$ digits, not just the ones at the end. $\endgroup$ Jan 25, 2013 at 21:25
  • $\begingroup$ I had misread (or stopped reading). The number of $0$'s is in principle accessible. But as far as I know, certainly not by a back of the envelope calculation. Very much doubt it would be an interview question, unless the hoped for answer is "I don't know." $\endgroup$ Jan 25, 2013 at 21:27
  • 2
    $\begingroup$ I think this is a great question, but I do not think it has an easy answer - and that may be the point. The most straightforward thing I think of doing is estimating. Suppose there are $n+2+k$ digits in your factorial, and the $k$ trailing digits are known to be all the trailing zeros. Then the there are two digits (the first, and the last before the trailing zeros) which are known to be non-zero. And the rest (all $n$ of them) seem to be as likely to be zero as anything else. $\endgroup$ Jan 25, 2013 at 21:29
  • $\begingroup$ @Nicolas: my interest in this question is that it is simple and I have no idea how to approach it $\endgroup$
    – Lior B-S
    Jan 25, 2013 at 21:38
  • 1
    $\begingroup$ I would have replied, are you familiar with the Digit Count algorithm, so Total number of zeros in 100! using my WA App is 30. Basically, I know how to find the answer by some means. Regards $\endgroup$
    – Amzoti
    Jan 25, 2013 at 21:41

1 Answer 1

25
$\begingroup$

You can get a very good estimate by (a) calculating the number of powers of ten in the factorial, (b) estimating the total number of decimal digits (using Stirling's approximation), and (c) assuming all digits except the trailing zeroes are equally likely to have any value. Since there are plenty of powers of $2$ to go around, the number of trailing zeroes is equal to the number of powers of five, plus the number of powers of twenty-five, etc. $$ T_n=\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{5^{k}}}\right\rfloor. $$ The total length as estimated by Stirling's approximation is $$ L_n=\log_{10}n!=n\log_{10} n - \frac{n}{\ln 10}+O(\ln n). $$ Combining these, our estimate of the total number of zeroes is $$ Z_{n}\sim T_n + \frac{1}{10}\left(L_n - T_n\right)=\frac{9}{10}\sum_{k=1}^{\infty}\left\lfloor{\frac{n}{5^{k}}}\right\rfloor+\frac{1}{10}n\log_{10}n-\frac{n}{10\ln 10}+O(\ln n). $$ This turns out to be pretty good. Using WolframAlpha to get the exact values: $$ \begin{matrix} \text{n} & \text{Estimate} & \text{Exact} & \text{Abs. Error}\\ \hline 1000 & 481 & 472 & 9\\ 2000 & 1022 & 1025 & 3\\ 4000 & 2166 & 2143 & 23\\ 8000 & 4573 & 4645 & 72 \\ 16000 & 9631 & 9560 & 71 \\ 32000 & 20226 & 20227 & 1 \end{matrix} $$ The result for $n=32000$ is fortuitously precise...

$\endgroup$
6
  • $\begingroup$ Could you please elaborate how did you arrive at $Z_{n}\sim T_n + \frac{1}{10}\left(L_n - T_n\right)$ $\endgroup$
    – Gaurav
    May 4, 2014 at 12:16
  • $\begingroup$ @Gaurav -- this is the assumption that each of the $L_n-T_n$ digits that is not a trailing zero has probability $1/10$ of being a zero. $\endgroup$
    – mjqxxxx
    May 4, 2014 at 23:23
  • $\begingroup$ Very nice! But it should be added that the great accuracy in the absolute error at $n=32000$ is a coincidence. The absolute error is expected to diverge as $n\to\infty$, but the ratio is expected to approach $1$. $\endgroup$
    – Winther
    Jul 1, 2014 at 15:41
  • 1
    $\begingroup$ This heuristic reasoning can be made into a theorem if we knew that $\log_{10}(n!)$ is equi-distributed modulo $1$. The latter seems to follow from van der Corput's inequalities, I don't know how yet, but see <a href="mathoverflow.net/questions/159393/…> related question in mathoverflow. $\endgroup$
    – Lior B-S
    Jul 28, 2014 at 11:05
  • $\begingroup$ I realise that this is a decade old but if you are still here, can you please let me know if your formula accounts for the fact that the first digit is necessarily not a zero and that if the length of the answer is greater than 2 + T, then then there must necessarily be another non zero digit. I make it $$Z_{n}\sim T_n + \frac{1}{10}\left(L_n - T_n - 2\right)$$ but I am no mathematician and appreciate that I am missing something. Thank you $\endgroup$
    – matt
    Oct 13, 2023 at 1:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .