Problem

Source: 2019 Argentina L2 P6

Tags: combinatorics



Let $n$ be a natural number. We define $f(n)$ as the number of ways to express $n$ as a sum of powers of $2$, where the order of the terms is taken into account. For example, $f(4) = 6$, because $4$ can be written as: \begin{align*} 4;\\ 2 + 2;\\ 2 + 1 + 1;\\ 1 + 2 + 1;\\ 1 + 1 + 2;\\ 1 + 1 + 1 + 1. \end{align*}Find the smallest $n$ greater than $2019$ for which $f(n)$ is odd.