If a_{n} represents the largest n-bit integer for a positive
integer n, how many bits are 1 in a_{1} + a_{2} + … + a_{1000000}?

Sunday, December 11, 2011

Please email your solutions to puzzles@cotpi.com.

### 1 comment

### Credit

This is an original puzzle from cotpi.

### Further reading

The following is a list of resources on related topics:

- Pal, Susam. "From the Tower of Hanoi to counting bits." Susam Pal. 25 Sep. 2011. 17 Dec. 2011 <http://susam.in/blog/from-tower-of-hanoi-to-counting-bits/>.
- Caldwell, Chris K. "Mersenne Primes: History, Theorems and Lists." The Prime Pages. University of Tennessee at Martin. 17 Dec. 2011 <http://primes.utm.edu/mersenne/>.

## Ilan Mayer solved this puzzle:

Answer: 999993.

a

_{n}= 2^{n}− 1.Σ

^{N}_{n = 1}2^{n}− 1 = 2^{N + 1}− 1 − N + 1.For N = 1000000, 2

^{N + 1}− 1 consists of 1000001 1s in binary notation.For N = 1000000, N + 1 is 11110100001001000001

_{2}in binary notation. It contains 8 1s.Subtracting the 2nd number from the 1st replaces 8 1s with 0s, leaving 999993 1s.