[#P2872] Infinitely many ones in the greedy three-term-progression-free sequence

A mathematical schematic of Infinitely many ones in the greedy three-term-progression-free sequence. — A statement-only illustration of the mathematical objects and operations in this problem.

Problem. Define a sequence \((a_m)_{m\ge 1}\) of positive integers recursively by \(a_1=1\), and, for each \(m\ge 2\), let \(a_m\) be the least positive integer such that \(a_{m-2k}+a_m\ne 2a_{m-k}\) for every integer \(k\) with \(1\le k\le (m-1)/2\). Is the set \(\{m\ge 1:a_m=1\}\) infinite?

1Context

The sequence is forced by a local greedy rule but displays large sparse regions. Long prefix computations are easy to duplicate, so certified occurrence lists and failed structural recurrences are useful shared artifacts.

2Problem setup

Remark 1. The recurrence is greedy in lexicographic order: at position m it chooses the smallest positive value that creates no three-term arithmetic progression in the values at equally spaced indices ending at m.

Definition 1. A three-term arithmetic progression here means indices m-2k, m-k, m together with values satisfying a_{m-2k}+a_m=2a_{m-k}; the three values need not be distinct.

3What counts as a solution

Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index.
Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list.

1Status

Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow thread remains open with zero answers, and the checked OEIS records still present the infinitude of ones as an unresolved question. No later proof or counterexample was located. Exact unresolved remainder: Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list.^[1][2][3]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 Unresolved in this packet after the dated source check. Strongest checked result: The MathOverflow thread remains open with zero answers, and the checked OEIS records still present the infinitude of ones as an unresolved question. No later proof or counterexample was located. Exact unresolved remainder: Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list.^[1][2][3] Relevance to this problem For Infinitely many ones in the greedy three-term-progression-free sequence, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: The MathOverflow thread remains open with zero answers, and the checked OEIS records still present the infinitude of ones as an unresolved question. No later proof or counterexample was located. Exact unresolved remainder: Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list. Open full record →
	Trace	Reported
attempt · Route 1 Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list.^[1] Relevance to this problem For Infinitely many ones in the greedy three-term-progression-free sequence, record grahl-sequence-infinitely-many-ones-next-route-20260801 (“Complete the stated acceptance conditions”) documents a concrete method, search boundary, or failed route. The record states: Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Work against the displayed statement and preserve every hypothesis and quantifier. Prove that for every integer N there exists m>N with a_m=1, or prove that a_m is never 1 beyond an explicit index. Any computational component must use exact integer recurrence checks and publish the verified prefix length, code revision, and a digest of the resulting occurrence list. Any computation must retain a replayable witness and a matching exclusion or completeness certificate. Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-27. The MathOverflow thread remains open with zero answers, and the checked OEIS records still present the infinitude of ones as an unresolved question. No later proof or counterexample was located.

On 2026-07-27 the Stack Exchange API reported zero answers, no accepted answer, and no closure for MathOverflow question 338415; every visible comment was checked, including the proof for a different weakly-increasing variant.
The dated search checked OEIS A229037, which defines the same greedy sequence, and OEIS A236246, which records the observed indices of the value 1. Neither entry supplied a proof of infinitude.
A TheoremDB corpus search for A229037, Grahl sequence, greedy arithmetic-progression sequence, and the exact recurrence found no existing target.
Reusable work consists of certified prefix blocks, occurrence indices, and recurrence-state summaries. Evidence for the weakly-increasing variant does not settle this sequence.
Independent source, duplicate, exact-title, and equivalent-formulation review completed on 2026-08-01.

Recorded example 1. The sequence begins 1,1,2,1,1,2,2,4,4,1, and hence the first positions carrying 1 are 1,2,4,5,10.

Computational notes

OEIS A236246 records a long prefix of the indices m for which a_m=1, but a finite list cannot decide infinitude.

2See also

Minimum avoiding alphabet for every avoidable wordcombinatorics on words
Zero density in the easily bored sequencecombinatorics on words
Least uniform modulus of an abelian-square-free morphism on four letterscombinatorics on words

How to cite

TheoremDB contributors, “Infinitely many ones in the greedy three-term-progression-free sequence,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/grahl-sequence-infinitely-many-ones

This page as plain text: grahl-sequence-infinitely-many-ones.md

This problem includes 2 records joined by 2 typed links, sourced from mathoverflow.net^[1], current as of August 1, 2026.

1References

Packet source. MathOverflow question 338415, “Infinitely many ones in the greedy three-term-progression-free sequence,” checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗forum · reference source · checked 2026-08-01Source use: original summary.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at Question 338415 and all visible comments, checked through the Stack Exchange API on 2026-07-27.Also cited at Full question, answers, and visible comments concerning Infinitely many ones in the greedy three-term-progression-free sequence; checked 2026-08-01.Also cited at Editorial research route recorded 2026-08-01.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Infinitely many ones in the greedy three-term-progression-free sequence: This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.Source named by the research packet.
OEIS Foundation Inc., entry A229037, checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Reused material: definition, terms, formulas, programs, and linked million-term tables for the forest-fire sequence.Reuse basis: fair use reviewed · rights holder: The OEIS Foundation Inc. and the credited contributors · checked 2026-08-01 by Philip Weiss, TheoremDB staff.Required attribution: OEIS Foundation Inc., entry A229037, checked 2026-08-01.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at definition, terms, formulas, programs, and linked million-term tables for the forest-fire sequence.Source used to assess the problem's recorded status.For Infinitely many ones in the greedy three-term-progression-free sequence, this source defines the exact greedy sequence and supplies reproducible prefix data.
OEIS Foundation Inc., entry A236246, checked 2026-08-01. Question statement, visible answers and comments, or the linked article sections described in the source record. ↗reference database · reference source · checked 2026-08-01Source use: original summary.Reused material: definition as indices n with A229037(n)=1, listed terms, infinitude comment, and exact programs.Reuse basis: fair use reviewed · rights holder: The OEIS Foundation Inc. and the credited contributors · checked 2026-08-01 by Philip Weiss, TheoremDB staff.Required attribution: OEIS Foundation Inc., entry A236246, checked 2026-08-01.Supports the exact formulation, the nearest published result, or the unresolved boundary recorded for this problem.Also cited at definition as indices n with A229037(n)=1, listed terms, infinitude comment, and exact programs.Source used to assess the problem's recorded status.For Infinitely many ones in the greedy three-term-progression-free sequence, this source records the exact support sequence and explicitly preserves the infinitude question.

This is an original CC0 textbook restatement motivated by the cited MathOverflow thread; no MathOverflow prose was copied.

[#P2872] Infinitely many ones in the greedy three-term-progression-free sequence

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance