USAMO 1995 Problem 1

The sequence $\mathrm{a}_{0} \mathrm{a}_{1}, \mathrm{a}_{2}, \ldots$ of non-negative integers is defined as follows. The first $\mathrm{p}-1$ terms are $0,1,2,3, \ldots$, $p-2$. Then $a_{n}$ is the least positive integer so that there is no arithmetic progression of length $p$ in the first $\mathrm{n}+1$ terms. If $\mathrm{p}$ is an odd prime, show that $\mathrm{a}_{\mathrm{n}}$ is the number obtained by writing $\mathrm{n}$ in base $\mathrm{p}-1$, then treating the result as a number in base p. For example, if p is 5 , to get the 5 th term one writes 5 as 11 in base 4 , then treats this as a base 5 number to get 6 .