Let and be positive integers, where . Determine the smallest possible number of not necessarily pairwise distinct powers of 2 that add up to .
Solution
The required minimum is .
To prove this, notice that the sum of two like powers of 2 is again a power of 2, so the number of powers of 2 that add up to a positive integer can successively be decreased while keeping the sum constant. The process then ends up with being expressed as a sum of pairwise distinct powers of 2; that is, the binary expansion of . At this stage, the number of summands can no longer be decreased, so the smallest number of powers of 2 that add up to is equal to the number of units in the binary expansion of .
1st Proof.
Since multiplication by a power of 2 does not change the number of units in a binary expansion, we may and will assume that is odd. Leaving aside the trivial case , let so its binary expansion is , where ; and since , it follows that , so . Now, write .
The first sum consists of exactly pairwise distinct powers of 2, each of which is greater than , and the number in parentheses is the sum of exactly pairwise distinct powers of 2, each of which is less than .
Consequently, is the sum of exactly pairwise distinct powers of 2; that is, its binary expansion has exactly units, as stated.
2nd Proof.
If for some , then , so the binary expansion of has exactly units.
If is not a power of 2, let , where and , be the binary expansion of , to write .
Clearly, the first sum is an integer greater than whose binary expansion has exactly units.
The number in parentheses is a positive integer () smaller than whose binary expansion has exactly units.
Consequently, the binary expansion of has exactly units, as stated.