$f(n+1)-f(n)=2^{f(n)}$ we have these $f(2)-f(1)=2^{f(1)}$ $f(3)-f(2)=2^{f(2)}$ ....... $f(n)-f(n-1)=2^{f(n-1)}$ then we have that $f(n)=2^{f(1)}+2^{f(2)}+...+2^{f(n-1)}+1$ $f(1)$ is odd, => $f(n)$ is odd for every natural $n$=> $2^{f(n)}$ leave $2$ remainder when divided by $3$ for every $n \in N$ Assume that $f(a)-f(b)$ divisible by $3^{2013}$ for $b<a<3^{2013}$ $f(a)-f(b)=2^{f(b)}+2^{f(b+1)}+...+2^{f(a-1)}$ leave $2(a-b)$ remainder when divided by $3^{2013}$, because $f(a)$ is not equal to $f(b)$ for $a$ is not equal to $b$ $2$ is not divisible by $3$ => $a-b$ divisible by $3^{2013}$ but $a-b<3^{2013}$ => contradiction => we have proved problem!

I do not understand ISHO95's solution at all. Here is a solution which I believe is correct. First, note that $\text{ord}_{3^n}(2) = 2 \cdot 3^{n-1}$. As $f(1)$ is odd, we know that for all $n$ $f(n)$ is odd, therefore knowing $f(n)$ modulo $3^{m-1}$ is sufficient to determine $f(n+1)$ modulo $3^m$. Denote $f(0) = 0$ for convenience (note the recursion still works from $0$ to $1$). Now, I claim that for a nonnegative integer $m$, we have for all nonnegative integers $n$ that $f(n+3^m) \equiv f(n) + 2 \cdot 3^{m} \pmod{3^{m+1}}$ and furthermore that $f(3^m) \equiv 2 \cdot 3^m \pmod{3^{m+1}}$. We prove this by induction on $m$. Its trivially true for $m=0$. Now assume it holds for all $n$ when $m \le M$. We prove it works for $m = M+1$. First remark that $f(n + 3^{M+1}) \equiv f(n) + 3 \cdot 2 \cdot 3^M \equiv f(n) \pmod{3^{M+1}}$ so we have $3^{M+1}|(f(n + 3^{M+1}) - f(n))$. In particular we have $3^{M+1}|f(3^{M+1})$. Now, remark that: \begin{eqnarray*} f(n + 1 + 3^{M+1}) - f(n+1) & \equiv & f(n + 3^{M+1}) + 2^{f(n + 3^{M+1})} - f(n) - 2^{f(n)} \\ & \equiv & f(n + 3^{M+1}) - f(n) \pmod{3^{M+2}} \end{eqnarray*} utilizing the fact that $f(n + 3^{M+1}) \equiv {f(n) \pmod{3^{M+1}}}$ so $2$ to those respective values are congruent modulo $3^{M+2}$ as they are both odd. Thus it follows by induction on $n$ that $f(n + 3^{M+1}) - f(n) \pmod{3^{M+2}}$ is the same across all values of $n$. Now we have: \[f(3^{M+1}) - f(2 \cdot 3^M) \equiv f(2 \cdot 3^M) - f(3^M) \equiv f(3^M) \pmod{3^{M+2}}\] Therefore we have $f(2 \cdot 3^M) \equiv 2 f(3^M) \pmod{3^{M+2}}$, so $f(3^{M+1}) \equiv 3 f(3^M) \equiv 2 \cdot 3^{M+1} \pmod{3^{M+2}}$. Therefore as $f(3^{M+1}) - f(0) \equiv 2 \cdot 3^{M+1} \pmod{3^{M+2}}$ our induction is complete. Now we apply induction on $m$ to show that $f(1), f(2), ..., f(3^m)$ form a complete residue system modulo $m$. It is obviously true for $m=0$. Now suppose it is true for all $m \le M$ and we wish to show it for $M+1$. Consider an arbitrary number $k$ modulo $3^{M+1}$. By the inductive hypothesis we have for some integer $1 \le n \le 3^M$ that $k \equiv f(n) \pmod{3^M}$. Now write $k \equiv f(n) + z \cdot 3^M \pmod{3^{M+1}}$. Then we have $f(n + 2z 3^M) \equiv k \pmod{3^{M+1}}$, and then reduce $n + 2z 3^M$ modulo $3^{M+1}$ to get something in $f(1), f(2), ..., f(3^{M+1})$. Thus they form a complete residue system as every number $k$ is congruent to one of the values modulo $3^{M+1}$, completing our induction. As them being a complete residue system implies they are distinct, the problem follows by setting $m = 2013$ so we are done. Overall this is a pretty simple problem, the observation that $f(n)$ modulo $3^m$ gives you $f(n)$ modulo $3^{m+1}$ is the only thing you need to see and from then on its just details.

I know my solution is incredibly similar to dinoboy's and his is a lot more concise however I would like to share mine: Define $f(x)$ to be such that $f(1)=1$ and $f(x+1)=2^{f(x)}+f(x)$. Define a function $f_{n}(x)$ such that $0\le f_{n}(x)\le 3^n-1$ and $f_{n}(x)\equiv f(x)\pmod{3^n}$. Next, define $g_{n}(x)$ such that $0\le g_{n}(x)\le \phi(3^n)-1$ and $g_{n}(x)\equiv f(x)\pmod{\phi(3^n)}$. We re-write the problem statement as if $x,y\in \{1, 2, \cdots, 3^n\}$ we have $f_{n}(x)=f_{n}(y)\iff x=y$ (i.e. $f_{n}(x)$ is distinct). A few nice properties of these: By Chinese remainder theorem we have $f_{n-1}(x)\equiv f_{n}(x)\equiv g_{n}(x)\pmod{3^{n-1}}$. By Euler's totient we have $f_{n}(x)\equiv 2^{g_n(x-1)}+f_{n}(x-1)\pmod{3^n}$. From (1) and (2) along with Chinese Remainder Theorem we have $g_{n}(x)\equiv 2^{g_n(x-1)}+g_{n}(x-1)\pmod{\phi(3^n)}$ What we are attempting to prove: The problem statement holds for $n=k$ and we have $f_{k}(x)=f_{k}(x+3^km)$ where $m$ is a positive integer. We use induction. Base case: We have $f_{1}(1)=1, f_{1}(2)=0, f_{1}(3)=2$ therefore the problem statement holds for $k=1$. Notice that $g_{1}(x)=1$ therefore $f_{1}(x)\equiv 2+f_{n}(x-1)\pmod{3}$ from proposition (2). Therefore it is clear that $f_{1}(x)=f_{1}(x+3m)$. Induction hypothesis: The problem statement holds for $n=k$ and we have $f_{k}(x)=f_{k}(x+3^km)$ where $m$ is a positive integer. We now must prove the problem statement holds for $n=k+1$ and we have $f_{k+1}(x)=f_{k+1}(x+3^{k+1}m)$. From (1) we have $g_{k+1}(x)\equiv f_{k}(x)\pmod{3^{k}}$. Therefore we have $g_{k+1}(x)$ is distinct mod $3^k$ when $x\in \{1,2,\cdots, 3^k\}$. We also have that $g_{k+1}(x)=g_{k+1}(x+3^km)$. This means that we can separate $g_{k+1}(x)$ into three "groups" that have length $3^k$ and are ordered $g_{k+1}(1), g_{k+1}(2), \cdots, g_{k+1}(3^k)$. This is incredibly useful. (At this point I know all the notation must be incredibly confusing to the reader, so hence I personally have a table made for $g_{2}(x)$ and $f_{2}(x)$ lining up the terms. When you do this out the notation makes a lot more sense, trust me.) Because $f_{k}(x)\equiv g_{k+1}(x)\equiv f_{k+1}(x)\pmod{3^k}$ we can separate $f_{k+1}(x)$ into three groups all of whose elements correspond to $f_{k}(x)$. It is also evident that $f_{k+1}(x)=f_{k+1}(x+3^k)=f_{k+1}(x+2\cdot 3^k)\pmod{3^k}$. Out of these three groups we must now prove the following: $f_{k+1}(x)=f_{k+1}(x+3^{k+1}m)$ where $m$ is a positive integer. $f_{k+1}(x)\neq f_{k+1}(x+3^k)\neq f_{k+1}(x+2\cdot 3^k)\pmod{3^{k+1}}$. Both of these two statements boil down to (2). We notice that we have \begin{align*} f_{k+1}(x+3^k)\equiv 2^{g_{k+1}\left(x+3^k-1\right)}+f_{k+1}\left(x+3^k-1\right)\pmod{3^{k+1}} \\ \implies f_{k+1}(x+3^k)\equiv 2^{g_{k+1}\left(x+3^k-1\right)}+2^{g_{k+1}\left(x+3^k-2\right)}+\cdots+2^{g_{k+1}\left(x\right)}+f_{k+1}(x)\pmod{3^{k+1}} \end{align*} We now notice that $g_{k+1}\left(y\right)$ takes on all of the odd integers from $1$ to $\phi\left(3^{k+1}\right)-1$. This is exactly the number of elements we have above henceforth it happens that \begin{align*} f_{k+1}(x+3^k)\equiv 2^1+2^3+\cdots+2^{\phi\left(3^{k+1}\right)-1}+f_{k+1}(x)\pmod{3^{k+1}} \\ f_{k+1}(x+3^k)\equiv \left(2\right)\left(\frac{2^{\phi(3^{k+1})}-1}{3}\right)+f_{k+1}(x) \pmod{3^{k+1}}.\end{align*} Notice that \[v_3(2^{\phi(3^{k+1})}-1)=v_3(4^{3^k}-1)=k+1\]via lifting the exponent. Therefore $v_3\left(\frac{2^{\phi(3^{k+1})}-1}{3}\right)=k$ henceforth $f_{k+1}(x+3^k)\equiv f_{k+1}(x)\pmod{3^k}$ but $f_{k+1}(x+3^k)\neq f_{k+1}(x)\pmod{3^{k+1}}$. We write $f_{k+1}(x+3^k)-f_{k+1}(x)=z3^k$ where $\gcd(z,3)=1$. Notice that substituting $x=n3^k+x_1$ we arrive at \[f_{k+1}(x_1+(n+1)\cdot 3^k)-f_{k+1}(x_1+n3^k)=z3^k\]from which we can derive \[f_{k+1}\left(x+a\cdot 3^k\right)-f_{k+1}\left(x+b\cdot 3^k\right)\equiv (a-b)3^k\pmod{3^{k+1}}\] Now, notice that $f_{k+1}(x+3^k)-f_{k+1}(x)=z3^k, f_{k+1}(x+2\cdot 3^k)-f_{k+1}(x+3^k)=z3^k$ and $f_{k+1}(x+2\cdot 3^k)-f_{k+1}(x)=2z3^k$ therefore the first part of our list of necessary conditions is taken care of. Now, notice that substituting $a=3m, b=0$ into the second equation we arrive at the second condition. Our induction is henceforth complete. Because the problem statement holds for all $n$ it also holds for $2013$ and we are done.

Someone still solving that problems?

dinoboy wrote: ... furthermore that $f(3^m) \equiv 2 \cdot 3^m \pmod{3^{m+1}}$. We prove this by induction on $m$. Since $f(3)=11\equiv 2 \pmod{9}$ this claim is not true. dinoboy wrote: Overall this is a pretty simple problem, the observation that $f(n)$ modulo $3^m$ gives you $f(n)$ modulo $3^{m+1}$ is the only thing you need to see and from then on its just details. This is also not true since $f(3) \equiv 2 \pmod{9}$ but $f(3)\equiv 11 \pmod{27}$. Here is my solution. We will use induction on $k$ to prove that $\{f(1), \ldots, f(3^k)\}$ give distinct residues modulo $3^k$ and $f(3^k+i)\equiv f(i) \pmod{3^k}$ for all $i\geq 0$. In other words $f(n) \pmod{3^k}$ is periodic with minimum period $3^k$. It can be easily checked for small values of $k$. Suppose it is true for $k$. Claim: $f(a+1)\equiv f(b+1) \pmod{3^{k+1}}$ if and only if $f(a)\equiv f(b) \pmod{3^{k+1}}$ . Proof: If $f(a+1)\equiv f(b+1) \pmod{3^{k+1}}$ , then obviously $f(a+1)\equiv f(b+1) \pmod{3^{k}}$. By induction hypothesis we get $f(a)\equiv f(b) \pmod{3^{k}}$. Since all $f(n)$s are odd this gives $f(a)\equiv f(b) \pmod{2\cdot 3^{k}}$. Therefore $2^{f(a)}\equiv 2^{f(b)} \pmod{3^{k+1}}$. Hence $$f(a)=f(a+1)-2^{f(a)}\equiv f(b+1)-2^{f(b)}\equiv f(b) \pmod{3^{k+1}}$$Conversely, if $f(a)\equiv f(b) \pmod{3^{k+1}}$, then $f(a)\equiv f(b) \pmod{3^{k}}$ which gives $f(a)\equiv f(b) \pmod{2\cdot 3^{k}}$. Hence $2^{f(a)}\equiv 2^{f(b)} \pmod{3^{k+1}}$ and $$f(a+1)=2^{f(a)}+f(a)\equiv 2^{f(b)}+f(b)\equiv f(b+1) \pmod{3^{k+1}}$$ From above claim $f(n) \pmod{3^{k+1}}$ is periodic and minimum period is an integer $n_0$ such that $f(n_0+1)\equiv f(1) \pmod{3^{k+1}}$. Since $n_0$ is also a period of $f(n) \pmod{3^{k}}$ by induction hypothesis $3^k\mid n_0$. Hence $n_0=\alpha \cdot 3^k$ for some $\alpha \in \{1, 2, 3\}$. So all we need is to prove that $\alpha=3$. By induction hypothesis we know that $f(1), \ldots, f(n_0)$ give each residue modulo $3^k$ exactly $\alpha$ times. Since $f(n)$s are odd we deduce that these numbers give each odd residue modulo $2\cdot 3^k$ exactly $\alpha$ times. Hence \begin{align*} f(n_0+1)&=1+2^{f(1)}+2^{f(2)}+\cdots+2^{f(n_0)}\\ &\equiv 1+\alpha\left(2^1+2^3+\cdots+2^{2\cdot 3^k-1}\right) \tag{mod $3^{k+1}$}\\ &\equiv 1+\frac{2\alpha(2^{2\cdot 3^k}-1)}{3} \tag{mod $3^{k+1}$}\ \end{align*}Since $2$ is a primitive root modulo $3^{m}$ for all $m$ the numerator of the last fraction is divisible by $3^{k+1}$ but not $3^{k+2}$. Thus $f(n_0+1)\equiv 1 \pmod{3^{k+1}}$ if and only if $\alpha=3$.

I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$. The base case $k=1$ is easily checked ($f$ is always odd, hence $f$ cycles $1$, $0$, $2$ mod $3$). For the inductive step, assume it's true up to $k$. Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$, and $f$ is always odd, it follows that \begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}Hence \[ f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1} \]noting that $C$ does not depend on $n$. Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$, $f(n+3^k)$, $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$, and the inductive hypothesis now solves the problem.

I think this is pretty similar to above solutions (at least v_Enhance's), but I want to practice proof-writing.

v_Enhance wrote: I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$. The base case $k=1$ is easily checked ($f$ is always odd, hence $f$ cycles $1$, $0$, $2$ mod $3$). For the inductive step, assume it's true up to $k$. Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$, and $f$ is always odd, it follows that \begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}Hence \[ f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1} \]noting that $C$ does not depend on $n$. Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$, $f(n+3^k)$, $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$, and the inductive hypothesis now solves the problem. Can you explain please what did you assume by induction and i couldn't understand the steps which lead to find C

....................

v_Enhance wrote: I'll prove by induction on $k \ge 1$ that any $3^k$ consecutive values of $f$ produce distinct residues modulo $3^k$. The base case $k=1$ is easily checked ($f$ is always odd, hence $f$ cycles $1$, $0$, $2$ mod $3$). For the inductive step, assume it's true up to $k$. Since $2^\ast \pmod{3^{k+1}}$ cycles every $2 \cdot 3^k$, and $f$ is always odd, it follows that \begin{align*} f(n+3^k) - f(n) &= 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)} \pmod{3^{k+1}} \\ &\equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} \pmod{3^{k+1}} \\ &= 2 \cdot \frac{4^{3^k}-1}{4-1}. \end{align*}Hence \[ f(n+3^k)-f(n) \equiv C \pmod{3^{k+1}} \qquad\text{where} \qquad C = 2 \cdot \frac{4^{3^k}-1}{4-1} \]noting that $C$ does not depend on $n$. Exponent lifting gives $\nu_3(C) = k$ hence $f(n)$, $f(n+3^k)$, $f(n+2\cdot3^k)$ differ mod $3^{k+1}$ for all $n$, and the inductive hypothesis now solves the problem. please can you explain the part where you found C??

We will prove by induction that $$f(1),f(2), \dots , f(3^n)$$leave distinct remainders modulo $3^n$. Base case: $n=1$. Clearly $1,3,11 \mod 3$ is a complete residue class modulo $3$. Induction hypothesis: Assume it holds for $n=k$ Now we will prove it for $k+1$. Notice that $\phi (3^{k+1}) =2 \cdot 3^k$. So $\text{ord}_2(3^{k+1}) \mid 2 \cdot 3^k$. If $f(a) \equiv f(b) \mod 3^k$ then $f(a) \equiv f(b) \mod 2 \cdot 3^k$, since $f(n)$ is odd for all $n$. Hence $2^{f(a)} \equiv 2^{f(b)} \mod 3^{k+1}$. By the induction hypothesis, $f(1), f(2), \dots , f(3^k)$ is a complete residue system modulo $3^k$. Then $f(3^{k}+1) \equiv f(c) \mod 3^k \Longrightarrow 2^{f(3^k +1)} \equiv 2^{f(c)} \mod 3^{k+1}$, where $c \leq 3^k$. As a result $f(3^k +2) -f(3^k +1) \equiv f(c+1) -f(c) \mod 3^{k+1}$. Hence $f(3^k +2 ) \equiv f(c+1) \mod 3^k$. So $f(3^k +3) -f(3^k+2) = f(c+2)-f(c+1)$. Continuing in this way, $f(3^k+s) - f(3^k+1) \equiv f(c+s-1) -f(c) \mod 3^{k+1}$. Now, using the fact that $f$ is always odd, and the IH we have $$f(3^k+1) =1+ \sum_{i=1}^{3^k} 2^{f(i)} \equiv 2+2^3 +2^5 +\dots +2^{2 \cdot 3^k -1} \equiv 2 \cdot \frac{2^{2 \cdot 3^k }-1}{3} +1 \mod 3^{k+1}$$But $v_3 (2^{2 \cdot 3^k }-1) =k+1 \Longrightarrow f(3^k + 1) \equiv 1 \mod 3^k$, but $f(3^k+1) \not \equiv 1 \mod 3^{k+1}$ Hence $f$ is periodic modulo $3^k$. But $f(3^k) \not \equiv f(1) \mod 3^{k+1}$. Clearly, this gives $f(1), f(2), \dots f(2 \cdot 3^k)$ are all distinct modulo $3^{k+1}$. Moreover, $f(2 \cdot 3^k +1)- f(3^k +1) \equiv f(3^k +1)-f(1) \equiv \lambda 3^k \Longrightarrow f(2 \cdot 3^k+1) \equiv 2 \lambda 3^k +1$ where $ \lambda \in \{1,2 \}$ But $2 \lambda \not \equiv \lambda \mod 3$. So $f(2 \cdot 3^k+1)$ is distinct from all previous values. Then using periodicity again, we are done.

Sorry this is a little bit rough I will try to make it more clear later.

We'll show that $f(1),f(2),\ldots,f(3^n)$ leave distinct remainders mod $3^n$ for all $n$. We proceed by induction on $n$. The base case is $n=1$, and we see that $f(1)=1$, $f(2)=3$, and $f(3)=11$, which are all distinct mod $3$. Now suppose $f(1),\ldots,f(3^n)$ are all distinct mod $3^n$. We'll show that $f(1),\ldots,f(3^{n+1})$ are all distinct mod $3^{n+1}$. Note that since $f(x)$ is always odd, we have by CRT that \[\{f(1),\ldots,f(3^n)\} \equiv \{1,3,5,\ldots,2\cdot 3^n-1\}\pmod{2\cdot 3^n}.\]Thus, \[f(3^n+1)\equiv f(1)+2^1+2^3+\cdots+2^{2\cdot 3^n-1}\pmod{3^{n+1}}\]by Euler's theorem. We compute \[D:=2^1+2^3+\cdots+2^{2\cdot 3^n-1}=2\frac{4^{3^n}-1}{3}.\]By LTE, we have $\nu_3(D)=n$, so $D\equiv \pm 3^n\pmod{3^{n+1}}$. But this means that $f(2),\ldots,f(3^n+1)$ are all distinct mod $3^n$ since $f(1)\equiv f(3^n+1)\pmod{3^n}$, so by the same argument, we get that $f(3^n+2)\equiv f(2)+D\pmod{3^{n+1}}$. Continuing in the same way, we get that $f(3^n+k)\equiv f(k)+D\pmod{3^{n+1}}$. Thus, \[\{f(1),\ldots,f(3^{n+1})\}\equiv\{f(1),f(1)+3^n,f(1)+2\cdot 3^n\}\cup\cdots\cup\{f(3^n),f(3^n)+3^n,f(3^n)+2\cdot 3^n\}\pmod{3^{n+1}}.\]It's clear then that this covers all residue classes mod $3^{n+1}$, since every induced residue class mod $3^n$ is one of the $3^n$ three element sets, and within each one, we cover all residues mod $3^{n+1}$ in that induced residue class mod $3^n$, so the induction is complete. $\blacksquare$

My solution is somewhat similar to that of ISHO95. First,looking carefully at the functional equation reveals a telescopic cancellation. \[f(n)-f(n-1)=2^{f(n-1)}\].......... and so on till: \[f(2)-f(1)= 2^{f(1)}\]. Adding all these equations, we get : \[f(n)=\sum_{i=1}^{n-1}2^{f(i)}+1.\]Clearly f(n) is odd for all n. Suppose,f(m) and f(t) leave the same remainders when divided by $3^{2013}$ leave the same remainder. Then, \[f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\]must be divisible by $3^{2013}$ and also since f(n) is always odd for any n : \[\Rightarrow f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\equiv 2(m-t)(mod 3^{2013})\]But this is not True since 3 does not divide 2 and m-t<2013 and this is a contradiction.So, we have proved the required result and we are done.

andersarnold123 wrote: \[\Rightarrow f(m)-f(t)= \sum_{i=f(t)}^{f(m-1)}2^{f(i)}\equiv 2(a-b)(mod 3^{2013})\]But this is not True since 3 does not divide 2 and a-b<2013 and this is a contradiction.So, we have proved the required result and we are done. This step is not clear at all. Where is the contradiction?

Thanks for your correction.The solution remains correct.

It is just a typo error.I have edited my post now..

Where did you get $2(m-t)$ from? That's the part I don't understand.

Nice problem! Let $f_n(x)$ be the remainder when $f(x)$ is divided by $3^n$, and let $g_n(x)$ be the remainder when $f(x)$ is divided by $\phi(3^n)$. Observe that that by Euler's totient function, $f_n(x)\equiv f_n(x-1)+2^{f_n(x-1)}\equiv f_n(x-1)+2^{g_n(x-1)} \pmod{3^n}$, and we also see that $f_{n-1}(x)\equiv f_n(x)\equiv g_n(x) \pmod{3^{n-1}}$. Note that $g_n(x)\equiv f_n(x)\equiv f_n(x-1)+2^{g_n(x-1)}\equiv g_n(x-1)+2^{g_n(x-1)} \pmod{3^{n-1}}$, and $g_n(x)$ is always odd so $g_n(x)\equiv g_n(x-1)+2^{g_n(x-1)}\pmod{2}$, so by CRT, $g_n(x)\equiv g_n(x-1)+2^{g_n(x-1)} \pmod{\phi(3^n)}$. We will prove that for all integers $n$, $f_n(x)$ has a period of $3^n$, and $f_n(x)\equiv f_n(y)\pmod{3^n}$ iff $x\equiv y\pmod{3^n}$, and then the problem statement would directly follow. This can be proven through induction. Base case: When $n=1$, $f(1)=1\equiv 1\pmod{3}$, $f(2)=3\equiv 0\pmod{3}$, and $f(3)=11\equiv 2\pmod{3}$, so $f_1(1)$, $f_1(2)$, and $f_1(3)$ are distinct mod 3. We also see that $g_1(x)=1$ for all $x$, meaning that $f_1(x)$ has a period of 3. This proves the base case. Inductive step: Suppose that the claim holds for $n-1$, and we will now prove that it holds for $n$ as well. Note that $f_{n-1}(x)\equiv g_n(x)\pmod{3^{n-1}}$, and because the claim holds for $n-1$, $f_{n-1}(x)=f_{n-1}(x+3^{n-1})$, so $g_n(x)\equiv g_n(x+3^{n-1})\pmod{3^{n-1}}$. We know that $g_n(x)$ is always odd, so $g_n(x)\equiv g_n(x+3^{n-1})\pmod{2}$, and by CRT $g_n(x)$ has a period of $3^{n-1}$. We also know that $f_{n-1}(x)$ has a period of $3^{n-1}$, meaning that $f_n(x)\equiv f_n(x+3^{n-1})\pmod{3^{n-1}}$ for all $x$. Also, by previous assumption, $f_{n-1}(x)\equiv f_{n-1}(y)\pmod{3^{n-1}}$ iff $x\equiv y\pmod{3^{n-1}}$, meaning that $f_n(x)\equiv f_n(y)\pmod{3^n}$ only if (but not necessarily if) $x\equiv y\pmod{3^{n-1}}$. This means that in order to prove our claim, it suffices to prove that $f_n(x+3^n)=f_n(x)$ and $f_n(x)\ne f_n(x+3^{n-1}m)$ for $m\in \{1, 2\}$. Lemma: $\nu_3(2^1+2^3+2^5+...+2^{\phi(3^n)-1})=n-1$ for all positive integers $n$. Proof: Note that by the geometric series sum formula, $2^1+2^3+2^5+...+2^{\phi(3^n)-1}=\frac{2(1-4^{3^{n-1}})}{1-4}=\frac{2(2^{\phi(3^n)}-1)}{3}$, meaning that it suffices to prove that $\nu_3(2^{\phi{3^n}}-1)=n$. Note that $2^{\phi{3^n}}-1=2^{2\cdot 3^{n-1}}-1=(2^{3^{n-1}}+1)(2^{3^{n-1}}-1)$, and because $2^{3^{n-1}}-1\equiv -1-1\equiv 1\pmod{3}$, it suffices to prove that $\nu_3(2^{3^{n-1}}+1)=n$ for all valid $n$. This can be proved through induction. Base case: For $n=1$, $\nu_3(2^1+1)=\nu_3(3)=1$, and for $n=2$, $\nu_3(2^3+1)=\nu_3(9)=2$, completing the base case. Inductive step: Suppose that $n$ works. Then, through sum of cubes, $2^{3^n}+1$ can be factored as $(2^{3^{n-1}}+1)(2^{2\cdot 3^{n-1}}-2^{3^{n-1}}+1)$, Note that by previous assumption, $\nu_3(2^{3^{n-1}}+1)=n$, and because $n\ge 2$, $2^{2\cdot 3^{n-1}}-2^{3^{n-1}}+1\equiv (-1)^2-(-1)+1\equiv 1+1+1\equiv 3\pmod{9}$, meaning that $\nu_3(2^{2\cdot 3^{n-1}}-2^{3^{n-1}}+1)=1$. This means that $\nu_3(2^{3^n}+1)=n+1$, thus completing the inductive step. End lemma. Now, note that because $f_{n-1}(x)\equiv g_n(x)\pmod{3^{n-1}}$ and $f_{n-1}(1), f_{n-1}(2)... ,f_{n-1}(3^{n-1})$ are distinct modulo $3^{n-1}$, it follows that $g_n(1)$, $g_n(2)... g_n(3^{n-1})$ are also distinct modulo $3^{n-1}$. Since $g_n(x)$ is always odd, we now have that $(g_n(1), g_n(2)... g_n(3^{n-1})$ is some permutation of $(1, 3, 5... 3^{\phi(n)}-1)$. Combining this with the fact that $g_n(x)$ has period $3^{n-1}$ yields that for any $x$, $(g_n(x), g_n(x+1), g_n(x+2)... g_n(x+3^{n-1}-1))$ is some permutation of $(1, 3, 5... 3^{\phi(n)}-1)$. This means that $f_n(x+3^{n-1})\equiv f_n(x)+2^{g_n(x)}+2^{g_n(x+1)}+...+2^{g_n(x+3^{n-1}-1)}\equiv f_n(x)+2^1+2^3+2^5+...+2^{\phi(3^n)-1}$. By our lemma, $2^1+2^3+2^5+...+2^{\phi(3^n)-1}\not\equiv 0\pmod{3^n}$, so $f_n(x+3^{n-1})\not\equiv f_n(x)\pmod{3^n}$. This means that $f_n(x+3^{n-1})\ne f_n(x)$. Similarly, $f_n(x+2\cdot 3^{n-1})\equiv f_n(x)+2(2^1+2^3+2^5+...+2^{\phi(3^n)-1})\not\equiv f_n(x)\pmod{3^n}$. This means that $f_n(x+2\cdot 3^{n-1})\ne f_n(x)$. Also by our lemma, $\nu_3(3(2^1+2^3+2^5+...+2^{\phi(3^n)-1}))=n$, meaning that $3(2^1+2^3+2^5+...+2^{\phi(3^n)-1})\equiv 0\pmod{3^n}$, so $f_n(x+3^n)=f_n(x+3\cdot 3^{n-1})\equiv f_n(x)+3(2^1+2^3+2^5+...+2^{\phi(3^n)-1})\equiv f_n(x)\pmod{3^n}$. This means that $f_n(x+3^n)=f_n(x)$. Hence, we have proven the inductive step, and we are now done. $\blacksquare$

First, since $f(n)$ is clearly odd for all positive integers $n$, given the remainder when $f(n)$ is divided by $3^a$ for some $a$ we can uniquely determine the remainder when $f(n)$ is divided by $2\cdot 3^a$ and hence the remainder when $2^{f(n)}$ is divided by $3^{a+1}$. We will induct to simultaneously prove $3$ claims for all positive integers $k$: Claim 1: $f(1),f(2),\dots,f(3^k)$ take all $3^k$ residues mod $3^k$. Claim 2: $f(3^k+1)\equiv 1\pmod{3^k}$. Claim 3: $f(3^k+1)\not\equiv 1\pmod{3^{k+1}}$. The base case $k=1$ is immediate by computing $f(2) = 3$, $f(3) = 11$, and $f(4) = 2059$. For the induction step, suppose the $3$ claims are true for some positive integer $k\ge 1$. Let $f(3^k+1)\equiv r\cdot 3^k + 1\pmod{3^{k+1}}$ for $r\in\{1,2\}$. Claim: For all $1\le t\le 3^k$ we have $f(3^k + t)\equiv f(t) + r\cdot 3^k\pmod{3^{k+1}}$. Proof: We induct on $t$. The base case of $t = 1$ is obvious. Then if the claim holds for some $t\ge 1$ we have $f(3^k + t + 1) = f(3^k + t) + 2^{f(3^k + t)}\equiv f(3^k + t) + 2^{f(t)}\equiv r\cdot 3^k + f(t) + 2^{f(t)}\equiv r\cdot 3^k + f(t+1)\pmod{3^{k+1}}$ and the claim is proved. Then $f(2\cdot 3^k + 1) = f(2\cdot 3^k) + 2^{f(2\cdot 3^k)}\equiv r\cdot 3^k + f(3^k) + 2^{f(3^k)}\equiv r\cdot 3^k + f(3^k + 1)\equiv 2r\cdot 3^k + f(1)$ and by a similar induction we have $f(2\cdot 3^k + t)\equiv f(t) + 2r\cdot 3^k\pmod{3^{k+1}}$ for all $1\le t\le 3^k$. This is enough to prove claim $1$ for $k+1$. But now we have $f(3^{k+1} + 1) = f(3^{k+1}) + 2^{f(3^{k+1})} = f(3^{k+1} - 1) + 2^{f(3^{k+1} - 1)} + 2^{f(3^{k+1})} = \dots = f(1) + 2^{f(1)} + 2^{f(2)} + \dots + 2^{f(3^{k+1})}$ $\equiv 1 + 2^1 + 2^3 + \dots + 2^{2\cdot 3^{k+1} - 1}\equiv 1 + 2\cdot \frac{4^{3^{k+1}} - 1}{4-1}\pmod{3^{k+2}}$ which proves both claims $2$ and $3$ for $k+1$ by LTE.

We claim by induction on $k$ that $f(\ell),f(\ell+1),\dots,f(\ell+3^k-1)$ are distinct modulo $3^k$ for all $\ell,k\in\mathbb{N}.$ Notice $f(n)$ is always odd, so $f(n+1)\equiv f(n)-1\pmod{3}.$ Hence, our claim holds for the base case $k=1.$ For our inductive step, assume $k$ works. Note \begin{align*}f(n)&=f(n-1)+2^{f(n-1)}\\&=f(n-2)+2^{f(n-1)}+2^{f(n-2)}\\&\dots\\&=1+2^{f(1)}+\dots+2^{f(n-1)}.\end{align*}Since $\varphi(3^{k+1})=2\cdot3^k,$ $f(n)$ are all odd, and by the inductive hypothesis $f(a),f(a+1),\dots,f(a+3^k-1)$ are distinct modulo $3^k,$ we have that $\{f(a),\dots,f(a+3^k-1)\}\equiv\{1,3,\dots,2\cdot 3^k-1\}\pmod{2\cdot 3^k}$ and so so \begin{align*}f(a+3^k)-f(a)&\equiv 2^{f(a)}+2^{f(a+1)}+\dots+2^{f(a+3^k-1)}\\&\equiv 2^1+2^3+\dots+2^{2\cdot 3^k-1}\\&\equiv \frac{2(4^{3^k}-1)}{4-1}.\pmod{3^{k+1}}\end{align*}By LTE, we know this is equal to $m_1\cdot 3^k\pmod{3^{k+1}},$ where $3\nmid m_1.$ Similarly, we can show that $f(a),f(a+3^k),f(a+2\cdot 3^k)$ are congruent modulo $3^k$ but pairwise distinct modulo $3^{k+1}.$ Consider $f(a)$ and $f(b),$ where $a\not\equiv b\pmod{3^k}$ and $1\le a,b\le 3^{k+1}.$ Then, $f(a)\equiv f(a_1)\pmod{3^k}$ and $f(b)\equiv f(b_1)\pmod{3^k},$ where $1\le a_1,b_1\le 3^k.$ Then, we cannot have $f(a)\equiv f(b)\pmod{3^k}$ by the inductive hypothesis, so they cannot be congruent modulo $3^{k+1}.$ If $a\equiv b\pmod{3^k},$ then we have already showed that $a\not\equiv b\pmod{3^k+1},$ so our induction is complete. $\square$

Let $g(n,m)$ denote the remainder when $f(n)$ is divided by $2\cdot 3^m$ (this definition will make sense later). Clearly, $g(n,0)=1.$ Due to Euler's Totient theorem, noting that $\phi(2\cdot 3^m)=2\cdot 3^{m-1},$ we have $$g(n+1,m)\equiv g(n,m)+2^{g(n,m-1)}\pmod {2\cdot 3^m}.$$Let's use this to make a recursion table for $g(n,m):$ \begin{tabular}{c|c|c|c|c|c|c|c|c|c}n horizontal, m vertical & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 0 & 1& 1& 1& 1& 1& 1& 1& 1& 1\\ 1 & 1 & 3 & 5& 1 & 3 & 5& 1 & 3 & 5\\ 2 & 1 & 3 & 11 & 7 & 9 & 17 & 13 & 15 & 5\\ \\ \end{tabular} Let's analyze this table. It seems that $g(n,m)$ repeats every $3^m$ with respect to $n$, and takes on different values for each of $1\leq n\leq 3^m.$ Let's show this claim by induction. Suppose that $g(1,m)$ through $g(3^m,m)$ are all distinct and $g(n,m)$ repeats every $3^m$, and consider $g(n,m+1)$. Using our earlier recurrence, we see that $$g(n+3^m,m+1)=g(n,m+1)+\sum_{n=1}^{3^m}2^{2n-1} \pmod{3^{m+1}},$$since when increasing by $3^m$, we are adding by 2 to the power of each of the odd numbers mod $2\cdot3^m.$ Let's carefully consider the sum $$\sum_{n=1}^{3^m}2^{2n-1}.$$This can be rewritten as $$\frac{2^{2\cdot3^m+1}-2}{3}.$$By exponent lifting, we have $$v_3(\frac{2^{2\cdot3^m+1}-2}{3})=v_3(2+1)+v_3(2\cdot3^m)-1=m.$$Therefore, going back to the formula $$g(n+3^m,m+1)=g(n,m+1)+\sum_{n=1}^{3^m}2^{2n-1}\pmod{3^{m+1}},$$the summation is a multiple of $3^m$ but not $3^{m+1}.$ Therefore, using the fact that the first $3^m$ values are distinct, the first $3^{m+1}$ values of the function are also distinct, since from each of the first $3^m$ terms, we can generate two new different ones by adding the summation twice (this is guranteed to be different value since the summation is a multiple of $3^m$ but not $3^{m+1}$), so we have shown the claim by induction. Therefore, the first $3^{2013}$ values of $g(n,2013)$ are distinct, and thus we are done (since they are all odd so the factor of 2 does not matter).

We induct to prove the statement: For integers $k\geq 0$ and $n\geq 1$, we have that $$\{f(n),f(n+1),\ldots, f(3^k-1+n)\}=\{1,3,5,\ldots, 2\cdot 3^k-1\}$$modulo $2\cdot 3^k$. The base case $k=0$ is trivial since $f(n)$ is always odd. Now assume it is true for $k=m$. Since $\phi(2\cdot 3^{m+1})=\phi(3^{m+1})=2\cdot 3^m$, we have that \begin{align*} f(a+3^m)-f(a)&\equiv f(a+3^m - 1)+2^{f(a+3^m - 1)}-f(a-1)-2^{f(a-1)}\pmod{2\cdot 3^{m+1}}\\ &\equiv f(a+3^m-1)-f(a-1)\\ &\vdots\\ &\equiv f(3^m+1)-1\\ &\equiv 2^{f(3^m)}+2^{f(3^m-1)}+\ldots+2^{f(2)}+2^{f(1)}+1-1\\ &\equiv \sum_{i=1}^{3^m} 2^{2i-1}\\ &\equiv 2\cdot \frac{4^{3^m}-1}{4-1}\\ &\equiv 2\cdot \frac{4^{3^m}-1}{3} \end{align*}By LTE, $$\nu_3\left(\frac{4^{3^m}-1}{3}\right)=\nu_3(4-1)+\nu_3(3^m)-1=m$$so we have that $f(a+3^m)-f(a)\equiv 2\cdot 3^m, 4\cdot 3^m$ modulo $2\cdot 3^{m+1}$ because $f(a+3^m)-f(a)$ is even and has $\nu_3$ equal to $m$. Thus, $\left\{f(n+i), f(n+i+3^m), f(n+i+2\cdot 3^m\right\}=\{f(n+i),f(n+i)+2\cdot 3^{m+1}, f(n+i)+4\cdot 3^{m+1}\}$. Therefore: $$\{f(n),\ldots, f(n+3^{m+1}\}=\{1,3,5,\ldots, 2\cdot 3^{m+1}-1\}$$modulo $2\cdot 3^{m+1}$ completing the inductive step and proof by setting $n=1$.

Replace $2013$ with $k$; then we will in fact show that $f(x), f(x + 1) \ldots, f(x + 3^{k} - 1)$ leave distinct remainders when divided by $3^k$ for any positive integer $x$ by induction on $k$. The base case of $k = 1$ is easy to verify. Now, assume that the statement holds for an arbitrary $k$. We will prove it holds for $k + 1$. Notice that $$\begin{aligned} f(x + 3^{k}) - f(x) &= f(n + 3^{k} - 1) + 2^{f(x + 3^{k} - 1)} - f(x) \\ &= f(x + 3^{k} - 2) + 2^{f(x + 3^{k} - 2)} + 2^{f(x + 3^{k} - 1)} - f(x) \\ &\vdots \\ &= f(x) + 2^{f(x)} + 2^{f(x + 1)} + \cdots + 2^{f(x + 3^{k} - 1}) - f(x) \\ &= 2^{f(x)} + 2^{f(x + 1)} + \cdots + 2^{f(x + 3^{k} - 1)}. \end{aligned}$$By the inductive hypothesis, we know that $f(x), f(x + 1), \ldots, f(x + 3^k - 1)$ are distinct modulo $3^k$. Additionally, since all outputs of $f$ are odd, they must in fact be a permutation of $\{1, 3, 5, \ldots, 2 \cdot 3^k - 1\}$ modulo $2 \cdot 3^k$. Therefore, since $2^{2 \cdot 3^k} \equiv 1 \pmod {3^{k + 1}}$ by Euler, our above sum is equivalent to $$\begin{aligned} 2^1 + 2^3 + \cdots + 2^{2 \cdot 3^k - 1} &\equiv \frac{2(4^{3^k} - 1)}{4 - 1} \pmod {3^{k + 1}}. \end{aligned}$$But from LTE, we have $\nu_3(4^{3^k} - 1) = \nu_2(4 - 1) + \nu_2(3^k) = k + 1$, so $\nu_3(f(x + 3^k) - f(x)) = k$. Thus, we have $f(x + 2 \cdot 3^k) - f(x + 3^k)) \equiv f(x + 3^k) - f(x) \equiv \alpha 3^k \pmod {3^{k + 1}}$ for some fixed $\alpha \in \{1, 2\}$. Using the inductive hypothesis again, this finishes the induction.

This was a relatively easier problem 45 min solve We'll prove that $f(n),f(n+1),...,f(n+3^k-1)$ leave different residues mod $3^k$ by induction; the base case k=1 is obvious since mod 3 it's f(n),f(n)-1,... Note that all f(n) are odd since the first term is odd and then it's odd+2^.=odd; also note that by recursion $f(n)=f(n-1)+2^{n-1}=f(n-2)+2^{n-1}+2^{n-2}=...=2^{n-1}+2^{n-2}+...+1$. We'll prove it for k+1, assuming the induction for the numbers less than it are already proven; call the inductive hypothesis returning distinct residues and that the exponent is taken mod $3^k2$ by Euler's theorem (1). We have $$ f(x + 3^{k}) - f(x) \equiv 2^{f(x)} + 2^{f(x + 1)} + \dots + 2^{f(x + 3^{k} - 1)}\stackrel{(1)}{\equiv}2^1+2^3+...+2^{3^k2-1}\equiv\frac{2(4^{3^k} - 1)}{4 - 1}\stackrel{LTE:\nu_3(4^{3^k}-1)=k+1}{\equiv}3^kc\pmod {3^{k + 1}}$$for some constant c either 1 or 2; by the same reasoning $$f(x+3^k2)-f(x+3^k)\equiv2^{f(x+3^k)}+2^{f(x+3^k+1)}+\dots\equiv2^1+2^3+...+2^{3^k2-1}\equiv3^kc\pmod {3^{k+1}}$$for the same c; in particular, no matter the choice, it's obvious they're all distinct since $2c,c\not\equiv0\pmod 3$, and modulo $3^{k+1}$ adding $3^kc$ sufficiently separates the residues in each group (one spans from $[0,3^k-1]$, another from $[3^k,3^k2-1]$, and a third from $[3^k2,3^{k+1}-1]$). $\blacksquare$

We will prove by induction that for any $3^k$ consecutive values of $f$ are different modulo $3^k$. The base case $k=1$ is clearly true. Assume the inductive statement holds to $n=m$. Since powers of $2$ cycle every $2 \cdot 3^k$ in mod $3^{k+1}$ and all of the terms are odd, we have \begin{align*} f(n+3^k)-f(n) &= \sum_{i=n}^{n+3^k-1} 2^{f(i)} \pmod{3^{k+1}} \\ &\equiv \sum_{i=1}^{3^k} 2^{2i-1} \pmod{3^{k+1}} \\ &\equiv 2 \cdot \frac{4^{3^k}-1}{3} \pmod{3^{k+1}} \end{align*} LTE gives us $v_3 (4^{3^k}-1) = v_3(4-1)+v_3(3^k)=k+1$, so \[v_3 \left(2 \cdot \frac{4^{3^k}-1}{3} \right) = k\] Thus, $f(n)$, $f(n+3^k)$, $f(n+2 \cdot 3^k)$ have different residues mod $3^{k+1}$, completing the inductive step. $\square$

woah nice, 15 minute solve. Claim: $\nu_3(f(a+3^i)-f(a)) = i$. Proof. Induct on $k$, with the base case $i=0$ trivial. Then write \[ f(a+3^i)-f(a) = \sum_{n=a}^{a+3^i-1} f(n+1)-f(n) = \sum_{n=a}^{a+3^i-1} 2^{f(n)}. \]By inductive hypothesis, all of the $f(n)$ for $a \le n \le a+3^i - 1$ leave distinct residues modulo $3^i$, and note in general that $f$ takes odd integer values. Thus modulo $3^{i+1}$, we can use FLT to find that \[ f(a+3^i)-f(a) \equiv \sum_{k=1}^{3^k} 2^{2k-1} = 2 \cdot \frac{4^i-1}{3}. \]Now taking $\nu_3$ we have by LTE that $\nu_3(f(a+3^i)-f(a)) = i$, as desired. A consequence of the claim is that $f(a)$, $f(a+3^i)$, and $f(a+2 \cdot 3^i)$ have distinct residues modulo $3^{i+1}$. Now given $f(a+\Delta)-f(a)$, write $\Delta$ in ternary so that \[ \Delta = \sum_{i} b_i \cdot 3^{a_i} \]for distinct $a_i$ and a sequence $b_i$ of numbers in $\{1, 2\}$. Thus we see by the claim's consequence that \[ \nu_3(f(a+\Delta)-f(a)) = \nu_3(\Delta) \]by basic $\nu_3$ properties, which finishes.

We use induction to show that $f(1), f(2), \ldots$ has period $3^m$ in modulo $3^m$. (Note that during a given period, we cannot have a residue repeat.) The base case $m=1$ is easy to verify. We then show the hypothesis holds for $n=k+1$ given that it holds for $n=k$. The problem then rests on the following: Claim: We have $v_3\left(f(n+2 \cdot 3^k)-f(n)\right) = v_3\left(f(n+3^k)-f(n)\right) = k$ for all positive integers $n$. We use our recursion to evaluate \[f(n+3^k)-f(n) = 2^{f(n)} + 2^{f(n+1)} + \ldots + 2^{f(n+3^k-1)}.\] Using modulo $3^{k+1}$, Euler's Totient Theorem tells us to look at the exponents modulo $2 \cdot 3^k$. Clearly every exponent is odd, and our inductive hypothesis tells us each leaves a distinct residue modulo $3^k$, so this expression is equivalent to \[2^1 + 2^3 + \ldots + 2^{2 \cdot 3^k-1} \equiv \frac{2 \left(4^{3^k}-1\right)}{3} \pmod{3^{k+1}}.\] Now we see that $f(n+2 \cdot 3^k)-f(n)$ is equivalent twice this expression, so their $v_3$'s should be equal. We finish using LTE, as \[v_3\left(\frac{2 \left(4^{3^k}-1\right)}{3}\right) = v_3(4-1) + v_3(3^k) - 1 = k. \quad {\color{blue} \Box}\] Thus we know $f(1), \ldots, f(3^{n+1})$ leave distinct residues modulo $3^{n+1}$, completing our induction. $\blacksquare$

We claim that any $3^m$ values for $n$ gives $f(n)$ with $n \leq 3^m$ distinct remainders when divided by $3^m$. Note that $f$ is always odd. Now we induct. Say that the desired holds true for $n = 3^{m-1}$ and that the sequence $f(n)$ is periodic modulo $3^{m-1}$, with period $3^{m-1}$. We now show similar statements hold for $3^m$. Clearly it suffices to show that $f(k)$, $f(k + 3^{m-1})$ and $f(k + 2 \cdot 3^{m-1})$ leave distinct remainders modulo $3^m$. Now we can compute, \begin{align*} f(3^{m-1} + k) &= f(3^{m-1} + k - 1) + 2^{f(3^{m-1} + k - 1)}\\ &= f(3^{m-1} + k - 2) + 2^{f(3^{m-1} + k - 1)} + 2^{f(3^{m-1} + k - 2)}\\ &\vdots\\ &= f(k) + \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} \end{align*}Then it suffices to show that, \begin{align*} \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} \not\equiv 0 \pmod{3^m} \end{align*}Note that $\phi(3^m) = 2 \cdot 3^{m-1}$. Then noting that any $3^{m-1}$ consecutive terms of $f$ leave distinct remainders modulo $3^{m-1}$ from our induction combined with the fact that $f$ is always odd we must have, \begin{align*} \{f(3^{m-1} + k - 1), f(3^{m-1}+k - 2), \dots, f(k) \} \equiv (1, 3, 5, \dots, 2 \cdot 3^{m-1} - 1) \pmod{2 \cdot 3^{m-1}} \end{align*}Thus we have, \begin{align*} \sum_{i = 1}^{3^{m-1}} 2^{f(3^{m-1} + k - i)} =\sum_{i=1}^{3^{m-1}} 2^{2i - 1} \pmod{3^m} \end{align*}Now from sum of geometric series we have, \begin{align*} \sum_{i=1}^{3^{m-1}} 2^{2i - 1} = 2 \cdot \left(\frac{4^{3^{m-1}} - 1}{3} \right) \end{align*}Now it suffices to show $\nu_3(4^{3^{m-1}} - 1) \leq m$, as then we will have that the product is nonzero modulo $3^m$. However LTE we find, \begin{align*} \nu_3(4^{3^{m-1}} - 1) = m \end{align*}as desired.

Our goal is to prove that $f(n)$, $f(n + 3^k)$, and $f(n + 2 \cdot 3^k)$ all have different residues$\pmod{3^{k+1}}$, which we will accomplish by induction. Our $k = 1$ case is obviously true. $\newline$ Now, we need to prove that $f(n + 3^k) - f(n) \not\equiv 0 \pmod{3^{k+1}}$. Notice that \[f(n + 3^k) - f(n) = \sum_{i=0}^{i = 3^k - 1} 2^{f(n) + i}\]Since $\phi(3^{k+1}) = 2 \cdot 3^k$, we will take the exponents of this expression mod $2 \cdot 3^k$, which results in \[\sum_{i=0}^{3^k-1} 2^{2i+1}\]which is equivalent to \[2 \cdot \frac{4^{3^k} - 1}{3}\]By LTE, $v_3$ of this expression is equal to $k$, which is less than $k + 1$, so $f(n + 3^k)$ and $f(n)$ are distinct, modulo $3^{k+1}$.

Really nice problem. We will prove a stronger claim, that the remainders when $f(1), f(2), \dots, f(3^m)$ leave distinct remainders when divided by $3^m$ for all positive integers $m$. The $m = 1$ case is easy to verify. Now assume the claim for $m$, we will prove for $m + 1$. Lemma 1. The order of $2 \pmod{3^{m + 1}}$ is $2 \cdot 3^m$. Proof. Let the order be $t$, clearly it is even. By Lifting the Exponent Lemma, we obtain $$m + 1 = \nu_3 \left((2^2)^{t / 2} - 1^{t/2} \right) = \nu_3(2^2 - 1) + \nu_3(t / 2),$$then the result follows. Claim 1. The remainder when $f(k + 3^m) - f(k)$ is divided by $3^{m + 1}$ for positive integers $1 \le k \le 2 \cdot 3^m$ is some constant $d$, and $d$ is either $3^m$ or $2 \cdot 3^m$. Proof. Clearly $f(n)$ is odd for all $n \in \mathbb{N}$, then the residues of $f(1), f(2), \dots, f(3^m)$ in $\pmod{2 \cdot 3^m}$ are some permutation of $\{ 1, 3, 5, \dots, 2 \cdot 3^m - 1 \}$ by the Chinese Remainder Theorem. Then by Lemma 1, we have $$f(3^m + 1) \equiv f(1) + 2^{f(1)} + 2^{f(2)} + \dots + 2^{f(3^m)} \equiv f(1) + 2^1 + 2^3 + \dots + 2^{2 \cdot 3^m - 1} \equiv f(1) + 2 \left(\frac{2^{2 \cdot 3^m} - 1}{3} \right) \pmod{3^{m + 1}}.$$ By Lifting the Exponent Lemma, $$\nu_3 \left((2^2)^{3^m} - 1^{3^m} \right) = \nu_3(2^2 - 1) + \nu_3(3^m) = m + 1,$$then clearly the remainder when $f(3^m + 1) - f(1)$ is divided by $3^{m + 1}$ is $3^m$ or $2 \cdot 3^m$. Now repeatedly applying this process for the next set of remainders, we will constantly generate a unique remainder $\pmod{3^{m + 1}}$. Note that the process works as the remainders when $f(k), f(k + 1), \dots, f(k + 3^m - 1)$ are divided by $\pmod{3^m}$ will always be made all distinct. The latter claim finishes as for any residue $r$ of $3^m$, we have $r, r + d, r + 2d$ leaving distinct residues in $3^{m + 1}$. Our induction is complete. Now let $m = 2013$, and we are done. $\blacksquare$

We will prove by induction that $f(1),f(2), \cdots , f(3^n)$ have distinct remainders $\pmod 3^n$. Base case: n=1. Obviously $1,3,11 \pmod 3$ have distinct residues modulo 3. Induction hypothesis: Assume it holds for n=k. Now we will prove it for k+1. We can see that $\phi (3^{k+1}) = 2.3^k$. So ${ord}_2(3^{k+1}) \mid 2.3^k$. If $f(x) \equiv f(y) \pmod {3^k}$ then $f(x) \equiv f(y) \pmod {2.3^k}$, since f(n) is odd for all n $\Rightarrow$ $2^{f(x)} \equiv 2^{f(y)} \pmod {3^{k+1}}$. By the induction hypothesis $f(1), f(2), \cdots , f(3^k)$ is a complete residue system mod $3^k$. Then $f(3^{k}+1) \equiv f(z) \pmod {3^k}$ $\Rightarrow$ $2^{f(3^k +1)} \equiv 2^{f(z)} \pmod {3^{k+1}}$. So now we have $f(3^k +2) - f(3^k +1) \equiv f(z+1) - f(z) \pmod {3^{k+1}}$ $\Rightarrow$ $f(3^k + 2) \equiv f(z+1) \pmod {3^k}$. So $f(3^k +3) - f(3^k+2) = f(z+2) - f(z+1)$. Continuing this $f(3^k+s) - f(3^k+1) \equiv f(z+s-1) - f(z) \pmod {3^{k+1}}$. Now, using the fact that f is always odd, and the hypothesis we have, $f(3^k+1) = 1 + \sum_{i=1}^{3^k} 2^{f(i)} \equiv 2+2^3 +2^5 +\cdots +2^{2.3^k - 1} \equiv 2 \cdot \frac{2^{2.3^k} - 1}{3} +1 \pmod {3^{k+1}}$. But $v_3 (2^{2 \cdot 3^k} - 1) = k+1$ $\Rightarrow$ $f(3^k + 1) \equiv 1 \pmod {3^k}$, but $f(3^k+1) \not \equiv 1 \pmod {3^{k+1}}$ Hence $f$ is periodic modulo $3^k$. But $f(3^k) \not \equiv f(1) \pmod {3^{k+1}}$ Clearly, this shows that $f(1), f(2), \dots f(2 \cdot 3^k)$ are all distinct mod $3^{k+1}$. Also, $f(2 \cdot 3^k +1)- f(3^k +1) \equiv f(3^k +1)-f(1) \equiv m.3^k$ $\Rightarrow$ $f(2 \cdot 3^k+1) \equiv 2.m 3^k +1$ where $ m \in \{1,2 \}$. But $2.m \not \equiv m \pmod 3$. So $f(2.3^k+1)$ is distinct from all previous values and using the periodicity, we are ready.

Fix some $k$, and consider the assertion that $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ are distinct mod $3^k$ for all integers $n \geq 0$. We prove this by induction on $k$, with the base case $k = 1$ trivial (the sequence repeats $1, 0, 2, 1, 0, 2, \dots$ mod $3$). This clearly implies the $k = 2013$ case. We prove the following lemma first, which allows us to lift from $3^k$ to $3^{k + 1}$. Claim: Let $\ell$ be a positive integer. Then $\text{ord}_{3^\ell}(2) = 2 \cdot 3^{\ell - 1}$. Proof. Let $r = \text{ord}_{3^\ell}(2)$. Clearly $r$ is even (otherwise $2^r \equiv 2 \pmod 3$), so by LTE we have \[\nu_3(2^r - 1) = \nu_3(4^{r/2} - 1) = \nu_3(r/2) + \nu_3(4 - 1) = \nu_3(r) + 1.\]Since $3^\ell \mid 2^r - 1$, it follows that $3^{\ell - 1} \mid r$. Thus $r$ is divisible by $2 \cdot 3^{\ell - 1}$, and by minimality we have $r = 2 \cdot 3^{\ell - 1}$ as claimed. $\square$ Continuing with the problem, suppose the result holds for some $k$, and let $n$ be a positive integer. We're given that $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ are distinct mod $3^k$, and since $f(m)$ is odd for all positive integers $m$, $f(n + 1), f(n + 2), \dots, f(n + 3^k)$ form a permutation of $1, 3, 5, \dots, 2 \cdot 3^k - 1$ mod $2 \cdot 3^{k - 1}$. Thus we have \[f(n + 3^k + 1) = f(n + 3^k) + 2^{f(n + 3^k)} = \dots = f(n + 1) + \sum_{i = 1}^{3^k} 2^{f(n + i)}\]\[ \equiv f(n + 1) + \sum_{i = 1}^{3^k} 2^{2i - 1} = f(n + 1) + \frac23\left(4^{3^k} - 1\right).\]But since \[\nu_3\left(\frac23\left(4^{3^k} - 1\right)\right) = \nu_3\left(4^{3^k} - 1\right) - 1 = k\]by LTE again, we obtain $\nu_3(f(n + 3^k + 1) - f(n + 1)) = k$. By similar arguments, for each $i = 1, 2, \dots, 3^k - 1$, the values $f(n + i), f(n + 2i), f(n + 3i)$ are in some order congruent to \[f(n + i), f(n + i) + 3^k, f(n + i) + 2 \cdot 3^k\]mod $3^{k + 1}$, which combined with the inductive hypothesis completes the induction. $\square$