The sequence a0a1, a2, ... of non-negative integers is defined as follows. The first p-1 terms are 0, 1, 2, 3, ... , p-2. Then an is the least positive integer so that there is no arithmetic progression of length p in the first n+1 terms. If p is an odd prime, show that an is the number obtained by writing n in base p-1, then treating the result as a number in base p. For example, if p is 5, to get the 5th term one writes 5 as 11 in base 4, then treats this as a base 5 number to get 6.
Solution
Let bn be the number obtained by writing n in base p-1 and then treating the result as a number in base p. The resulting sequence bn is all those non-negative integers whose base p representation does not have a digit p-1. We show that bn cannot contain an arithmetic progression of length p. For suppose there was such a progression with difference d. Suppose the last non-zero digit of d in base p is k. Suppose the first term of the progression has digit h in that position, then the terms of the progression have digit h, h+k, h+2k, ... h+(p-1)k mod p in that position. But these must be a complete set of residues mod p, so one of them must be p-1 mod p. So the corresponding term has a digit p-1 in this position. Contradiction.
Now to show that an = bn we use induction on n. Evidently, it is true for n < p-1. Suppose it is true for all m < n. It is sufficient to show that if bn < m < bn+1, then {b1, b2, ... , bn, m} contains an arithmetic progression. m must contain a digit p-1, for otherwise it would be bk for some k > n. Let m1 be the number obtained from m by reducing every digit p-1 in m by 1. Then m has no digit p-1s, so it must be some bk and hence one of b1, ... , bn. Now take m2 to be the number obtained by reducing the same digits by another 1. Similarly, define m3, ... , mp-1. Then each mi is in {b1, ... , bn} and mp-1, ... , m1, m is a progression of length p.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002