And now for the solution to problem #3 from Challenge #12, which asked: how many ways are there to write a positive integer n as a sum of powers of two, with no restrictions on how many powers of two may be used?

In the comments to Challenge #12, Jonathan posted some good thoughts, and Anand posted a thorough analysis, so if you want more details you can go read those.

The main idea is to break our analysis down into two cases based on whether n is even or odd, like we did in our analysis of the solution to problem #1. If is odd, then any way of writing n must have at least one copy of (since otherwise the sum would be even). If we just remove one copy of , we get a way to write ; conversely, any way to write can be made into a way to write by adding . Therefore, letting denote the number of ways to write n as a sum of powers of two, we have .

On the other hand, suppose is even. For any particular way to write n, we consider two cases: either it includes at least one , in which case we can remove it to give a way to write ; or it doesn’t contain , in which case we can divide everything else by 2 to yield a way to write . So, we have .

Oh, and of course, for a base case, . Let’s calculate a few values of (omitting odd values since they are simply equal to the previous value (boring!)):

Notice how the first two differences ( and ) are equal to 2; the next two differences are 4; then 6, then 10… and yes, then 14, and so on. Interesting! This self-similar structure is a direct result of the recurrence . You can see more of the sequence on the Online Encyclopedia of Integer Sequences (one of my favorite web sites!).