Maximum of a function from integers to integers

Question

Suppose $f$ is a function form positive integers to positive integers satisfying $f(1)=1$, $f(2n)=f(n)$, and $f(2n+1)=f(2n)+1$ for all positive integers $n$.

Job:
Find the maximum of $f(n)$ when $n$ is greater than or equal to $1$ and less than or equal to $1994$.

Any ideas?

Answer 1

$f(1)=1,f(3)=2,f(7)=3,f(15)=4,...$ The sequence $1,3,7,15,...$ has closed form $$a_n=2^n-1$$ so we need $$2^n-1\le 1994\implies n\le {\ln{1995}\over \ln 2}\approx 10.96$$ Therefore we choose $n=10$ so that $$a_n=2^{10}-1=1024-1=1023$$ and $f(1023)=n=10$ is the maximum.

EDIT: For added rigor, we can use induction. I claim that the first occurrence of $n$ in the sequence is at $2^n-1$. Clearly the first occurrence of $1$ of is at $2^1-1=1$ so the base case checks. Assuming it holds for $n$, the first occurrence of $n+1$ will be at one more than its double, or $$2(2^n-1)+1=2^{n-1}-1$$ completing the proof.

Answer 2

Hint: The function relates nicely to the base two representation of $n$.

Anyway, we truncate all the zeroes at the end so it is optimal to have as much $1's$ as possible.