Maths Olympiad Prep

Library / /10 of 18

Number theory Difficulty 5.9 AIME, harder Prove it Austria

A sequence an\langle a_n \rangle of positive integers is given, such that a1=1a_1 = 1 and an+1a_{n+1} is the smallest positive integer such that
lcm(a1,a2,,an,an+1)>lcm(a1,a2,,an).lcm(a_1, a_2, \dots, a_n, a_{n+1}) > lcm(a_1, a_2, \dots, a_n).
Which numbers are contained in the sequence?

Solution

The first few elements of the sequence are given by
1,2,3,4,5,7,8,9,11,1, 2, 3, 4, 5, 7, 8, 9, 11, \ldots
and we note that the first two positive integers not contained in the sequence are 66 and 1010.
These would not have made the lcm larger when it was "their turn", and they would certainly
not do so at a later date. We therefore note that a number that has been "left out" in the
sequence of positive integers cannot turn up at some later point.

Next, we note that each prime is included in the sequence. When a prime number pp is the next number under consideration, its inclusion will certainly always increase the value of the lcm, and it will therefore certainly be included in the sequence an\langle a_n \rangle. This is also true of any power of a prime. All powers of primes are therefore included in the sequence an\langle a_n \rangle.

On the other hand, any integer NN that has at least two different prime divisors has only divisors of the form pkp^k (with pp prime) that have already been included in the sequence of powers of primes to that point. Inclusion of NN in the sequence will therefore certainly not raise the value of the lcm, and no such NN can be included in the sequence an\langle a_n \rangle.

Summarizing, we note that the sequence an\langle a_n \rangle is composed of the number 11 and all powers of primes in ascending order.
qed

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.