FMM2

Friday Morning Math Problem

Sums of Powers of 2

For a given positive integer N, the binary representation of N is a way of expressing N as a linear combination (with coefficients of 0 or 1) of powers of 2. But there are many more ways of writing N as a linear combination of powers of 2 with positive integer coefficients.

For example, 15 has binary representation of 1111 so it can be written as

$2^{3}+2^{2}+2^{1}+2^{0}$

But 15 can also be written as

$7\times 2^{1}+2^{0}$

or as

$2\times 2^{2}+3\times 2^{1}+1\times 2^{0}$

or as

$4\times 2^{1}+7\times 2^{0}$

etc.

How many ways can the number 55 be written as the linear combination (with integer coefficients) of powers of 2?

Solution

Let's imagine that there exists a magical infinite polynomial (series), one whose coefficients correspond exactly to the solutions to our problem: 1 + a_1 z + a_2 z^2 + a_3 z^3 + ... That is, a_N is the number of ways you can write N as a linear combination of powers of 2. If we can find an expression for this polynomial, we just have to evaluate the Nth term to answer our question. Let's start with the most trivial case, where we can only write N as a linear combination of 2^0 (no other powers of 2). There is always only one way to combine 2^0 to form N, and that's by multiplying it by N. The magical infinite series would be trivial: 1 + z + z^2 + z^3 + ... Now if we consider the trivial case where we can only write N as a linear combination of 2^1 (no other powers of 2), we get the series: 1 + z^2 + z^4 + z^6 + ... And if we consider the trivial case where we can only write N as a linear combination of 2^2 (no other powers of 2), we get the series: 1 + z^4 + z^8 + z^12 + ... Now, to count the number of ways we can write N as a linear combination of 2^0 or 2^1, we would multiply the two series above together, to get: (1 + z + z^2 + z^3 + ...)*(1 + z^2 + z^4 + z^6 + ...) = 1 + z + z^2 + z^3 + z^4 + z^5 + ... + z^2 + z^3 + z^4 + z^5 + ... + z^4 + z^5 + ... = 1 + z + 2z^2 + 2z^3 + 3z^4 + 4z^5 + ... and find the coefficient of the z^N term. The coefficient of z^3 is 2 because each of the two cases (2^0 or 2^1) contribute one possible way of making 3 from powers of 2. Likewise, if we wanted to account for 2^0 or 2^1 or 2^2, we would multiply three infinite series together. And so on... It would be nice if we had some way of using functions instead of infinite series, to avoid all the bookkeeping. It turns out we can: Let c = 1 + z + z^2 + z^3 + ... Then zc = z + z^2 + z^3 + z^4 + ... and c - zc = 1 therefore c (1-z) = 1 and c = 1/(1-z) (Note this is not mathematically rigorous, but by introducing rigor we can arrive at the same conclusion.) Now we can write 1/(1-z) in place of 1+z+z^2+... Likewise, we can also show 1 + z^2 + z^4 + z^6 + ... = 1/(1-z^2) (using the fact that (1-z^2) = (1+z)(1-z)). Now we can very easily multiply series together to get a new series, and determine the coefficient of z^N to determine the solution. If we include as many 1/(1-z^p) terms as we need, we will end up with the magic polynomial that we were after at the beginning: 1/(1-z) * 1/(1-z^2) * 1/(1-z^4) * (...) = 1 + a_1 z + a_2 z^2 + a_3 z^3 + ... To more formally write the quantity on the left side, we say: \prod_{k >= 0} 1/( 1 - z^2^k ) where the maximum value of k we need is determined by the largest value of N (the largest term we expect to appear in the magical infinite series we are after). For example, if we have N = 15, we can write the generating function: 1/( (1-z) (1-z^2) (1-z^4) (1-z^8) ) and use a Taylor series expansion to convert this back into a series and find the coefficient of the Nth term: 1/( (1-z) (1-z^2) (1-z^4) (1-z^8) ) = 1 + x + 2z^2 + 2z^3 + 4z^4 + 4z^5 + ... + 26z^14 + 26z^15 Therefore, there are 26 ways to write 15 as a linear combination of powers of 2. If we now try N = 55, our generating function can be expanded similarly to get: 1/( (1-z) (1-z^2) (1-z^4) (1-z^8) (1-z^16) (1-z^32) ) = 1 + z + 2x^2 + 2x^3 + 4x^4 + ... + 900x^53 + 1014x^54 + 1014x^55 So our final answer is 1014.