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 ?

Solution 1:

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

Solution 2:

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.