Sum of all powers of two Prove that for any positive integer $n$, there exists a nonnegative integer $k$ with the property that $n$ can be written as a sum of the numbers $2^0,2^1,\dots,2^k$, each appearing once or twice.
It seems that we should begin with the canonical representation of $n$ as a sum of powers of two. To make sure that every powers of two appears, we will need to "break down" some powers of two to fill in the gaps.

Given any binary string $\overline{b_n\dots b_1b_0}(b_i\in \{0, 1\}, b_n = 1)$ , consider the following procedure:

Repeat 1, 2, and 3 until the string does not contain '0':
  
  
*
  
*$10\mapsto 02$: If $\overline{b_{j +1}b_j} = 10$, let $\overline{b_{j +1}b_j} \gets02$.
  
*Delete the highest digit if it is 0.
  
*$20\mapsto 12$: If $\overline{b_{j +1}b_j} = 20$, let $\overline{b_{j +1}b_j} \gets 12$.
  

The procedure will eventually end and give the string you want. To see why this procedure will end, note that if we define $m = \max\{i\colon b_i = 0\}$ for string $\overline{b_n\dots b_1b_0}$, then $m \leq n -1$ and decreases by at least 1 during one loop (1-2-3). As a consequence, this procedure will end in at most $n$ steps. 
As an example, given '110101', this procedure gives
$110101 \mapsto 102021 \mapsto 101221 \mapsto 021221 \mapsto 21221$. 
