Problem 271

../

claims/: The 2 claim pages of Problem 271, one per claimant's result; the problem's standing derives from them.

---

Statement. Let $A(n)=\{a_0<a_1<\cdots\}$ be the sequence defined by $a_0=0$ and $a_1=n$, and for $k\geq 1$ define $a_{k+1}$ as the least positive 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?

Formulation. The notation $a_0<a_1<\cdots$ makes the sequence increasing, so $a_{k+1}$ is read as the least integer greater than $a_k$ for which $\{a_0,\ldots,a_{k+1}\}$ contains no three-term arithmetic progression, as [OdSt78] defines it. Read as the site words it, the rule can pick a repeated term or one below $a_k$: for $n=1$ it gives $a_2=1$.

Status. Open, the site's label (OPEN; page last edited 20 January 2026). The site's commentary credits Odlyzko and Stanley [OdSt78] with explicit descriptions of $A(3^m)$ and $A(2\cdot3^m)$ for every $m\ge0$, which answer both questions for those $n$; the memorandum states them without proof, and they are recorded as a claimed partial claim on its claim page. Rolnick proved them for $m\ge1$, with growth of order $k^{\log_23}$, in a refereed paper, recorded as an accepted partial claim on his claim page. Moy's bound $a_k\le(1/2+\epsilon)k^2$ [Mo11] holds for every $n$ and fixes no sequence's growth, so it settles no instance and has no claim page. For every other $n$ both questions are open.

Source. erdosproblems.com/271, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #271, https://www.erdosproblems.com/271.

References.

• [Li90] S. Lindhurst, An investigation of several interesting sets of numbers generated by the greedy algorithm. Senior thesis at Princeton University (1990).
• [Mo11] Moy, Richard A., On the growth of the counting function of Stanley sequences. Discrete Math. (2011), 560-562.
• [OdSt78] A. Odlyzko and R. Stanley, Some curious sequences constructed with the greedy algorithm. Bell Laboratories internal memorandum (1978).

Formalization. None recorded.

Current assessment

The site formulation asks, for the greedy sequence $A(n)$ with $a_0=0$ and $a_1=n$, whether the $a_k$ can be explicitly determined and how fast they grow; the Formulation above records the increasing reading of the greedy rule, which is the one every source uses, and the standing answers the site's wording in that reading. The site labels the problem OPEN (page last edited 20 January 2026). Sequences that start from a finite progression-free set and continue greedily are called Stanley sequences, and $A(n)$ is the Stanley sequence $S(0,n)$.

Regular values. For $n=3^m$ and $n=2\cdot3^m$ the members of $A(n)$ are described by their ternary digits, and $a_k$ is of order $k^{\log_23}$, with $\liminf a_k/k^{\log_23}=1/2$ and $\limsup a_k/k^{\log_23}=1$: stated without proof by Odlyzko and Stanley [OdSt78] (card; claim page Odlyzko and Stanley 1978), and proved for $m\ge1$ by Rolnick (European J. Combin. 59 (2017), 51--70; claim page Rolnick 2017), whose Theorem 1.2 covers these sequences as the simplest members of a class of independent Stanley sequences and whose Corollary 2.9 gives every regular Stanley sequence growth of order $k^{\log_23}$. The case $n=1$ is the sequence of integers with no digit $2$ in base $3$, as the site notes.

Irregular values. For every other $n$ no explicit description is known. Odlyzko and Stanley conjectured that each such sequence grows like $k^2/\log k$, on a probabilistic heuristic and a table of values; no sequence is proved to grow at that rate. Lindhurst [Li90] gives data suggesting that $A(4)$ (OEIS A005487) does. Rolnick's paper proposes a definition of regularity by local structure, proves that regular sequences have the first growth rate, and conjectures that the irregular ones have the second.

Bounds for every $n$. Moy [Mo11] (card) proved that every Stanley sequence has counting function at least $(\sqrt2-\epsilon)\sqrt x$ for large $x$, so $a_k\le(1/2+\epsilon)k^2$ for all large $k$; the site's commentary adds that comments on its thread sharpen the argument to the explicit bound $a_k\le(k-1)(k+2)/2+n$ for every $k\ge0$. These bounds fix no sequence's growth, so they settle no instance and have no claim page; the thread comments are not a dated manuscript.

Search scope, 2026-10-07: the site's page and commentary (last edited 20 January 2026), the community database (the problem recorded as unformalized, with the OEIS entry A005487), the formal-conjectures catalog (no statement file for the problem) and the arXiv and Crossref records of Rolnick's paper. No proof claim is recorded for the problem. Remaining gaps: an explicit description or the growth rate of $A(n)$ for any $n$ other than $3^m$ and $2\cdot3^m$, and a proof of the conjectured $k^2/\log k$ growth for any sequence; no proof has been compiled or independently reviewed by this corpus.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• moy_2011_growth_counting_function_stanley_sequences
• moy_2011_growth_counting_function_stanley_sequences / lemma_2_4
• moy_2011_growth_counting_function_stanley_sequences / theorem_1_1
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm / definition_p1
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm / heuristic_p3
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm / remark_2
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm / theorem_1
• odlyzko_1978_curious_sequences_constructed_greedy_algorithm / theorem_2