# How many numbers (positive integers) smaller than $n$ can be written as a sum of two or more consecutive power of 2 integers? [closed]

How many numbers (positive integers) smaller than $$n$$ can be written as a sum of two or more consecutive power of 2 integers?

My attempt so far: So basically we're searching how many $$x$$ and $$y$$ we have such that: $$2^x+2^{x+1}+\ldots+2^{x+y} \leq n$$, where $$x,y,n\in\mathbb{N}$$. By calculating the sum we arrive at: $$2^x(2^{y+1}-1)\leq n$$. And here I am stuck... Any ideas?

## closed as off-topic by Carl Mummert, Vinyl_cape_jawa, Riccardo.Alestra, Cesareo, Parcly TaxelMar 11 at 13:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Carl Mummert, Vinyl_cape_jawa, Riccardo.Alestra, Cesareo, Parcly Taxel
If this question can be reworded to fit the rules in the help center, please edit the question.

• This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. In particular, what is the source and background of the question? – Carl Mummert Mar 10 at 20:43

If we only consider the case $$n = 2^k$$, and represent in binary the numbers matching the criteria, it seems simple enough to list them. E.g. for $$n = 2^4 = 16$$ we get the following four-bit numbers:

0011b  =     2+1 =  3
0110b  =   4+2   =  6
0111b  =   4+2+1 =  7
1100b  = 8+4     = 12
1110b  = 8+4+2   = 14
1111b  = 8+4+2+1 = 15


That is, there are three numbers with two consecutive ones, two with three ones, and one with four ones. That's $$1+2+3 = 6$$. The one-bits represent the terms of your sum as shown.

For $$n = 32$$, we have five bits and $$1+2+3+4 = 10$$ different numbers. Adding bits (or increasing $$k$$ by one; or doubling $$n$$) adds one possible position for each of the run lengths, so the amount of such numbers smaller than $$n = 2^k$$ is the triangular number $$T_{k-1}$$:

$$T_{k-1} = \frac{(k-1)k}{2}$$

The case where $$n$$ is not a power of two seems less simple.