3. For a given positive constant $k$, define $f_{1}(k)$ as the square of the sum of the digits of $k$, and let $f_{n+1}(k)=f_{1}\left(f_{n}(k)\right)$, find the value of $f_{1991}\left(2^{1990}\right)$.
(IMO - 31 Shortlist)
3. First, note that for large $k$ values, $f_{1}(k)$ is much smaller than $k$. Since $f_{1}$ is not monotonic, this fact can be expressed as follows: if $A \leqslant B$, then the number of digits of $A \leqslant$ the number of digits of $B \leqslant 1+\lg B, f_{1}(A)<(1+\lg B)^{2}<\left(4 \log _{2} 16 B\right)^{2}$. Using this inequality twice, we get an estimate for $f_{2}\left(2^{1900}\right)$: $f_{1}\left(2^{1900}\right)<4^{2} \cdot(1994)^{2}<2^{26}, f_{2}\left(2^{1900}\right)<(4 \cdot 30)^{2}=14400$. Therefore, the sum of the digits of $f_{2}\left(2^{1900}\right)$ is at most $36(=4 \cdot 9)$, so $f_{3}\left(2^{1990}\right) \leqslant 36^{2}=1296, f_{4}\left(2^{1900}\right)<(9+9+9)^{2}=729, f_{5}\left(2^{1900}\right)<(6+$ $9+9)^{2}=576$. On the other hand, since $f_{1}(k) \equiv k^{2}(\bmod 9)$, we have $f_{1}\left(2^{1900}\right) \equiv\left(2^{1900}\right)^{2} \equiv(-2)^{2} \equiv 4(\bmod 9)$, $f_{2}\left(2^{1090}\right)=4^{2} \equiv-2(\bmod 9), f_{3}\left(2^{1900}\right) \equiv(-2)^{2}=4(\bmod 9) \cdots$ Therefore, when $n$ is odd, $f_{n}\left(2^{1900}\right) \equiv 4(\bmod 9)$. When $n$ is even, $f_{n}\left(2^{1990}\right) \equiv-2(\bmod 9)$.

If $x^{2} \equiv 4(\bmod 9)$ and $x \leqslant 24$, then $x^{2} \in H=\{4,49,121,256,400\}$, and by simple calculation (for each $h \in$ $H), f_{3}(h)=f_{5}(h)=f_{7}(h)=\cdots=169, f_{4}(h)=f_{6}(h)=f_{8}(h)=\cdots=256$. Since $f_{5}\left(2^{1900}\right) \in H$, so