______________________________
SUM OF BINARY TRAILING ZEROS
Leon Rische
______________________________
[2018-05-15 Tue 20:46]
Table of Contents
_________________
1. Example
2. Proof
3. Trailing Zeros of $n!$
While working through a [project euler] problem I noticed an interesting
pattern:
When writing down the numbers from $1$ to $n$ the total number of
trailing zeros (called $S(n)$ for the rest of this post) is equal to $n
- popcount(n)$ where $popcount(n)$ is the number of ones in the binary
representation of $n$.
It took me a while to understand why this is true and even longer to
formulate a somewhat elegant proof. What follows is my best try so far.
[project euler]
1 Example
=========
1. 0001
2. 001 *0*
3. 0011
4. 01 *00*
5. 0101
6. 011 *0*
7. 0111
8. 1 *000*
9. 1001
10. 101 *0*
In the first $n = 10$ numbers there are $8$ trailing zeros.
$popcount(n) = 2$, so the equation holds.
2 Proof
=======
A binary number has at least $z$ trailing zeros $\iff$ it is a
multiple of $2^z$.
In the example above there are
$\left\lfloor\frac{10}{2^1}\right\rfloor = 5$ numbers with at least
one trailing zero, $\left\lfloor\frac{10}{2^2}\right\rfloor = 2$
numbers with at least two trailing zeros, and
$\left\lfloor\frac{10}{2^3}\right\rfloor = 1$ numbers with at least
three trailing zeros.
For arbitrary $n$ this can be written as
\[ S(n) = \sum\limits_{i=1}^{\infty}
\left\lfloor\frac{n}{2^i}\right\rfloor \]
which is not really an infinite sum because after a while ($i >
\log_2(n)$) all the remaining summands are zero.
$n$ can be written (binary notation) as $\sum\limits_{j = 0}^\infty
a_j 2^j$ with $a_j \in \{0, 1\}$.
\begin{aligned}
S(n) =
\sum\limits_{i=1}^{\infty} \left\lfloor\frac{n}{2^i}\right\rfloor
=
\sum\limits_{i=1}^{\infty} \left\lfloor\frac{
\sum\limits_{j = 0}^\infty a_j 2^j
}{2^i}\right\rfloor
=
\sum\limits_{i=1}^{\infty} \left\lfloor
\sum\limits_{j = 0}^\infty a_j 2^{j-i}
\right\rfloor
\end{aligned}
The division by $2^i$ can be understood as moving the "decimal" point
in the binary representation of $n$ $i$ places to the left.
$\left\lfloor x \right\rfloor$ is equivalent to cutting off everything
after the "decimal" point of $x$ (independent of the base).
\begin{aligned}
S(10) = &
\sum\limits_{i=1}^{\infty} \left\lfloor\frac{1010_2}{2^i}\right\rfloor
\\ = &
\left\lfloor 101.0_2 \right\rfloor
+ \left\lfloor 10.10_2 \right\rfloor
+ \left\lfloor 1.010_2 \right\rfloor
+ \left\lfloor 0.1010_2 \right\rfloor
+ \left\lfloor 0.01010_2 \right\rfloor
+ \ldots
+ \left\lfloor 0.0\ldots01010_2 \right\rfloor
\\ = &
101_2 + 10_2 + 1_2 + 0_2 + 0_2 + \ldots + 0_2
\\ = &
100_2 = 8
\end{aligned}
How does this apply to the equation from before? First I'll introduce
a simple indicator function that will make the next steps of the proof
a little bit easier to follow:
\[ I(x) = \begin{cases} 1 & \text{ if } x \geq 0 \\ 0 & \text{ if } x
< 0 \end{cases} \]
What this allows us to do is to rewrite $\left\lfloor \ldots
\right\rfloor$ by multiplying each $a_i 2^{j-i}$ with $I(j - i)$ so
that it removed from the sum if $2^{j - i} < 1$ (as part of the
numbers behind the "decimal" point that are cut of).
\begin{aligned}
S(n) = &
\sum\limits_{i=1}^\infty \left\lfloor
\sum\limits_{j = 0}^\infty a_j 2^{j-i}
\right\rfloor
\\ = &
\sum\limits_{i=1}^\infty
\sum\limits_{j=0}^\infty
a_j 2^{j-i} I(j - i)
\\ = &
\sum\limits_{j=0}^\infty
\sum\limits_{i=1}^\infty
a_j 2^{j-i} I(j - i)
&& \text{ (swapping the sums) }
\\ = &
\sum\limits_{j=0}^\infty
a_j
\sum\limits_{i=1}^\infty
2^{j-i} I(j - i)
\\ = &
\sum\limits_{j=0}^\infty a_j
\sum\limits_{i=1}^j 2^{j-i}
&& \text{ (by definition of $I(x)$) }
\\ = &
\sum\limits_{j=0}^\infty a_j
\sum\limits_{i=0}^{j-1} 2^j
\\ = &
\sum\limits_{j=0}^\infty a_j (2^j - 1)
\\ = &
\sum\limits_{j=0}^\infty a_j 2^j
- \sum\limits_{j=0}^\infty a_j
\\ = &
n - popcount(n)
\end{aligned}
If the step from $\sum\limits_{i=0}^{j-1} 2^i$ to $2^{j} - 1$ is not
obvious, think about what happens when $1$ is added to a binary number
that is made up entirely of ones: $1111_2 + 1_2 = 10000_2$.
3 Trailing Zeros of $n!$
========================
Let $T(n)$ be the number of trailing zeros when $n$ is written in
binary.
$T(ab) = T(a) + T(B)$ (see [Binary Trailing Zeros of Products]), so
$T(n!) = \sum_{i=1}^n T(n) = S(n)$.
Example: $10! = 3628800 = 1101110101111100000000_2$ has $S(10) = 10 -
2 = 8$ trailing zeros.
[Binary Trailing Zeros of Products]