I got 2047...

Same. I basically showed that $f(n)$ was odd iff $n=2^k-1$ for some $k\in\mathbb{Z}^+$.

That's what I did!

How did you guys do that? I used induction.

My method: Bash. I bashed the cases up to 9 and then found the generalization formula. Apparently, with values of a, b, c, d, e,...f(n) is f(n)=f(n-a)+f(n-b)+f(n-c)+f(n-d)+f(n-e)... That was my bad method of doing it. Proved with induction.

I used strong induction and divided it into 2 cases, showing that $f(n)$ is odd if and only if $n=2^m-1$ for a positive integer k, which gave me 2047.

i showed that parity of f(k) is even for evens and has same parity as f((k-1)/2) for odds

I did strong induction. The recursion was pretty easy to find.

Yeah, those are the 2 cases I did.

Yup, I got 2047, like you guys did.

Yes, 2047 is right. I'll post a rigorous solution in a little.

I hope you were a little more rigorous on that first point, ABCDE, but yeah, that's basically what I wrote. I think that noting why that first point is true is necessary, but I'm not sure. I always write more than necessary .

I put ABCDE's first point in mine as a LEMMA.

Oh, I put it as a lemma too, don't worry.

Whoa, my proof was five pages long. For induction I had four cases. 100th post!!!

Obviously no points, and I basically "found" the answer by checking low n values. Also, the above is clearly legitimate because I am a boss at casework

My proof was going to be 5 pages long, then I realize I was on the wrong track, scrapped the last 3 and wrote the rest of the solution in one page.

I claim that $f(n)\equiv 1 \pmod{2}$ if and only if $n=2^k-1$. We prove this with induction, note that if $2^x\leq n<2^{x+1}$, then we have the recurrence relation \[f(n)= \sum_{i=0}^{x} f(n-2^i) \]Now, we proceed with induction. Note that $f(0)=1,f(1)=1,f(2)=2$ are our base cases. Now, if $n=2^k-1=\overline{111\cdots 1}$, note that only the last term $f(2^k-1-2^{k-1})$ is of the form $2^m-1$ \[f(2^k-1)\equiv f(2^{k-1}-1) \equiv 1 \pmod{2}\]On the other hand if $n\neq 2^k-1$, we consider a few cases. \begin{itemize} \item $n=2^k$. There will be two odd terms, $f(2^k-1)$ and $f(2^k-2^k)$ \item $n=2^a+2^b-1$, in this case removing either the $2^a$ or $2^b$. \item Otherwise, we will never have a $f(0)$ or $f(2^k-1)$ term in the recurrence relation. \end{itemize} Thus, we will always have that $f(n)$ is even if $n\neq 2^k-1$. Thus, our strong induction is complete, and we may answer extract that the smallest choice of $n\geq 2013$ is $2^{11}-1=\fbox{2047}$

I think I win the award for the longest and ugliest combo solution... The answer is $2^{11} - 1 = 2047$. In fact, we will prove a stronger claim: Claim: The value of $f(n)$ is odd if and only if $n = 2^k - 1$, where $k$ is a positive integer. Let $p(n) \in \{0, 1\}$ denote the residue class of $f(n)$ modulo $2$. To determine $p(n)$, it suffices to consider palindromic sums, as all non-palindromic sums have a counterpart (i.e. they form pairs). Claim: For all $k \ge 1$, we have $p(2k - 1) = p(k-1)$ and $$p(2k) = p(k) + \sum_{i = 0}^{j} p(k - 2^{i})$$where $2^j \le k < 2^{j+1}$. (In addition, we define $p(0) = 1$, which obviously works.) Proof. First, we consider $n = 2k-1$. If a palindromic sum contains an odd number of terms, then parity implies the middle term must be $1$. Now, there's $f(k-1)$ ways to finish the palindrome, as the back half of our sum is completely determined by the front half. If our palindromic sum contains an even number of terms, then the final sum must be even, which is impossible for $n = 2k-1$. Thus, $$p(2k-1) \equiv f(k-1) \equiv p(k-1) \pmod{2}.$$Now, suppose $n = 2k$. If our palindromic sum contains an odd number of terms, then parity tells us the middle term must be even, i.e. one of $\{2^1, 2^2, \ldots, 2^{j+1} \}$ where $2^{j+1} \le 2k < 2^{j+2}$. Using similar logic from our last case implies there's $$\sum_{i = 0}^{j} f(k - 2^i)$$ways to do this. If our palindromic sum contains an even number of terms, then the first half our of sum completely determines the second half. Hence, there's $f(\frac{2k}{2}) = f(k)$ ways to create such a palindrome. Thus, $$p(2k) \equiv f(k) + \sum_{i = 0}^{j} f(k - 2^i) \equiv p(k) + \sum_{i = 0}^{j} p(k - 2^i)$$as desired. $\square$ Now, to prove our stronger claim, we proceed with strong induction by considering distinct gaps $2^m \le n \le 2^{m+1} - 1$ for all $m \ge 0$. Proof. Base Case ($m = 0$, $2^0 \le n \le 2^{1} - 1$): By inspection, $$f(2^1 - 1) = f(1) = 1$$which is odd, completing the base case. Induction Hypothesis: For all $0 \le m \le b-1$, i.e. $1 \le n \le 2^b - 1$, $p(n) = 1$ holds if and only if $n = 2^{m+1} - 1$. Now, we will prove the hypothesis also holds for all $0 \le m \le b$. Inductive Step: First, observe $$p(2^{b+1} - 1) = p(2^b - 1) = 1$$by our Inductive Hypothesis. Now, we consider all odd $n$ between $2^b$ and $2^{b+1} - 2$ inclusive. Notice $$2^{b} + 1 \le 2k - 1 \le 2^{b+1} - 3 \implies 2^{b-1} \le k-1 \le 2^{b} - 2$$so the Inductive Hypothesis implies $p(n) = 0$ all aforementioned odd $n$. Now, we consider all even $n$ between $2^b$ and $2^{b+1} - 2$ inclusive. (In this case, $2^{b-1} \le k \le 2^{b} - 1$.) First, we discard all $n = 2k$ where all terms of $$\mathbb{T} = \{p(k), p(k - 2^0), p(k - 2^1), \ldots, p(k - 2^{b-1})\}$$output $0$. If $p(k) = 1$, i.e. $k = 2^{b} - 1$, then $$2^{b-1} - 1 \le k - 2^i \le 2^{b} - 2$$so the only other term in $\mathbb{T}$ which is odd is $p(k - 2^{b-1})$, implying $p(2k) = p(2^{b+1} - 2)$ is even. Henceforth, we assume $p(k) = 0$. Now, suppose $p(k - 2^j) = 1$ for some $0 \le j \le b-2$. Since $$2^{b} - 2 \ge k - 2^j \ge 2^{b-1} - 2^{b-2} = 2^{b-2}$$we know $p(k - 2^j) = 1$ can hold for at most $1$ value of $j$, as $n = 2^{b-1} - 1$ is the only value of $n$ satisfying the previous bound such that $p(n) = 1$. Thus, we know $$k - 2^j = 2^{b-1} - 1 \implies k - 2^{b-1} = 2^j - 1.$$Thus, $p(k - 2^{b-1}) = 1$ as well for this case, and we conclude $$p(2k) \equiv p(k - 2^j) + p(k - 2^{b-1}) \equiv 1 + 1 \equiv 0 \pmod{2}.$$Because $p(k - 2^{b-1}) = 1$ implies $p(k - 2^j) = 1$ holds for exactly $1$ value of $0 \le j \le 2$, we've covered all possible cases, which completes the induction. $\square$ Since $2^{10} - 1 = 1023 < 2013 < 2^{11} - 1 = 2047$, we know the answer is $2^{11} - 1 = 2047$ as desired. $\blacksquare$

Lemma: $f(n)=f(n-1)+f(n-2)+f(n-4)+\ldots f(n-2^{\lfloor \log_2(n)\rfloor })$.

$\blacksquare$. Now we only need to consider $f(n)\pmod2$. Using the lemma, $f(0)\equiv 0\pmod2$ $f(1)\equiv 1\pmod2$. $f(2)\equiv 0\pmod2$. $f(3)\equiv 1\pmod2$. $f(4)\equiv 0\pmod2$. $f(5)\equiv 0\pmod 2$. $f(6)\equiv 0\pmod2$. $f(7)\equiv 1\pmod 2$. Claim: $f(n)\equiv 1\pmod 2\iff n+1$ is a power of $2$. Proof: We use strong induction (with base cases above). Suppose this claim is true for $0,1,2,\ldots ,n-1$. We will show that it is also true for $n$. We have $f(n)=f(n-2^0)+f(n-2^1)+f(n-2^2)+\ldots+f(n-2^{\lfloor \log_2(n)\rfloor })$. If $f(n)$ is odd, then one of $n-2^0, n-2^1, \ldots, n-2^{\lfloor \log_2(n)\rfloor }$ is (a power of $2$) minus $1$. So for some non-negative integers $x$ and $y$, $n-2^y=2^x-1\implies 2^x+2^y-1=n$. Clearly, these values $x$ and $y$ are unique (except for swapping $x$ and $y$). If $x=y$, then $f(n)$ is odd, as the only term in $f(n)$ that's even is $f(n-2^x)$. $n=2^{x+1}-1$, and so $n+1$ is a power of $2$. If $x\ne y$, then $n+1$ is not a power of $2$. But both of $f(n-2^x)$ and $f(n-2^y)$ are even, so $f(n)$ is even. This completes the induction. $\blacksquare$. Thus, the answer is the smallest (power of $2$) minus $1$ greater than $2013$, which is $\boxed{2047}$.

$f(n)=f(n-1)+f(n-2)+f(n-4)+\ldots f(n-2^k)$ $$2^k\leq n < 2^{k+1}$$Lemma:The function for numbers of the form $2 ^ k-1$ is odd. Even in all other numbers. Proof is easy by induction.

The answer is $2047$. In general, I will show that $f(n)$ is odd if and only if $n = 2^k-1$ for some positive integer $k$. The proof proceeds inductively. To begin with, if $n = 2^k-1$, then $$f(n) = f(2^k - 2) + f(2^k - 3) + f(2^k - 5) + \cdots + f(2^{k-1} - 1).$$None of these terms are odd except for the last term because none of the inside expressions are one less than a power of two. If $n \neq 2^k - 1$, for any $i, j$ such that $n - 2^i = 2^j - 1$, we also have $n - 2^j = 2^i-1$. Furthermore, $i \neq j$ by assumption, so all terms of the form $f(2^i - 1)$ in the additive expansion come in pairs. Hence $f(n)$ is even.

Suppose $f(0) \stackrel{\text{def}}{=} 1$. Then, we have that$$f(n) = \sum_{k = 0}^{k = \lfloor \log_2n \rfloor} f(n - 2^k).$$I claim that $f(n)$ is odd iff $n$ is one less than a power of two. We will prove it by strong induction on $n$. Obviously, base cases ($n = 0, 1$) are true. Suppose that the claim is true for $n = 0, 1, \cdots, k - 1$. We shall show that $f(k)$ is odd iff $k$ is one less than a power of two. Note that all the numbers $k - 2^x$ not of the form $2^y - 1$ don't matter, since $f(k - 2^x)$ is even (by induction hypothesis). Thus, only the ones that are of the form $2^y - 1$ contribute anything to the parity of $f(k)$. In particular, the parity of $f(k)$ is the same as the parity of the number of solutions $(x, y)$ to $k = 2^x + 2^y - 1$, or $k + 1 = 2^x + 2^y$. Note that if $x \ne y$, then $(x, y)$ being a solution implies that $(y, x)$ is another (different) solution. If $k + 1$ is not a power of two, there doesn't exist any solution $(x, y)$ with $x = y$, so the number of solutions is even implying that $f(k)$ is even, and conversely, if $k + 1$ is a power of two, there exists exactly one solution $(x, y)$ with $x = y$, so the number of solutions is odd implying that $f(k)$ is odd. Thus, $f(k)$ is odd iff $k$ is one less than a power of two. Thus, the answer is $2^{11} - 1 = \boxed{2047}$. solved this in like 20 minutes :clown: hence the rushed writeup

Let $a_n$ be the remainder when $f(n)$ is divided by $2$. Then manual computation yields $a_0=1$, $a_1=1$, $a_2=0$, $a_3=1$. Claim. $a_n\equiv a_{n-1}+a_{n-2}+a_{n-4}+a_{n-8}+\dots\pmod 2$. Proof. This is immediate by caseworking on the first term in the sum. Claim. $a_n=1$ if and only if $n+1$ is a power of $2$. Proof. We will do this by inducting on $k=\lceil\log_2(n+1)\rceil$. We already manually checked $k=0,1,2$ for our base cases. Now assume that $k$ works. For $k+1$, consider how $n$ would work. We know that $a_{n-2^i}=1$ if and only if $n-2^i+1$ is a power of $2$, so consider when $n-2^i+1=2^j$. Then $n=2^i+2^j-1$. But if $(i,j)$ works, $(j,i)$ also works. So if $i\ne j$, $a_n$ is always even because the $1$s are paired. If $i=j$, $n=2^{i+1}-1$, which works(everything else pairs up), completing our induction. $\blacksquare$ It remains to extract the numerical answer $\boxed{2047}$.

We can do casework on the last number in the sum to find that it can be anything from $1$ to $2^{\lfloor \log_2 (n) \rfloor}$. This means that $f(n) = f(n-1) + f(n-2) \ldots f \left(n-2^{\lfloor \log_2 (n) \rfloor} \right)$. (Let $f(0) = 1$ for these purposes) We claim that the only integers that produce odd values of $n$ are $n = 2^x - 1$ for some integer $x$. Thus our answer is $\boxed{2047}$. We prove the result by induction. Our base case of $1$ is trivial. Now for the inductive step. Let $n = 2^x + y - 1$. Where $y < 2^x$ and $x$ and $y$ are positive integers. We can see that the only way that the expansion of $n$ from our recursive formula has at most one odd integer in it of the form $f(2^z - 1)$ where $z < x$ (this is because the only possible decrease to get down to such an integer is when we decrease by $2^x$). Thus we can see that we have $y = 2^z$, and this means that $f(2^x - 1)$ is also included in the sum. This means we have $2$ odd integers which sum to an even and thus all the other integers are even. $\blacksquare$

Infinite recurrence sequence Using Dynamic Programming (from Informatics Olympiad) reasoning we can get the recurrence sequence $$f(n)=\sum_{i=0}^{\lfloor log_2 n \rfloor}f(n-2^i)$$The rest is simple We get that $f(n)$ odd only when n is of the form $2^m-1$, giving the answer 2047 Full proof here: https://infinityintegral.substack.com/p/usajmo-2013-contest-review

We claim the answer is 2047; in general, f(n) is odd iff $n=2^k-1$, which will be proved by induction, by taking mod 2; check manually that f(0)=1,f(1)=1,f(2)=0,f(3)=1 mod 2. The key is that $f(n)=f(n-1)+f(n-2)+f(n-4)+...+f(n-2^{\lfloor\log_2n\rfloor})$ by caseworking on where the extra numbers are appended. Then, it follows by induction $$n=2^k-1\implies f(2^k-1)=f(n-1)+...+f(2^k-1-2^{k-1})\equiv1\pmod 2,$$while if for some $j\ne i$ we have $n-2^i=2^j-1$ (meaning $f(n-2^i)\equiv1\pmod 2$) then it can be paired with $n-2^j=2^i-1$; in particular, each of the f(...) that are 1 mod 2 are paired up, so that f(n) overall will be 0 mod 2 since there are an even number of 1 mod 2s. Note that if i=j then indeed n is of the form $2^k-1$.

Here is my solution from about April 2021, utilizing generating functions. It is clear that the generating function for $f(n)$ is \[ F(X) := -1 + \sum_{i=0}^{\infty} \left(\sum_{j=0}^{\infty} X^{2^j}\right)^i = \frac{1}{1-(X+X^2+X^4+\cdots)} - 1. \] Claim: Over $\mathbb{F}_2[X]$, \[ F(X) = \sum_{n=1}^{\infty} X^{2^n-1}. \]Proof. It suffices to show that \[ (1+X^1+X^3+X^7+\cdots)(1 + X^1+ X^2 + X^4 + \cdots ) = 1, \]which can be checked upon expansion. Therefore, $f(n)$ is odd if and only if $n+1$ is a power of 2, and thus the answer is $2^{\lceil \log_2 2013 \rceil}-1=\boxed{2047}$.

ok, so first, we easily get that $f(x)$ is equal to the sum of all positive $f(x-2^{n})$ via recursion $f(1)=1$ is easily obtained since you can only express $1$ as $2^0$ from $f(1)=f(1-2^0)$, we get that $f(0)=1$ now, plug in the formula to obtain values for early $f(x)$ \begin{tabular}{|c|c|c|} x & f(x) & odd/even\\ \hline 0 & 1 & odd\\ 1 & 1 & odd\\ 2 & 2 & even\\ 3 & 3 & odd\\ 4 & 6 & even\\ 5 & 10 & even\\ 6 & 18 & even\\ 7 & 31 & odd\\ \end{tabular}it seems like all $f(2^a-1)$ are odd, so i will try proving that base case is true since $f(0)=1$ and $f(2)=2$ $f(2^a-1)=f(2^{a-1}-1)+\sum_{n=0}^{a-2} f(2^{a}-2^{n}-1)$ none of $2^{a}-2^{n}-1=2^{p}-1$ for some $p$ where $0<n<a-2$, so $\sum_{n=0}^{a-2} f(2^{a}-2^{n}-1)$ is even, and $f(2^a-1)$ is odd on the other hand, for $f(2^a+b)$ where $b \neq 2^a-1$ we have $f(2^a+b)=\sum_{n=0}^{a} f(2^{a}-2^{n}+b)$ note that if any of $f(2^{a}-2^{n}+b)$ are equal to $2^{p}-1$ for some $p$, there must exist exactly two $f(2^{a}-2^{n}+b)=2^{p}-1$ for some $p$ and $n$, since $2^{p}-1$ and $2^{p-1}-1$ differ by $2^{p-1}$, so all $f(2^a+b)$ where $b \neq 2^a-1$ are even. therefore, $f(x)$ is odd if and only if $x=2^a-1$ for some $a$ thus, the question statement is equivalent to finding the smallest $2^a-1>2013$, which is $a=11$ in this case thus, the answer is $2047$

Note $f(x) = \sum f(x-2^k)$. I claim that the answer is $\boxed{2047}$ and that $f(n) \equiv 1 \pmod{2}$ iff it is of the form $2^k-1, k \in \mathbb{Z}^+$. We proceed using strong induction, in particular assuming the statement is true for $n = 1, 2, \dots, k-1$ then we wish to prove the same for $n=k$. The base case is trivial. If $k$ is of the desired form, then it remains to show that $f(k)$ is odd. If $k=2^a-1$, then we want $2^a-1 - 2^b = 2^c-1 \implies 2^a = 2^b + 2^c$ for some integers $b, c$ from our recursion. But $2^a=2^b+2^c$ is only true for $b=c$, so we only have one solution for a given $a$. Therefore we only have one case in our recursion summation that contributes an odd number, hence $f(k)$ is odd. If $k$ is not of the desired form, a similar argument reduces it to solving $k+1=2^c+2^b$ for integers $b, c$. Now this time $b \neq c$ because $k$ is not of the desired form. Therefore, if $(b, c)$ satisfies this then so does $(c, b)$, hence there are an even number of terms in our summation that contribute an odd factor. The conclusion follows.

We can build the recursion \[f(n) = f(n-1) + f(n-2) + f(n-4) + \ldots,\] from which we induct to see that $f(n)$ is odd iff $n = 2^m-1$, which gives us our answer $\boxed{2047}$. $\blacksquare$

No one posting the easiest solution using bijection, so i am writing the proof here. Let's name every one that counted in the f(n) partition of n. When n is even, then every partitions have an reverse partition (Reverse of an [4,1,2,2] is [2,2,1,4]), so let's consider two cases. Case1) If our partition is not equal to it's reverse, then just pair them with one another. (Like [1,2,2,4] paired with [4,2,2,1]). Case2) If our partition is equal to it's reverse. Then it consists odd number of power of 2's or even number of power of 2's. Let's consider such partitions consisting of even number of power of 2's, then there is two median numbers one equals another. (Like [1,2,4,4,2,1]). Then we can just add them up and will gain another odd length partition.(Like [1,2,4,4,2,1] to [1,2,8,2,1]). Similarly we can show the other side which forming one to one pairing between all the partitions of even n. So when n is even f(n) is even. When is odd: Case1) If our partition is not equal to it's reverse, then just pair them to one another.(Which means we are no longer cares about these partitions) Case2) If our partition is equal to it's reverse, then it consist of odd number of power of 2's.(if it contains even number elements then let S be the sum of first half of the numbers, then since it's equal to it's reversion then sum of second half of this partition is also S, so n=2*S which is clearly a contradiction). If we consider the median of these numbers then this number should be an odd number(otherwise n must be even and contradiction). So this number must be 1. Which means when n=2k+1 then f(2k+1) and f(k) has same parity. From here we can easily prove that f(n)=1(mod2) iff n=2^m-1 for some m.