Let a_r be the order-r almost Golomb sequence, defined by the sliding-window greedy recurrence in the source, and let G denote Golomb's sequence. Prefix Conjecture. For all r≥ 3, a_r(r)=G(r-1). This has been verified computationally for all r≤ 200. It asserts that the common initial prefix of the order-r sequences, evaluated at n=r, agrees with the corresponding value of Golomb's sequence; proving this boundary identity remains open.

The Prefix Conjecture for almost Golomb sequences

Less than 1 year old · traced to 2026

Let $a_r$ be the order- $r$ almost Golomb sequence, defined by the sliding-window greedy recurrence in the source, and let $G$ denote Golomb's sequence. Prefix Conjecture. For all $r\ge 3$ ,

a_r(r)=G(r-1).

This has been verified computationally for all $r\le 200$ . It asserts that the common initial prefix of the order- $r$ sequences, evaluated at $n=r$ , agrees with the corresponding value of Golomb's sequence; proving this boundary identity remains open.

References

Primary source

Benoit Cloitre, “Almost Golomb Sequences”, arXiv:2604.02404 (2026).

golomb-sequence integer-sequences

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

The conjecture has been checked through 200, and a posted but unverified argument claims a much stronger agreement result that would prove it.

Benoit Cloitre’s April 2026 preprint asks whether the order- $r$ sequence satisfies $a_r(r)=G(r-1)$ for every $r\ge 3$ . The paper presents this as open and gives no proof or counterexample.

Known results

Computational verification covers every $r\le 200$ .
The proved run-length identity $N_r(m)=a_r(m+1)-a_r(m+1-r)$ reduces a related multiplicity claim to the Prefix Conjecture.
The broader threshold law additionally requires an unproved Domination Lemma.

Posted attempt

An unverified argument claims the stronger theorem $a_r(n)=G(n-1)$ for $3\le n\le C_r$ , where $C_r=\sum_{j=1}^rG(j)$ , with the first discrepancy at $n=C_r+1$ . If correct, it proves the Prefix Conjecture and identifies the exact maximal common prefix; it has not been independently verified.

Current status (as of August 2026): The identity is computationally established for $r\le 200$ , while the all- $r$ conjecture remains mathematically unproved; a stronger posted proof claim is unverified.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

A stronger exact maximal-prefix theorem holds. Let $G$ be Golomb's sequence, and write

C_m=\sum_{j=1}^mG(j),\qquad C_0=0.

For every $r\ge3$ , the order- $r$ almost Golomb sequence satisfies

\boxed{ a_r(n)=G(n-1) \qquad(3\le n\le C_r). }

Moreover, the next term is the first discrepancy:

a_r(C_r+1)=r+1 \ne r=G(C_r).

In particular, $r\le C_r$ , so the original conjecture

a_r(r)=G(r-1)

follows immediately.

To prove the stronger assertion, write $a=a_r$ , extend $a(j)=0$ for $j\le0$ , and put

S_m=\sum_{i=0}^{r-1}a(m-i).

The established run characterization gives, for every $m\ge3$ ,

a(n)=m \quad\Longleftrightarrow\quad S_m\le n<S_{m+1}. \tag{1}

The initial values are $a(1)=1$ , $a(2)=a(3)=2$ ; thus $S_3=5$ , and $a(4)=2$ .

First, we prove by strong induction that

a(n)=G(n-1) \qquad(3\le n\le C_{r-1}+1). \tag{2}

The cases $n=3,4$ hold by the initial values. Suppose $n\ge5$ , and put

g=G(n-1).

The Golomb run boundaries are

C_{g-1}+1\le n-1\le C_g. \tag{3}

Since $n\le C_{r-1}+1$ , we have $g\le r-1$ . Also $g\ge3$ and $g+1\le n-1$ . Consequently, both windows $S_g,S_{g+1}$ are untruncated, and all entries in them are known inductively. Hence, for $m=g,g+1$ ,

S_m = \sum_{j=1}^m a(j) = 1+2+\sum_{j=3}^mG(j-1) = 2+C_{m-1}.

By (3),

S_g=C_{g-1}+2 \le n < C_g+2=S_{g+1}.

Equation (1) now gives $a(n)=g=G(n-1)$ , proving (2).

Because $C_{r-1}\ge r$ , equation (2) also gives

a(r+1)=G(r).

Therefore

S_r=2+C_{r-1},

and the next sliding window satisfies

S_{r+1} = S_r+a(r+1)-a(1) = C_r+1.

Thus the value $r$ occupies precisely the positions

C_{r-1}+2,\ldots,C_r

in $a_r$ . The shifted Golomb sequence $G(n-1)$ occupies the same positions with value $r$ , and additionally has value $r$ at $n=C_r+1$ .

Combining this with (2) proves equality throughout

3\le n\le C_r.

At $n=C_r+1=S_{r+1}$ , equation (1) gives

a_r(C_r+1)=r+1, \qquad G(C_r)=r.

Hence the agreement interval is exact, proving the conjecture and its sharp maximal-prefix strengthening.