← All problems

Erdős Problem #271 — Growth of Stanley sequences

Let nn be a positive integer. Define the increasing sequence A(n)={a0<a1<⋯ }A(n)=\{a_0<a_1<\cdots\} by a0=0a_0=0 and a1=na_1=n. For each k≥1k\geq 1, choose the least integer greater than aka_k whose addition preserves the absence of three-term arithmetic progressions: Erdős Problem #271 On the Growth of the Counting Function of Stanley Sequences

ak+1=min⁡{m∈Z:m>ak, {a0,…,ak,m} contains no three-term arithmetic progression}.a_{k+1}=\min\bigl\{m\in\mathbb Z:m>a_k,\ \{a_0,\ldots,a_k,m\}\text{ contains no three-term arithmetic progression}\bigr\}.

Here a three-term arithmetic progression consists of three distinct integers x<y<zx<y<z with x+z=2yx+z=2y. The question is whether the terms aka_k can be determined explicitly and how they grow as k→∞k\to\infty. The condition m>akm>a_k makes explicit the increasing-order requirement in the definition. Erdős Problem #271

Background

This greedy construction is a Stanley sequence: one starts from a finite set with no three-term arithmetic progression and repeatedly adjoins the least larger integer that preserves this property. Odlyzko and Stanley introduced these sequences; Erdős and collaborators later studied them and posed questions about their growth. The initial pair {0,n}\{0,n\} is a simple family of starting sets within this broader construction. On the Growth of the Counting Function of Stanley Sequences

Some starting pairs produce highly structured sequences. For n=1n=1, A(1)A(1) consists exactly of the nonnegative integers whose base-33 expansions contain no digit 22. Odlyzko and Stanley also found related characterizations for the starting pairs {0,3r}\{0,3^r\} and {0,2⋅3r}\{0,2\cdot 3^r\}, where r≥0r\geq 0. These examples underlie the contrast between regular, relatively slow-growing sequences and the less understood irregular cases. Erdős Problem #271 On the growth of Stanley sequences

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.