inverted factorial and trailing zeros problem

2011-09-27T05:54:25Z

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

Answer by Greg Martin for inverted factorial and trailing zeros problem

2011-09-27T07:37:06Z

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

inverted factorial and trailing zeros problem - MathOverflow

inverted factorial and trailing zeros problem

Answer by Greg Martin for inverted factorial and trailing zeros problem