inverted factorial and trailing zeros problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T20:30:48Z http://mathoverflow.net/feeds/question/76472 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/76472/inverted-factorial-and-trailing-zeros-problem inverted factorial and trailing zeros problem jmacboy 2011-09-27T05:54:25Z 2011-09-27T07:37:06Z <p>First than anything a big Hello for all math fans like me.</p> <p>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:</p> <p>$$c = (n/5)+(n/25)+(n/125)+(n/5^q)$$</p> <p>Now the problem is the following:</p> <p>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?</p> <p>Thanks in advance and sorry about my English and my lack of Latex, but I'm already learning :D</p> http://mathoverflow.net/questions/76472/inverted-factorial-and-trailing-zeros-problem/76476#76476 Answer by Greg Martin for inverted factorial and trailing zeros problem Greg Martin 2011-09-27T07:37:06Z 2011-09-27T07:37:06Z <p>Consider the <a href="http://en.wikipedia.org/wiki/Mixed_radix" rel="nofollow">mixed radix representation</a> 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 &lt;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 &lt;22450>, the mixed radix representation of 2029 is &lt;22500>, and the mixed radix representation of 2030 is &lt;23000>.</p> <p>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$).</p> <p>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.</p> <p>For example, with $c=2011={}$&lt;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}.)</p> <p>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 <em>exactly</em> $c$ trailing zeros. But we can find the smallest integer $n$ such that $n!$ has <em>at least</em> $c$ trailing zeros by "carrying" the 5s to the left.</p> <p>For example, with $c=2028={}$&lt;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 &lt;23000>${}={}$2030 trailing zeros.</p>