Define a sequence $latex a_0$, $latex a_1$, $latex a_2$, $latex \ldots$ of integers as follows:

$latex a_0=0$, and given $latex a_0$, $latex a_1$, $latex a_2$, $latex \ldots$, $latex a_n$, then $latex a_{n+1}$ is the least integer greater than $latex a_n$ such that no three distinct terms (not necessarily consecutive) of $latex a_0$, $latex a_1$, $latex a_2$, $latex \ldots$, $latex a_{n+1}$ are in arithmetic progression. (This means that for no $latex 0\leq i < j < k \leq n+1$ do we have $latex a_j – a_i = a_k – a_j$.)

Find a simple rule for determining $latex a_n$. For instance, what is $latex a_{1000000}$? The sequence begins $latex 0$, $latex 1$, $latex 3$, $latex 4$, $latex 9$, $latex 10$, $latex 12$, $latex \ldots$.

Due day is May 3.