HMMT-Feb 2019 alg, Problem 4

Let $\mathbb{N}$ be the set of positive integers, and let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a function satisfying \begin{itemize} $f(1)=1$ for $n \in \mathbb{N}, f(2 n)=2 f(n)$ and $f(2 n+1)=2 f(n)-1$. \end{itemize} Determine the sum of all positive integer solutions to $f(x)=19$ that do not exceed 2019.

Solution: For $n=2^{a_{0}}+2^{a_{1}}+\cdots+2^{a_{k}}$ where $a_{0}>a_{1}>\cdots>a_{k}$, we can show that $f(n)=2^{a_{0}}-2^{a_{1}}-\cdots-2^{a_{k}}=$ $2^{a_{0}+1}-n$ by induction: the base case $f(1)=1$ clearly holds; for the inductive step, when $n$ is even\\ we note that $f(n)=2 f\left(\frac{n}{2}\right)=2\left(2^{a_{0}}-\frac{n}{2}\right)=2^{a_{0}+1}-n$ as desired, and when $n$ is odd we also have $f(n)=2 f\left(\frac{n-1}{2}\right)-1=2\left(2^{a_{0}}-\frac{n-1}{2}\right)-1=2^{a_{0}+1}-n$, again as desired. Since $19=f(n) \leq 2^{a_{0}} \leq n$, we have $a_{0} \geq 5$ and $n=2^{a_{0}+1}-19 \leq 2019$ gives $a_{0} \leq 9$. So the answer is $\sum_{a=5}^{9}\left(2^{a+1}-19\right)=\left(2^{11}-2^{6}\right)-19 \cdot 5=1889$. $\fbox{1889}$.

Answer: 1889