1
$\begingroup$

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?

$\endgroup$

closed as off-topic by Carl Mummert, Vinyl_cape_jawa, Riccardo.Alestra, Cesareo, Parcly Taxel Mar 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.

  • $\begingroup$ 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? $\endgroup$ – Carl Mummert Mar 10 at 20:43
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.