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.

  • 3
    $\begingroup$ Note to all: This question is asking about all $0$ digits, not just the ones at the end. $\endgroup$ – Jonas Meyer Jan 25 '13 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$ – André Nicolas Jan 25 '13 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$ – Mark Bennet Jan 25 '13 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 '13 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 '13 at 21:41

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

  • $\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 '14 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 '14 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 '14 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 '14 at 11: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.