Stanley sequences: explicit structure and growth of the greedy 3-AP-free sequences $A(n)$ (Erdős #271)
Statement
For a positive integer $n$, let $A(n)=\{a_0<a_1<\cdots\}$ be the sequence defined by $a_0=0$, $a_1=n$, and, for $k\geq 1$, $a_{k+1}$ is the least positive integer such that $\{a_0,\ldots,a_k,a_{k+1}\}$ contains no three-term arithmetic progression. Can the $a_k$ be explicitly determined? How fast do they grow?
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof — that for every $n$ either explicitly determines $A(n)$ or establishes its exact growth order; proving or refuting the Odlyzko–Stanley dichotomy stated in the background would qualify. ADVANCES: a proof of an explicit characterisation or exact growth rate of $A(n)$ for any starting value or infinite family beyond $A(3^k)$ and $A(2\cdot 3^k)$; a proof that some specific sequence (e.g. $A(4)$) has growth $a_k\asymp k^2/\log k$ — the first witness of the second regime; a proof strictly improving Moy's quadratic upper bound (or its explicit van Doorn–Sothanaphan form) stated in the background; or a computational extension: reproducible code computing $A(4)$ (and other unexplained starting values) to an index/height frontier well beyond previously published data, with a quantitative growth analysis discriminating $k^{\log_2 3}$ from $k^2/\log k$ and the raw terms delivered (e.g. as an OEIS b-file extension for A005487). Deliver the proof file, or the code + extended sequence data + growth analysis.
Background
Posed by Erdős and Graham [ErGr80, p.22]; listed as open on erdosproblems.com/271 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | arithmetic progressions'). Sequences built greedily to avoid three-term arithmetic progressions from an initial segment are known as Stanley sequences. It is classical that $A(1)$ is the set of integers with no digit $2$ in base $3$; Odlyzko and Stanley [OdSt78] found analogous explicit characterisations for $A(3^k)$ and $A(2\cdot 3^k)$ for all $k\geq 0$, and conjectured a striking dichotomy: every such sequence eventually satisfies either $$a_k\asymp k^{\log_2 3}$$ or $$a_k\asymp\frac{k^2}{\log k}.$$ No sequence is known to attain the second growth rate, but Lindhurst [Li90] gives numerical data suggesting $A(4)$ does ($A(4)$ is OEIS A005487). Moy [Mo11] proved that every such sequence satisfies $a_k\leq(\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$; van Doorn and Sothanaphan noted in the site's comments that Moy's argument upgrades to the fully explicit bound $a_k\leq\frac{(k-1)(k+2)}{2}+n$ for all $k\geq 0$. The attacker's tool: high-throughput exact computation of Stanley sequences (pushing $A(4)$ far beyond Lindhurst's 1990 data), rigorous statistical discrimination between the two conjectured growth regimes, automatic structure detection (eventual periodicity of difference patterns, base-3-like descriptions) for new starting values, and proofs of explicit characterisations for families beyond $3^k$ and $2\cdot 3^k$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #271 (T. F. Bloom) | website |
| REF-02 | OEIS A005487 — starts 0, 4 and contains no 3-term arithmetic progression (the Stanley sequence A(4)) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.