, 2013

Let $n$ be a nonnegative integer. We have
$$f(2n)^2 < f(2n)^2 + 6f(n) + 1 = f(2n+1)^2 < f(2n)^2 + 6f(2n) + 9 = (f(2n) + 3)^2.$$
Therefore,
$$f(2n) < f(2n+1) < f(2n) + 3.$$
Assume that $f(2n+1) = f(2n) + 2$. In this case
$$6f(n) + 1 = f(2n+1)^2 - f(2n)^2 = 4f(2n) + 4.$$
This is impossible since the left hand side is odd while the right hand side is even. Therefore $f(2n+1) = f(2n) + 1$.

On the other hand,
$$6f(n) + 1 = f(2n+1)^2 - f(2n)^2 = 2f(2n) + 1.$$
We deduce that $f(2n) = 3f(n)$, and $f(0) = 0$.

Now, let $n \geq 0$ and write $n = \overline{a_1 a_2 \cdots a_k}_{(2)}$ in basis 2. We prove by induction on $k$ that $f(n) = \overline{a_1 a_2 \cdots a_k}_{(3)}$ in basis 3.

For $k = 1$, we have
$$f\left(\overline{0}_{(2)}\right) = f(0) = 0 = \overline{0}_{(3)} \quad \text{and} \quad f\left(\overline{1}_{(2)}\right) = f(1) = f(0) + 1 = 1 = \overline{1}_{(3)}.$$
Assume this true for $k$. We have
$$\begin{aligned} f\left(\overline{a_1 a_2 \cdots a_k a_{k+1}}_{(2)}\right) & = f\left(2\, \overline{a_1 a_2 \cdots a_k}_{(2)} + a_{k+1}\right) \\ & = f\left(2\, \overline{a_1 a_2 \cdots a_k}_{(2)}\right) + a_{k+1} \\ & = 3 f\left(\overline{a_1 a_2 \cdots a_k}_{(2)}\right) + a_{k+1} \\ & = 3 \overline{a_1 a_2 \cdots a_k}_{(3)} + a_{k+1} \\ & = \overline{a_1 a_2 \cdots a_k a_{k+1}}_{(3)} \\ & . \end{aligned}$$
This completes the induction.

Applying this to 1000, we have
$$1000 = \overline{1101001}_{(3)} = f\left(\overline{1101001}_{(2)}\right) = f(105).$$