Difference of powers of 2 Find the number of positive integers from $1$ to $1000 $ (inclusive) that can be expressed as the difference of two numbers in the set $\{1,2,2^2,2^3,\ldots\}$. I know how to solve this but the counting is becoming difficult.
 A: A positive number is the difference of two powers of two if and only if its representation in binary contains no more than one consecutive string of digits $1$. For numbers less than $2^{10}=1024$ you've got $10$ bit positions available, and you want to set bits in positions$~i$ with $m\leq i<n$ where $0\leq m<n\leq10$; there are $\binom{11}2=55$ such pairs $(m,n)$. (Incidentally your number will be $2^n-2^m$, so using binary representation is not really necessary here.) Among those, the ones that are greater than $1000=1111101000_2$ are those with $n=10$ and $m<5$, five of them, leaving $50$ true solutions.
A: HINT: First $2^{11}-2^{10}=1024>1000$, so you need only concern yourself with $\{2^0,\ldots,2^{10}\}$. Secondly, if $2^n-2^m=2^\ell-2^k$, what can you say about $k,\ell,m$, and $n$? The answer to that question gives you an easy way to do the counting.
A: Hint You want $n \leq 1000$ and $n =2^m-2^k$.
Case 1: $2^m \leq 1000$ then $m \leq 9$ and $ 0 \leq k \leq m$. Thus in total you have .... choices.
Case 2: $2^m \geq 1000$. Then, 
$$1000 \geq n=2^m-2^k \geq 2^{m}-2^{m-1}=2^{m-1}$$ 
hence $m=10$. In this case you have ... choices..
