Problem

Source: 2022 IGMO Round 2 #4 International Gamma Mathematical Olympiad

Tags: number theory, sum of digits



Let's take any positive integer $n_0 \in \{1, 2,...,\}$. Then, let $n_1$ be equal to the sum of digits of the square of $n_0$. Repeat this process to obtain $n_2$ from $n_1$, $n_3$ from $n_2$ and so on. In this way we obtain a sequence of natural numbers denoted as $(n_0; n_1, n_2,...)$. For example when we pick $n_0 = 7$ we obtain $$7 \to 4 + 9 = 13 \to 1 + 6 + 9 = 16 \to ...$$which creates sequence $$(7; 13, 16, ,,,)$$If in the $(n_0; n_1, n_2,...)$ sequence we are able to find two indices $i$ and $j$ such that $i > j$ and $n_i = n_j$ , then we say that this sequence "gets caught in a loop". If in the $(n_0; n_1, n_2,...)$ sequence we are able to find an index $i > 0$ such that $n_i = n_0$, then we call this sequence "a loop". Find all possible loops and prove that for every $n_0$, the sequence $(n_0; n_1, n_2,...)$ gets caught in a loop.