Every positive integer is the sum of powers of two, with no power repeating. For example,
Is there a quick way to tell whether an integer is the sum of consecutive powers of two, though? Keep reading to find out, or jump ahead to the challenge if you think you already know.
Ancient Egyptians broke down numbers into powers of two as part of their multiplication system. To find powers of two, they just needed to add repeatedly. The fewer powers of two one of the numbers was made of, the better, since that would mean less work to multiply the numbers.
If both numbers were the sum of many powers of two, though, there would be more work for the scribe to do. Numbers that were the sum of consecutive powers of two meant a lot of work. One example is since and
Let's look at a sum of consecutive powers of two that starts with and call it
Now here's doubled:
Subtracting then leaves us with but in a much simpler form than what we started with:
That leaves us with
Any time we do this with a sum of consecutive powers of two (starting with one), the middle terms cancel out.
What kind of number will a sum like this always be?