The sequence a1, a2, a3, ... is defined as follows. a1 = 1. an is the smallest integer greater than an-1 such that we cannot find 1 ≤ i, j, k ≤ n (not necessarily distinct) such that ai + aj = 3ak. Find a1998.
Solution
Answer: 4494.
We show that a4n+1 = 9n+1, a4n+2 = 9n+3, a4n+3 = 9n+4, a4n+4 = 9n+7. Note that this sequence includes all positive integers which are 1 mod 3 and some of those which are 0 mod 3.
Note first that we cannot find a, b, c in the sequence ... 9n+1, 9n+3, 9n+4, 9n+7, ... such that a + b = 3c. No members of the sequence are 2 mod 3, so we cannot have a or b 1 mod 3 (because 3c is 0 mod 3). But if a and b are both 3 mod 9, then their sum is 6 mod 9, so c must be 2 mod 3, which is impossible. So it remains to show that an satisfies the smallest criterion.
Consider first n = 1. We are given that a1 = 1. a2 cannot be 2, or we have 1 + 2 = 3.1. Similarly, a4 cannot be 5 or we have 4 + 5 = 3.3. It cannot be 6 or we have 3 + 6 = 3.3. So n = 1 is established.
Now suppose that n is given. We cannot have a4n+5 = 9n+8 or (9n+8) + (9n+4) = 3(6n+4). We have 6n+4 = 1 mod 3, so 6n+4 is in the sequence. We cannot have a4n+5 = 9n+9, because (9n+9) + (9n+3) = 3(6n+4). So a4n+5 = 9(n+1)+1. We cannot have a4n+6 = 9(n+1)+2, because (9n+11) + (9n+1) = 3(6n+4). So a4n+6 = 9(n+1)+3. We cannot have a4n+8 = 9(n+1)+5, because (9n+14) + 7 = 3(3n+7) and 3n+7 = 1 mod 3. We cannot have a4n+8 = 9(n+1)+6, because (9n+15) + (9n+15) = 3(6n+10) and 6n+10 = 1 mod 3. So the result holds for n+1 and hence for all n.
Thus a1998 = a4·499+2 = 9·499+3 = 4494.
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2002