# inverted factorial and trailing zeros problem

First than anything a big Hello for all math fans like me.

I've found a problem that is pretty interesting and I can't find the answer. As all of you must know, to counting the trailing zeros of $n$ factorial goes by this formula:

$$c = (n/5)+(n/25)+(n/125)+(n/5^q)$$

Now the problem is the following:

What happen if the problem is in the other side, you have $c$ number of trailing zeros and you want to know the first $n$ that its $n!$ has $q$ trailing zeros, how can it be done?, I've searched a lot and I can't reach a solution. Is there an approach that I'm missing or something?

Thanks in advance and sorry about my English and my lack of Latex, but I'm already learning :D

-
I guess that $q$ is the floor of $\log_5 (n)$. So it amounts to inverting the above function. There might not be a nice closed form for this, but I'd guess that you can write program to do this quickly. –  Tony Huynh Sep 27 '11 at 6:11
I guess that $(m)$ refers to the floor function $\lfloor m\rfloor$, and that some dots are missing between the $125$ term and the $5^q$ term. Use $\backslash\text{lfloor}$, $\backslash\text{rfloor}$ and $\backslash\text{cdots}$. –  Did Sep 27 '11 at 6:29
I looked at this too quickly to check the following but it seems that $\frac16n-\log_5n\le c\le\frac16n+\log_5n$, hence $x\le n\le y$ where $x=6c-6\log_5x$ and $y=6c+6\log_5y$. –  Did Sep 27 '11 at 6:39
Please replace every $6$ by $4$ in my previous comment. Sorry. –  Did Sep 27 '11 at 7:28
The number of trailing zeros in $n!$ is at oeis.org/A027868 -- perhaps some of the facts about the sequence given there can be inverted to give what you want. –  Michael Lugo Sep 27 '11 at 16:05

An article in GanitCharcha (www.ganitcharcha.com) will help you and have discussed on your question. Look at Problem 2 here.

-

Consider the mixed radix representation of a positive integer using the bases 1, 6, 31, 156, 781, ... defined recursively by $b_n = 5b_{n-1}+1$, or in closed form as the sequence $(5^n-1)/4$. For example, the mixed radix representation of 2011 is <22421>, since $2011 = 2\cdot 781 + 2\cdot156 + 4\cdot 31+2\cdot 6+1\cdot 1$. All the digits in this representation are 0, 1, 2, 3, or 4, except that a number can have 5 as a digit if all digits after the 5 equal 0; for example, the mixed radix representation of 2028 is <22450>, the mixed radix representation of 2029 is <22500>, and the mixed radix representation of 2030 is <23000>.

The point of defining this mixed radix representation is as follows: if $n$ is written in base 5 as $n = [d_kd_{k-1}\cdots d_1d_0]_5$, then the number of trailing zeros in $n!$ is equal to the integer whose mixed radix representation is <$d_kd_{k-1}\cdots d_1$> (note the omission of $d_0$).

Therefore we can invert the function - that is, given the number $c$, we can find the smallest integer $n$ such that $n!$ has $c$ trailing zeros - as follows. Write $c$ in mixed radix representation; then append a zero to that string of numbers; then convert the string of numbers to a base-5 integer.

For example, with $c=2011={}$<22421>, the first integer $n$ such that $n!$ has $c$ trailing zeros is $n = [224210]_5 = 8055$. (Of course, the set of such integers $n$ is then precisely {8055,8056,8057,8058,8059}.)

One must be a little careful if the mixed radix representation of $c$ contains the digit 5: that means that there is no integer $n$ such that $n!$ has exactly $c$ trailing zeros. But we can find the smallest integer $n$ such that $n!$ has at least $c$ trailing zeros by "carrying" the 5s to the left.

For example, with $c=2028={}$<22450>, we rewrite $[224500]_5 = [225000]_5 = [230000]_5$, and so $n=[230000]_5= 8125$ is the smallest integer such that $n!$ contains at least 2028 trailing zeros; in fact, thanks to the 2 carries, $n!$ actually contains <23000>${}={}$2030 trailing zeros.

-