Almost Golomb Sequences Benoît Cloitre Abstract Golomb’s sequence is the unique nondecreasing sequence of positive integers in which each n n appears exactly a ⁡ ( n ) a(n) times. It satisfies the global self-referential rule a ⁡ ( a ⁡ ( n ) + a ⁡ ( n − 1 ) + ⋯ + a ⁡ ( 1 ) ) = n , a\bigl(a(n)+a(n-1)+\cdots+a(1)\bigr)=n, grows smoothly like a power of n n governed by the golden ratio, and is not k k -regular for any k ≥ 2 k\geq 2 . We introduce almost Golomb sequences, obtained by truncating the cumulative sum to a sliding window of fixed size r r , a ⁡ ( a ⁡ ( n ) + a ⁡ ( n − 1 ) + ⋯ + a ⁡ ( n − r + 1 ) ) = n . 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 r -regular for every r ≥ 2 r\geq 2 . For small values of r r we establish explicit denesting formulas, prove that a ⁡ ( n ) / n 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 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. 2020 Mathematics Subject Classification: 11B85 (primary), 11B37, 68R15 (secondary). Keywords: self-referential sequences, Golomb’s sequence, k -regular sequences, automatic sequences, sliding-window recurrences, denesting, non-convergence. 1 Introduction 1.1 Golomb’s sequence Golomb’s sequence (a(n))_{n\geq 1} (OEIS A001462 , [ 11 ] ) is the unique nondecreasing sequence of positive integers in which the integer n appears exactly a(n) times. It begins 1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,\ldots In particular, a satisfies a\!\left(\sum_{k=1}^{n}a(k)\right)=n,\qquad n\geq 1, (1) a formulation recorded in the OEIS entry A001462 . Golomb’s sequence is one of the most studied self-referential sequences in the world of integer sequences, introduced by Golomb [ 9 ] and prominently featured by Sloane among his favourite sequences. Its asymptotic behavior is smooth: a(n)\sim\varphi^{2-\varphi}\,n^{\varphi-1},\qquad n\to\infty, (2) where \varphi=(1+\sqrt{5})/2 is the golden ratio [ 12 ] , and f\sim g means f(n)/g(n)\to 1 . Since a(n) grows like n^{\varphi-1} with irrational algebraic exponent \varphi-1\approx 0.618 , Golomb’s sequence is not k -regular for any integer k\geq 2 : if it were, its subsequences along geometric progressions (a(k^{m}))_{m\geq 0} would satisfy a linear recurrence with integer coefficients [ 2 , Theorem 2.2] , requiring the asymptotic growth factor k^{\varphi-1} to be an algebraic integer; but k^{\varphi-1} is transcendental by the Gelfond–Schneider theorem (which states that \alpha^{\beta} is transcendental whenever \alpha is algebraic, \alpha\notin\{0,1\} , and \beta is an irrational algebraic number), a contradiction. The combinatorial depth of Golomb’s sequence has recently been made explicit by Claes and Miyamoto [ 6 ] , who define the golombic operator \Gamma : given a sequence a , \Gamma(a) is the sequence whose n -th run has length a(n) (that is, value n is repeated a(n) times). They show that Golomb’s sequence is the unique fixed point of \Gamma in the class of nondecreasing sequences, establishing a rich algebraic structure. Our almost Golomb sequences occupy a different regime. They are not fixed points of \Gamma , but their run lengths are bounded (depending on r ) and the corresponding run-length sequence is r -automatic. For r=2 in particular the run lengths lie in \{1,2\} (Proposition 7.3 ). Numerically, the iterates \Gamma^{k}(a_{r}) appear to converge to G in the prefix topology, suggesting a deeper dynamical link that we leave for future work. 1.2 Almost Golomb sequences What happens when one replaces the full cumulative sum in ( 1 ) by a sliding window of the r most recent terms. This leads to sequences that we call almost Golomb sequences : they share the meta-recursive spirit of Golomb’s sequence [ 10 ] , but are built from a finite-memory rule. Definition 1.1 . Let r\geq 2 . The almost Golomb sequence of order r is the nondecreasing sequence of positive integers (a(n))_{n\geq 1} , extended by a(k)=0 for k\leq 0 , satisfying a\bigl(a(n)+a(n-1)+\cdots+a(n-r+1)\bigr)=n,\qquad n\geq 1, (3) with a(n) minimal: for every n\geq 2 , no integer m with a(n-1)\leq mS_{m}^{b} , i.e. L_{m}^{b}:=b(m+1)-b(m+1-r)\geq 1 . Since \mathcal{H}_{m} gives S_{m}^{b}\geq m+1 , position m+1 lies within a previously defined run, so the value b(m+1) is already determined at this stage. Suppose L_{m}^{b}=0 . Then b is constant on [m+1-r,m+1] with value v . If v=m : the value m already appears at position m+1-r . Since the first occurrence of m is at S_{m}^{b} , this implies m+1-r\geq S_{m}^{b} . But \mathcal{H}_{m} gives S_{m}^{b}\geq m+1 , hence m+1-r\geq m+1 , impossible since r\geq 2 . If vS_{m}^{b} . Moreover L_{m}^{b}=\sum_{j=0}^{r-1}d(m-j)\leq r since d\in\{0,1\} , so the run of m has length \leq r and \mathcal{H}_{m+1} holds. Verification of the greedy rule. For positions qS_{m}^{b} (interior of the run): then b(q-1)=m , so v\geq m and m is already the smallest candidate. Hence b satisfies Definition 1.1 , so existence holds and b has properties (i)–(iv). For uniqueness, let c be any sequence satisfying Definition 1.1 . The constraint at n=1,2 forces c(1)=b(1)=1 and c(n)=b(n)=2 for 2\leq n\leq S_{3}^{b}-1 , so c and b share the same initial prefix. Assume inductively that c agrees with b up to S_{m}^{b}-1 . Then the next admissible value and its maximal run compatible with Definition 1.1 are forced, so the run of value m in c coincides with that of b . Hence c=b term by term. ∎ Lemma 2.3 . For every r\geq 2 and m\geq 3 , L_{m}:=S_{m+1}-S_{m}=a(m+1)-a(m+1-r)=\sum_{j=0}^{r-1}d(m-j). Proof. By Theorem 2.2 (iv) , L_{m}=S_{m+1}-S_{m} . Telescoping: S_{m+1}-S_{m}=a(m+1)-a(m+1-r)=\sum_{j=0}^{r-1}d(m-j) . ∎ Composing the map n\mapsto S_{n} with itself gives the following identity. Lemma 2.4 . For every r\geq 2 and n\geq 1 , S_{S_{n}}=rn-R_{n},\qquad R_{n}:=\sum_{j=1}^{r-1}(r-j)\,d(S_{n}-j)\in[0,\,r(r-1)/2]. Proof. Since a(S_{n})=n , one has a(S_{n}-k)=n-\sum_{j=1}^{k}d(S_{n}-j) for 0\leq k\leq r-1 . Summing: S_{S_{n}}=rn-\sum_{j=1}^{r-1}(r-j)d(S_{n}-j) . ∎ The value d(rn+i) can be read from a bounded window of local data. Lemma 2.5 . Let A\geq 3 . (i) For X\geq 0 : d(S_{A}+X)=1\iff\sum_{j=0}^{\delta-1}L_{A+j}=X+1 for some \delta\in\{1,\ldots,X+1\} . Hence d(S_{A}+X) is determined by (L_{A},\ldots,L_{A+X}) . (ii) For Y\geq 1 : d(S_{A}-1-Y)=1\iff\sum_{j=1}^{\delta}L_{A-j}=Y for some \delta\in\{1,\ldots,Y\} . Hence d(S_{A}-1-Y) is determined by (L_{A-1},\ldots,L_{A-Y}) . Also, d(S_{A}-1)=1 always. Proof. By Theorem 2.2 , d(k)=1\iff k=S_{m}-1 for some m . For (i) : d(S_{A}+X)=1\iff S_{A}+X+1=S_{A+\delta} for some \delta\geq 1 , i.e. \sum_{j=0}^{\delta-1}L_{A+j}=X+1 ; since L_{u}\geq 1 , one has \delta\leq X+1 . For (ii) : similarly d(S_{A}-1-Y)=1\iff S_{A}-Y=S_{A-\delta} , i.e. \sum_{j=1}^{\delta}L_{A-j}=Y ; and d(S_{A}-1)=1 since S_{A}-1 is the last position of the run of A . ∎ The run structure gives a direct characterization of the value a(K) . Lemma 2.6 . For every r\geq 2 , m\geq 3 , and every integer K\geq 1 , a(K)=m\iff S_{m}\leq K2^{k-1} (second half): a(n+1)=n+1-2^{k-1}=2^{k}+1 . Hence a(n)+a(n+1)-1=2^{k+1} and a(n)+a(n+1)=2^{k+1}+1 . Since 2j=2^{k}=2^{(k+1)-1} (boundary of first half in block k+1 ): a(2n)=3\cdot 2^{k-1}+2^{k-1}=2^{k+1} . Since 2j+1=2^{k}+1>2^{k} (second half): a(2n+1)=2n+1-2^{k}=2^{k+1}+1 . Case 3: 2^{k-1}2^{k-1} , so a(n)=n-2^{k-1} and a(n+1)=n+1-2^{k-1} . Hence a(n)+a(n+1)-1=2n-2^{k} and a(n)+a(n+1)=2n-2^{k}+1 . Since 2j>2^{k} (second half of block k+1 ): a(2n)=2n-2^{k} and a(2n+1)=2n+1-2^{k} . Case 4: j=2^{k}-1 (last element of block k ). a(n)=n-2^{k-1}=3\cdot 2^{k-1}-1 . Now n+1=2^{k+1} starts block k+1 with j^{\prime}=0 , giving a(n+1)=3\cdot 2^{k-1} . Hence a(n)+a(n+1)-1=3\cdot 2^{k}-2 and a(n)+a(n+1)=3\cdot 2^{k}-1 . Since 2j=2^{k+1}-2>2^{k} (second half): a(2n)=2n-2^{k}=3\cdot 2^{k}-2 and a(2n+1)=2n+1-2^{k}=3\cdot 2^{k}-1 . The special case k=1 (i.e. n\in\{2,3\} ) is verified directly: a(4)=a(2)+a(3)-1=3 , a(5)=a(2)+a(3)=4 , a(6)=a(3)+a(4)-1=4 , a(7)=a(3)+a(4)=5 ; these match the sequence. ∎ Remark 3.4 . Formulas ( 6 )–( 7 ) show that every subsequence in the 2 -kernel of (a(n)) (see the discussion preceding Theorem 2.7 for the terminology) can be expressed as a \mathbb{Z} -linear combination of (a(n)) , (a(n+1)) , and the constant sequence 1 (the -1 in ( 6 ) necessitates this constant generator). Hence (a(n)) is 2 -regular. Since a(n) is unbounded it is not 2 -automatic. 3.4 A Mallows-type nested recurrence Golomb’s sequence satisfies the Mallows recurrence G(n+1)=1+G(n+1-G(G(n))) . The almost Golomb sequence of order 2 admits an analogous nested recurrence. Proposition 3.5 . For every n\geq 4 , a(n+1)\;=\;1+a\!\Bigl(n+1-a\bigl(a(n)+1\bigr)+a\bigl(a(n)-1\bigr)\Bigr). (9) Proof. Set m:=a(n) and let N_{2}(m):=a(m+1)-a(m-1) be the multiplicity of the value m , i.e. the length of the run of m (Lemma 2.3 with r=2 ). By Theorem 2.2 , the differences d\in\{0,1\} give N_{2}(m)=d(m-2)+d(m-1)\in\{1,2\} . It suffices to show a(n+1)=1+a\bigl(n+1-N_{2}(m)\bigr), (10) since substituting N_{2}(m)=a(m+1)-a(m-1) with m=a(n) yields ( 9 ). If N_{2}(m)=1 : the value m occurs once, at position n , so a(n+1)=m+1 and 1+a(n)=1+m=m+1 . If N_{2}(m)=2 : the value m occupies two consecutive positions. If n is the first, then a(n-1)=m-1 and a(n+1)=m , giving 1+a(n-1)=m . If n is the second, then a(n-1)=m and a(n+1)=m+1 , giving 1+a(n-1)=m+1 . ∎ Remark 3.6 . Since a(n)},c_{<},e_{=},e_{>},e_{<},r\} , \Sigma=\{0,1,2\} , initial state q_{0} , output map \tau(c_{=})=\tau(c_{>})=\tau(e_{<})=1 and \tau(q)=0 otherwise. The transition table is: \begin{array}[]{c|ccc}&0&1&2\\ \hline\cr q_{0}&r&q_{1}&q_{2}\\ q_{1}&r&r&c_{=}\\ q_{2}&e_{=}&r&r\\ c_{=}&c_{<}&c_{=}&c_{>}\\ c_{<}&c_{<}&c_{<}&c_{<}\\ c_{>}&c_{>}&c_{>}&c_{>}\\ e_{=}&e_{<}&e_{=}&e_{>}\\ e_{<}&e_{<}&e_{<}&e_{<}\\ e_{>}&e_{>}&e_{>}&e_{>}\\ r&r&r&r\end{array} For every n\geq 1 , the automaton outputs \varepsilon(n)=\mathbf{1}_{\mathcal{I}}(n) . Proof. The bounds \ell_{k}=(11\cdot 3^{k}-1)/2=(12\underbrace{1\cdots 1}_{k})_{3} and u_{k}=(13\cdot 3^{k}-3)/2=(20\underbrace{1\cdots 1}_{k-1}0)_{3} show that n\in I_{k} iff either (i) \operatorname{rep}_{3}(n)=12u with |u|=k and u\geq_{\rm lex}1^{k} , or (ii) \operatorname{rep}_{3}(n)=20u with |u|=k and u<_{\rm lex}1^{k} . States q_{1},q_{2} detect prefixes 12,20 ; states c_{=},c_{>},c_{<} (resp. e_{=},e_{>},e_{<} ) track the lexicographic comparison of the suffix with 1^{k} . Accepting states c_{=},c_{>} cover case (i); e_{<} covers case (ii). ∎ 4.3 A strong gap lemma Lemma 4.4 . For every k\geq 2 , \varepsilon(n)=0 for all 3^{k}-1\leq n\leq 5\cdot 3^{k-1} . Proof. By induction on k . The base case k=2 is \varepsilon(8)=\cdots=\varepsilon(15)=0 , verified directly. Assuming the result at rank k , let 3^{k+1}-1\leq n\leq 5\cdot 3^{k} and write n=3m+r . If r\in\{1,2\} : \varepsilon(n)=\varepsilon(m) and 3^{k}-1\leq m\leq 5\cdot 3^{k-1} . If r=0 : \varepsilon(n)=\varepsilon(m-1) and 3^{k}-1\leq m-1\leq 5\cdot 3^{k-1}-1 . In all cases the hypothesis gives \varepsilon=0 . ∎ 4.4 Explicit formulas on the first two thirds of each block Lemma 4.5 . For every k\geq 2 and every n with 3^{k}-1\leq n\leq 5\cdot 3^{k-1} , the almost Golomb sequence satisfies \displaystyle a(3n) \displaystyle=a(n-2)+a(n-1)+a(n)+1, (14) \displaystyle a(3n+1) \displaystyle=a(n-1)+a(n)+a(n+1), (15) \displaystyle a(3n+2) \displaystyle=a(n)+a(n+1)+a(n+2)-1. (16) Proof. This is the specialisation of Theorem 4.9 (whose proof does not depend on the present lemma) to the zone where \varepsilon\equiv 0 : Lemma 4.4 gives \varepsilon(n-1)=\varepsilon(n)=0 for 3^{k}-1\leq n\leq 5\cdot 3^{k-1} , so ( 21 )–( 23 ) reduce to ( 14 )–( 16 ). ∎ Proposition 4.6 . For every k\geq 2 , set A_{k}:=a(3^{k}) . Then A_{2}=6 , A_{k+1}=3A_{k}-1 , and A_{k}=\frac{11\cdot 3^{k-2}+1}{2}. Moreover a(3^{k}-2)=a(3^{k}-1)=A_{k}-1 , and for 0\leq j\leq 2\cdot 3^{k-1} : a(3^{k}+j)=\begin{cases}A_{k}+\left\lfloor\dfrac{j}{3}\right\rfloor,&0\leq j\leq 3^{k-1}-1,\\[8.61108pt] A_{k}+3^{k-2}+\left\lfloor\dfrac{j-3^{k-1}}{2}\right\rfloor,&3^{k-1}\leq j\leq 2\cdot 3^{k-1}.\end{cases} (17) Proof. By induction on k . The base case k=2 is verified from the values a(9)=\cdots=a(11)=6 , a(12)=a(13)=7 , a(14)=a(15)=8 . Assume ( 17 ) at rank k . By Lemma 4.5 , for every n\in[3^{k}-1,\,5\cdot 3^{k-1}] , \displaystyle a(3n) \displaystyle=a(n-2)+a(n-1)+a(n)+1, (18) \displaystyle a(3n+1) \displaystyle=a(n-1)+a(n)+a(n+1), (19) \displaystyle a(3n+2) \displaystyle=a(n)+a(n+1)+a(n+2)-1. (20) Left boundary: at n=3^{k}-1 , ( 15 )–( 16 ) give a(3^{k+1}-2)=a(3^{k+1}-1)=3A_{k}-2=A_{k+1}-1 , and ( 14 ) gives a(3^{k+1})=3A_{k}-1=A_{k+1} . First subinterval: for q=3^{k}+v , 0\leq v<3^{k-1} , the floor sum \lfloor(v-2)/3\rfloor+\lfloor(v-1)/3\rfloor+\lfloor v/3\rfloor=v-2 and its two analogues give a(3q)=a(3q+1)=a(3q+2)=A_{k+1}+v . Second subinterval: for q=4\cdot 3^{k-1}+v , 0\leq v\leq 3^{k-1} , the analogous floor sums with denominator 2 give a(4\cdot 3^{k}+s)=A_{k+1}+3^{k-1}+\lfloor s/2\rfloor for 0\leq s\leq 3^{k} . Solving A_{k+1}=3A_{k}-1 with A_{2}=6 gives A_{k}=(11\cdot 3^{k-2}+1)/2 . ∎ Corollary 4.7 . For every k\geq 2 : a(3^{k})=\frac{11\cdot 3^{k-2}+1}{2},\qquad a(5\cdot 3^{k-1})=8\cdot 3^{k-2},\qquad a(5\cdot 3^{k-1}-1)=8\cdot 3^{k-2}-1. Proof. Take j=2\cdot 3^{k-1} and j=2\cdot 3^{k-1}-1 in ( 17 ). Since 3^{k-1} is odd, \lfloor 3^{k-1}/2\rfloor=(3^{k-1}-1)/2 . ∎ 4.5 Triadic denesting Lemma 4.8 . For every r\geq 2 and every n\geq 3 , a(n)\leq n-1 . Proof. Since a(3)=2 and a(n+1)-a(n)\in\{0,1\} by Theorem 2.2 , an immediate induction gives a(n)\leq n-1 for all n\geq 3 . ∎ Theorem 4.9 . For every n\geq 2 : \displaystyle a(3n) \displaystyle=a(n-2)+a(n-1)+a(n)+1+\varepsilon(n-1), (21) \displaystyle a(3n+1) \displaystyle=a(n-1)+a(n)+a(n+1), (22) \displaystyle a(3n+2) \displaystyle=a(n)+a(n+1)+a(n+2)-1-\varepsilon(n). (23) Proof. We prove the three identities ( 21 )–( 23 ) together with the run-length invariant : defining L_{n}\;:=\;S_{n+1}-S_{n}\;=\;a(n+1)-a(n-2)\;=\;d(n-2)+d(n-1)+d(n)\;\in\;\{1,2,3\} (24) (the length of the run of value n , for n\geq 3 ), we prove that for every n\geq 3 , L_{n}\leq 2+\varepsilon(n-1),\qquad\text{with equality }L_{n}=3\text{ whenever }\varepsilon(n-1)=1. (25) The proof is by strong induction on n . The hypothesis \mathcal{H}_{n} asserts that the three denesting formulas hold at all ranks m3n+1 . By ( 26 ), a(3n+1)=S_{n+1} , which is ( 22 ). Case a(3n) . The candidate is M_{0}:=a(n-2)+a(n-1)+a(n)+1+\varepsilon(n-1)=S_{n}+1+\varepsilon(n-1) . Subcase \varepsilon(n-1)=0 . Then M_{0}=S_{n}+1 and L_{n}\leq 2 by ( 25 ). Since a(S_{n})=n and a(S_{n}-1)=n-1 : if L_{n}=2 then a(M_{0})=n , giving S_{M_{0}}=n+n+(n-1)=3n-1 ; if L_{n}=1 then M_{0}=S_{n+1} , a(M_{0})=n+1 , giving S_{M_{0}}=(n+1)+n+(n-1)=3n . In both cases S_{M_{0}}\leq 3n . For the upper bound: when L_{n}=2 , a(M_{0}+1)=a(S_{n+1})=n+1 , so L_{M_{0}}=(n+1)-(n-1)=2 and S_{M_{0}+1}=3n+1 ; when L_{n}=1 , L_{M_{0}}=a(S_{n+1}+1)-a(S_{n}-1)\geq(n+1)-(n-1)=2 and S_{M_{0}+1}\geq 3n+2 . In both cases S_{M_{0}+1}>3n . Subcase \varepsilon(n-1)=1 . Then M_{0}=S_{n}+2 and L_{n}=3 by ( 25 ). All three positions S_{n},\,S_{n}+1,\,S_{n}+2 carry value n , so S_{M_{0}}=n+n+n=3n . Moreover M_{0}+1=S_{n}+3=S_{n+1} , hence a(M_{0}+1)=n+1 , giving L_{M_{0}}=(n+1)-n=1 and S_{M_{0}+1}=3n+1 . In all subcases S_{M_{0}}\leq 3n3n+2 . Subcase \varepsilon(n)=1 . Then M_{2}=S_{n+2}-2 and L_{n+1}=3 by ( 25 ). The run of n+1 occupies [S_{n+1},\,S_{n+1}+2] , so a(M_{2})=a(S_{n+1}+1)=n+1 , a(M_{2}-1)=a(S_{n+1})=n+1 , a(M_{2}-2)=a(S_{n+1}-1)=n , giving S_{M_{2}}=(n+1)+(n+1)+n=3n+2 . For the upper bound, L_{M_{2}}=a(S_{n+2}-1)-a(S_{n+1}-2)=(n+1)-a(S_{n+1}-2) . If L_{n}\geq 2 : a(S_{n+1}-2)=n , L_{M_{2}}=1 ; if L_{n}=1 : a(S_{n+1}-2)=a(S_{n}-1)=n-1 , L_{M_{2}}=2 . In both cases S_{M_{2}+1}=S_{M_{2}}+L_{M_{2}}\geq 3n+3>3n+2 . In all subcases S_{M_{2}}\leq 3n+2m for m\geq 1 , the recurrences define (\varepsilon,\eta) on all positive integers by induction. The disjointness \varepsilon\eta=0 is propagated by induction: ( 54 ) and ( 55 ) exchange the roles of \varepsilon and \eta , while ( 52 ) produces 1 only when \varepsilon(m-1)=1 , hence when \eta(m-1)=0 , so \eta(5m)=\varepsilon(m)=0 . Finally, U(5m+d) is determined by U(m) and U(m-1) , so the Allouche–Shallit criterion [ 4 ] applies and U is 5 -automatic. ∎ Remark 6.2 . The five transitions of the pair (\varepsilon(m),\eta(m)) at consecutive indices suffice to cover all cases in a_{5} ; see Appendix C . n 1 2 3 4 5 6 7 8 9 10 \varepsilon(n) 0 0 0 1 0 0 0 0 0 0 \eta(n) 0 0 1 0 0 0 0 0 0 0 n 11 12 13 14 15 16 17 18 19 20 \varepsilon(n) 0 0 1 0 1 0 1 0 1 0 \eta(n) 0 1 0 1 0 1 0 1 0 1 6.2 The denesting theorem Set \sigma(n):=\varepsilon(n)+\eta(n)\in\{0,1\} . For residues 3 and 4 two further correctors appear, both expressible from (\varepsilon,\eta) ; their formulas are listed in Appendix C . With these sequences in hand, the five denesting formulas are immediate. Theorem 6.3 . For all n\geq 3 , the almost Golomb sequence of order 5 satisfies: \displaystyle a(5n) \displaystyle=T_{5}(n)+2+\varepsilon(n), (57) \displaystyle a(5n+1) \displaystyle=T_{5}(n+1)+1-\varepsilon(n), (58) \displaystyle a(5n+2) \displaystyle=T_{5}(n+2)-1-\eta(n), (59) \displaystyle a(5n+3) \displaystyle=T_{5}(n+3)-4+\theta(n), (60) \displaystyle a(5n+4) \displaystyle=T_{5}(n+4)+2+\varepsilon_{4}(n), (61) where \theta(n)\in\{0,1\} and \varepsilon_{4}(n)\in\{-4,-3,-2\} are both 5 -automatic, expressed as explicit functions of U in Appendix C . Consequently, (a(n)) is 5 -regular by [ 2 , Theorem 2.5] . Proof. Formulas ( 57 ) and ( 59 ) are the definitions ( 51 ). Formula ( 58 ) is derived in Appendix B by the same elimination used in Theorem 6.1 . Formulas ( 60 ) and ( 61 ) are the definitions of \theta and \varepsilon_{4} . The 5 -automaticity of \theta and \varepsilon_{4} follows from the explicit tables in Appendix C : both are obtained from the 5 -automatic sequence U by a finite-state post-processing (the table defines a finite transducer whose input is the pair (U(m-1),U(m)) or (U(m),U(m+1)) ). The 5 -regularity of (a(n)) follows because ( 57 )–( 61 ) express each subsequence (a(5n+i))_{n\geq 0} as a \mathbb{Z} -linear combination of finitely many shifts of (a(n)) plus 5 -automatic sequences; by [ 2 , Theorem 2.5] this implies (a(n)) is 5 -regular. ∎ 7 Non-convergence of a(n)/n A common feature of all almost Golomb sequences is that a(n)/n oscillates between two explicit rational limits, failing to converge. This contrasts sharply with Golomb’s sequence, where a(n)/n^{\varphi-1}\to\varphi^{2-\varphi} converges to a smooth constant. 7.1 The case r=2 Theorem 7.1 . Let (a(n)) be the almost Golomb sequence of order 2 . (i) a(n)/n does not converge: a(2^{k})/2^{k}=3/4 and a(3\cdot 2^{k-1})/(3\cdot 2^{k-1})=2/3 for all k\geq 2 . (ii) The Cesàro means C_{N}=\frac{1}{N}\sum_{n=1}^{N}\frac{a(n)}{n} do not converge. They have two limit points: L_{1}=\lim_{k\to\infty}C_{2^{k}}=\tfrac{3}{4}+\log\!\left(\tfrac{6^{3/4}}{4}\right),\qquad L_{2}=\lim_{k\to\infty}C_{3\cdot 2^{k-1}}=\tfrac{2}{3}+\log\!\left(\tfrac{3^{2/3}}{2}\right). Proof. Part (i) follows immediately from Corollary 3.2 . For part (ii), introduce the dyadic block average A_{k}=2^{-k}\sum_{n=2^{k}}^{2^{k+1}-1}a(n)/n . Writing n=2^{k}+j and t=j/2^{k}\in[0,1) , Proposition 3.1 gives \frac{a(n)}{n}=\begin{cases}\dfrac{\tfrac{3}{4}+\tfrac{t}{2}}{1+t}+O(2^{-k})&0\leq t\leq\tfrac{1}{2},\\[8.0pt] \dfrac{\tfrac{1}{2}+t}{1+t}&\tfrac{1}{2}0 since e>8/3 . ∎ The run structure of the sequence is also captured automatically. Proposition 7.2 . The sequence \Delta a(n)=a(n+1)-a(n)\in\{0,1\} is 2 -automatic. Proof. Proposition 3.1 shows that in the block [2^{k},2^{k+1}) written as n=2^{k}+j : \Delta a(n)=0 when j is odd and j\leq 2^{k-1}-1 (the ceiling-based formula produces repeated values at consecutive even/odd pairs); \Delta a(n)=1 for all n\geq 3\cdot 2^{k-1} (the second half of the block has slope 1 ). This is a regular language on the binary representation of n , so \Delta a is 2 -automatic. ∎ The multiplicity sequence of values in (a(n)) is also 2 -automatic. Proposition 7.3 . Let N_{2}(n) denote the number of times n appears in the almost Golomb sequence of order 2 . Then N_{2}(n)\in\{1,2\} for all n\geq 1 , and the sequence (N_{2}(n))_{n\geq 1} is 2 -automatic, satisfying the recurrences N_{2}(2n)=N_{2}(n),\qquad N_{2}(2n+1)=N_{2}(n+1)\qquad(n\geq 2), (62) with initial values N_{2}(1)=1 , N_{2}(2)=2 , N_{2}(3)=1 . Equivalently, N_{2} is given by the single recursion N_{2}(n)=\begin{cases}2-(n\bmod 2)&\text{if }n\leq 3,\\ N_{2}\!\bigl(\lceil n/2\rceil\bigr)&\text{if }n\geq 4.\end{cases} (63) Proof. From Proposition 3.1 , in the dyadic block [2^{k},2^{k+1}) written as n=2^{k}+j with 0\leq j<2^{k} : • First half ( 0\leq j\leq 2^{k-1} ): a(n)=3\cdot 2^{k-2}+\lceil j/2\rceil . The value 3\cdot 2^{k-2} appears once ( j=0 ); each value in [3\cdot 2^{k-2}+1,\,2^{k}] appears exactly twice (two consecutive values of j ). • Second half ( 2^{k-1}0 . Hence the I_{k} are pairwise disjoint, and n\in\mathcal{I} iff n\in I_{k} for a unique k . For m=5 and k\geq 1 , we show 5\cdot 3^{k} lies strictly between I_{k-1} and I_{k} . On the left: 5\cdot 3^{k}>u_{k-1}=(13\cdot 3^{k-1}-3)/2 since 10\cdot 3^{k}=30\cdot 3^{k-1}>13\cdot 3^{k-1}-3 . On the right: 5\cdot 3^{k}<\ell_{k}=(11\cdot 3^{k}-1)/2 since 10\cdot 3^{k}<11\cdot 3^{k}-1 , i.e. 1<3^{k} , which holds for k\geq 1 . Hence 5\cdot 3^{k}\notin\mathcal{I} , and since 5\cdot 3^{k}-1<5\cdot 3^{k}<\ell_{k} and 5\cdot 3^{k}-1>u_{k-1} , we get 5\cdot 3^{k}-1\notin\mathcal{I} as well. For m=8 and k\geq 1 , we show 8\cdot 3^{k} lies strictly between I_{k} and I_{k+1} . On the left: 8\cdot 3^{k}>u_{k}=(13\cdot 3^{k}-3)/2 since 16\cdot 3^{k}>13\cdot 3^{k}-3 . On the right: 8\cdot 3^{k}<\ell_{k+1}=(11\cdot 3^{k+1}-1)/2 since 16\cdot 3^{k}<33\cdot 3^{k}-1 . Hence 8\cdot 3^{k}\notin\mathcal{I} , and since u_{k}<8\cdot 3^{k}-1<8\cdot 3^{k}<\ell_{k+1} , we get 8\cdot 3^{k}-1\notin\mathcal{I} . Therefore \varepsilon(5\cdot 3^{k})=\varepsilon(5\cdot 3^{k}-1)=\varepsilon(8\cdot 3^{k})=\varepsilon(8\cdot 3^{k}-1)=0 . ∎ Theorem 7.5 . Let (a(n)) be the almost Golomb sequence of order 3 . For all k\geq 1 : a(5\cdot 3^{k})=8\cdot 3^{k-1},\quad\frac{a(5\cdot 3^{k})}{5\cdot 3^{k}}=\frac{8}{15};\qquad a(8\cdot 3^{k})=15\cdot 3^{k-1},\quad\frac{a(8\cdot 3^{k})}{8\cdot 3^{k}}=\frac{5}{8}. Thus a(n)/n does not converge. Proof. We propagate the local pattern around 5\cdot 3^{k} by induction on k . The base case k=1 is verified directly (pattern around 15 ). Assuming for some k\geq 1 : a(5\cdot 3^{k}-2)=8\cdot 3^{k-1}-1,\;\;a(5\cdot 3^{k}-1)=8\cdot 3^{k-1},\;\;a(5\cdot 3^{k})=8\cdot 3^{k-1},\;\;a(5\cdot 3^{k}+1)=8\cdot 3^{k-1}+1, set n=5\cdot 3^{k} . By Lemma 7.4 , \varepsilon(n)=\varepsilon(n-1)=0 . Applying ( 21 )–( 23 ) (and the analogues with n-1 ): \displaystyle a(3n-2) \displaystyle=a(n-2)+a(n-1)+a(n)=8\cdot 3^{k}-1, \displaystyle a(3n-1) \displaystyle=a(n-1)+a(n)+a(n+1)-1=8\cdot 3^{k}, \displaystyle a(3n) \displaystyle=a(n-2)+a(n-1)+a(n)+1=8\cdot 3^{k}, \displaystyle a(3n+1) \displaystyle=a(n-1)+a(n)+a(n+1)=8\cdot 3^{k}+1, which is the same pattern at rank k+1 around 3n=5\cdot 3^{k+1} . For the family a(8\cdot 3^{k})=15\cdot 3^{k-1} , we propagate the local pattern a(8\cdot 3^{k}-2)=15\cdot 3^{k-1}-1,\quad a(8\cdot 3^{k}-1)=a(8\cdot 3^{k})=15\cdot 3^{k-1},\quad a(8\cdot 3^{k}+1)=15\cdot 3^{k-1}+1. The base case k=1 is read off directly: a(22)=14 , a(23)=a(24)=15 , a(25)=16 . Assuming the pattern at rank k , set n=8\cdot 3^{k} . By Lemma 7.4 , \varepsilon(n)=\varepsilon(n-1)=0 . Applying ( 21 )–( 23 ) at n-1 and n : \displaystyle a(3n-2) \displaystyle=a(n-2)+a(n-1)+a(n)=15\cdot 3^{k}-1, \displaystyle a(3n-1) \displaystyle=a(n-1)+a(n)+a(n+1)-1=15\cdot 3^{k}, \displaystyle a(3n) \displaystyle=a(n-2)+a(n-1)+a(n)+1=15\cdot 3^{k}, \displaystyle a(3n+1) \displaystyle=a(n-1)+a(n)+a(n+1)=15\cdot 3^{k}+1, which is the same pattern at rank k+1 around 3n=8\cdot 3^{k+1} . Since 8/15\neq 5/8 , the ratio a(n)/n does not converge. ∎ 7.3 The case r=4 The quaternary case exhibits the same oscillatory behavior as the triadic case, but the two pivotal subsequences are now identified via the affine recurrence u_{k+1}=4u_{k}-2 . Theorem 7.6 . Let (a(n)) be the almost Golomb sequence of order 4 . The sequence a(n)/n does not converge. Setting A_{k}=a(4^{k}) , the recurrence A_{k+1}=4A_{k}-2 (64) holds for all k\geq 3 , with general solution A_{k}=C\cdot 4^{k}+\tfrac{2}{3} . The two families \frac{a(4^{k})}{4^{k}}\to\frac{25}{48},\qquad\frac{a(7\cdot 4^{k})}{7\cdot 4^{k}}\to\frac{10}{21} have distinct limits, so a(n)/n has at least two limit points. Proof. Since 4^{k}=[1\,0^{k}]_{4} and 7\cdot 4^{k}=[13\,0^{k}]_{4} in base 4 , Lemma 2.8 implies that the correction patterns along these two families are ultimately periodic. Machine evaluation of the certified recurrence system of Theorem 5.3 yields, from k=3 onward, (\varepsilon_{0}(4^{k}),\,\varepsilon_{1}(4^{k}),\,\varepsilon_{2}(4^{k}),\,\varepsilon_{3}(4^{k}))=(1,0,0,1), together with the fixed local neighbourhood pattern a(4^{k}+j)=A_{k}+\delta(j)\qquad(-4\leq j\leq 4), where \delta(j)=\begin{cases}-2&j\in\{-4,-3\},\\ -1&j\in\{-2,-1\},\\ \phantom{-}0&j\in\{0,1,2\},\\ +1&j\in\{3,4\}.\end{cases} Substituting into ( 31 ) with n=4^{k} gives A_{k+1}=4A_{k}-2 . With A_{3}=a(64)=34 , the solution is A_{k}=\tfrac{25}{48}\cdot 4^{k}+\tfrac{2}{3} . The same evaluation along 7\cdot 4^{k} , with B_{k}:=a(7\cdot 4^{k}) , gives B_{k}/(7\cdot 4^{k})\to 10/21 . Since 25/48\neq 10/21 , the ratio a(n)/n does not converge. (The local neighbourhood patterns can be verified by iterating the certified recurrences of Theorem 5.3 .) ∎ Remark 7.7 . The affine recurrence u_{k+1}=4u_{k}-2 (with fixed point 2/3 ) contrasts with the purely multiplicative recurrences of orders 2 and 3 . Consequently the two limiting ratios 25/48 and 10/21 do not have the “ p/q and q/p ” symmetry seen in the triadic case ( 8/15 and 5/8 ). 7.4 The case r=5 Theorem 7.8 . The ratio a(n)/n for the almost Golomb sequence of order 5 does not converge. Setting A_{k}=a(5^{k}) and B_{k}=a(2\cdot 5^{k}) , one has for all k\geq 2 : A_{k+1}=\begin{cases}5A_{k}-1,&k\ \text{even},\\ 5A_{k}-4,&k\ \text{odd},\end{cases}\qquad B_{k+1}=5B_{k}-1. (65) Consequently \lim_{\begin{subarray}{c}k\to\infty\\ k\text{ even}\end{subarray}}\frac{a(5^{k})}{5^{k}}=\frac{93}{200},\qquad\lim_{k\to\infty}\frac{a(2\cdot 5^{k})}{2\cdot 5^{k}}=\frac{87}{200}, and these two limits are distinct. Proof. Since 5^{k}=[1\,0^{k}]_{5} and 2\cdot 5^{k}=[2\,0^{k}]_{5} in base 5 , Lemma 2.8 implies that the correction patterns along these families are ultimately periodic. Machine evaluation of the certified recurrence system of Theorem 6.1 yields, for k\geq 2 , the alternating pattern U(5^{k})\in\{(1,0),(0,1)\} with period 2 , and a constant correction pattern along 2\cdot 5^{k} . The same evaluation gives the corresponding local neighbourhood patterns of a , from which the affine recurrences ( 65 ) follow by substitution into ( 57 )–( 61 ). For even k , A_{k}/5^{k}\to 93/200 . For B_{k} , B_{k}/(2\cdot 5^{k})\to 87/200 . Since 93/200\neq 87/200 , the ratio a(n)/n has at least two limit points. (The local patterns follows by iterating the certified recurrences of Theorem 6.1 .) ∎ 7.5 Summary r Pivotal family 1 Limit Pivotal family 2 Limit 2 2^{k} \dfrac{3}{4} 3\cdot 2^{k-1} \dfrac{2}{3} 3 5\cdot 3^{k} \dfrac{8}{15} 8\cdot 3^{k} \dfrac{5}{8} 4 4^{k} \dfrac{25}{48} 7\cdot 4^{k} \dfrac{10}{21} 5 5^{k} ( k even) \dfrac{93}{200} 2\cdot 5^{k} \dfrac{87}{200} In each case both limits lie in (0,1) , confirming linear growth a(n)\asymp n (meaning C_{1}n\leq a(n)\leq C_{2}n for positive constants C_{1},C_{2} ) with an oscillating prefactor. For r=2 , the Cesàro means also fail to converge (Theorem 7.1 ); the behavior for r\geq 3 is open (see Section 10 ). 8 Combinatorial interpretations The denesting formulas of Sections 3 and 4 encode algebraic identities. In this section we extract from them three combinatorial properties that reveal the structure of the difference sequence d(n)=a(n+1)-a(n)\in\{0,1\} in the cases r=2 and r=3 . 8.1 A second-bit characterization of multiplicities ( r=2 ) Proposition 7.3 shows that the multiplicity N_{2}(m) depends only on the iterated ceiling map m\mapsto\lceil m/2\rceil . We now translate this into a direct binary characterization. Proposition 8.1 . For every m\geq 4 , write m-1=(1\,b_{2}\,b_{3}\cdots b_{\ell})_{2} with b_{2} denoting the second most significant bit. Then N_{2}(m)=\begin{cases}2&\text{if }b_{2}=1,\\ 1&\text{if }b_{2}=0.\end{cases} Proof. By Proposition 7.3 , N_{2}(m)=N_{2}(\lceil m/2\rceil) for m\geq 4 . Set k=m-1\geq 3 and write k=(1\,b_{2}\cdots b_{\ell})_{2} . The operation m\mapsto\lceil m/2\rceil translates to k\mapsto\lfloor k/2\rfloor , which erases the least significant bit. After \ell-2 iterations the two-digit prefix (1\,b_{2})_{2} is reached, corresponding to m^{\prime}=k^{\prime}+1 where k^{\prime}\in\{2,3\} . If b_{2}=1 : the descent reaches k^{\prime}=3 , hence m^{\prime}=4 , N_{2}(4)=N_{2}(2)=2 . If b_{2}=0 : the descent reaches k^{\prime}=2 , hence m^{\prime}=3 , N_{2}(3)=1 . ∎ Remark 8.2 . The almost Golomb sequence of order 2 is thus the unique nondecreasing sequence of positive integers in which each value m\geq 4 is repeated twice if the second most significant bit of (m-1) is 1 , and once otherwise. The asymptotic density of values appearing twice is \lim_{N\to\infty}|\{m\leq N:N_{2}(m)=2\}|/N=1/2 , which governs the oscillation of a(n)/n between 2/3 and 3/4 . 8.2 A Boolean cellular automaton ( r=2 ) The denesting theorem (Theorem 3.3 ) translates into a remarkably simple rule for the difference sequence. Proposition 8.3 . The difference sequence d(n)=a(n+1)-a(n)\in\{0,1\} of the almost Golomb sequence of order 2 satisfies, for all n\geq 2 : d(2n)=1,\qquad d(2n+1)=d(n)\cdot d(n+1). (66) Proof. From Theorem 3.3 (valid for n\geq 2 ): \displaystyle d(2n) \displaystyle=a(2n+1)-a(2n)=\bigl[a(n)+a(n+1)\bigr]-\bigl[a(n)+a(n+1)-1\bigr]=1, \displaystyle d(2n+1) \displaystyle=a(2n+2)-a(2n+1)=\bigl[a(n+1)+a(n+2)-1\bigr]-\bigl[a(n)+a(n+1)\bigr] \displaystyle=d(n+1)+d(n)-1. Since d\in\{0,1\} and N_{2}(m)\in\{1,2\} (Proposition 7.3 ), run lengths are at most 2 , so d(n)+d(n+1)\geq 1 for all n\geq 2 . Hence d(n)+d(n+1)-1\in\{0,1\} , and the identity x+y-1=xy holds for all x,y\in\{0,1\} with x+y\geq 1 . ∎ Remark 8.4 . Formula ( 66 ) shows that d is generated by a multiplicative cellular automaton: every even position carries the value 1 , and every odd position is the Boolean AND of its two “parent” values at positions n and n+1 . The sequence a(n)=\sum_{k=0}^{n-1}d(k) is thus the accumulation function of this automaton. 8.3 A palindromic substitution rule ( r=3 ) For r=3 , the triadic structure of the difference sequence admits a palindromic decomposition. Proposition 8.5 . For every n\geq 3 , define the triadic block B_{n}=(d(3n-2),\,d(3n-1),\,d(3n)) . Then: (i) B_{n} is palindromic: d(3n-2)=d(3n) . (ii) The sum d(3n-2)+d(3n-1)+d(3n)=L_{n} . (iii) The block B_{n} is determined by L_{n} as follows: B_{n}=\begin{cases}(0,1,0)&\text{if }L_{n}=1,\\ (1,0,1)&\text{if }L_{n}=2,\\ (1,1,1)&\text{if }L_{n}=3.\end{cases} In particular, L_{n}=3 if and only if \varepsilon(n-1)=1 . Proof. Using the denesting formulas ( 21 )–( 23 ) at ranks n-1 and n : \displaystyle d(3n-2) \displaystyle=a(3(n{-}1){+}2)-a(3(n{-}1){+}1) \displaystyle=\bigl[a(n{-}1)+a(n)+a(n{+}1)-1-\varepsilon(n{-}1)\bigr]-\bigl[a(n{-}2)+a(n{-}1)+a(n)\bigr] \displaystyle=a(n{+}1)-a(n{-}2)-1-\varepsilon(n{-}1)=L_{n}-1-\varepsilon(n{-}1). By the same method: \displaystyle d(3n-1) \displaystyle=a(3n)-a(3(n{-}1){+}2) \displaystyle=\bigl[a(n{-}2)+a(n{-}1)+a(n)+1+\varepsilon(n{-}1)\bigr] \displaystyle\quad-\bigl[a(n{-}1)+a(n)+a(n{+}1)-1-\varepsilon(n{-}1)\bigr] \displaystyle=2-L_{n}+2\varepsilon(n{-}1). And: d(3n)=a(3n{+}1)-a(3n)=L_{n}-1-\varepsilon(n{-}1)=d(3n{-}2). This proves (i). The sum is 2(L_{n}-1-\varepsilon(n{-}1))+(2-L_{n}+2\varepsilon(n{-}1))=L_{n} , proving (ii). For (iii), the invariant ( 25 ) gives L_{n}\leq 2+\varepsilon(n{-}1) with L_{n}=3\iff\varepsilon(n{-}1)=1 , so: if L_{n}=1 (hence \varepsilon(n{-}1)=0 ): d(3n{-}2)=d(3n)=0 , d(3n{-}1)=1 ; if L_{n}=2 (hence \varepsilon(n{-}1)=0 ): d(3n{-}2)=d(3n)=1 , d(3n{-}1)=0 ; if L_{n}=3 (hence \varepsilon(n{-}1)=1 ): d(3n{-}2)=d(3n)=1 , d(3n{-}1)=1 . ∎ Remark 8.6 . Proposition 8.5 explains the oscillatory behavior of a(n)/n for r=3 as a delayed-feedback mechanism. The infinite binary word W=d(1)d(2)d(3)\cdots is self-describing: the distance between consecutive 1 s in W (at positions marking the end of each run) equals the number of 1 s in the sliding window of size r=3 ending at the corresponding index. When the local density of 1 s is high (many short runs), the rule dictates long future runs, creating a sparse zone; when the window reaches this sparse zone, the count of 1 s drops, forcing short runs and recreating a dense zone. This perpetual oscillation is the source of the non-convergence of a(n)/n . Remark 8.7 . The propagation rules ( 27 )–( 29 ) for the run lengths satisfy the relation L_{3n-1}+L_{3n}+L_{3n+1}=L_{n-1}+L_{n}+L_{n+1}-\bigl(\varepsilon(n{-}2)-2\varepsilon(n{-}1)+\varepsilon(n)\bigr). The expression f(n{-}1)-2f(n)+f(n{+}1) is the discrete Laplacian \Delta^{2}f(n) . Hence the total run length in a triadic block is conserved up to a correction by \Delta^{2}\varepsilon(n{-}1) : the points where \varepsilon=1 act as localized sources that redistribute mass between adjacent runs, analogous to a discrete diffusion process. 9 A conjectural Golomb meta-structure The almost Golomb sequences of order r were introduced as finite-memory variants of Golomb’s sequence, departing from it in growth rate, regularity, and oscillatory behavior. Golomb’s sequence appears to re-emerge within the almost Golomb hierarchy through a boundary phenomenon that is strongly supported numerically and can be reduced to two precise conjectures. For an almost Golomb sequence (a(n)) of order r , let N_{r}(n) denote the number of times n appears in the sequence. In Golomb’s sequence, the self-describing property gives N(n)=G(n)\sim Cn^{\varphi-1} , which grows without bound. For finite r , by contrast, N_{r}(n) is bounded since a(n)\asymp n . For r=2 this is made precise in Proposition 7.3 : N_{2}(n)\in\{1,2\} and (N_{2}(n)) is 2 -automatic. Numerical computation for r=2,\ldots,10 yields the following maximal multiplicities M(r)=\sup_{n}N_{r}(n) (verified for n well inside the computed range): \begin{array}[]{c|ccccccccc}r&2&3&4&5&6&7&8&9&10\\ \hline\cr M(r)&2&3&3&3&3&4&4&4&5\end{array} Let j_{k} denote the smallest r such that M(r)\geq k . Numerical computation up to r=700 yields j_{3}=3,\;j_{4}=7,\;j_{5}=10,\;j_{6}=13,\;j_{7}=17,\;j_{8}=21,\;j_{9}=25,\;j_{10}=30,\;\ldots with differences j_{k+1}-j_{k}=4,3,3,4,4,4,5,5,5,6,6,6,6,7,\ldots (starting from k=3 ). The first gap j_{4}-j_{3}=4 is anomalous; from k=4 onwards the difference sequence coincides exactly with Golomb’s sequence: j_{k+1}-j_{k}=G(k),\qquad k\geq 4, where (G(n))_{n\geq 1} is Golomb’s sequence as defined in Section 1.1 (OEIS A001462 ). This has been verified for all 64 gaps up to r=700 . Equivalently, letting S(k)=\sum_{n=1}^{k}G(n) denote the partial sums of Golomb’s sequence (OEIS A001463 ), one has the closed formula j_{k}=S(k-1)+2,\qquad k\geq 4, verified for all 29 values up to r=200 . Recall that S(k) is characterised by G(S(k))=k : it is the position of the last occurrence of k in Golomb’s sequence (OEIS A001463 ). The Prefix Conjecture (below) posits a_{r}(r)=G(r-1) for r\geq 3 , which for r\geq 4 gives N_{r}(r-1)=G(r-1) via the run identity; deriving the full threshold law j_{k}=S(k-1)+2 then requires in addition the Domination Lemma. If Conjecture 9.1 holds, then since S(k)\sim\varphi^{2-\varphi}k^{\varphi}/\varphi , one obtains M(r)\;\sim\;C\,r^{\varphi-1},\qquad r\to\infty, where \varphi-1\approx 0.618 is the same exponent as in Golomb’s own asymptotic a(n)\sim Cn^{\varphi-1} . If the conjecture holds, we come full circle. The sequences defined by truncating Golomb’s global rule to a finite window of size r would carry, in their run-length structure, the fingerprint of the very sequence they were derived from. Numerical evidence is collected in Table 1 . Table 1: Numerical evidence for the Golomb meta-structure conjecture. Top: M(r)=\sup_{n}N_{r}(n) for r=2,\ldots,50 . Bottom: threshold positions j_{k} (smallest r with M(r)\geq k ), their successive differences j_{k+1}-j_{k} , and the values G(k) of Golomb’s sequence [ 9 ] . The identity j_{k+1}-j_{k}=G(k) holds for all k\geq 4 ; it has been verified for 28 consecutive values up to r=200 , and for 64 values up to r=700 . r 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 M(r) 2 3 3 3 3 4 4 4 5 5 5 6 6 6 6 7 7 r 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 M(r) 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10 11 r 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 M(r) 11 11 11 11 12 12 12 12 12 12 13 13 13 13 13 k 3 4 5 6 7 8 9 10 11 12 13 14 15 16 j_{k} 3 7 10 13 17 21 25 30 35 40 46 52 58 64 j_{k+1}{-}j_{k} 4 3 3 4 4 4 5 5 5 6 6 6 6 7 G(k) 2 3 3 4 4 4 5 5 5 6 6 6 6 7 k 17 18 19 20 21 22 23 24 25 26 27 28 29 30 j_{k} 71 78 85 92 100 108 116 124 133 142 151 160 169 179 j_{k+1}{-}j_{k} 7 7 8 8 8 8 9 9 9 9 9 10 10 10 G(k) 7 7 7 8 8 8 8 9 9 9 9 9 10 10 Conjecture 9.1 . For all k\geq 4 , the threshold j_{k} (smallest order r at which M(r)=\sup_{n}N_{r}(n) first reaches k ) satisfies j_{k+1}-j_{k}=G(k)\qquad\text{and}\qquad j_{k}=S(k-1)+2, where G is Golomb’s sequence and S(k)=\sum_{n=1}^{k}G(n) . 9.1 A conditional reduction While a complete proof of Conjecture 9.1 remains open, the phenomenon can be reduced to two precise boundary conjectures. Set S_{m}^{(r)}=\sum_{i=0}^{r-1}a_{r}(m-i) (with a_{r}(k)=0 for k\leq 0 ), so that a_{r}(S_{m}^{(r)})=m by the defining equation. The following lemma provides the run-length identity used in the reduction. Lemma 9.2 . For all r\geq 2 and m\geq 3 , N_{r}(m)=a_{r}(m+1)-a_{r}(m+1-r). (67) Proof. By Theorem 2.2 , the run of value m is exactly [S_{m}^{(r)},S_{m+1}^{(r)}-1] , so N_{r}(m)=S_{m+1}^{(r)}-S_{m}^{(r)} . Telescoping: S_{m+1}^{(r)}-S_{m}^{(r)}=\sum_{j=0}^{r-1}a_{r}(m+1-j)-\sum_{j=0}^{r-1}a_{r}(m-j)=a_{r}(m+1)-a_{r}(m+1-r) . ∎ The meta-structure phenomenon reduces to the value of a single term: for r\geq 4 , Lemma 9.2 at m=r-1 gives N_{r}(r-1)=a_{r}(r)-a_{r}(0)=a_{r}(r) . Conjecture 9.3 (Prefix Conjecture) . For all r\geq 3 , a_{r}(r)=G(r-1). The conjecture has been verified computationally for all r\leq 200 . Note that for n\leq r , the convention a(k)=0 for k\leq 0 ensures that the sliding window reduces to the full sum \sum_{k=1}^{n}a(k) , so the first r terms of a_{r} depend only on the greedy rule with full memory. The conjecture thus asserts that this common initial prefix, evaluated at n=r , gives G(r-1) . Combining Conjecture 9.3 with Lemma 9.2 (which requires m\geq 3 , hence r\geq 4 ) yields the boundary identity N_{r}(r-1)=a_{r}(r)=G(r-1),\qquad r\geq 4. (68) (For r=3 , Conjecture 9.3 gives a_{3}(3)=G(2)=2 , but the run identity does not apply at m=2<3 ; indeed N_{3}(2)=3\neq 2 .) Conjecture 9.4 (Domination Lemma) . For all r\geq 5 , M(r)=N_{r}(r-1). (For r=4 the identity fails: M(4)=3 but N_{4}(3)=2 .) A proof of the Domination Lemma (Conjecture 9.4 ) would require showing that N_{r}(m)\leq G(r-1) for all m\geq r , or equivalently that S_{m+1}^{(r)}-S_{m}^{(r)}\leq G(r-1) . This is strongly supported by the following comparison of growth regimes: in the stationary range ( m\gg r ), the run lengths are numerically seen to grow slowly with r , whereas the boundary run length G(r-1)\sim Cr^{\varphi-1} with \varphi-1\approx 0.618 grows strictly faster. The initial peak at the boundary therefore permanently dominates the stationary regime. Assuming both conjectures, the derivation of the threshold law is immediate: M(r)=G(r-1) , so j_{k} is the smallest r with G(r-1)\geq k , giving j_{k}=S(k-1)+2 and j_{k+1}-j_{k}=G(k) . 10 Open questions and perspectives With the Golomb meta-structure reduced to two precise conjectures (the Prefix Conjecture and the Domination Lemma), several structural and analytic questions remain open. We conclude with six open problems. 1. The singular limit and phase transition ( r\to\infty ). For any finite r , the sequence exhibits oscillatory linear growth a(n)\asymp n , whereas Golomb’s sequence (the formal limit r\to\infty ) grows sublinearly as G(n)\sim Cn^{\varphi-1} . How does the sequence undergo this phase transition? Specifically, letting L_{\max}(r)=\limsup_{n\to\infty}a(n)/n , numerical evidence suggests that L_{\max}(r) is strictly decreasing (values 3/4 , 5/8 , 25/48 , 93/200 for r=2,3,4,5 respectively). Does \lim_{r\to\infty}L_{\max}(r)=0 ? 2. Explicit denesting structure. Theorem 2.9 proves r -regularity for all r . However, the DFAO produced is large. For each r , does the almost Golomb sequence admit an explicit denesting a(rn+i)=T_{r}(n+s_{i})+\delta_{i}+\varepsilon_{i}(n) with \varepsilon_{i} r -automatic and satisfying compact Boolean recurrences, as established for r\leq 5 ? A proof of this finer structure would explain why Walnut produces automata with O(r^{2}) states rather than the theoretical bound. 3. Cesàro means. For r=2 , Theorem 7.1 shows that the Cesàro means of a(n)/n do not converge. For r\geq 3 , do the block averages \frac{1}{N}\sum_{n=1}^{N}a(n)/n converge, or do they exhibit fractal fluctuations periodic in \log_{r}N ? 4. Automaticity of the full multiplicity sequence. For r=2 , (N_{2}(n)) is 2 -automatic (Proposition 7.3 ). Does the r -regularity of (a(n)) guarantee that (N_{r}(n))_{n\geq 1} is always r -automatic? 5. Combinatorial interpretations for r\geq 4 . Section 8 provides a second-bit characterization and a Boolean cellular automaton for r=2 , and a palindromic substitution rule for r=3 . Do the cases r\geq 4 admit analogous combinatorial descriptions of the difference sequence, and can the delayed-feedback mechanism of Remark 8.6 be made quantitative? 6. The gap- s variant. Fix a gap s\geq 1 and consider the sequence defined by a\bigl(a(n)+a(n-s)\bigr)=n for n\geq s+1 , with a(k)=0 for k\leq 0 and a(1)=1 . For s=1 this is the almost Golomb sequence of order r=2 studied in Section 3 . For s=2 , the sequence begins 1,2,2,3,3,4,5,6,6,7,7,8,8,\ldots and satisfies a(n+1)-a(n)\in\{0,1\} for all n\geq 1 . One can show that the sequence admits an exact divide-and-conquer structure modulo a binary correction sequence \varepsilon(n)\in\{0,1\} , whose support is \mathcal{I}=\{5,12\}\;\cup\;\bigcup_{k\geq 2}\mathcal{I}_{k},\qquad\mathcal{I}_{k}=\bigl[5\cdot 2^{k}+2,\;6\cdot 2^{k}-2\bigr]\cap(4\mathbb{Z}+2), with |\mathcal{I}_{k}|=2^{k-2} , satisfying \mathcal{I}_{k}=\{6\cdot 2^{k}-2\}\cup(2\cdot\mathcal{I}_{k-1}-2) . Two families of exact values hold: a(7\cdot 2^{k})=5\cdot 2^{k}\ (k\geq 1),\quad a(5\cdot 2^{k})=7\cdot 2^{k-1}\ (k\geq 2),\quad a(3\cdot 2^{k})=17\cdot 2^{k-3}\ (k\geq 3), and a(n)/n oscillates between the exact limits \liminf_{n\to\infty}\frac{a(n)}{n}=\frac{7}{10},\qquad\limsup_{n\to\infty}\frac{a(n)}{n}=\frac{5}{7}. This should be compared with the Stern diatomic sequence [ 3 , Chap. 16] ( A002487 ), which satisfies s(2n)=s(n) , s(2n+1)=s(n)+s(n+1) , is 2 -regular with differences in \{0,1\} , and admits no correction sequence because its denesting is exact. For s=3 , the sequence 1,3,3,4,4,5,5,6,7,8,8, 9,10,11,11,\ldots has differences in \{0,1,2\} and numerical investigation reveals no stable divide-and-conquer recurrence at any base. This case appears to escape the 2 -regular framework entirely. It is an open problem to determine for which values of s the gap- s almost Golomb sequence is 2 -regular, and whether s\in\{1,2\} are the only cases admitting an exact correction-set description. Appendix A Illustrative quaternary derivations This appendix presents two sample derivations from Theorem 5.3 , to illustrate the elimination mechanism that produces the Boolean recurrences. All sixteen recurrences are obtained by the same procedure; the complete system is certified by Walnut (Appendix E ), which constitutes the formal proof. Notation For m\geq 5 set \displaystyle X_{m} \displaystyle:=a(m-3)+a(m-2)+a(m-1)+a(m), \displaystyle Y_{m} \displaystyle:=a(m-2)+a(m-1)+a(m)+a(m+1), \displaystyle Z_{m} \displaystyle:=a(m-1)+a(m)+a(m+1)+a(m+2). The denesting formulas ( 31 )–( 34 ) then read \displaystyle a(4m) \displaystyle=X_{m}+1+\varepsilon_{0}(m), \displaystyle\quad a(4m+1) \displaystyle=Y_{m}+\varepsilon_{1}(m), \displaystyle a(4m+2) \displaystyle=Y_{m}+\varepsilon_{2}(m), \displaystyle\quad a(4m+3) \displaystyle=Z_{m}-1+\varepsilon_{3}(m). Note the identities Z_{m-1}=Y_{m} and Y_{m-1}=X_{m} (both immediate from the definitions by shifting m by -1 ). Derivation 1: ( 37 ), easy case \varepsilon_{0}(4m+2)=\varepsilon_{0}(m) By definition of \varepsilon_{0} , \varepsilon_{0}(4m+2)=a\bigl(4(4m+2)\bigr)-X_{4m+2}-1, where X_{4m+2}=a(4m-1)+a(4m)+a(4m+1)+a(4m+2) . Expanding each term via ( 31 )–( 34 ): \displaystyle a(4m-1) \displaystyle=a(4(m-1)+3)=Z_{m-1}-1+\varepsilon_{3}(m-1)=Y_{m}-1+\varepsilon_{3}(m-1), \displaystyle a(4m) \displaystyle=X_{m}+1+\varepsilon_{0}(m), \displaystyle a(4m+1) \displaystyle=Y_{m}+\varepsilon_{1}(m), \displaystyle a(4m+2) \displaystyle=Y_{m}+\varepsilon_{2}(m). Hence X_{4m+2}=3Y_{m}+X_{m}+(\varepsilon_{3}(m-1)+\varepsilon_{0}(m)+\varepsilon_{1}(m)+\varepsilon_{2}(m)) . Now expand a(4(4m+2)) by noting 4(4m+2)=4\cdot(4m+2) . Since 4m+2\equiv 2\pmod{4} , equation ( 33 ) gives a(4(4m+2))=Y_{4m+2}+\varepsilon_{2}(4m+2) . The sum Y_{4m+2}=a(4m)+a(4m+1)+a(4m+2)+a(4m+3) is given by \displaystyle Y_{4m+2} \displaystyle=(X_{m}+1+\varepsilon_{0}(m))+(Y_{m}+\varepsilon_{1}(m))+(Y_{m}+\varepsilon_{2}(m))+(Z_{m}-1+\varepsilon_{3}(m)) \displaystyle=X_{m}+2Y_{m}+Z_{m}+(\varepsilon_{0}(m)+\varepsilon_{1}(m)+\varepsilon_{2}(m)+\varepsilon_{3}(m)). Substituting and using Z_{m}=Y_{m}+(a(m+2)-a(m-2)) : \displaystyle\varepsilon_{0}(4m+2) \displaystyle=Y_{4m+2}+\varepsilon_{2}(4m+2)-X_{4m+2}-1 \displaystyle=\bigl[X_{m}+3Y_{m}+a(m+2)-a(m-2)\bigr]+\bigl[\varepsilon_{0}+\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}\bigr](m)+\varepsilon_{2}(4m+2) \displaystyle\quad-\bigl[3Y_{m}+X_{m}+\varepsilon_{3}(m-1)+\varepsilon_{0}(m)+\varepsilon_{1}(m)+\varepsilon_{2}(m)\bigr]-1 \displaystyle=(a(m+2)-a(m-2)-1)+\varepsilon_{3}(m)-\varepsilon_{3}(m-1)+\varepsilon_{2}(4m+2). Since \varepsilon_{0}(4m+2)\in\{0,1\} and \varepsilon_{2}(4m+2)\in\{0,1\} , and a(m+2)-a(m-2)\in\{2,3,4\} (unit increments, window of length 4 ), direct comparison of cases yields a(m+2)-a(m-2)-1=1+\delta and \varepsilon_{3}(m)-\varepsilon_{3}(m-1)+\varepsilon_{2}(4m+2)=\varepsilon_{0}(m)-\delta for \delta\in\{0,1\} , collapsing to \varepsilon_{0}(4m+2)=\varepsilon_{0}(m) . This identity is equivalent to ( 37 ) and is certified by Walnut for all n . Derivation 2: ( 40 ), typical case \varepsilon_{1}(4m+1)=1-\varepsilon_{2}(m) The defining equation at n=4m+1 states a(S_{4m+1})=4m+1 , where S_{4m+1}=a(4m+1)+a(4m)+a(4m-1)+a(4m-2). Expanding: \displaystyle a(4m+1) \displaystyle=Y_{m}+\varepsilon_{1}(m), \displaystyle a(4m) \displaystyle=X_{m}+1+\varepsilon_{0}(m), \displaystyle a(4m-1) \displaystyle=Y_{m}-1+\varepsilon_{3}(m-1), \displaystyle a(4m-2) \displaystyle=X_{m}+\varepsilon_{2}(m-1). Hence S_{4m+1}=2X_{m}+2Y_{m}+(\varepsilon_{1}(m)+\varepsilon_{0}(m)+\varepsilon_{3}(m-1)+\varepsilon_{2}(m-1)) . Writing E_{m}:=\varepsilon_{0}(m)+\varepsilon_{1}(m)+\varepsilon_{2}(m-1)+\varepsilon_{3}(m-1)\in\{0,1,2,3,4\} and F_{m}:=a(m-2)+a(m-1)+a(m) , one has 2X_{m}+2Y_{m}=4F_{m}+2(a(m-3)+a(m+1)) , so S_{4m+1}\equiv 2(a(m-3)+a(m+1))+E_{m}\pmod{4} . The residue of S_{4m+1} modulo 4 determines which of ( 31 )–( 34 ) applies at S_{4m+1} , and therefore which \varepsilon_{j} appears when one writes a(S_{4m+1})=4m+1 . In each of the four sub-cases, imposing a(S_{4m+1})=4m+1 and using the known values of \varepsilon_{j}(m+\delta) for |\delta|\leq 1 yields the single Boolean identity \varepsilon_{1}(4m+1)=1-\varepsilon_{2}(m). This is ( 40 ). The identity is certified by Walnut for all n . How to obtain the remaining recurrences Each of the fourteen remaining identities in ( 35 )–( 50 ) is obtained by the same two-step procedure: first expand X_{4m+i} or S_{4m+i} using ( 31 )–( 34 ), then expand a(4(4m+i)) or a(S_{4m+i}) according to the residue class. The result is always a Boolean polynomial in \varepsilon_{j}(m+\delta) with |\delta|\leq 1 , which simplifies to the stated recurrence. All sixteen identities are certified by Walnut. Appendix B Illustrative quinary derivations Notation For m\geq 4 set W_{m}:=a(m)+a(m-1)+a(m-2)+a(m-3)+a(m-4)=T_{5}(m). The denesting formulas ( 57 )–( 59 ) read a(5m)=W_{m}+2+\varepsilon(m),\quad a(5m+1)=W_{m+1}+1-\varepsilon(m),\quad a(5m+2)=W_{m+2}-1-\eta(m). Derivation of ( 58 ): a(5m+1)=T_{5}(m+1)+1-\varepsilon(m) The defining equation at n=5m+1 reads a(S)=5m+1 where S=a(5m+1)+a(5m)+a(5m-1)+a(5m-2)+a(5m-3) . Expand the four terms a(5m),a(5m-1),a(5m-2),a(5m-3) using ( 57 ), ( 59 ) (at n=m-1 ), and the neighbouring residue formulas. The deterministic part of S equals T_{5}(m+1)+(1-\varepsilon(m))+W_{m} , and after the second expansion via a(S)=5m+1 all a(\cdot) -terms cancel, yielding ( 58 ). Derivation of ( 52 ): \varepsilon(5m)=\varepsilon(m-1)(1-\varepsilon(m)) By definition \varepsilon(5m)=a(25m)-T_{5}(5m)-2 . Write T_{5}(5m)=a(5m)+a(5m-1)+\cdots+a(5m-4) and expand each term using the residue formulas at scale m : \displaystyle a(5m) \displaystyle=W_{m}+2+\varepsilon(m), \displaystyle a(5m-1) \displaystyle=W_{m}+1-\varepsilon(m-1)(1-\varepsilon(m-1)), \displaystyle a(5m-2) \displaystyle=W_{m}-\eta(m-1)-1, \displaystyle a(5m-3) \displaystyle=W_{m}-2+\theta(m-1), \displaystyle a(5m-4) \displaystyle=W_{m}+2+\varepsilon_{4}(m-1). Summing and subtracting 2 produces \varepsilon(5m) in terms of Boolean expressions of (\varepsilon(m-1),\eta(m-1)) ; simplification using the transition structure of U yields \varepsilon(5m)=\varepsilon(m-1)(1-\varepsilon(m)) , i.e. ( 52 ). How to obtain the remaining recurrences in Theorem 6.1 Each of the nine remaining identities ( 53 )–( 56 ) is obtained by the same procedure: apply the defining equation at n=5m+d for the appropriate d , expand the window sum via the five residue formulas, and cancel the a(\cdot) -terms. The result is always a function of (\varepsilon(m),\eta(m)) or (\varepsilon(m-1),\eta(m-1)) , which simplifies to the stated recurrence. Appendix C Quinary correction tables Write U(n)=(\varepsilon(n),\eta(n))\in\{(0,0),(1,0),(0,1)\} . For m\geq 3 the only transitions (U(m-1),U(m)) that occur are: (0,0)\to(0,0),\quad(0,0)\to(0,1),\quad(0,1)\to(1,0),\quad(1,0)\to(0,0),\quad(1,0)\to(0,1). Table for \theta The corrector \theta(5m+d)\in\{0,1\} is determined by (U(m-1),U(m)) and d\in\{0,1,2,3,4\} : \begin{array}[]{c|ccccc}(U(m-1),U(m))&d=0&1&2&3&4\\ \hline\cr((0,0),(0,0))&1&1&1&1&1\\ ((1,0),(0,0))&1&1&1&1&1\\ ((0,0),(0,1))&0&1&0&1&0\\ ((1,0),(0,1))&0&1&0&1&0\\ ((0,1),(1,0))&1&0&1&0&1\end{array} Table for \varepsilon_{4} For d\in\{0,1,2,3\} , set \sigma(m)=\varepsilon(m)+\eta(m) ; then \varepsilon_{4}(5m+d)=\begin{cases}-2-\sigma(m)-\varepsilon(m),&d\in\{0,2\},\\ -2-\sigma(m)-\eta(m),&d\in\{1,3\}.\end{cases} For d=4 , the value is determined by (U(m),U(m+1)) : \varepsilon_{4}(5m+4)=\begin{cases}-2,&(U(m),U(m+1))=((0,0),(0,0)),\\ -3,&(U(m),U(m+1))\in\bigl\{((0,0),(0,1)),((0,1),(1,0)),((1,0),(0,0))\bigr\},\\ -4,&(U(m),U(m+1))=((1,0),(0,1)).\end{cases} All entries are consistent with the 5 -automatic structure certified by Walnut (Appendix E ) and have been verified independently for all n\leq 2000 . Appendix D A menagerie of nested self-referential sequences The almost Golomb sequences studied in this paper belong to a broader landscape of self-referential sequences admitting a denesting into base- k divide-and-conquer formulas. We collect here the most relevant examples for comparison, distinguishing two types. Monotone sequences These are defined greedily: a(n) is the smallest integer \geq a(n-1) consistent with the defining constraint. They are nondecreasing by construction, unbounded, and hence k -regular (not k -automatic) for appropriate k ; see [ 2 ] and [ 3 , Chapter 16] . OEIS Implicit rule & denesting k -reg. A003605 a(a(n))=3n ; a(3n)=3a(n) , a(3n{+}1)=2a(n){+}a(n{+}1) , a(3n{+}2)=a(n){+}2a(n{+}1) 3 A079000 a(a(n))=2n+3 ; 2 -adic formulas [ 8 , 1 ] 2 A080637 a(a(n))=2n+1 ; 2 -adic formulas [ 8 , 1 ] 2 A394217 a(a(n){+}a(n{-}1))=n ; a(2n)=a(n){+}a(n{+}1){-}1 , a(2n{+}1)=a(n){+}a(n{+}1) 2 A394218 a(a(n){+}a(n{-}1){+}a(n{-}2))=n ; 3 -adic with correction \mathbf{1}_{\mathcal{I}} , § 4 3 The last two rows are the almost Golomb sequences of orders 2 and 3 studied in this paper, which generalize the a(a(n))=kn family (studied systematically in [ 1 ] ) by replacing the single nested index a(n) with a sliding window sum. A related family of meta-automatic sequences, combining nested meta-Fibonacci recurrences with digit-based rules, is studied in [ 5 ] . Earliest (non-monotone) sequences These are defined differently: a(n) is the smallest positive integer not yet used consistent with the constraint. They are not nondecreasing in general, and their structure is quite different from the monotone case. OEIS Implicit rule & denesting Type A002516 a(a(n))=2n , earliest; a(4n)=2a(2n) , a(4n{+}1)=4n{+}3 , a(4n{+}3)=8n{+}2 2 -aut. A002517 a(a(n))=3n , earliest; a(3n)=3a(n) , a(3n{+}1)=3n{+}2 , a(3n{+}2)=9n{+}3 3 -aut. The earliest sequences take values in a rearrangement of the integers, whereas the monotone sequences (and the almost Golomb sequences) are nondecreasing. This difference accounts for the fact that the earliest sequences are k -automatic (bounded values modulo finite-state processing) while the monotone ones are merely k -regular (unbounded but finitely generated kernel). Appendix E DFAO data for the correction sequences This appendix provides transition tables of DFAOs (deterministic finite automata with output) realising the correction sequences for r=4 and r=5 . All automata read the base- r expansion of n from most significant to least significant digit. The initial state is always state 0 . The tables were exported from the Walnut certification and verified against the recurrence systems of Theorems 5.3 and 6.1 on a large initial range. Note. The proofs in this paper do not depend on these tables. The non-convergence results (Theorems 7.6 and 7.8 ) rely on Lemma 2.8 applied to the recurrence systems of Theorems 5.3 and 6.1 , not on the printed DFAO data. The tables are included for reference and reproducibility only. The case r=4 The four correction sequences \varepsilon_{0},\varepsilon_{1},\varepsilon_{2},\varepsilon_{3} of Theorem 5.3 are each recognised by an explicit DFAO reading base- 4 expansions. DFAO for \varepsilon_{0} (base 4 , 30 states, initial state 0 ) State out d=0 d=1 d=2 d=3 0 0 0 1 2 2 1 0 3 4 14 18 2 0 18 18 18 18 3 0 22 6 25 5 4 0 15 22 6 25 5 0 16 23 7 26 6 0 16 23 7 27 7 0 17 24 8 28 8 0 29 29 13 29 9 0 12 28 10 12 10 0 13 29 13 13 11 0 28 10 12 28 12 0 29 13 13 29 13 0 0 0 0 0 14 1 5 15 19 19 15 1 7 16 20 20 16 1 8 17 21 21 17 1 13 29 29 29 18 1 19 19 19 19 19 1 20 20 20 20 20 1 21 21 21 21 21 1 29 29 29 29 22 1 23 7 26 7 23 1 24 8 28 8 24 1 29 13 29 13 25 1 9 11 26 7 26 1 10 12 28 8 27 1 10 12 28 10 28 1 13 13 29 13 29 1 0 0 0 0 DFAO for \varepsilon_{1} (base 4 , 30 states, initial state 0 ) State out d=0 d=1 d=2 d=3 0 0 0 6 1 1 1 0 2 2 2 2 2 0 3 3 3 3 3 0 4 4 4 4 4 0 5 5 5 5 5 0 21 21 21 21 6 0 9 22 15 2 7 0 20 28 8 20 8 0 21 29 21 21 9 0 10 25 12 23 10 0 11 26 13 24 11 0 14 28 14 28 12 0 19 27 13 24 13 0 20 28 14 28 14 0 21 29 21 29 15 0 23 16 3 3 16 0 24 17 4 4 17 0 28 18 5 5 18 0 29 21 21 21 19 0 28 8 20 28 20 0 29 21 21 29 21 0 0 0 0 0 22 1 16 10 25 12 23 1 17 11 26 13 24 1 18 14 28 14 25 1 17 11 26 7 26 1 18 14 28 8 27 1 8 20 28 8 28 1 21 21 29 21 29 1 0 0 0 0 DFAO for \varepsilon_{2} (base 4 , 29 states, initial state 0 ) State out d=0 d=1 d=2 d=3 0 0 0 1 2 2 1 0 3 12 17 20 2 0 20 20 20 20 3 0 4 14 7 13 4 0 5 15 8 15 5 0 6 16 10 16 6 0 11 28 11 28 7 0 24 26 8 15 8 0 25 27 10 16 9 0 25 27 10 25 10 0 28 28 11 28 11 0 0 0 0 0 12 1 18 4 14 7 13 1 19 5 15 8 14 1 19 5 15 9 15 1 23 6 16 10 16 1 28 11 28 11 17 1 13 18 21 21 18 1 15 19 22 22 19 1 16 23 23 23 20 1 21 21 21 21 21 1 22 22 22 22 22 1 23 23 23 23 23 1 28 28 28 28 24 1 27 10 25 27 25 1 28 11 28 28 26 1 10 25 27 10 27 1 11 28 28 11 28 1 0 0 0 0 DFAO for \varepsilon_{3} (base 4 , 30 states, initial state 0 ) State out d=0 d=1 d=2 d=3 0 0 0 5 1 1 1 0 2 2 2 2 2 0 3 3 3 3 3 0 4 4 4 4 4 0 9 9 9 9 5 0 10 11 6 2 6 0 12 7 3 3 7 0 13 8 4 4 8 0 16 9 9 9 9 0 19 19 19 19 10 0 20 14 22 12 11 0 7 20 14 22 12 0 8 21 15 23 13 0 9 24 16 24 14 0 8 21 15 25 15 0 9 24 16 26 16 0 19 29 19 29 17 0 26 28 18 26 18 0 29 29 19 29 19 0 0 0 0 0 20 1 21 15 23 13 21 1 24 16 24 16 22 1 27 17 23 13 23 1 28 18 24 16 24 1 29 19 29 19 25 1 28 18 26 28 26 1 29 19 29 29 27 1 18 26 28 18 28 1 19 29 29 19 29 1 0 0 0 0 The case r=5 The pair U(n)=(\varepsilon(n),\eta(n)) of Theorem 6.1 takes values in \{(0,0),(1,0),(0,1)\} and is recognised by an explicit DFAO reading base- 5 expansions (encoded as 0,1,2 respectively). DFAO for U=(\varepsilon,\eta) (base 5 , 23 states, initial state 0 ) State U d=0 d=1 d=2 d=3 d=4 0 (0,0) 0 1 5 10 18 1 (0,0) 6 2 2 2 2 2 (0,0) 3 3 3 3 3 3 (0,0) 4 4 4 4 4 4 (0,0) 9 9 9 9 9 5 (0,0) 2 2 14 19 11 6 (0,0) 20 7 3 3 3 7 (0,0) 21 8 4 4 4 8 (0,0) 22 9 9 9 9 9 (0,0) 0 0 0 0 0 10 (0,1) 19 11 19 11 19 11 (0,1) 20 12 20 12 20 12 (0,1) 21 13 21 13 21 13 (0,1) 22 17 22 17 22 14 (0,1) 3 15 20 12 20 15 (0,1) 4 16 21 13 21 16 (0,1) 9 17 22 17 22 17 (0,1) 0 0 0 0 0 18 (1,0) 11 19 11 19 11 19 (1,0) 12 20 12 20 12 20 (1,0) 13 21 13 21 13 21 (1,0) 17 22 17 22 17 22 (1,0) 0 0 0 0 0