Let $f(n)$ be the number of ways to write $n$ as a sum of powers of 2 , where we keep track of the order of the summation. For example, $f(4)=6$ because 4 can be written as $4,2+2,2+1+1,1+2+1,1+1+2$, and $1+1+1+1$. Find the smallest $n$ greater than 2013 for which $f(n)$ is odd.
The answer is 2047 .
For convenience, we agree that $f(0)=1$. Then by considering cases on the first number in the representation, we derive the recurrence
$$
f(n)=\sum_{k=0}^{\left\lfloor\log _{2} n\right\rfloor} f\left(n-2^{k}\right) .
$$

We wish to understand the parity of $f$. The first few values are
$$
\begin{array}{l}
f(0)=1 \\
f(1)=1 \\
f(2)=2 \\
f(3)=3 \\
f(4)=6 \\
f(5)=10 \\
f(6)=18 \\
f(7)=31 .
\end{array}
$$

Inspired by the data we make the key claim that
Claim - $f(n)$ is odd if and only if $n+1$ is a power of 2 .

Proof. We call a number repetitive if it is zero or its binary representation consists entirely of 1 's. So we want to prove that $f(n)$ is odd if and only if $n$ is repetitive.
This only takes a few cases:
- If $n=2^{k}$, then $(\odot)$ has exactly two repetitive terms on the right-hand side, namely 0 and $2^{k}-1$.
- If $n=2^{k}+2^{\ell}-1$, then $(\nu)$ has exactly two repetitive terms on the right-hand side, namely $2^{\ell+1}-1$ and $2^{\ell}-1$.
- If $n=2^{k}-1$, then $(\bigcirc)$ has exactly one repetitive terms on the right-hand side, namely $2^{k-1}-1$.
- For other $n$, there are no repetitive terms at all on the right-hand side of $(\odot)$.

Thus the induction checks out.
So the final answer to the problem is 2047 .