Partitions using only powers of two on $1000.$

Question

How many ways are there to write $1000$ as a sum of powers of $2,$ ($2^0$ counts), where each power of two can be used a maximum of $3$ times. Furthermore, $1+2+4+4$ is the same as $4+2+4+1$. These count as one arrangement, not two separate ones.

To clarify, the ways to write $4$ as a sum of powers are:

$4=4, 2+2=4, 1+2+1.$

I think these go up in increments of $2,$ for example the ways to write $8$ is 5...etc. so it would just be the 1000th term of that sequence, but I may be missing something. How would I start this problem?

Answer 1

You can write a recurrence. If $n$ is odd, you need an odd number of $1$ terms, so write down a $1$ and consider $n-1$ in what follows. If $n$ is even, you can either use $0$ or $2\ 1$s. If you use $2\ 1$s, you have $n-2$ left to express and can't use any $1$s, so you can express $\frac 12(n-2)$ and multiply all the terms by $2$. If you don't use any $1$s, you can express $\frac n2$ and multiply all the terms by $2$. So if $a(n)$ is the number of ways to express $n$ we have $$a(n)=\begin{cases}1&n=1\\2&n=2\\a(\frac n2)+a(\frac{n}2-1)&n \text{ even}\\a(n-1)&n\text{ odd}\end{cases}$$ Rob Pratt finds that the solution is $a(n)=1+\lfloor \frac n2 \rfloor$. This works for $1,2$. Then if it works up through even $n$, $a(n+1)=a(n)=1+\lfloor \frac {n+1}2 \rfloor, a(n+2)=a(\frac n2+1)+a(\frac n2)=1+\lfloor \frac{\frac n2+1}2\rfloor+1+\lfloor \frac{\frac n2}2\rfloor=1+\lfloor \frac {n+2}2\rfloor$

Answer 2

The generating function is \begin{align} &(1+x+x^2+x^3) (1+x^2+x^4+x^6) (1+x^4+x^8+x^{12}) \dots \\ &= \prod_{k=0}^\infty (x^{0\cdot 2^k}+x^{1\cdot 2^k}+x^{2\cdot 2^k}+x^{3\cdot 2^k}) \\ &= \prod_{k=0}^\infty ((x^{2^k})^0+(x^{2^k})^1+(x^{2^k})^2+(x^{2^k})^3) \\ &= \prod_{k=0}^\infty (1+x^{2^k})(1+x^{2^{k+1}}) \\ &= \prod_{k=0}^\infty (1+x^{2^k}) \prod_{k=0}^\infty (1+(x^2)^{2^k}) \\ &= \frac{1}{1-x} \cdot \frac{1}{1-x^2} \quad \text{by uniqueness of binary representation}\\ &= \frac{1}{(1+x)(1-x)^2} \\ &= \frac{1/4}{1+x} + \frac{1/4}{1-x} + \frac{1/2}{(1-x)^2} \\ &= \frac{1}{4}\sum_{n=0}^\infty (-x)^n + \frac{1}{4}\sum_{n=0}^\infty x^n + \frac{1}{2}\sum_{n=0}^\infty (n+1)x^n, \end{align} which immediately implies explicit formula $$\frac{1}{4}(-1)^n + \frac{1}{4}\cdot 1 + \frac{1}{2}(n+1) = \frac{2n+3+(-1)^n}{4}=\left\lfloor\frac{n+2}{2}\right\rfloor=1+\left\lfloor\frac{n}{2}\right\rfloor.$$ In particular, $n=1000$ yields $501$.

Answer 3

Here's another approach that counts via an explicit bijection.

Claim: The number of ways is equal to the number of solutions to $ n = a + 2b$, where $a, b$ are non-negative integers.

Corollary: There are $ 1 + \lfloor \frac{n}{2} \rfloor$ ways.

Genearlize this: Show that the number of ways of expressing $n$ as the sum of powers of two each used a maximum of 7 times, is equal to the number of ways of writing $n = a + 2b + 4c $, where $a, b, c$ are non-negative integers.

Proof of claim: We show the bijection between ways to express $n$ as sum of powers of $2$ at most 3 times and representations $n = a+b$ by creating the map in each direction.

Given a representation $n = a+2b$,
There is a unique way to express $a$ in binary, which determines the powers of 2.
There is a unique way to express $b$ in binary, which we will use to determine the powers of 2 that appear twice (or more).
For example, with $ 1000 = 124 + 2 \times 418$, we have
$a = 124 = 1111100_2 = 2^6 + 2^5 + 2^4 + 2^3 + 2^2 $
$b = 418 = 110110110_2 = 2^8 + 2^7 + 2^5 + 2^4 + 2^2 + 2^1. $
Then, we have $ 1000 = a + 2b = 2\times 2^8 + 2 \times 2^7 + 2^6 + 3 \times 2^5 + 3 \times 2^4 + 2^3 + 3\times 2^2 + 2 \times 2^1$ gives a way of writing 1000 as the sum of powers of 2, each used at most 3 times.

Conversely, given a valid way, we can split it up into our $a$ and $b$ parts, corresponding to the number of terms. Namely

• If the power of 2 appears 0 times, it goes into neither.
• If the power of 2 appears 1 times, it goes into $a$
• If the power of 2 appears 2 times, it goes into $b$.
• If the power of 2 appears 3 times, it goes into $a$ and $b$.

Note: The better way to write this, is to condition on the binary digits. Namely, if the power of 2 appears $k$ times, then it goes into $a$ if the "units digit" is 1, and get into $b$ if the "tens digit" is 1.
This helps with the generalization.

To check that you understand this,

• Reverse the worked example.
• Verify that we yield $ n = a + b$.
• Verify that the composition of both maps yields the identify.

Hence, we have a bijection and the exact number of ways is $ 1 + \lfloor \frac{n}{2} \rfloor$.