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: a1=1,a2=2,a3=3 and for n>3, an=The smallest integer not occurring earlier, which is relatively prime to an1 but not relatively prime to an2.Prove that every natural number occurs exactly once in this sequence. M. Ivanov