The Prefix Conjecture for almost Golomb sequences

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.