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:

000
001
010
011
100
101
110
111

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.

Advertisements

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…