China National Team Selection Test

Step 1: We prove that there are infinitely many even numbers in this sequence.
Suppose on the contrary that there are only finitely many even numbers, and there is an integer $E$, such that all even numbers greater than $E$ do not appear in the sequence. It follows that there exists a positive integer $K$ such that $a_n$ is an odd number greater than $E$ for any $n \ge K$. Then there is some $n_1 > K$ such that $a_{n_1+1} > a_{n_1}$ (otherwise the sequence is strictly decreasing after $a_{n_1}$, a contradiction).
Let $p$ be the smallest prime divisor of $a_{n_1}$, $p \ge 3$. Since
$$(a_{n_1+1} - a_{n_1}, a_{n_1}) = (a_{n_1+1}, a_{n_1}) > 1,$$
we have $a_{n_1+1} - a_{n_1} \ge p$, i.e. $a_{n_1+1} \ge a_{n_1} + p$.
On the other hand, $a_{n_1} + p$ is even and greater than $E$, so it does not appear before $a_{n_1}$, and therefore $a_{n_1+1} = a_{n_1} + p$, which is even — a contradiction.

Step 2: We prove that all even numbers are in this sequence.
Suppose on the contrary that $2k$ is not in this sequence and is the smallest such even number. Let $\{a_{n_i}\}$ be the subsequence of $\{a_n\}$ consisting of all even numbers. By step 1, it is an infinite sequence. Since $(a_{n_i}, 2k) > 1$ and $2k \notin \{a_n\}$, we have $a_{n_i+1} \le 2k$ by definition.
However, $\{a_{n_1+1}\}$ is infinite — a contradiction. Thus, $\{a_n\}$ contains all even numbers.

Step 3: We prove that $\{a_n\}$ contains all odd numbers greater than $1$.
Suppose on the contrary that $2k+1$ is an odd integer greater than $1$ which is not in $\{a_n\}$, and is the smallest such number. By step 2, there is an infinite subsequence $\{a_{m_i}\}$ of $\{a_n\}$ consisting of even numbers that are multiples of $2k+1$. Arguing analogously as in step 2, we have $a_{m_i+1} \le 2k+1$, $i=1, 2, \dots$, a contradiction.

We have shown that $\{a_n\}$ contains all positive integers except $1$.