What is the algorithm to find the numbers of different ways an integer can be expressed as a sum of powers of 2?

Question

At first, we define f(0)=1 and f(n) to be the numbers of ways n can be represented as a sum of powers of 2. But the restriction is that no power can be repeated more than 2 twice.

For example, f(10)=5 since, 10=8+2, 10=8+1+1, 10=4+4+2, 10=4+4+1+1, 10=4+2+2+1+1.

I am looking for an algorithm which can calculate this function f. I suspect, it has something to do with recurrence.

Answer 1

In Mathematica:

mycount[n_] := 
 Length[Select[
   IntegerPartitions[n, All, Table[2^i, {i, 0, Ceiling[Log[2, n]]}]], 
   Max[ Length /@ Gather[#]] < 3 &]]

Answer 2

Let $f(n)$ be the number of "hyperbinary" partitions of $n$ (as these are sometimes called).

If $n$ is odd, with $n = 2k+1$, then we have $f(2k+1) = f(k)$. Any hyperbinary partition of $2k+1$ must contain a single 1; then the remainder of the partition is just double some partition of $k$. For example, we have the hyperbinary partitions of 9:

$$8 + 1, 4 + 4 + 1, 4 + 2 + 2 + 1$$

and we can double these partwise and add 1 at the end to get the hyperbinary partitions of 19:

$$16 + 2 + 1, 8 + 8 + 1, 8 + 4 + 4 + 2 + 1$$

Now if $n$ is even, then we have $f(2k) = f(k) + f(k-1)$. Any hyperbinary partition of $2k$ either has zero or two 1s. If it has zero 1s, then it can be made by doubling a hyperbinary partition of $k$; if it has two 1s, then it can be made by doubling a hyperbinary partition of $k-1$ and adding two 1s onto the end. For example, the hyperbinary partitions of $8$ are

$$8, 4 + 4, 4 + 2 + 2, 4 + 2 + 1 + 1$$ and these give four hyperbinary partitions of 18, each with two 1s: $$16 + 1 + 1, 8 + 8 + 1 + 1, 8 + 4 + 4 + 1 + 1, 8 + 4 + 2 + 2 + 1 + 1$$ while the three hyperbinary partitions of 9 give us three more hyperbinary partitions of 18, each with no 1s: $$16 + 2, 8 + 8 + 2, 8 + 4 + 4 + 2$$

Starting with $f(0) = 1, f(1) = 1$ you can get $f(n)$ for any $n$ using this recurrence, and you don't need to compute all the intermediate values or actually write out the partitions. For example, we can compute $f(45)$:

\begin{align}f(45) &=& f(22) \\ &=& f(10) + f(11) \\ &=& f(4) + f(5) + f(5) \\ &=& f(4) + 2f(5) \\ &=& (f(1) + f(2)) + 2f(2) \\ &=& f(1) + 3f(2) \\ &=& f(1) + 3(f(0) + f(1)) \\ &=& 3f(0) + 4f(1) \\ &=& 3 + 4 \\ &=& 7 \end{align} where basically at each step we have $a f(k) + b f(k+1)$, one of $k$ and $k+1$ is even and one is odd, so we expand using the recurrence above to get three terms, two of which are the same. We can regroup and continue until we've reduced to multiples of $f(0)$ and $f(1)$ which are both 1.

Fun fact: the sequence $f(0)/f(1), f(1)/f(2), f(2)/f(3), \cdots$, which begins $1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, \ldots$, contains every positive rational number exactly once, in lowest terms! See the paper Recounting the rationals by Neil Calkin and the late Herb Wilf (that link should work as long as Penn doesn't take down Wilf's web page).