Integers up to n having an even number of trailing zeros in their factorial 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? 
 A: 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$).
A: 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. 
