2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Sep 27, 2011 at 6:11
  • $\begingroup$ 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}$. $\endgroup$
    – Did
    Sep 27, 2011 at 6:29
  • $\begingroup$ 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$. $\endgroup$
    – Did
    Sep 27, 2011 at 6:39
  • $\begingroup$ Please replace every $6$ by $4$ in my previous comment. Sorry. $\endgroup$
    – Did
    Sep 27, 2011 at 7:28
  • $\begingroup$ 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. $\endgroup$ Sep 27, 2011 at 16:05

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.