Integers up to n having an even number of trailing zeros in their factorial

Question

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?

Answer 1

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$).

Answer 2

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.