If an represents the largest n-bit integer for a positive integer n, how many bits are 1 in a1 + a2 + … + a1000000?

[SOLVED]

1 comment

Ilan Mayer solved this puzzle:

Answer: 999993.

an = 2n − 1.

ΣNn = 1 2n − 1 = 2N + 1 − 1 − N + 1.

For N = 1000000, 2N + 1 − 1 consists of 1000001 1s in binary notation.

For N = 1000000, N + 1 is 111101000010010000012 in binary notation. It contains 8 1s.

Subtracting the 2nd number from the 1st replaces 8 1s with 0s, leaving 999993 1s.

Credit

This is an original puzzle from cotpi.

Further reading

The following is a list of resources on related topics:

Post a comment

RSS