With Greater Powers

As in Agnishom's solution, we have the recurrence $f(n) = \sum_{k=0}^{\infty} f(n-2^k)$ , where $f(0) = 1$ and $f(m) = 0$ for $m < 0$ .

(To see this, we classify the partitions of $n$ into powers of $2$ by the first term; there are $f(n-1)$ partitions starting with a $1$ , $f(n-2)$ starting with a $2$ , and so on.)

We'd like to show that $f(n)$ is odd if and only if $n$ is one less than a power of $2$ . We proceed by induction.

Clearly the statement is true for $n = 0,1$ . Now suppose $n \ge 1$ and use the recurrence to see that the parity of $f(n)$ is determined by the number of $k$ such that $f(n-2^k)$ is odd. By the inductive hypothesis, this is the number of $k$ such that $n- 2^k = 2^j-1$ for some $j$ , i.e. the number of ways to write $n = 2^k + 2^j -1$ . Since we can interchange $k$ and $j$ , this number is even unless there is a representation with $j= k$ , in which case it is odd.

So $f(n)$ is odd if and only if $n = 2^k + 2^k - 1$ for some $k$ , i.e. if and only if $n$ is one less than a power of $2$ . Hence we are done by induction.

The answer to the problem is $2^{11} - 1 = \fbox{2047}$ .

First, notice that for every $n$ , the first summand could be either $1$ or, $2$ , or $4$ ... or $2^j$ .

So, this gives us the recurrence relation:

$f(n) = f(n-1) + f(n-2) + f(n-4) + \cdots$

Using this recurrence, we can build up the following table containing the values of $n$ modulo $2$ .

1
2
3
4
5
6
7
8

f = [1] #because f(0) = 1
for i in xrange(1,10001):
     j = 0
     s = 0
     while 2**j <= i:
             s += f[i-2**j]
             j += 1
     f.append(s%2)

Now, we just look for the numbers above 2013 for which $f(n)$ is odd:

1
2

>>> filter (lambda n: t[n],range(2013,3000))
[2047]

f(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k

To prove this, assume that this is true for all values up to $n-1$ .

Now,

$f(2^k - 1) = f(2^k - 2) + f(2^k - 3) + \cdots f(2^k - 2^{k-1} - 1)$

It is not to hard to see that none of the arguments above except the last one is of the form $2^k - 1$ . Hence, they are all even by assumption.

The last term, however, simplifies to $2^k - 2^{k-1} - 1 = 2^{k-1} - 1$ the $f$ of which is odd, by the induction hypotheses.

Hence, in such a case, $f(2^k - 1)$ is always odd.

For the next part of the proof, we need to show that all the odds pair up whenever $n \neq 2^k - 1$ , yielding an even number.

[The rest of the proof is too big for this margin to contain]