Sum of Binary Trailing Zeros

Keywords: math
Created: 2018-05-15 Tue 20:46:00

While working through a project euler problem I noticed an interesting pattern:

When writing down the numbers from sum_of_binary_trailing_zeros_5378959fae81cd69e904f954fd84fd3b1562010e.svg to sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg the total number of trailing zeros (called sum_of_binary_trailing_zeros_1576ad2a260e55ef7e4f7b98e18266e7189bf111.svg for the rest of this post) is equal to sum_of_binary_trailing_zeros_f8daefbf171b4c455356a3be48416906b30e3239.svg where sum_of_binary_trailing_zeros_6f3948a4f014dd51f087dd869e1d697201b3eda1.svg is the number of ones in the binary representation of sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg .

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.

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 sum_of_binary_trailing_zeros_d2628b4293a1174e2694b072d02299a7a4dc3b03.svg numbers there are sum_of_binary_trailing_zeros_a6d9bed29d7fb390f106048948ea1a79abcb621e.svg trailing zeros. sum_of_binary_trailing_zeros_2fa41caf6fd738d3556ba2f22d66d4244908061c.svg , so the equation holds.

Proof

A binary number has at least sum_of_binary_trailing_zeros_31787291ee6ca49493bb29899c28c0003faf053a.svg trailing zeros sum_of_binary_trailing_zeros_b0ee490ea9e5e88d78ffac3760980ba03ad5731d.svg it is a multiple of sum_of_binary_trailing_zeros_4c884b8ed91b840f7a53fcad9d2bbae271915c83.svg .

In the example above there are sum_of_binary_trailing_zeros_b0b7e803d23ac554a13d05836e4eb8a9ced5f0cd.svg numbers with at least one trailing zero, sum_of_binary_trailing_zeros_54c1e34d9aa945a25c36a6d17b73ae9627fc5e09.svg numbers with at least two trailing zeros, and sum_of_binary_trailing_zeros_5cb9ec0b73922068bba446a396630c30655fa5e1.svg numbers with at least three trailing zeros.

For arbitrary sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg this can be written as

sum_of_binary_trailing_zeros_e32a5847eea9cdebc7c9fb1be24aeffbe76c9292.svg

which is not really an infinite sum because after a while ( sum_of_binary_trailing_zeros_0cfdccd289ea16cb5ea439798dea46512554b71e.svg ) all the remaining summands are zero.

sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg can be written (binary notation) as sum_of_binary_trailing_zeros_79733af8783b3d8291920d2f98a4da1324f61a4d.svg with sum_of_binary_trailing_zeros_a10b901f4b851860e0e4f2e853e442cc98cefb93.svg .

sum_of_binary_trailing_zeros_bc062c256c5ff28a26b34d67b4c0febd508f730d.svg

The division by sum_of_binary_trailing_zeros_47ccca8fa9490eb8234224467a1da697c219c1b5.svg can be understood as moving the "decimal" point in the binary representation of sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg sum_of_binary_trailing_zeros_fced39474a8f7b2b730bb694b880e6925b57b50c.svg places to the left. sum_of_binary_trailing_zeros_971701f26f20531c70e07efafa56a8a247219de3.svg is equivalent to cutting off everything after the "decimal" point of sum_of_binary_trailing_zeros_786fc745118311e436770f0544a821745c3ccd07.svg (independent of the base).

sum_of_binary_trailing_zeros_a4b425c8a97565b4039364ee55b4411d44d4d269.svg

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:

sum_of_binary_trailing_zeros_50026c0b672f1cb446e787ea6449094b07b4611c.svg

What this allows us to do is to rewrite sum_of_binary_trailing_zeros_6b337158fab541bb53a4a3dafe90a18459304aef.svg by multiplying each sum_of_binary_trailing_zeros_7e35c03154eae7ceb582b204d46dedfc34297d07.svg with sum_of_binary_trailing_zeros_5f958554d82e5ece1b65a2bd292273e11a4bbd62.svg so that it removed from the sum if sum_of_binary_trailing_zeros_2fe4de1c96be8af5fc6762fe40aa1d73afab5236.svg (as part of the numbers behind the "decimal" point that are cut of).

sum_of_binary_trailing_zeros_b11335d806585dc7c4226e6f991c4d4658174b81.svg

If the step from sum_of_binary_trailing_zeros_7f79632c923a6b02a28cd0b2ff37999846fbd0ae.svg to sum_of_binary_trailing_zeros_4061fe668cde7a9389f8d843fce8ec35f13c45d4.svg is not obvious, think about what happens when sum_of_binary_trailing_zeros_5378959fae81cd69e904f954fd84fd3b1562010e.svg is added to a binary number that is made up entirely of ones: sum_of_binary_trailing_zeros_6a15d97575c9fa7355992ba9b1ef42addc0ca87c.svg .

Trailing Zeros of sum_of_binary_trailing_zeros_7c8c9133cf871aa79d5db8f7e773b2e98560b242.svg

Let sum_of_binary_trailing_zeros_be3b778850b84ec5819f7aaa471bb1a9909bb73c.svg be the number of trailing zeros when sum_of_binary_trailing_zeros_5fde1ea98712ce221077b775bb8b84a1986c8218.svg is written in binary.

sum_of_binary_trailing_zeros_0c4a83ac95004945713a2eee2fb7c660eef7b7f0.svg (see Binary Trailing Zeros of Products ), so sum_of_binary_trailing_zeros_76f3d67436eff79681e33f1e9e4b450b52ea4a13.svg .

Example: sum_of_binary_trailing_zeros_7b9f6bb977e45843448672102df58d74e9062514.svg has sum_of_binary_trailing_zeros_c5b3cf6d2c8d2213345d56e110f8fbfffb00df70.svg trailing zeros.


Last export: 2020-05-29 Fri 00:09
This document is also available as plain text and pdf.

If you have an idea how this page could be improved or a comment send me a mail.