2
$\begingroup$

It is well-known that the number of trailing zeros in the factorial $k!$ is given by the nice function $$ z(k) := \sum_{i \ge 1} \left\lfloor \frac{k}{5^i} \right\rfloor. $$

Now assume that we want to count how many nonnegative integers up to $n$ have an even number of trailing zeros in their factorial. We could just compute $z(k) \pmod 2$ for $k=0,1,2,\ldots,n$, but this is too slow for large $n$ (say, $n=10^{18}$).

Can we count those integers more efficiently? For example, in time polynomial in $\log n$?

About the problem: This problem was described in a programming competition (Problem F here). The official solutions describe an efficient algorithm (polynomial in the number of digits of $n$), based on visual inspection of the parity patterns. But there is no proof that the algorithm is correct. So an alternative question would be, why is that algorithm correct?

$\endgroup$
  • 1
    $\begingroup$ Number of trailing zeroes is tabulated at oeis.org/A027868 --- maybe some of the references there would be helpful. $\endgroup$ – Gerry Myerson Mar 26 '14 at 9:54
4
$\begingroup$

You can use a very similar reasoning to the one commonly used to prove Lucas's lemma. The method below is not very short, but I think it's transparent, and it's straightforward to adapt it to trailing zeros in any base $b$ congruent to any remainder $r$ mod $m$ (10, 0, 2 respectively in our case). You can probably also use it to prove the patterns that the solution you linked exploits.

To get some symmetry, let's define $$F(n) = \#\left\{ 1 \le j \le n : 2 \mid z(k) \right\} - \#\left\{ 1 \le j \le n : 2 \nmid z(k) \right\}.$$ The number of even $z$'s up to $n$ can easily be recovered as $\frac{F(n)+n}2$.

Let ${\rm ord}_p(n) = \max \{ t \in \mathbb Z : p^t | n\}$ denote the largest exponent of $p$ that divides $n \in \mathbb N$. Then, an alternative formula for $z$ is: $$z(n) = \sum_{i=1}^n {{\rm ord}_5(i)},$$ the advantage being that the sequence $({\rm ord}_5(i): i\in \mathbb N)$ is almost periodic in a sense: $({\rm ord}_5(i): 1\le i \le 5^{k+1})$ is the same as $({\rm ord}_5(i): 1\le i \le 5^k)$ five times, except for the last term.

Let's first compute $z(5^k)$ and $F(5^k)$ inductively (actually, we only care about $z$ mod $2$).

$$z(5^{k+1}) = 5\cdot z(5^k) + 1$$ $$F(5^{k+1}) = \left( 3+2\cdot(-1)^{z(5^k)} \right)\cdot F(5^k) + 2\cdot(-1)^{z(5^{k+1})}$$

Similarly, for $1 \le d < 5$:

$$z(d\cdot 5^k) = d\cdot z(5^k)$$ $$F(d\cdot 5^k) = \left( \left \lceil{\frac d 2}\right \rceil + \left \lfloor{\frac d 2}\right \rfloor \cdot(-1)^{z(5^k)} \right) \cdot F(5^k)$$

Finally, note that if $0 < b < 5^k$ and $5^k | a$, then $$ z(a+b) = z(a) + z(b) $$ $$ F(a+b) = F(a) + F(b)\cdot(-1)^{z(a)} $$

If your number in base 5 is $n = \overline{ d_{k-1}d_{k-2}\dots d_0 } _{(5)}$, then this allows you to iteratively compute $F\left(\overline{ d_{k-1}d_{k-2}\dots d_{k-j}00\dots0 } _{(5)} \right)$ for $1 \le j \le k$, all in $O(k) = O(\log n)$ steps. (That is, if you assume that $F(j)$ will fit in a constant precision integer. As $F(i) = O(i)$, I think the real asymptotic runtime is $O(\log^2 n)$ for truly large values of $n$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great answer, thanks! Could you clarify how you derived the recurrences for F? Did you do it directly, or based on the ones for z? $\endgroup$ – Vincenzo Mar 26 '14 at 16:15
  • 1
    $\begingroup$ You need to keep track of the parity of $z$. The idea is that we want to compute the change of $F$ from some $a$ to $b$, i.e. $F(a+b)-F(a)$. To do this, we decompose $z(a+c)$ as $z(a) + \sum_{i=1}^c {\rm ord}_5(a+i)$ for any $1 \le c \le b$. Therefore, whenever you look at the parity of $z(a+c)$, it's composed of $z(a)$ and an appropriately chosen sum of ${\rm ord}_5$'s. So $z(a)$ is there as an "offset" that can flip the parity of all $z(a+c)$'s when we compute $F(a+b) - F(a)$. Hope this makes it somewhat clearer :-) $\endgroup$ – EdgarTheWise Mar 26 '14 at 17:30
1
$\begingroup$

Let me add that, as one might naively expect, the number of such $k \leq n$ is asymptotically $n/2$. Equivalently, the exponent of $5$ in the factorization of $k!$ is uniformly distributed modulo $2$. This follows from a paper of Sander:

On the Parity of Exponents in the Prime Factorization of Factorials Journal of Number Theory 90 (2001), 316--328

See also the following paper of Luca and Stanica: On the prime power factorization of n! J. Number Theory 102 (2003), no.298–305.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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