Erdős Problem #271

Erdős Problem 271 --- Round 2

1) ROUND-2 OBJECTIVE

Path (C): the general problem is still open, so the most promising strict advance is to correct the Round 1 computational slip, then extend the fully explicit theory from $A(1)$ to the next nontrivial seed $A(2)$ by a complete proof. This adds a genuinely new explicit family beyond Round 1.

2) Round-1 FOUNDATION USED

From Round 1 I use only the following established facts.

• $A(1)$ is exactly the set $S$ of nonnegative integers whose base-$3$ expansion uses only the digits $0$ and $1$.
• The key representation lemma for $S$: for every integer $u\ge 0$ there exist $a,b\in S$ with \[ u=2b-a, \] and if $u\notin S$ then one may choose $b<u$.
• The growth of $A(1)$ is $a_k=\Theta(k^{\log_2 3})$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new object is \[ T:=3S\cup(3S+2). \] Equivalently, $T$ is the set of nonnegative integers whose ternary expansion has digits $0$ or $1$ in every position except the units digit, which is allowed to be $0$ or $2$.

The Round-2 claim is that \[ A(2)=T. \] This yields an explicit binary-to-ternary formula and an exact two-line recursion for the sequence generated by $\{0,2\}$.

4) ATTACK PLAN (ROUND-2)

There were two Round 1 gaps relevant here.

• The small illustrative sample for $A(4)$ in Round 1 was computational only, and needed verification.
• No seed beyond $n=1$ had been treated explicitly.

The plan is therefore:

• first correct the $A(4)$ sample by direct greedy checking;
• then prove that $T=3S\cup(3S+2)$ is 3-free;
• finally show that every integer $m>2$ outside $T$ is rejected by the greedy algorithm because it completes a 3-term progression with earlier elements of $T$.

5) WORK (ROUND-2)

Round-2 correction of the Round-1 sample.

The Round 1 sample for $A(4)$ was incorrect. The correct initial segment is \[ A(4):\ 0,4,5,7,11,12,16,23,26,31,33,37,38,44,49,56,\dots \] A quick check already shows why $6$ could not have appeared: after choosing $0,4,5$, the candidate $6$ completes the arithmetic progression $4,5,6$ and must be rejected.

This correction affects only the heuristic illustration from Round 1; none of the actual theorems from Round 1 depended on the erroneous list.

Theorem 5.1.

Let $S=A(1)$, and define \[ T:=3S\cup(3S+2). \] Then the Stanley sequence generated by $\{0,2\}$ is exactly $T$.

Proof. We first show that $T$ is 3-free.

Suppose $x<y<z$ lie in $T$ and satisfy $x+z=2y$. Reduce modulo $3$.

• If $x\equiv z\equiv 0\pmod 3$, then also $y\equiv 0\pmod 3$, so \[ x=3x',\quad y=3y',\quad z=3z' \] with $x',y',z'\in S$, and then $x'+z'=2y'$, contradicting the 3-freeness of $S$.

• If $x\equiv z\equiv 2\pmod 3$, then also $y\equiv 2\pmod 3$, so \[ x=3x'+2,\quad y=3y'+2,\quad z=3z'+2 \] with $x',y',z'\in S$, and again $x'+z'=2y'$, contradiction.

• If $x\equiv 0\pmod 3$ and $z\equiv 2\pmod 3$ (or vice versa), then \[ x+z\equiv 2\pmod 3, \] so $2y\equiv 2\pmod 3$, hence $y\equiv 1\pmod 3$, impossible because every element of $T$ is congruent to $0$ or $2$ modulo $3$.

Thus $T$ contains no nontrivial 3-term arithmetic progression.

Now let $m>2$ be an integer with $m\notin T$. We show that $m$ is rejected by the greedy algorithm for seed $\{0,2\}$. There are three residue classes modulo $3$.

Case 1: $m\equiv 0\pmod 3$. Write $m=3u$. Since $m\notin T$, we have $u\notin S$. By the Round 1 representation lemma for $S$, there exist $a,b\in S$ with \[ u=2b-a, \qquad b<u. \] Then \[ m=3u=2(3b)-3a. \] Both $3a$ and $3b$ lie in $T$, and $3b<m$ because $b<u$. Hence $m$ completes a 3-term progression with earlier elements of $T$.

Case 2: $m\equiv 2\pmod 3$. Write $m=3u+2$. Since $m\notin T$, again $u\notin S$. Choose $a,b\in S$ with $u=2b-a$ and $b<u$. Then \[ m=3u+2=2(3b+2)-(3a+2). \] Now $3a+2,3b+2\in T$, and $3b+2<m$ because $b<u$. So $m$ is rejected.

Case 3: $m\equiv 1\pmod 3$. Write $m=3u+1$. Since $m>2$, we have $u\ge 1$. Apply the Round 1 representation lemma to $u-1$: choose $a,b\in S$ with \[ u-1=2b-a, \qquad b\le u-1. \] Then \[ m=3u+1=3(u-1)+4=2(3b+2)-3a. \] Again $3a\in T$ and $3b+2\in T$, while \[ 3b+2\le 3(u-1)+2=3u-1<m. \] So $m$ is rejected.

Therefore every integer $m>2$ outside $T$ is rejected, while every integer in $T$ is accepted because $T$ is 3-free. Since the seed is $\{0,2\}$, the greedy sequence is exactly $T$.

Corollary 5.2 (explicit formula for $A(2)$).

Let \[ A(2)=\{b_0<b_1<b_2<\cdots\}. \] If \[ k=\sum_{i\ge 0}\varepsilon_i 2^i \qquad (\varepsilon_i\in\{0,1\}) \] is the binary expansion of $k$, then \[ b_k=2\varepsilon_0+\sum_{i\ge 1}\varepsilon_i 3^i. \] Equivalently, if $A(1)=\{a_0<a_1<a_2<\cdots\}$, then \[ b_{2m}=3a_m, \qquad b_{2m+1}=3a_m+2. \]

Proof. The set $T=3S\cup(3S+2)$ is the disjoint union of two increasing translates of $S$, and for every $s\in S$ we have \[ 3s<3s+2<3s' \qquad\text{whenever } s'\ge s+1. \] Hence the increasing enumeration of $T$ interleaves as \[ 3a_0,\ 3a_0+2,\ 3a_1,\ 3a_1+2,\ 3a_2,\ 3a_2+2,\dots, \] which is exactly the stated recursion. Rewriting this in terms of the binary digits of $k$ gives the explicit formula.

Corollary 5.3 (growth of $A(2)$).

The sequence $A(2)$ satisfies \[ b_k=\Theta(k^{\log_2 3}). \]

Proof. From Corollary 5.2, \[ b_{2m}=3a_m, \qquad b_{2m+1}=3a_m+2. \] Since Round 1 proved $a_m=\Theta(m^{\log_2 3})$, the same asymptotic follows immediately for $b_k$.

6) ADVERSARIAL VERIFICATION

• The correction of the $A(4)$ sample is genuine: the earlier list was wrong, but only in a heuristic example, not in any proved statement.
• In the proof of Theorem 5.1, the only nontrivial imported fact is the Round 1 representation lemma for $S=A(1)$. I used it exactly in the two forms already proved there: for $u\notin S$, one may choose $u=2b-a$ with $b<u$; and for arbitrary $u\ge 0$, one may choose $u=2b-a$ with $b\le u$.
• The residue-$1$ case is the delicate one. The formula \[ 3u+1=2(3b+2)-3a \] requires a representation of $u-1$, not of $u$. This was checked explicitly; the inequality $3b+2<m$ follows from $b\le u-1$.
• The proof is self-contained once Round 1 is accepted.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED)

Round 2 corrects the faulty $A(4)$ sample and gives a full explicit determination of $A(2)$, including the exact recursion \[ b_{2m}=3a_m, \qquad b_{2m+1}=3a_m+2, \] and the growth law $A(2)=\Theta(k^{\log_2 3})$. The general problem for arbitrary $n$ remains open.

8) COMPLETION ESTIMATE

COMPLETION: 65%

9) REFERENCES

• A. M. Odlyzko and R. P. Stanley, Some Curious Sequences Constructed with the Greedy Algorithm, January 1978. Checked in this round for the classical regular/irregular context and the corrected initial examples.
• T. F. Bloom, Erdős Problem #271, checked 2026-03-07.

Problem 271: sharp oscillation bounds for the regular seed

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read all of 271.tex, which identifies the greedy progression-free sequence from $\{0,2\}$ and leaves the general seed $\{0,n\}$ unexplained. Its description of that regular case as a new family needs qualification: the primary 1978 Odlyzko--Stanley paper already describes regular seeds and states their limiting oscillation. I give a direct proof of that oscillation for the two smallest seeds. This is a verification and sharpening of the supplied exposition, not a new literature result or a classification of arbitrary seeds.

2) WORK

Let $a_k$ be obtained by reading the binary digits of $k$ in base three, with $a_0=0$, and put $\alpha=\log_2 3$. Then \[ a_{2m}=3a_m,\qquad a_{2m+1}=3a_m+1. \] The following pointwise bounds hold for every integer $k\ge0$: \[ \frac{(k+1)^\alpha-1}{2}\le a_k\le k^\alpha. \] Prove them simultaneously by induction. For the upper bound, the even step is exact; the odd step follows from $3m^\alpha+1\le(2m+1)^\alpha$. The difference on the right minus the left vanishes at $m=0$ and has nonnegative derivative, because $2(2m+1)^{\alpha-1}\ge3m^{\alpha-1}$. For the lower bound the odd step is exact, while the even step uses \[ 3(m+1)^\alpha-(2m+1)^\alpha\ge2. \] This expression equals $2$ at zero and increases: $2(2m+1)^{\alpha-1}\le3(m+1)^{\alpha-1}$.

At $k=2^r$, $a_k=3^r$; at $k=2^r-1$, $a_k=(3^r-1)/2$. The bounds and these two subsequences give \[ \liminf_{k\to\infty}\frac{a_k}{k^\alpha}=\frac12, \qquad \limsup_{k\to\infty}\frac{a_k}{k^\alpha}=1. \] For the seed $\{0,2\}$, the supplied digit characterization gives $b_k=a_k+(k\bmod2)$. Its difference from $a_k$ is bounded, so precisely the same two limits follow. In particular there is no asymptotic equivalence $b_k\sim c k^\alpha$ for any constant $c$, despite the valid two-sided order bound.

3) ADVERSARIAL VERIFICATION

The induction includes $k=0$ and uses zero-based indexing consistently. The digit characterization of the supplied sequence is compatible with the classical theorem. No finite irregular-seed sample can establish a growth law for that seed. The oscillation calculation explains why replacing a $\Theta$ statement by an assumed leading constant would already fail in the simplest regular examples.

4) FINAL

UNRESOLVED. The regular-seed asymptotics are verified sharply, but they were already known. No verified advance toward determining the general seed's behavior is obtained here.

5) SOURCES CHECKED

The complete supplied version; A. M. Odlyzko and R. P. Stanley, Some Curious Sequences Constructed with the Greedy Algorithm $1978$, Theorems 1--2 and Remark 2, https://math.mit.edu/~rstan/papers/od.pdf, checked 2026-09-23.

6) COMPLETION ESTIMATE

Subjective progress toward the general-seed problem. COMPLETION: 8%

Problem 271

Problem statement (as given)

For $n$ a positive integer, let $A(n)$ be the Stanley sequence generated by $\{0,n\}$. Can $a_k$ be explicitly determined? How fast do they grow?

1. Formal restatement

Fix $n\in\mathbb{N}$. Define the Stanley sequence $A(n)=(a_k)_{k\ge 0}$ by: \[ a_0=0,\qquad a_1=n, \] and for $k\ge 1$, $a_{k+1}$ is the smallest integer $>a_k$ such that the set \[ \{a_0,a_1,\dots,a_k,a_{k+1}\} \] contains no nontrivial 3-term arithmetic progression, i.e. no distinct $x<y<z$ with $y-x=z-y$.

Questions:

• Can we write a closed form for $a_k$ (for general $n$)?
• What is the asymptotic growth of $a_k$ as $k\to\infty$ (depending on $n$)?

2. Quick literature/context check

The Erdős Problems Project lists this as open in general and summarizes known structure for some special $n$ (e.g. $n=1$, and more generally $n=3^k$ and $n=2\cdot 3^k$) going back to Odlyzko--Stanley and others. % citeturn1view1

There is an extensive modern literature on Stanley sequences; for example, a 2025 preprint studies "irregular" behavior of Stanley sequences beyond the well-structured cases. % citeturn21view0

3. Attack plan

1. Compute small examples to see patterns (especially $n=1$ versusS$0,1$ and a "generic" $n$ like $4$).
2. Prove what can be proved cleanly:
   • an explicit description and growth rate for $A(1)$;
   • a general, elementary upper bound $a_k \le n + O(k^2)$ valid for all $n$.
3. Compare with the conjectural dichotomy "structured" vs "irregular" Stanley sequences (but not attempt to resolve the full open problem).

4. Work

4.1 Small-case computation

For $n=1$, the greedy sequence begins \[ A(1):\ 0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,\dots \] For $n=4$, it begins \[ A(4):\ 0,4,5,6,9,11,13,14,15,19,20,22,23,24,29,\dots \] The $n=1$ case is highly structured; $n=4$ already looks less obviously structured.

4.2 Explicit determination of $A(1)$ (complete)

Let \[ S:=\left\{\sum_{i\ge 0}\varepsilon_i 3^i:\ \varepsilon_i\in\{0,1\}\right\}, \] i.e. the set of nonnegative integers whose base-$3$ expansion uses only digits $0$ and $1$ (no digit $2$).

4.3 Growth rate of $A(1)$ (complete)

4.4 A general quadratic upper bound for all $n$ (complete)

5. Verification

• The proof of Theorem thm:A1 hinges on Lemma Lemma (Every integer has a "Cantor" 2-term representation). I checked the induction carefully: the key is that for $a=2$ we force $y<m$ automatically, which is what makes "digit 2" positions genuinely forbidden.
• Theorem Theorem (Elementary bound) is a clean counting argument that avoids the earlier "pairs involving the last element" overcount: any $m<a_k$ is rejected before $a_k$ is chosen, so the witness pair must come from $\{a_0,\dots,a_{k-1}\}$.
• These results do not settle the explicit structure of $A(n)$ for general $n$ (the main open part).

6. Final

UNRESOLVED.

1. Farthest-reaching partial results proved here.
   • Complete explicit description of $A(1)$ (Theorem thm:A1), and the growth $a_k=\Theta(k^{\log_2 3})$ (Corollary Corollary).
   • A uniform quadratic upper bound $a_k\le n + (k-1)(k+2)/2$ for all $n$ (Theorem Theorem (Elementary bound)).

2. Precise obstacle. For general $n$, the greedy choices depend on the evolving pattern of forbidden values $2a_j-a_i$. Unlike $n=1$ (and a few other special $n$), there is no known closed-form description of which candidates survive, and the structure can be "irregular" in ways that defeat current techniques.

3. Most promising next steps.
   • Identify additional classes of $n$ for which $A(n)$ is "regular" (self-similar / described by digital constraints), extending the known $n=3^t$ and $n=2\cdot 3^t$ families.
   • Develop invariants that detect and control irregularity (as explored in recent work). % citeturn21view0
   • Improve general bounds (both upper and lower) on $a_k$ and/or the counting function of $A(n)$, possibly with explicit constants.

4. Belief about truth value. It is plausible that most $A(n)$ are "irregular" and do not admit a simple closed form, but that there are infinitely many structured $n$ with explicit descriptions; current evidence supports a mix rather than a uniform behavior.

7. Completion estimate

\[ \textbf{55\%} \] (I gave complete proofs for $n=1$ and a strong general upper bound, but not an explicit formula or sharp growth for general $n$.)