Solving the binary puzzle

(This is the answer to the puzzle proposed in the previous post.)

If you write all binary numbers between 0 and 2n-1 you will notice that the columns show a pattern. See for example the first 8 binary numbers:


Each column has exactly the same number of zeroes and ones! Then the total number of ones is half the total number of digits:

\displaystyle \frac{n 2^n}{2} = n 2^{n-1}.

Once we have the formula, the values for n = 1 to 50 can easily be calculated.

A binary number puzzle

As I haven’t finished the posts I’ve planned to write, here is a quick puzzle involving binary numbers:

Compute the total number of one-bits in the binary representations of the numbers 0 to 2n-1 for n from 1 to 50.

For example, for n = 2 we have four different binary representations: 00, 01, 10 and 11. Adding the number of one-bits: 0 + 1 + 1 + 2 = 4.

Hint: it’s quite easy once you get the pattern…