First, there are arbitrary large primes $q$ such that $q$ divides $a_n$, i.e. if $q_n$ is the largest prime dividing $a_n$ then $\{q_1, q_2, \ldots \}$ is infinite. This is obvious, since otherwise there's a finite list of primes $p_1, \ldots, p_k$ such that all of $a_n$ is of the form $p_1^{e_1} \cdots p_k^{e_k}$, whence there's a prime $p$ dividing infinitely many $a_n$ but this clearly implies that all of $p$, $2p$, $3p$, ... must occur in $\{ a_n \}$, and in particular $qp$ occurs in $\{ a_n \}$ for a prime $q$ larger than any of the $p_k$'s, in which case the next term is $q$, contradiction. In particular, $a_n$ is prime for infinitely many $n$. Next we can prove by induction that all multiples of $2$ occur in $\{ a_n \}$. First it's clear that $2$ must exist in $\{ a_n \}$ (in fact $2$ must occur in the first three terms!). For induction, suppose $2, 2(2), \ldots, 2m$ occur in $\{ a_n \}_{1 \leq n \leq r}$. By the first paragraph, choose $N$ large enough so that $N > r$, $a_N > 2(m+1)$, $a_N$ is prime, and $a_N$ does not divide any of the $a_n$ for $1 \leq n \leq r$. If the next term $a_{N+1}$ is not $2a_N$, then $a_{k} = 2a_N$ for some $r < k$ since $a_N$ was chosen so that it doesn't divide $a_n$ for $1 \leq n \leq r$. So we can choose $k$ such that $a_{k} = 2a_N$ and $r < k$. Now the next term $a_{k+1}$ will be smallest in $\{ 2(m+1), a_N x \}_{x \geq 1}$ for varying positive integers $x$. Since $2(m+1) < a_N$, we're done (either the next term is $2(m+1)$ or $2(m+1)$ had already occured in one of the previous terms!). Now for any other prime $p$ it's easy to see that all multiples of $p$ must occur in $\{ a_n \}$ by noting that (thanks to the second paragraph) $2^s p \in \{ a_n \}$ for all $s \geq 1$, and hence all positive integers except $1$.

Have anybody checked that solution ?

hochs wrote: First, there are arbitrary large primes $q$ such that $q$ divides $a_n$, i.e. if $q_n$ is the largest prime dividing $a_n$ then $\{q_1, q_2, \ldots \}$ is infinite. This is obvious, since otherwise there's a finite list of primes $p_1, \ldots, p_k$ such that all of $a_n$ is of the form $p_1^{e_1} \cdots p_k^{e_k}$, whence there's a prime $p$ dividing infinitely many $a_n$ but this clearly implies that all of $p$, $2p$, $3p$, ... must occur in $\{ a_n \}$, and in particular $qp$ occurs in $\{ a_n \}$ for a prime $q$ larger than any of the $p_k$'s, in which case the next term is $q$, contradiction. In particular, $a_n$ is prime for infinitely many $n$. I can't understand this part.(The other parts are OK.) I think "there are arbitrary large primes $q$ such that $q$ divides $a_n$" $\Rightarrow$"In particular, $a_n$ is prime for infinitely many $n$. " is not "In particular". I write my solution below. Let $U=\{a_{1},a_{2},...\}$, $S(m)=\{a_{n}; n\in\mathbb{Z}^{+}, GCD(a_{n},m)>1\}$ for any positive integer m larger than 1, and $\{p_{1},p_{2},...\}(p_{1}<p_{2}<...)$ denotes the set of all primes. Assume that there exists an integer $M$ that $2\le M$ and $M\notin U$. LEMMA1. $m\notin U\Rightarrow S(m)$ is finite PROOF. If $a_{n}\in S(m)$, then (because $a_{n+1}\not=m$)$a_{n+1}<m$. So $|S(m)|\le m-2.$$\blacksquare$ LEMMA2.$\forall i\in \mathbb{Z^{+}}, S(p_{i})$ is finite. PROOF. Since $S(M)$ is finite, for any prime $p$ there is a positive integer $k$ large enough $p^{k}M\notin S(M)$. This means $p^{k}M\notin U$, thus $S(p^{k}M)$ is finite. In particular, $S(p)$ is finite.(because $S(p)\in S(p^{i}M)$)$\blacksquare$ Since $S(2)$ is finite, there exists a positive integer $x$ such that $\forall j\ge x, 2p_{j}\notin U$. Because $p_{i}\in U \Rightarrow 2p_{i} \in U$, by contraposition, we get $\forall j\ge x, p_{j}\notin U$ Then, for any $j\ge x$, we get $a_{k}\in S(p_{j})\Rightarrow a_{k+1}<p_{j}$(because $a_{k+1}\not=p_{j}$) $\Rightarrow a_{k+1}\in \bigcup^{j-1}_{i=1}S(p_{i})$ $\Rightarrow...\Rightarrow a_{k+s}\in \bigcup^{x-1}_{i=1}S(p_{i})$($s$ is a positive integer no more than $j-x+1$) Here, since every integer larger than 1 belongs to $\bigcup^{\infty}_{i=1}S(p_{i})$, we can say that "$\forall j>1$ , there exists a nonnegative integer $s$ such that $a_{j+s}\in\bigcup^{x-1}_{i=1}S(p_{i})$", which contradicts the finiteness of $\bigcup^{x-1}_{i=1}S(p_{i})$

Suppose, $ g_n=\text {gcd} (a_n,a_{n+1}) $. Consider the sequence $ \{b_n\} $. $ P $ be the set of all prime divisors of $ b_i $ .If $ P $ is finite, then some prime will appear infinitely many times, say $ p $. So all the multiples of $ p $ will appear in the sequence of $ \{a_n\} $. So for some prime $ q $ which is not in $ P $, there will be infinitely many $ i $ such that $ a_i $ is divisible by $ pq $. But since $ q $ doesn't appear in $ P $, so the next term will be $ >q $ for infinitely many $ a_i's $ which is not possible. So $ q $ will appear in $ P $. So $ P $ can't be finite. So we can choose arbitrarily large prime $ p $ from $ P $. Consider the smallest $ I $ such that $ p|b_i $. Clearly, $ p|a_i $,,$ b_{i-1}p|a_i $. So for any integer $ u<p $. $ b_{i-1}.u $ has already appeared in the sequence $ \{a_n\} $. So if we choose arbitrarily large $ p $, we will get infinitely many terms which are divisible by $ p $. But that implies that $ p $ appears in the sequence. So every prime appears in the sequence and infinitely many multiples of each prime appears in the sequence. Now we'll prove if one prime has infinitely multiples then it's all multiple are in the sequence. We argue by contradiction, and let $kp$ be the first multiple of p that is missed. Choose $n_0$ so that $a_n> kp$ for all $n>n_0$. Since infinitely many multiples of p occur, there exists $n > n_0$ with $a_n = lp$ for some $l$. But now we must have $a_{n + 1} = kp$, because $gcd{a_n, kp}\geq p$ is allowed, and all smaller possible values which are ever going to appear in the sequence have already appeared. This is a contradiction. Now as all primes appear and also all of their multiples so sequence covers all natural number now as we have all terms are distinct by construction of sequence so it's permutation of all natural numbers.

$\textbf{Lemma 1:}$ If infinitely many numbers which are $0 \pmod{p}$ are in the sequence, the claim is proven, where $p$ is prime. $\textbf{Proof:}$ I claim the number $kp$ appears in the sequence. Assume that $\{i_n\}$ is a sequence of numbers such that $p \mid a_{i_n}$ for each value of $n$. Then, observe that $kp$ follows at least one of $a_{i_1}, a_{i_2}, \cdots a_{i_{kp}}$, since the numbers which follow each of them are distinct so if none of them are $kp$ one of them is greater than $kp$, which is obviously a contradiction. Hence, all multiples of $p$ are in the sequence. Now observe that since all multiples of $p$ are in the sequence, infinitely many multiples of every prime are in the sequence, so all multiples of every prime are in the sequence and we may conclude. $\textbf{Lemma 2:}$ If the number $p$ exists in a sequence, so does the number $2p$, where $p$ is prime. $\textbf{Proof:}$ If $2p$ appears before $p$, we're done. Otherwise, it follows directly afterward. If there are infinitely many even integers in the sequence, we are finished by the lemma. Hence, it suffices to show that infinitely many evens are in the sequence. Assume that all even integers $n$ in the sequence are less than $M$ (otherwise, there are obviously infinitely many). I claim that for any prime $p \ge \frac{M}{2}$, we have that $p$ does not divide any element in the sequence. Also, take $M > 3$. Assume that such a $p$ exists and consider the first $a_i$ such that $a_i$ has a prime factor at least $\frac{M}{2}$. To this end, let $a_i = np^{\ell}$ where $p \nmid n$ and let $a_{i-1} = d$. By maximality, $a_i$ has no prime factors which are at least $\frac{M}{2}$. ($i \neq 1$: this is because $a_2$ or $a_3$ will then exceed $M$ and be even) Let this factor be $p$. Observe that if $a_i \ge 2M$, we have that there will exist a $k$ for which \[ a_i \ge 2M > p2^k \ge M \], which will be contradiction since $2^kp$ will have broken the ceiling for even numbers (they can't exceed $M$). Hence, since $p \ge \frac{M}{2}$, we have that $\ell = 1$. Then, $n$ is $3$ or $2$. Moreover, we know it cannot be two either, because $2p \ge M$. So $3p$ has to follow, and the preceding number is a multiple of $3$. The number after $3p$ is $p$, because if a smaller multiple of $3$ existed it would have been $a_i$, as if it was less than $p$ it would be less than $3p = a_i$ as well and after that we know that $2p$ will appear by Lemma 2 and we're done. Hence, the set of prime factors of $a_i$ is limited. And with this we're done, as by piegonhole infinitely many of them are multiples of some prime, so by lemma 1 we may conclude.

The main claim is the following. Claim : There exists a prime $p$ which divides infinitely many terms in the sequence. Proof : Suppose for the contradiction that each prime divides only finitely many terms. Then let $p_i$ be the smallest prime divisor of $a_i$. Clearly a prime $p$ can be appeared on $p_1,p_2,...$ only finitely many times so this sequence is unbounded. However, note that $p_i$ is the smallest positive integer not coprime to $a_i$ so either $a_{i+1}=p_i$ or $p_i$ has appeared before in this sequence. Either way, $p_1,p_2,...$ appeared in this sequence. As it's unbounded, there are infinitely many prime in the sequence. However, if $p$ appears, $2p$ is the smallest positive integer not coprime to $p$, thus it must be the next term or it has appeared somewhere. This means $2p$ appeared for infinitely many prime $p$ which means $2$ works, contradiction. Now it's easy to finish. Let $p$ be such prime and $k\in\mathbb{Z}^+$. Then $kp$ is not coprime to all multiple of $p$ in the sequence. As there are infinitely many such terms, all of $1,2,...,kp-1$ must be eventually run out. Thus all multiple of $p$ must appear somewhere in the sequence. Finally, consider any positive integer $n>1$, it is not coprime to $np, 2np, 3np,...$. At some point, each positive integer less than $n$ must be run out. Thus $n$ must appear after one of these integers. Hence every positive integer except $1$ appears in this sequence.

An extension for this problem: Let $c$ be a positive integer. Define the sequence $\{a_n\}$ : $a_1=1,a_2=2,...,a_c=c$ and $a_n$ to be the smallest positive integer which $gcd(a_n,a_{n-1})>c$ and not equal to $a_1,a_2,\cdots, a_{n-1}$. Prove that every positive integer appears in this sequence $\{a_n\}$.

This is pretty neat. Say some number $N \geqslant 2$ does not appear in the sequence. Then clearly only finitely many multiples of $N$ can occur in the sequence, because every time a multiple of $N$ appears, the only way $N$ doesn't get written is if something smaller is, which can happen at most $N - 2$ times, which is finite. If there is a prime $p$ that divides infinitely many terms of the sequence, then it's easy to see that every multiple of $p$ appears on the sequence. But this means infinitely multiples of $pN$ appear in the sequence, which is a contradiction. So every prime divides only finitely many terms of the sequence. This means infinitely many primes appear in the sequence, so for infinitely many primes $q$, it is either followed by $2q$ or precedes $2q$, which means $2$ divides infinitely many terms of the sequence, again a contradiction to the previous things. So such an $N$ cannot exist, implying that every positive integer at least $2$ appears in the sequence, as desired. $\blacksquare$

After proving that all even numbers will appear, We can observe that after appearing 2k,4k,....,(2^k)*k then k must have appeared.