Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Note to all: This question is asking about all $0$ digits, not just the ones at the end. –  Jonas Meyer Jan 25 '13 at 21:25
    
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." –  André Nicolas Jan 25 '13 at 21:27
2  
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. –  Mark Bennet Jan 25 '13 at 21:29
    
@Nicolas: my interest in this question is that it is simple and I have no idea how to approach it –  Lior B-S Jan 25 '13 at 21:38
1  
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 –  Amzoti Jan 25 '13 at 21:41

2 Answers 2

up vote 13 down vote accepted

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

share|improve this answer
    
Thanks! It is a very simple and nice solution! –  Lior B-S Jan 26 '13 at 7:56
    
Could you please elaborate how did you arrive at $Z_{n}\sim T_n + \frac{1}{10}\left(L_n - T_n\right)$ –  Gaurav May 4 at 12:16
    
@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. –  mjqxxxx May 4 at 23:23
    
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$. –  Winther Jul 1 at 15:41
    
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. –  Lior B-S Jul 28 at 11:05

You might calculate easily the number m of last consecutive zeroes of a factorial n! by $m =floor(n/5) + floor(n/5^2) +...+ foor(n/5^K)+...$ stopping obviously when you get to a zero value. For $1000!$ we obtain : $ 200 + 40 + 8+ 1+ 0 = 249 $ zeroes. We have m= 24 zeroes for n =100 that is $m/n = 24/100 = 0.24 $ zeroes per unit for n=100 while it is 249/1000 = 0.249 zeroes per unit for n=1000; and so ·the number of zeroes in a factorial increases more than in a proportion when n increases·

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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