Problem Statement
For any $n$, let $A(n)=\{0<n<\cdots\}$ be the infinite sequence with $a_0=0$ and $a_1=n$, and for $k\geq 1$ we define $a_{k+1}$ as the least integer such that there is no three-term arithmetic progression in $\{a_0,\ldots,a_{k+1}\}$.
Can the $a_k$ be explicitly determined? How fast do they grow?
Can the $a_k$ be explicitly determined? How fast do they grow?
Categories:
Additive Combinatorics Arithmetic Progressions
Progress
It is easy to see that $A(1)$ is the set of integers which have no 2 in their base 3 expansion. Odlyzko and Stanley [OdSt78] have found similar characterisations are known for $A(3^k)$ and $A(2\cdot 3^k)$ for any $k\geq 0$ and conjectured in general that such a sequence always eventually either satisfies\[a_k\asymp k^{\log_23}\]or\[a_k \asymp \frac{k^2}{\log k}.\]There is no known sequence which satisfies the second growth rate, but Lindhurst [Li90] gives data which suggests that $A(4)$ has such growth ($A(4)$ is given as A005487 in the OEIS).Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$. van Doorn and Sothanaphan have noted in the comment section that Moy's proof can be upgraded to give a fully explicit result of\[a_k\leq \frac{(k-1)(k+2)}{2}+n\]for all $k\geq 0$.
In general, sequences which begin with some initial segment and thereafter are continued in a greedy fashion to avoid three-term arithmetic progressions are known as Stanley sequences.
Source: erdosproblems.com/271 | Last verified: January 14, 2026