Erdős #271 · additive combinatorics / arithmetic progressions

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

or

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

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.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.