2000 As Powers of Two

Let $f(n)$ be the number of ways to write $n$ as the sum of powers of 2 with non-negative exponents, where each power is used at most twice. (Call each of these ways of writing $n$ as a sum an expression of $n$ .) We want to find $f(2000)$ .

Firstly note that $f(1)=1$ and $f(2)=2$ .

If $n=2m+1$ is odd, then clearly any expression of $n$ must contain an odd number of '1's. But the number of '1's in an expression can only be 0, 1 or 2, so there is exactly one '1' in the expression of $n$ . By removing this '1' and halving the remaining terms of the expression, we get an expression of $\frac{n-1}2=m$ . Conversely, for every expression of $m$ , we can double every term and include a '1' to get an expression for $n$ . Hence the number of expressions of $n$ is equal to the number of expressions of $m$ , thus $f(2m+1)=f(m)$ for all positive integers $m$ .

If $n=2m$ is even, there are an even number of '1's in any expression of $n$ , so there are either zero or two '1's in the expression. If there are no '1's in the expression then we can halve every term of the expression to get an expression of $\frac{n}2=m$ . If there are two '1's in the expression then we remove these '1's and halve the remaining terms to get an expression of $\frac{n-2}2=m-1$ . Conversely, given an expression of either $m$ or $m-1$ we can double each term, and add either zero or two '1's to get an expression for $n$ . Thus $f(2m)=f(m)+f(m-1)$ for all positive integers $m\geq2$ .

Now we are ready to calculate $f(2000)$ :

$\begin{aligned}f(2000)&=f(1000)+f(999)\\ &=(f(500)+f(499))+f(499)\\ &=(f(250)+f(249))+2f(249)\\ &=(f(125)+f(124))+3f(124)\\ &=f(62)+4(f(62)+f(61))\\ &=5(f(31)+f(30))+4f(30)\\ &=5f(15)+9(f(15)+f(14))\\ &=14f(7)+9(f(7)+f(6))\\ &=23f(3)+9(f(3)+f(2))\\ &=32f(1)+9f(2)\\ &=32\cdot1+9\cdot2\\ &=50, \end{aligned}$

and so the answer is $\boxed{50}$ .

We will begin by expressing $2000_{10} = 11111010000_2$ ; note that it has 11 binary digits.

Now, let $P_1, P_2, \ldots, P_{11}$ be points in a line, in that order. Put a marker on $P_1, P_2, P_3, P_4, P_5, P_7$ , corresponding to the set bits in the binary representation; call the marker initially on $P_i$ to be marker $M_i$ . Additionally, also put a stop sign underneath them, and a stop sign on $P_{11}$ . The markers can be moved any number of spaces to the right (stopping on a named point), as long as it doesn't cross over any stop sign. (If it is on a stop sign, it's not considered to cross over that stop sign. It is also not assumed to cross over the stop sign that is initially placed below it. This basically means the marker may not cross over the closest stop sign to the right.)

We will compute the number of ways of the markers configurations such that no two markers are on the same point.

First, $M_7$ has 5 positions ( $P_7, P_8, P_9, P_{10}, P_{11}$ ), unless $M_5$ comes to $P_7$ in which $M_7$ only has 4 positions ( $P_8, P_9, P_{10}, P_{11}$ ). Similarly, $M_5$ has 3 positions ( $P_5, P_6, P_7$ ; remember that it may not cross over the stop sign at $P_7$ ) unless $M_4$ comes to $P_5$ in which it only has 2 positions. In total, there are 14 positions ( $5 \cdot 3$ , subtract by $1$ because $M_5$ and $M_7$ may not both occupy $P_7$ ) when $M_4$ is not on $P_5$ and 9 positions ( $5 \cdot 2 - 1$ , same reason) when $M_4$ is on $P_5$ .

Remember that markers can't cross over a stop sign. This has a side effect of that markers can't cross over each other. If a marker $M_i$ crosses over $M_j$ , then it must cross over $P_j$ because $M_j$ is necessarily on $P_j$ or to the right of $P_j$ , which involves $M_i$ crossing over a stop sign.

Now, because $M_4$ may not cross over $P_5$ , we have $M_1, M_2, M_3, M_4$ to occupy four points out of $P_1, P_2, P_3, P_4, P_5$ , so there are $\binom{5}{4} = 5$ ways to do this (remember that the leftmost marker must always be $M_1$ , the second leftmost marker must always be $M_2$ , and so on, because markers can't cross over each other). One of the ways have $M_4$ on $P_4$ , which gives 14 positions as above, while the others have $M_4$ on $P_5$ , which gives 9 positions each, for a total of $14 + 4 \cdot 9 = 50$ ways.

It remains to prove that the above visualization indeed counts the number of ways to represent 2000 as powers of two, where no power of two is used more than twice.

We interpret each marker $M_i$ to be the number $2^{11-i}$ , and moving a marker from $P_i$ to $P_{i+1}$ means splitting $2^{11-i}$ to two instances of $2^{10-i}$ . So, if a marker $M_i$ comes to the point $P_j$ with $j \neq i$ , the terms generated are $2^{10-i}, 2^{9-i}, \ldots, 2^{11-j}$ and another $2^{11-j}$ . We will prove that this mapping is a function, which is injective and surjective. In other words, we will prove that this mapping uniquely maps each markers configuration to the powers of two representation, so that exactly all powers of two representations are mapped (and no other).

First, the proof that we mapped only to valid representations.

Suppose a marker $M_i$ is on point $P_j$ . Then the corresponding representation has the terms $2^{10-i}, 2^{9-i}, \ldots, 2^{11-j}, 2^{11-j}$ . When $j > i$ , there is no term $2^{11-i}$ generated by $M_i$ , and since a marker to the left of $M_i$ may not cross over point $P_i$ , it will not generate any term whose exponent is less than $11-i$ , so no two different markers will generate the same term. When $j = i$ , no marker to the left of $M_i$ can come to point $P_i$ , so the claim still stays true.

This means for any exponent $a$ , it is only generated by one marker. It can also be easily seen that no marker generates more than two identical terms. Also, the fact that the sum of all terms remains the same throughout the operation is trivial (the term before a split is equal to the two terms generated after the split). So the representation is valid.

Second, the proof that we mapped to all valid representations.

We will approach this in the opposite way: Every valid representation can be transformed to a markers configuration.

Starting from the largest term, if some term $2^{11-i}$ occurs twice, take all the terms $2^{11-i}, 2^{12-i}, \ldots, 2^{10-j}$ and $2^{11-i}$ (exponents are consecutive integers, and we take as many as possible, in the sense that there is no $2^{11-j}$ term), and replace them as a marker $M_j$ on the point $P_i$ . After doing this, if there are terms left behind, none of them is repeated; replace every term $2^{11-i}$ with a marker $M_i$ on $P_i$ .

To prove that this configuration indeed leads to our valid representation, we can simply observe that all our transformations above are precisely the inverse of our transformation from markers to powers of two. To prove that no two markers occupy the same space, note that in order for two markers to occupy the same space then either $2^{11-i}$ exists at least three times (so there are two markers occupying $P_i$ , once by the first transformation and once by the second), or there are two terms $2^{11-i}$ that got both transformed by the second transformation. Neither is allowed (the first is not a valid powers of two representation and the second should have taken the first transformation), so no two markers occupy the same space. To prove that no marker cross a stop sign, just note that if a marker crosses a stop sign, then there are two terms generated by two different markers, which by the first transformation means there should have been a different marker configuration occurring (with these two terms become a single marker instead of the trails of two markers).

Finally, proof that each powers of two representation is mapped from a single markers configuration. But our transformation above has guaranteed this. If we process the markers from left to right when transforming to the powers of two representation, then we will never have to return back to an earlier marker as an effect of a later marker (by transformation rules).

This forms a bijection between the two schemes, markers configuration and powers of two representation. So there must be an equal number of powers of two representations as there are markers configurations, which means there are $\boxed{50}$ ways.

2000, as any other positive whole number, can be written as a sum of powers of two by dividing the number by the largest power of two then subtracting the quotient by one and repeating the process. 2000 can be written as : $2^4 (125) = 2^4(1 + 124) = 2^4(1 + 2^2(31)) = 2^4(1 + 2^2(1 + 30))$

$\ldots$

$2^4(1 + 2^2(1 + 2(1 + 2(1 + 2(1 + 2)))))$

By distributing the numbers in and out of the parenthesis, we get $2^4 + 2^6 + 2^7 + 2^8 + 2^9 + 2^{10}$ . It is easy to see that there are many more cases because $2^k = 2 * 2^{k-1} = 2^{k-1} + 2^{k-1}$ . The restriction is that no power of two can be used more than twice. This poses a problem so we split $2^4$ from the rest. The next steps will show why. Let $A = 2^4$ and the rest equal to $B$

First we count the cases for $B$ restricted by $2^4$

• $2^6 + 2^7 + 2^8 + 2^9 + 2^{10}$
• $2^5 + 2^5 + 2^7 + 2^8 + 2^9 + 2^{10}$
• $2^5 + 2^5 + 2^6 + 2^6 + 2^8 + 2^9 + 2^{10}$
• $2^5 + 2^5 + 2^6 + 2^6 + 2^7 + 2^7 + 2^9 + 2^{10}$
• $2^5 + 2^5 + 2^6 + 2^6 + 2^7 + 2^7 + 2^8 + 2^8 + 2^{10}$
• $2^5 + 2^5 + 2^6 + 2^6 + 2^7 + 2^7 + 2^8 + 2^8 + 2^9 + 2^9$

The cases for $A$

• $2^4$
• $2^3 + 2^3$
• $2^2 + 2^2 + 2^3$
• $2^1 + 2^1 + 2^2 + 2^3$
• $2^0 + 2^0 + 2^1 + 2^2 + 2^3$ (recall that exponents here should be non-negative)

Total : $6 * 5 = 30$ ways

Since there are 4 cases of $A$ that do not have $2^4$ , $B$ may now reduce $2^5$ into $2^4$ . $B$ has 5 cases that contain $2^5$ , multiplying the unrestricted cases we have $4 * 5 = 20$ more cases.

The $2^4$ s of $B$ are thus restricted because there are no cases of $A$ which have their highest addend as $2^2$ . This means there are no more ways to reduce $B$ with respect to $A$ . Adding all possible cases we have a total of $30 + 20 = 50$ cases.

Seeing that powers of two are involved, its instinctive to think a solution using binary numbers. So, 2000 can be written as 11111010000.

It would have been wonderful if there was no repetition (not really since you wouldn't get such a nice question) . But since maximum two are allowed, we need some modifications.

Notice that if you add $2^2$ and $2^2$ , it becomes $2^3$ . Thus a 1 in the binary notation becomes 2 in the adjacent position. Also convince yourself that you won't be able to slide a '1' more than one place, because then the other powers will be repeated more than twice. But, you will be able to break the 2 in parts, like, 10000 can be written as 02000, 01200, 01120 and other ways.Thus, we need to find the ways in which this can happen under the given constraints.

Now, the possible conversion of 10 is 02. The possible conversion of 20 is 12. Consider our number 11111010000. Let the first case be that we don't shift a 2 in the 1010000 part (i.e. we cannot write it as 0210000 which becomes 0130000 which becomes 0122000 and so on.) So 111110 and 10000 can be considered two blocks and the total ways will be a product of that of those two. Ways to write 10000 is 02000, 01200, 01120, 01112 and of course 10000. (i.e. 5) Ways to write 111110 will come out to be 6. So ways are 30 for this case.

The second case is .... when we don't do the first case. Here, 11110 and 210000 can be considered two blocks. A similar approach gives the ways as 20.

So total ways are 50.

This is the number of hyperbinary representations of 2000. The number of hyperbinary representations of n is equal to fusc(n+1), where fusc is Stern's diatomic series. Dijkstra gives this algorithm for computing fusc:

Set a = 1, b = 0. While n>0, set b <- a + b if n is odd and a <- a + b if n is even, then replace n with floor(n/2). Once n = 0, the answer is b.

With n = 2001, this gives:

(n, a, b): (2001, 1, 0), (1000, 1, 1), (500, 2, 1), (250, 3, 1), (125, 4, 1), (62, 4, 5), (31, 9, 5), (15, 9, 14), (7, 9, 23), (3, 9, 32), (1, 9, 41), (0, 9, 50)

and so the answer is 50.

More generally, let $f(n)$ be the number of such representations of the positive integer $n$ . We claim that $f(2n) = f(n - 1) + f(n)$ and $f(2n + 1) = f(n)$ for all $n$ .

Consider a representation of $2n + 1$ . Since $2n + 1$ is odd, there must be exactly one term of 1. If we subtract this 1, then we obtain a representation of $2n$ , where every power of 2 is at least 2, and every power of 2 appears at most twice. If we divide every term by 2, then we obtain a representation of $n$ , where every power of 2 appears at most twice, which is exactly what $f(n)$ counts. Hence, $f(2n + 1) = f(n)$ . For example, here are the representations for $n = 9$ :

$\begin{aligned} 1 + 2 + 2 + 4 &\leftrightarrow 1 + 1 + 2 \\ 1 + 4 + 4 &\leftrightarrow 2 + 2 \\ 1 + 8 &\leftrightarrow 4 \end{aligned}$ Thus, $f(9) = f(4) = 3$ .

Now, consider a representation of $2n$ . Since $2n$ is even, there must be either zero or two terms of 1. If there are zero terms of 1, then we can divide every term by 2, to obtain a representation of $n$ . There are $f(n)$ such representations. If there are two terms of 1, then we can subtract both terms of 1, to obtain a representation of $2n - 2$ , where every power of 2 is at least 2, and every power of 2 appears at most twice. If we divide every term by 2, then we obtain a representation of $n - 1$ . There are $f(n - 1)$ such representations. Hence, $f(2n) = f(n) + f(n - 1)$ . For example, here are the representations for $n = 10$ :

$\begin{aligned} 2 + 4 + 4 &\leftrightarrow 1 + 2 + 2 \\ 2 + 8 &\leftrightarrow 1 + 4 \\ 1 + 1 + 2 + 2 + 4 &\leftrightarrow 1 + 1 + 2 \\ 1 + 1 + 4 + 4 &\leftrightarrow 2 + 2 \\ 1 + 1 + 8 &\leftrightarrow 4 \\ \end{aligned}$ Thus, $f(10) = f(5) + f(4) = 5$ .

Using the recursions $f(2n) = f(n - 1) + f(n)$ and $f(2n + 1) = f(n)$ , we then have $\begin{aligned} f(2000) &= f(1000) + f(1999) \\ &= f(500) + f(499) + f(499) = f(500) + 2f(499) \\ &= f(250) + f(249) + 2f(249) = f(250) + 3f(249) \\ &= f(125) + f(124) + 3f(124) = f(125) + 4f(124) \\ &= f(62) + 4[f(62) + f(61)] = 5f(62) + 4f(61) \\ &= 5[f(31) + f(30)] + 4f(30) = 5f(31) + 9f(30) \\ &= 5f(15) + 9[f(15) + f(14)] = 14f(15) + 9f(14) \\ &= 14f(7) + 9[f(7) + f(6)] = 23f(7) + 9f(6) \\ &= 23f(3) + 9[f(3) + f(2)] = 32f(3) + 9f(2) \\ &= 32f(1) + 9f(2) = 32 \cdot 1 + 9 \cdot 2 = 50. \end{aligned}$

[Notifying @starwar clone .]

First, we need to write 2000 in its binary form. (e.g. 2000 as “11111010000″ and 150 as “10010110″)

Then, we split the binary form into blocks of all ones then all zeroes: a) 2000 as “11111010000″ is split as “111110 – 10000″

For 2000 as “111110 – 10000″, we have 2 blocks – namely A and B respectively. i) If A and B both doesn’t move (–), then we have 1 form. ii) If only A moves (A-), then we have 5 ones that will move so we have 5 forms. iii) If only B moves (-B), then we have 4 forms. iv) If both A and B move (AB): then B moves 4 ways, the rightmost one in A will move 2 ways, and the remaining ones in A will have 5 moves (1 original and 4 moves to the right). This gives us 4 * 2 * 5 = 40 forms.

Therefore, 2000 can be written as such in 1 + 5 + 4 + 40 = 50 ways.

I’ve tried using recurrence relations. I started with the case when N = 2000 (as in the problem). Then let σ(N) be the list of all the ways we can write N as sum of non-negative powers of 2, with each power used at most twice. Then for N = 2000, the elements of σ(2000) can either have no 2^0′s or have two 2^0′s (no element has one 2^0 because 2000 is even). Then for the first case, the ways we can write 2000 without 2^0′s, is equivalent to the number of ways we can write 1000 using this way. There is a bijection between the number of elements of σ(1000) and {P ε σ(2000)| P has no 2^0′s}. Since for every element Q in σ(1000), we can multiply each addends of Q by 2 giving us an element of σ(2000) with assurance that it has no 2^0′s (just increase each power of Q by 1). Likewise, every element in {P ε σ(2000)| P has no 2^0′s} can be divided by 2 to get an element of σ(1000). Hence the bijection is established.

Thus for every even N, we have |σ(N)| = |σ(N/2)| + |σ(N/2 – 1)|. And it can also be shown that for odd N, |σ(N)| = |σ((N-1)/2)|.

Thus, |σ(2000)| = |σ(1000)| + |σ(999)|. Continuing in this fashion gives us |σ(2000)| = 32 |σ(3)| + 9 |σ(2)| = = 32 |σ(1)| + 9 |σ(2)| = 32 1 + 9 2 = 50.

Now I’m stuck in figuring out the formula for a general N. Now we reduce the generalization of the problem to finding for a and b such that |σ(N)| = a |σ(1)| + b |σ(2)| = a + 2b.

[Edit : Comments combined - Calvin]