Formula for how many combinations of powers of 2 sum to $2^n$

1.1k Views Asked by At

Given a number $2^n, n\in\mathbb{Z}\gt 0$, I would like to find a formula for how many unique sets of powers of $2$ sum to that number. This is related to the triangular numbers but excludes non-power-of-$2$ terms.

For example,

$$\begin{align}2^3 &= 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1\\ &= 2 + 1 + 1 + 1 + 1 + 1 + 1\\ &= 2 + 2 + 1 + 1 + 1 + 1\\ &= 2 + 2 + 2 + 1 + 1\\ &= 2 + 2 + 2 + 2\\ &= 4 + 1 + 1 + 1 + 1\\ &= 4 + 2 + 1 + 1\\ &= 4 + 2 + 2\\ &= 4 + 4\\ &= 8\end{align} $$ so $f(3) = 10$

1

There are 1 best solutions below

0
On BEST ANSWER

Define $g(m)$ to be the number of ways of writing $m$ as sums of powers. Then $f(n)=g(2^n)$. The sequence $g$ is OEIS sequence A018819.

There's a little more at the OEIS page, but it doesn't list a closed form.

The generating function for $g$ is:

$$G(x)=\sum_{m=0}^\infty g(m)x^m = \prod_{k=0}^\infty \frac{1}{1-x^{2^k}}$$ We see that $G(x^2)=G(x)(1-x)$.