Estonian Math Competitions

Let $n$ be a prime. By condition (1) the sequence $a_0, a_1, \dots$ contains only finitely many different numbers. If $a_m$ is maximal of them, then by condition (3) $a_{m+a_m}$ must also be maximal. Let us prove that if $a_m$ is maximal of the numbers, then $a_{m+k \cdot a_m}$ is also maximal for any $k \ge 0$. This holds for $k=0$. If the claim holds for $k$, then $a_{m+(k+1) \cdot a_m} = a_{m+k \cdot a_m + a_m} = a_{m+k \cdot a_m + a_{m+k \cdot a_m}} = a_{m+k \cdot a_m} = a_m$. This proves the claim. By condition (2) $a_m$ is not divisible by $n$. Since $n$ is prime, the numbers $a_m$ and $n$ are relatively prime. Hence among the numbers $m+k \cdot a_m$, where $0 \le k < n$, there is one in each congruence class modulo $n$. Hence all members of the sequence are maximal, i.e. they are equal.

Suppose $n$ is a composite number; let $m$ be its divisor with $1 < m < n$. For any $k < m$ choose $a_k = m + k \cdot n$ and continue the sequence with period $m$. Condition (1) holds, since $n$ is a multiple of $m$. Condition (2) holds, since all members of the sequence are congruent to $m$ modulo $n$. For the condition (3) notice that all members of the sequence are divisible by $m$. Hence $i$ and $i+a_i$ are always congruent modulo $m$, therefore $a_i = a_{i+a_i}$. At the same time not all the numbers are equal.