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$.