<s>[INST] Prove that ${f(1);f(2);f(3)...;f(3^{k})}$ is a complete set of residues mod $3^{k}$ 
Let a function $ f : \Bbb N^* \to \Bbb N^* $  ($\mathbb N^*$ is the set of positive integers)


$f(1) = 1 $;


$f(n+1) = f(n) +2^{f(n)}$ for all positive integers $n$.


Prove that ${f(1),f(2),f(3),\dots,f(3^{k})}$ is a complete set of residues mod $3^{k}$ (where $k$ is a positive interger).

$f(n+1) = f(n) +2^{f(n)}$
$\Rightarrow f(n+1) =f(n-1) + 2^{f(n-1)}+2^{f(n)} = ... = 1 + 2^{f(1)} + 2^{f(2)} +...+ 2^{f(n)}$
Suppose there exist $2$ positive integers $a, b$ satisfying $ 1 \le a < b \le 3^{k} $  :
$ f(a) \equiv f(b) \pmod{ 3^{k}} $
$\Rightarrow 1 + 2^{f(1)} + 2^{f(2)} +...+ 2^{f(a-1)} \equiv 1 + 2^{f(1)} + 2^{f(2)} +...+ 2^{f(b-1)} \pmod {3^{k}}$
$\Rightarrow 2^{f(a)} + 2^{f(a+1)} + ... + 2^{f(b-1)} \equiv \pmod {3^{k}}$
It is easy to see that $2$ is the primitive root mod $3^{k}$ and $f(n) \equiv 1 \pmod 2 $
$\Rightarrow 2^1 ; 2^2 ;...; 2^{ 2.3^{(k-1)} } $ reduced set of residues
mod $3^{k} $
So if $ f(a) \equiv f(b)$ (mod $3^{k}) \Rightarrow f(a) \equiv f(b)$ (mod $3^{k-1})$
$\Rightarrow f(a) \equiv f(b)$ (mod $2.3^{k-1})$
$\Rightarrow 2^{f(a)} \equiv 2^{f(b)}$ (mod $3^{k})$
$\Rightarrow f(a) + 2^{f(a)} \equiv f(b)+2^{f(b)}$ (mod $3^{k})$
$\Rightarrow f(a+1) \equiv f(b+1)$ (mod $3^{k})$
$\Rightarrow$ if $f(a) \equiv f(b)$ (mod $3^{k})$ then $f(a+s) \equiv f(b+s) $ (mod $3^{k}) (b+s \le 3^{k} )$
I want to point out the absurdity in the above argument but have no idea, I hope to get help from everyone. Thanks very much ! (This is a problem from a long time ago, I guarantee.)
 [/INST] can induct on k.
induction hypothesis: $f(n),f(n+1),...,f(n+3^k-1)$ is a complete set of residues modulo $3^k$ for all $n\geq1$
for the base case,
{f(1),f(2),f(3)}={1,3,11}={0,1,2} is a complete residue set mod 3.
$m_1\equiv m_2\pmod{3}\implies f(m_2)-f(m_1)\equiv 2^{f(m_1)} +2^{f(m_1+1)}...+ 2^{f(m_2)}\equiv 2+...+2\equiv 2(m_2-m_1)\equiv 0\pmod{3}$
f(n),f(n+1),f(n+2) is a complete residue set mod 3.
for the induction step,
$\{f(n),f(n+1),...,f(n+3^k-1)\}$ is a complete residue set, so it is $\{1,2,...,3^k\}\pmod{3^k}$
the $3^k$ numbers are all odd.
by CRT, $\{f(n),f(n+1),...,f(n+3^k-1)\}\equiv\{1,3,5,...,2*3^k-1\}\pmod{2*3^k}$
by FLT, $\{2^{f(n)},2^{f(n+1)},...,2^{f(n+3^k-1)}\}\equiv\{2^1,2^2,...,2^{2*3^k-1}\}\pmod{3^{k+1}}$
$f(n+3^k) - f(n) = 2^{f(n)} + 2^{f(n+1)} + \dots + 2^{f(n+3^k-1)}
\\ \equiv 2^1 + 2^3 + \dots + 2^{2 \cdot 3^k-1} 
\\ \equiv 2\frac{4^{3^k}-1}{4-1}
\\ \equiv 2*3^k \pmod{3^{k+1}}$
$f(n+3^{k+1}) - f(n)\equiv (f(n+3*3^k) - f(n+2*3^{k+1}))+...\equiv (2*3^k)*3\equiv0\pmod{3^{k+1}}$
$m_1\equiv m_2\pmod{3^{k+1}}\implies f(m_1)\equiv f(m_2)\pmod{3^{k+1}}$
now we show $f:Z/3^{k+1}Z\to Z/3^{k+1}Z$ is injective.
$f(m_1)\equiv f(m_2)\pmod{3^{k+1}}\implies f(m_1)\equiv f(m_2)\pmod{3^k} \implies m_1\equiv m_2\pmod{3^k}\implies m_1\equiv m_2\pmod{3^{k+1}}$
${f(n),…,f(n+3^{k+1}-1)}$ is a complete set of residues mod $3^{k+1}$, completing the induction step.
--
some calculations
$(f(1),...,f(9))\equiv(1,3,2,7,0,8,4,6,5)\pmod{9}$
</s>