For any natural number $n$, we denote $S(n)$ as the sum of the digits of the decimal representation of $n$. We say that a natural number $n$ is pretty if $S(n)=S\left(n^{2}\right)$. Determine all possible values of $S(n)$ for the pretty numbers $n$.
Modulo 9, $S(n)$ satisfies the equation $x^{2}=x$. By testing $x=$ $0,1, \ldots, 8$, we find that the only solutions (modulo 9) are 0 and 1, so $S(n)$ is necessarily congruent to 0 or 1 modulo 9. Conversely, we verify that if $n=10^{k}-1=99 \cdots 9$ ( $k$ times) then $n^{2}=99 \cdots 9800 \cdots 01$ (with $k-1$ digits 9 and $k-1$ digits 0), so $S(n)=S\left(n^{2}\right)=9 k$. Similarly, if $n=2 \times 10^{k}-1=199 \cdots 9$ then $n^{2}=399 \cdots 9600 \cdots 01$ so $S(n)=S\left(n^{2}\right)=9 k+1$.
We conclude that the possible values of $S(n)$ are the natural numbers congruent to 0 or 1 modulo 9.