# Trailing Zeros Problem - What am I doing wrong?

I am using this method. Click for method.

However, I keep getting the wrong answer. I need to find for what $n$ does $n!$ end in 37 trailing zeros. I have used the above method but with one more term $a_3$ and found that $a_1=0, a_2=1, a_3=1$ are the only solutions, then you add $a_0\in\{0,1,2,3,4\}$. I keep getting 30 up to 34 as the answers. The answer is supposed to be 150 to 154. The answer I had gotten is $$a_1+6a_2+31a_3=37$$

I really appreciate everyone taking their time to provide full answers, but I am more interested in where I have gone wrong. I am trying to figure out where I have gone wrong. Is it because I found the answer to be 30, but I am in base 5, so I need to multiply buy 5?

Edit: I see where I have gone wrong.

After finding the values of $a_1=0, a_2=1, a_3=1$, I went back and plugged them in. But what I did was plug them into: $$a_0+5a_1+25a_2$$ $$\Rightarrow 5(1)+25(1)=30+a_0$$ But what I should have done was this $$a_0+5a_1+25a_2+125a_3$$ $$\Rightarrow a_0+5(0)+25(1)+125(1)$$ $$\Rightarrow n=150+a_0$$ $$\Rightarrow n=\{150,151,152,153,154\}$$

-
+1 for showing your work. It makes giving (I hope) a useful answer much easier. – Ross Millikan Mar 28 '14 at 4:11
As the answer you linked to says in the very first line, $n = a_0 + 5a_1 + 25a_2 + 125a_3 + \cdots$. So finding $a_1 = 0, a_2 = 1, a_3 = 1$ (and higher $a_i$'s are zero) means that $n = a_0 + 25 + 125 = a_0 + 150$. – ShreevatsaR Mar 28 '14 at 4:55
Check out my edit:) – Frumpy Mar 28 '14 at 4:57
Only you know how you took $a_0 + 5a_1 + 25a_2$ (missing the $125a_3$ term), and the values $a_1 = 0$ and $a_2 = 1$, and plugged in $5(1) + 25(1)$. :-) – ShreevatsaR Mar 28 '14 at 4:59

## 3 Answers

$a_3,a_2,a_1,a_0$ represent the digits of $n$ in base $5$. You have shown that your number is $110x_5$ correctly, where $x$ can range from $0$ to $4$. Then to convert to base $10$, you get $x + 0\cdot 5 + 1 \cdot 25 + 1 \cdot 125=x+150$ It looks like you missed the zero from $a_1$

-
I don't follow exactly where you got 110 from, but I think I see my mistake. I have found it to equal 30, but these numbers are in base 5, so multiplying by 5 gets me 150, which are the answers I need. Do you believe that is where my mistake came from? – Frumpy Mar 28 '14 at 4:40
I got 110 from your statement that $a_1=0, a_2=1, a_3=1$ and the $x$ is your $a_0$ which can be anything. It looks to me like you were using base five, as you got $30$ from $25+5$, but lost the place shift that the zero represents. – Ross Millikan Mar 28 '14 at 4:43
check out my post again. – Frumpy Mar 28 '14 at 4:55
Yes, you have it right now. – Ross Millikan Mar 28 '14 at 5:08

For a positive integer $n$, the number of zeros at the end of $n!$ is $$\displaystyle\sum\limits_{k=1}^\infty \left\lfloor\frac{n}{5^k}\right\rfloor$$

Note that the successive terms in this sum will decrease by factors of $5$ or more. If we want the sum to equal $37$, the number of $5$s we'll want will have to be around $30$. If we have thirty $5$s, six $25$s, and one $125$, that works out to $37$ nicely.

This is satisfied for $n=150, 151, 152, 153$, and $154$.

-

To get $37$ trailing zeros, you need to have $37$ tens in the factorial. Said more precisely, you need $37$ twos and $37$ fives (such that you get $2^{37}5^{37}$). If you have $37$ fives, then you certainly have $37$ twos, so we just need to find the smallest number for which there are $37$ fives in all of the factors of all of the numbers up to that smallest $n$.

There $\left\lfloor \frac{n}{5}\right\rfloor$ numbers divisible by $5$ up to $n$. However, there are $\left\lfloor\frac{n}{25}\right\rfloor$ numbers which have two factors of $5$ up to $n$. Then there are $\left\lfloor\frac{n}{5^3}\right\rfloor$ numbers with three factors of five up to $n$, so on and so forth. We just need to add one for each of those (for $5^2$ we already counted the first $5$ when we did $\left\lfloor\frac{n}{5}\right\rfloor$). So you just need to see how big you need to go.

Do we need $5^3$? Well $\frac{125}{5} + \frac{125}{25} = 25 + 5 = 30$ (not enough). But we don't need $5^4$, since that would give: $125 + 25 + 5 = 155$ (way too big). So I would start with @ $125$. Right there you have $25 + 5 + 1 = 31$ fives. We only need $6$ more. Since we can get $6$ more by simply adding $6*5 = 30$, that's a good guess, but since that also adds another $25$, it's going to be one too many, we only need $5$ more fives:

$125 + 25 = 150$: $\frac{150}{5} + \frac{150}{25} + \left\lfloor\frac{150}{125}\right\rfloor = 30 + 6 + 1 = 37$. So the smallest factorial is $150!$ and that should work until we get to the next five (then there will be one more zero (and note that in between we added at least $3$ more two's). So $150!$, $151!$, $152!$, $153!$, and $154!$ will all have $37$ trailing zeros and $155!$ will have $38$ trailing zeros.

-