Explain the following mysterious property of the function $f_1$ where $f_1(k)$ is the square of sum of digits of $k$. We denote $f_n(k)=f_1(f_{n-1}(k))$.
I have to find out the value of $f_{1995}(2^{1995})$
My attempt :
Consider $f_x(2^x)$, with a little investigation, we would notice that value of $f_x(2^x)$ is $1$ whenever $x$ is a multiple of $3$. Many of my friends concluded the same thing. I was not satisfied with the answer. Nobody understood why it was the case.
My thoughts :
I think the reason is when we calculate $f_x(2^x)$ when $x$ is a multiple of $3$, we end up with $f_i(10^j)$ at some point, then all later calculations will only yield $1$.
But what's the guarantee that you will definitely end up with power of ten at some point? Maybe we can observe a pattern when we write numbers in both binary?( I thought it because we are concerned with power of 2). Unfortunately, I didn't see any pattern (maybe I have missed). Maybe be $8$ is involved in some way? I could not come to conclusion to any of the questions.Can anybody give hints or provide a proof? Any help would be great.
 A: This isn't a complete answer, insofar as it leaves the general case of $f_x(2^x)$ for any $x\equiv1\pmod{3}$ open.  But if I steal a key idea from David Cheng in the comments, then I can solve the original $x=1995$ case.  Moreover, I think it should be clear how to generalize this to a full solution.
Note that, for all $k\in\mathbb{N}$, $k$ has at most $\log_{10}(k)+1$ digits, each of which has size at most $9$.  So $$f_1(n)\leq(9\log_{10}(k)+1)^2$$  Call the right-hand side $F(k)$.
$f_1$ is not increasing (when digits "roll over", it decreases quite substantially), but $F$ is.  So we can iterate "from the outside": $$f_n(k)=f_1(f_{n-1}(k))\leq F(f_{n-1}(k))\leq F^2(f_{n-2}(k))\leq\dots\leq F^n(k)$$
$F$ is (strictly) decreasing on $[712,\infty)\cap\mathbb{N}$, so the long-term behavior of $f_n(k)$ must lie in $[0,711]\cap\mathbb{N}$.  Thus it suffices to characterize $f_1(k)\pmod{999}$.  Finally, note that $f_1(k\pmod{999})\equiv f_1(k)\pmod{999}$ (exercise).
We have now reduced the problem to a discrete dynamical system on a finite state space.  What is our initial condition?
Well, $999=3^3\cdot37$.  By computation, $2^{18}\equiv1\pmod{3^3}$ and, since the unit group of $\mathbb{Z}/(37)$ is cyclic, $2^{36}\equiv1\pmod{37}$ too.  $1995\equiv15\pmod{36}$, so $2^{1995}\equiv2^{15}\equiv800\pmod{999}$.  (That last bit used a calculator.)
Now we can compute: $$f_1(800)=64$$ $$f_1(64)=100$$ $$f_1(100)=1=f_1(1)$$
