Too Many 2s

Probability Level 3

Every positive integer can be written as a sum of distinct powers of two. For example, $101={ 2 }^{ 0 }+{ 2 }^{ 2 }+{ 2 }^{ 5 }+{ 2 }^{ 6 }$

As we can see, $101$ is written as a sum of four distinct powers of two. How many positive integers less than ${ 2 }^{222}$ can be written as a sum of four distinct powers of two?

Note: ${ 38=2 }^{ 1 }+{ 2 }^{ 2 }+{ 2 }^{ 4 }+{ 2 }^{ 4 }$ is NOT valid, since ${ 2 }^{ 4 }$ appears twice.

×