______________________________

                      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] <http://project-euler.com>


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]
<file:binary_trailing_zeros_of_products.org>