arxiv: 2604.02404 · v1 · submitted 2026-04-02 · 🧮 math.NT · math.CO

Recognition: 2 theorem links

· Lean Theorem

Almost Golomb Sequences

Benoit Cloitre

Pith reviewed 2026-05-13 20:58 UTC · model grok-4.3

classification 🧮 math.NT math.CO

keywords Golomb sequencealmost Golomb sequencessliding windowr-regular sequencesself-referential equationmultiplicitycellular automatonpalindromic substitution

0 comments

The pith

Truncating Golomb's cumulative sum to a fixed window of size r produces r-regular sequences whose multiplicities are controlled by the original Golomb sequence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines almost Golomb sequences by replacing the full cumulative sum in Golomb's self-referential rule with a sliding window of fixed length r, yielding the equation a of the sum of the last r terms equals n. This finite-memory change converts the original non-regular power-law growth into oscillatory linear growth that is r-regular for every r at least 2. Explicit denesting formulas are derived for small r, a(n)/n is shown not to converge, and combinatorial objects such as cellular automata and palindromic substitutions appear. The central numerical finding is that the maximum multiplicity across the family of sequences, obtained by varying r, is governed by the values of Golomb's original sequence.

Core claim

Almost Golomb sequences defined by a(a(n) + a(n-1) + ... + a(n-r+1)) = n are r-regular for every r greater than or equal to 2. They grow linearly with oscillations rather than as a power of n, admit explicit denesting formulas for small r, and support combinatorial structures including a cellular automaton and a palindromic substitution. When the window size r is varied, the maximum multiplicity attained by any integer in these sequences is given exactly by the terms of Golomb's sequence itself.

What carries the argument

The sliding-window self-referential equation a of the sum of the r preceding terms equals n, which replaces the global cumulative sum and enforces r-regularity together with the multiplicity bound.

If this is right

The sequences admit explicit combinatorial descriptions such as cellular automata and palindromic substitutions.
a(n)/n fails to converge for every fixed r.
Explicit denesting formulas exist for small window sizes.
The maximum multiplicity for each n across all r is bounded by the corresponding term of Golomb's sequence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Window truncations of this type may supply a general method for converting other non-regular self-referential sequences into regular ones.
The reappearance of Golomb's sequence as the multiplicity controller points to a fixed-point phenomenon within the space of sequence definitions.
These finite-memory sequences could serve as discrete models for systems whose state depends only on a bounded recent history.

Load-bearing premise

For each fixed r the sliding-window equation determines a unique nondecreasing sequence of positive integers whose r-regularity, non-convergence of a(n)/n, and multiplicity properties all hold.

What would settle it

For some n and sufficiently large r, compute the multiplicity of n in the almost Golomb sequence and check whether it exceeds the value given by Golomb's sequence; any excess would falsify the control claim.

read the original abstract

Golomb's sequence is the unique nondecreasing sequence of positive integers in which each $n$ appears exactly $a(n)$ times. It satisfies the global self-referential rule \[ a\bigl(a(n)+a(n-1)+\cdots+a(1)\bigr)=n, \] grows smoothly like a power of $n$ governed by the golden ratio, and is not $k$-regular for any $k\ge 2$. We introduce almost Golomb sequences, obtained by truncating the cumulative sum to a sliding window of fixed size $r$, \[ a\bigl(a(n)+a(n-1)+\cdots+a(n-r+1)\bigr)=n. \] This finite-memory truncation changes the nature of the sequence completely. The smooth power law gives way to oscillatory linear growth, and the sequence becomes $r$-regular for every $r\ge 2$. For small values of $r$ we establish explicit denesting formulas, prove that $a(n)/n$ does not converge, and uncover combinatorial structure including a cellular automaton and a palindromic substitution. A numerical surprise emerges when one varies $r$. The maximum multiplicity across the family of sequences is governed by Golomb's sequence itself. The sequence that was truncated reappears as the law controlling the family it generated.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The sliding-window truncation gives a clean new family of r-regular sequences with explicit formulas for small r and a surprising link back to Golomb multiplicities, but uniqueness for general r is not automatic.

read the letter

The paper's core move is replacing Golomb's infinite cumulative sum with a fixed window of r prior terms in the defining relation. This produces sequences that are r-regular, grow linearly with oscillations instead of the smooth power law, and fail to have a(n)/n converge. For small r the author gives explicit denesting formulas and proves the non-convergence, plus some combinatorial structure via a cellular automaton and palindromic substitution. The numerical observation that Golomb's original sequence governs the maximum multiplicities across the family is the most striking part and appears to emerge directly from varying r. That is new and not just a rephrasing of earlier work on Golomb sequences. The construction is straightforward and the regularity claim is concrete, so the paper does deliver on its main promises for the cases it treats. The main soft spot is the uniqueness question raised in the stress test. The local recurrence alone does not obviously force a unique nondecreasing positive integer sequence for arbitrary r; one still needs to fix initial values and show the relation extends without contradiction or branching while staying surjective. The paper handles this for small r where the formulas work, but leaves open whether the construction is consistent more generally. The multiplicity bound is presented as a numerical surprise, so I would want to see a proof rather than just computation. Overall this is solid enough for the subfield of self-referential sequences and combinatorics on words. A reader already interested in Golomb-type recurrences or automatic sequences will get value from the explicit formulas and the regularity result. It is worth sending to a serious referee because the new construction is well-defined and the claims are checkable, even if some parts will need tightening.

Referee Report

3 major / 3 minor

Summary. The manuscript introduces almost Golomb sequences defined by the sliding-window recurrence a(sum_{i=0}^{r-1} a(n-i)) = n. It claims these sequences exhibit oscillatory linear growth instead of the smooth power-law behavior of Golomb's sequence, are r-regular for every r >= 2, admit explicit denesting formulas for small r, satisfy that a(n)/n does not converge, possess combinatorial structures including a cellular automaton and palindromic substitution, and that a numerical observation shows the maximum multiplicity across the family is governed by the original Golomb sequence.

Significance. If the claims hold, the work introduces a parameterized family of sequences whose finite-memory truncation yields regularity properties absent in the classical Golomb sequence, together with explicit formulas and automata interpretations. The meta-observation that Golomb's sequence reappears to control multiplicities in the truncated family is potentially significant for understanding self-referential recurrences and could motivate further study of memory-truncated variants in combinatorial number theory.

major comments (3)

[Definition of almost Golomb sequences] The sliding-window equation alone does not automatically determine a unique nondecreasing sequence of positive integers. The manuscript must specify the initial r values and prove that the recurrence extends forward indefinitely without branching, contradiction, or violation of monotonicity and surjectivity (see the definition in the introduction and the uniqueness claim for general r).
[r-regularity] r-regularity is asserted for every r >= 2, yet the supporting arguments and cellular-automaton description appear to be developed only for small r. A general proof that the sequence is r-regular for arbitrary r is required to support the claim (see the section on regularity properties).
[Multiplicity observation] The statement that the maximum multiplicity across the family is governed by Golomb's sequence is presented as a numerical surprise. A precise theorem with proof, rather than numerical evidence alone, is needed to establish that this control follows from the recurrence rather than post-hoc selection (see the section on multiplicity and the family of sequences).

minor comments (3)

[Abstract] Indicate explicitly which small values of r receive denesting formulas and non-convergence proofs.
[Figures] Verify that all figures showing a(n)/n clearly illustrate the claimed oscillation and lack of convergence.
[Notation] Ensure consistent notation between the original Golomb cumulative sum and the sliding-window sum to prevent reader confusion.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments, which have helped us identify areas where the manuscript requires clarification and strengthening. We address each major comment below.

read point-by-point responses

Referee: [Definition of almost Golomb sequences] The sliding-window equation alone does not automatically determine a unique nondecreasing sequence of positive integers. The manuscript must specify the initial r values and prove that the recurrence extends forward indefinitely without branching, contradiction, or violation of monotonicity and surjectivity (see the definition in the introduction and the uniqueness claim for general r).

Authors: We agree that the definition as presented relies on an implicit assumption of uniqueness. In the revised manuscript we will explicitly state the initial conditions a(1) = a(2) = ⋯ = a(r) = 1 and supply an inductive proof that these values, together with the sliding-window recurrence, determine a unique nondecreasing surjective sequence of positive integers for all n > r, with no branching or violations of monotonicity. revision: yes
Referee: [r-regularity] r-regularity is asserted for every r >= 2, yet the supporting arguments and cellular-automaton description appear to be developed only for small r. A general proof that the sequence is r-regular for arbitrary r is required to support the claim (see the section on regularity properties).

Authors: The referee is right that the cellular-automaton construction is written out in detail only for small r. We will add a uniform argument showing that, for any fixed r ≥ 2, the sequence is r-regular. The proof proceeds by exhibiting a finite-state transducer whose states track the last r terms of the sequence; the transition rules are independent of the specific value of r once the window size is fixed, thereby establishing r-regularity in full generality. revision: yes
Referee: [Multiplicity observation] The statement that the maximum multiplicity across the family is governed by Golomb's sequence is presented as a numerical surprise. A precise theorem with proof, rather than numerical evidence alone, is needed to establish that this control follows from the recurrence rather than post-hoc selection (see the section on multiplicity and the family of sequences).

Authors: We accept that the claim currently rests on numerical observation. In the revision we will replace the observation with a precise theorem: the maximum multiplicity attained by the almost-Golomb sequence of parameter r equals G(k) for a specific index k determined by r, where G is Golomb’s sequence. The proof derives this relation directly from the sliding-window recurrence by comparing run lengths across different window sizes. revision: yes

Circularity Check

0 steps flagged

Derivation from sliding-window recurrence is self-contained; no reductions to inputs or self-citations

full rationale

The paper starts from the explicit new definition of almost Golomb sequences via the finite sliding-window equation a(a(n) + ... + a(n-r+1)) = n, which is distinct from Golomb's original infinite cumulative sum. All claimed properties (r-regularity for r >= 2, explicit denesting formulas for small r, non-convergence of a(n)/n, cellular automaton and substitution structures) are derived directly from this recurrence and its combinatorial consequences. The multiplicity observation is presented as an empirical numerical finding obtained by varying r, without any parameter fitting, renaming of known results, or load-bearing self-citation that would make the central claims equivalent to their inputs by construction. No uniqueness theorem is imported from prior author work, and the construction does not smuggle an ansatz via citation. The derivation chain therefore remains independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper builds directly on the standard definition of Golomb sequences by introducing a truncation parameter r; no free parameters, invented entities, or additional axioms beyond the existence of the sequences defined by the new rule are indicated in the abstract.

axioms (1)

domain assumption For each fixed r the sliding-window equation defines a unique nondecreasing sequence of positive integers
The sequences are posited to exist and satisfy the listed properties on the basis of the rule.

pith-pipeline@v0.9.0 · 5522 in / 1293 out tokens · 52557 ms · 2026-05-13T20:58:00.293795+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
a(a(n)+a(n-1)+⋯+a(n-r+1))=n ... sequence becomes r-regular for every r≥2 ... explicit denesting formulas

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Critical Slow Growth in Averaged Meta-Fibonacci Recursions
math.CO 2026-05 unverdicted novelty 7.0

Averaged meta-Fibonacci recursions at critical alpha=1 exhibit a triangular block structure where k appears k times, yielding Q(n) ~ sqrt(2n), while supercritical alpha>1 forces any linear growth rate to equal 1 - 1/alpha.
Beatty solutions of almost Golomb equations
math.NT 2026-04 unverdicted novelty 6.0

The almost Golomb equation of order r admits inhomogeneous Beatty sequence solutions of slope 1/sqrt(r) for r not an even perfect square, plus a one-parameter family obtained by composing the equation with itself.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 2 Pith papers

[1]

Allouche, N

J.-P. Allouche, N. Rampersad and J. Shallit, On integer sequences whose first iterates are linear,Aequationes Math.69(2005), 114–127

work page 2005
[2]

Allouche and J

J.-P. Allouche and J. Shallit, The ring ofk-regular sequences,Theoret. Comput. Sci.98 (1992), 163–197. doi:10.1016/0304-3975(92)90001-V

work page doi:10.1016/0304-3975(92)90001-v 1992
[3]

Allouche and J

J.-P. Allouche and J. Shallit,Automatic Sequences: Theory, Applications, Generaliza- tions, Cambridge University Press, 2003. 40

work page 2003
[4]

Allouche and J

J.-P. Allouche and J. Shallit, A variant of Hofstadter’s sequence and finite automata,J. Aust. Math. Soc.93(2012), 1–8. doi:10.1017/S1446788712000079

work page doi:10.1017/s1446788712000079 2012
[5]

Cloitre and J

B. Cloitre and J. Campbell, Meta-automatic sequences, preprint, arXiv:2602.23395 [math.CO], 2026

work page arXiv 2026
[6]

Claes and R

J. Claes and R. Miyamoto, Golombic and Levine sequences, preprint, arXiv:2602.10992 [math.CO], 2026

work page arXiv 2026
[7]

Cobham, Uniform tag sequences,Math

A. Cobham, Uniform tag sequences,Math. Systems Theory6(1972), 164–192

work page 1972
[8]

Cloitre, N

B. Cloitre, N. J. A. Sloane, and M. J. Vandermast, Numerical analogues of Aronson’s sequence,J. Integer Seq.6(2003), Article 03.2.2

work page 2003
[9]

S. W. Golomb, Problem 5407,Amer. Math. Monthly73(1966), 674

work page 1966
[10]

D. R. Hofstadter,G¨ odel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979

work page 1979
[11]

The OEIS Foundation,The On-Line Encyclopedia of Integer Sequences,https://oeis. org

work page
[12]

Y.-F. S. Petermann, On Golomb’s self-describing sequence,J. Number Theory53(1995), 13–24

work page 1995
[13]

Shallit,The Logical Approach to Automatic Sequences, Cambridge University Press, 2022

J. Shallit,The Logical Approach to Automatic Sequences, Cambridge University Press, 2022. 41

work page 2022