Is there a sequence of natural numbers with these properties?

Question

Is there a sequence of natural numbers (except 1) which every consecutive term is $\textbf{not}$ relatively prime and each natural number appears $\textbf{exactly once}$?

Answer 1

Start with $a_1=2$ and for $n\geq 2$ let $a_{n}$ be the smallest number not already used which shares a factor with $a_{n-1}$. $$2, 4, 6, 3, 9, 12, 8, 10, 5, 15, 18, 14, 7, 21, 24, 16,\dots$$ Prove that every integer number greater than $1$ appears exactly once.

This is called the EKG sequence. A proof that this sequence is a permutation of $\mathbb{N}\setminus\{1\}$ is given in "The EKG Sequence" by J. C. Lagarias, E. M. Rains and N. J. A. Sloane.