Challenge #12 solution, part III

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 n = 2k + 1 is odd, then any way of writing n must have at least one copy of 2^0 (since otherwise the sum would be even). If we just remove one copy of 2^0, we get a way to write n - 1 = 2k; conversely, any way to write 2k can be made into a way to write 2k + 1 by adding 2^0. Therefore, letting p(n) denote the number of ways to write n as a sum of powers of two, we have p(2k + 1) = p(2k).

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

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

\{p(2k)\}_{k=1,2,\dots} = \{ 2, 4, 6, 10, 14, 20, 26, 36, 46, \dots \}

Notice how the first two differences (4 - 2 and 6 - 4) 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 p(2k) = p(2k-1) + p(k). You can see more of the sequence on the Online Encyclopedia of Integer Sequences (one of my favorite web sites!).

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in counting, pattern, recursion, sequences, solutions. Bookmark the permalink.

1 Response to Challenge #12 solution, part III

  1. Pingback: Challenge #12 solution, part II « The Math Less Traveled

Comments are closed.