PROBLEM STATEMENT:
Let $ f:\mathbb N\to\mathbb N$ be a function defined by $$ f(1)=2, \ f(2)=1, \ \ f(3n)=3f(n), \ f(3n+1)=3f(n)+2, \ f(3n+2)=3f(n)+1 $$
Find the number of $n≤2001$ for which $f(n)=2n$.
MY PROGRESS:
I could easily figure out that the answer is $2^7 - 1=127$.
Evaluating $f(n)$ for small values of $n$, I found an interesting pattern:
First write the natural number $n$ in base 3 representation. Then to obtain $f(n)$, replace 2 by 1 and 1 by 2 in the base 3 representation obtained earlier. Finally convert the base 3 string in decimal system to get $f(n)$.
Examples:
$f(5)=8 : (5)_{10}= (12)_{3} \Rightarrow f(5)= (21)_{3} = (8)_{10} $
$f(11)=19 : (11)_{10}= (102)_{3} \Rightarrow f(11)=(201)_{3} = (19)_{10}$
Now, to prove the claim I am using induction. Inspired from one of the problem of the similar kind, I decided to use induction on $m$, the number of digits of $n$ in base 3 representation.
Suppose the result is true for every natural number $n$ such that the number of digits in the base 3 representation of $n$ is less than or equal to $m$. Now take any natural number $n$ whose base 3 representation consists of $m+1$ digits.
I am stuck here. How should I proceed?
Thanks.
All the numbers used below are base 3. Also, if $k=1021$ and $m=1221$, $\overline{km}=10211221$.
We are given:
$$f(\overline{k0})=\overline{f(k)0}$$ $$f(\overline{k1})=\overline{f(k)2}$$ $$f(\overline{k2})=\overline{f(k)1}$$
Now, in order to find $f(n)$, we use these equations on $n$ from right to left.
For example, $n=1021$:
$$f(1021)=\overline{f(102)2}=\overline{f(10)12}=\overline{f(1)012}=2012$$