# Given number of trailing zeros in n!, find out the possible values of n.

It's quite straightforward to find out number of trailing zeros in n!.

But what if the reverse question is asked?

n! has 13 trailing zeros, what are the possible values of n ?

How should we approach the above question ?

-
What can you say about when the number of trailing zeros increases - try the first few values of n! if you can't think of anything ... and make a hypothesis. – Mark Bennet Jun 26 '12 at 16:41
The number $13$ is very small. By $50$ we have a dozen $5$'s. – André Nicolas Jun 26 '12 at 16:43
@AndréNicolas: What is trailing zeros in problem? – Basil R Jun 26 '12 at 16:51
This is the number of $0$'s at the end of the decimal expansion of $n!$. So, counting from the right, it is the number of $0$'s up to the first non-zero digit. For example, $7!=5040$, so it has $1$ trailing $0$. You can see that $12!$ has $2$, $15!$ has $3$, $21!$ has $4$, and (first complication) $25!$ has $6$. – André Nicolas Jun 26 '12 at 17:12

Write $n$ in base $5$ as $n = a_0 + 5a_1 + 25a_2 + 125a_3 + \cdots$ where $0 \leq a_k \leq 4$. $$\left\lfloor \dfrac{n}5\right\rfloor = a_1 + 5a_2 + 25a_3 + \cdots$$ $$\left\lfloor \dfrac{n}{25}\right\rfloor = a_2 + 5a_3 + \cdots$$ $$\left\lfloor \dfrac{n}{125}\right\rfloor = a_3 + \cdots$$ Hence, $$\left\lfloor \dfrac{n}5\right\rfloor + \left\lfloor \dfrac{n}{25}\right\rfloor + \left\lfloor \dfrac{n}{125}\right\rfloor + \cdots = a_1 + 6 a_2 + 31 a_3 + \cdots$$ Note that the coefficients of the terms from $a_3$ are greater than $13$. Since the sum must give us $13$, we get that $a_k = 0$, for all $k \geq 3$. Hence, we need to find the number of integer solutions to $a_1 + 6a_2 =13$ with $0 \leq a_1,a_2 \leq 4$. The constraint $0 \leq a_1,a_2 \leq 4$ further implies that $a_2$ cannot be $0$ and $1$. Hence, $a_2 = 2$. This gives us $a_1 = 1$.

Hence, $n = a_0 + 5a_1 +25a_2 = a_0 + 5 \times 1 + 25 \times 2 = 55+a_0$ where $a_0 \in \{0,1,2,3,4\}$. Hence, the desired values of $n$ are $$\{55,56,57,58,59\}$$ The same idea in principle will work when the trailing number of zeros is any number not just $13$.

-
Why is this condition there in the first line 0≤ak≤4. – vinoth Jun 26 '12 at 17:33
@sun123 When you write a number in base $b$, its digits go from $0$ to $b-1$. Just like in decimal (base $10$), where the digits go from $0$ to $9$. – user17762 Jun 26 '12 at 17:58

To get a very good estimate, note that the number of trailing $0$'s is $$\left\lfloor \frac{n}{5}\right\rfloor+ \left\lfloor \frac{n}{5^2}\right\rfloor+ \left\lfloor \frac{n}{5^3}\right\rfloor+\cdots.$$ This is less than the infinite sum $$\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+\cdots.$$ The infinite geometric series has sum $\frac{n}{4}$. So if we want $z$ trailing zeros, then $n \gt 4z$.

A computation using $4z$ will tell us how much we need to go forward from $4z$. The difference between $\frac{n}{5^k}$ and $\left\lfloor \frac{n}{5^k}\right\rfloor$ is always less than $1$. So the amount we may need to go forward to find the appropriate $n$ (if there are any) is logarithmic in $z$.

Note that the first $n$ that works (if there is one) is a multiple of $5$. And then $n+1$, $n+2$, $n+3$, and $n+4$ are the others.

By that criterion, when $z=13$, our first candidate is $55$, the first multiple of $5$ after $(4)(13)$, and it works. Thereofore Of so do $56$, $57$, $58$, and $59$, and that's all.

Computations are equally straightforward for $z$ up to a few hundred. Calculate the number of trailing $0$'s for the first multiple of $5$ greater than $4z$, and make any minor adjustments necessary.

-
Why the first $n$ must be multiple of 5 ? – MathMan Sep 6 '13 at 8:49
@MathMan: Definitely $n$ need not be a multiple of $5$. We are using the "floor" ir greatest integer function. So $\lfloor \frac{88}{5}\rfloor=17$. – André Nicolas Sep 6 '13 at 13:35