Problem

Source: St. Petersburg Olympiad 2015, 2nd Round, Grade 9, also known as Yellowstone Permutation

Tags: number theory, relatively prime



A sequence of integers is defined as follows: $a_1=1,a_2=2,a_3=3$ and for $n>3$, $$a_n=\textsf{The smallest integer not occurring earlier, which is relatively prime to }a_{n-1}\textsf{ but not relatively prime to }a_{n-2}.$$Prove that every natural number occurs exactly once in this sequence. M. Ivanov