Beatty solutions of almost Golomb equations

Benoît Cloitre · 2026

Read Beatty solutions of almost Golomb equations by Benoît Cloitre (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-10822.txt.

Introduction

Cloitre studies the almost Golomb equation of order r: a of S of n equals n, S of n summing r consecutive terms of a. Its greedy solution is r-regular. For non-square order r, another solution exists: an inhomogeneous Beatty run with floor of n over root r plus d. The equation holds for n at or past r when d sits in an interval. That interval is a point at r equals 2, longer otherwise. Iterating gives solutions, settled at k equals 2 for r equals 2 and 3.

Catalog record

CREATORBenoît Cloitre
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60411
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.10822

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Beatty solutions of almost Golomb equations Benoît Cloitre Abstract The almost Golomb equation of order r r is the implicit functional equation a ⁡ ( ∑ j = 0 r − 1 a ⁡ ( n − j ) ) = n a\Bigl(\sum_{j=0}^{r-1}a(n{-}j)\Bigr)=n for nondecreasing sequences of positive integers with a ⁡ ( 1 ) = 1 a(1)=1 . Its earliest solution, the almost Golomb sequence of order r r , is r r -regular in the sense of Allouche and Shallit and has oscillating ratio a ⁡ ( n ) / n a(n)/n . We prove that for every r ≥ 2 r\geq 2 that is not an even perfect square, the equation admits a second monotone solution given by an inhomogeneous Beatty sequence of slope 1 / r 1/\!\sqrt{r} . Composing the equation with a a leads to a triple-nested identity which admits a continuous one-parameter family of inhomogeneous Beatty solutions, parametrised by a shift d d ranging over an explicit interval. We determine these intervals sharply for r = 2 r=2 and r = 3 r=3 , each proved by a local regime analysis combined with equidistribution of an irrational orbit. The endpoints of these intervals sit naturally inside the Pell–Ostrowski framework of Fokkink, and the defect set at the upper endpoint for r = 2 r=2 is characterised as the return-time set of an irrational rotation to an explicit interval. 2020 Mathematics Subject Classification. Primary 11B83. Secondary 11B37, 39B12, 91A46. Keywords. Beatty sequence, almost Golomb sequence, functional equation, Sturmian word, Pell tower, Ostrowski numeration. 1 Introduction 1.1 The almost Golomb equation Golomb’s sequence [ 6 ] is the unique nondecreasing sequence of positive integers in which n appears exactly a(n) times. It satisfies a(\sum_{k=1}^{n}a(k))=n and grows like a(n)\sim\varphi^{2-\varphi}n^{\varphi-1} , where \varphi=(1+\sqrt{5})/2 is the golden ratio. Replacing the cumulative sum by a sliding window of size r leads to the Golomb equation of order r a\Bigl(\sum_{j=0}^{r-1}a(n{-}j)\Bigr)=n,\qquad n\geq 1, (1) with a(k)=0 for k<1 . The earliest nondecreasing solution, called the almost Golomb sequence of order r in [ 2 ] , is obtained inductively: a(n) is the smallest integer \geq a(n{-}1) consistent with ( 1 ). This finite-memory truncation changes the nature of the sequence. The smooth power law gives way to oscillatory linear growth, and the greedy solution is r -regular in the sense of Allouche and Shallit [ 1 ] for every r\geq 2 [ 2 ] . Writing f(n)=\sum_{j=0}^{r-1}a(n{-}j) , equation ( 1 ) reads a\circ f=\mathrm{id} . Equation ( 1 ) is implicit . It constrains a at position f(n) , which depends on a itself and typically lies far beyond n . This self-referential addressing creates room for multiple solutions beyond the greedy one. 1.2 The greedy solution The greedy (earliest) solution of ( 1 ) is studied in detail in the companion paper [ 2 ] . It is unique, r -regular, and has explicit r -adic denesting formulas. For r=2 ( A394217 ), it begins 1,\,2,\,2,\,3,\,4,\,4,\,5,\,6,\,7,\,7,\,8,\,\mathbf{8},\,9,\,10,\,11,\,12,\,13,\,13,\,14,\,14,\,\ldots and satisfies the dyadic recurrences a(2n)=a(n)+a(n{+}1)-1 and a(2n{+}1)=a(n)+a(n{+}1) [ 2 ] . Its ratio a(n)/n oscillates between 2/3 and 3/4 and does not converge [ 2 ] . 1.3 A second solution In this paper we show that, once the greedy constraint is removed, the same implicit equation admits a second monotone solution of a different nature. The case r=2 already illustrates the phenomenon. Theorem 1 . The inhomogeneous Beatty sequence a(n)=\Bigl\lfloor\frac{n+1}{\sqrt{2}}\Bigr\rfloor,\qquad n\geq 1, (2) with a(k)=0 for k<1 , satisfies the Golomb equation of order 2 : a\bigl(a(n)+a(n{-}1)\bigr)=n\qquad\text{for all }n\geq 1. (3) This Beatty solution begins 1,\,2,\,2,\,3,\,4,\,4,\,5,\,6,\,7,\,7,\,8,\,\mathbf{9},\,9,\,10,\,11,\,12,\,12,\,13,\,14,\,14,\,\ldots The two solutions agree on [1,11] and diverge at n=12 , where the greedy repeats the value 8 (run of length 2 ), while the Beatty moves to 9 (run of length 1 ). This is possible because the constraint at n=12 applies at position f(12)=a(12)+a(11) , which is 16 for the greedy and 17 for the Beatty. Both sequences thus satisfy the equation at n=12 , but with the constraint applied at different positions, allowing divergence of the two solutions from that point on. In the rest of the paper, a_{\mathrm{G}} and a_{\mathrm{B}} denote the greedy and the canonical Beatty solutions for the case r=2 . Otherwise a is generic and is made precise by the context. The table below compares the two solutions and their constrained positions S_{n}=a(n)+a(n{-}1) near the first divergence point. n a_{\mathrm{G}}(n) a_{\mathrm{B}}(n) S^{\mathrm{G}}_{n} S^{\mathrm{B}}_{n} a_{\mathrm{G}}(S^{\mathrm{G}}_{n}) a_{\mathrm{B}}(S^{\mathrm{B}}_{n}) 10 7 7 14 14 10 10 11 8 8 15 15 11 11 12 8 9 16 17 12 12 13 9 9 17 18 13 13 14 10 10 19 19 14 14 Greedy Beatty Rule local, minimal global, irrational slope Structure 2-regular, dyadic Sturmian, Ostrowski a(n)/n oscillates ( 2/3\leftrightarrow 3/4 ) converges to 1/\!\sqrt{2} Multiplicity 2 -automatic Sturmian The residual a_{\mathrm{B}}(n)-n/\!\sqrt{2} is bounded and equals -\{(n{+}1)/\!\sqrt{2}\}\in(-1,0] , whereas a_{\mathrm{G}}(n)-n/\!\sqrt{2} grows without bound because a_{\mathrm{G}}(n)/n oscillates in [2/3,3/4] rather than converging to 1/\!\sqrt{2} . Theorem 1 is the case r=2 of the following general result. Theorem 2 . Let r\geq 2 and define the order- r Beatty sequence a(n)=\Bigl\lfloor\frac{n}{\sqrt{r}}+\frac{\sqrt{r}}{2}\Bigr\rfloor. (4) Then a\bigl(\sum_{j=0}^{r-1}a(n{-}j)\bigr)=n for all n\geq r if and only if r is not an even perfect square. When r=s^{2} with s even, the left-hand side equals n+1 instead of n . When s is odd the identity holds as in the non-square case (Theorem 13 ). The proof combines three ingredients. The continuous functional equation identifies the unique affine candidate (Section 2 ). Floor discretisation then reduces the identity to a finite counting inequality on fractional parts of multiples of 1/\!\sqrt{r} (Proposition 9 ). A parity argument on t=r-\lfloor\sqrt{r}\rfloor^{2} establishes this inequality for all non-square r (Section 3 ). 1.4 The triple-nested family Applying a to both sides of ( 3 ) gives a(a(f(n)))=a(n) , the triple-nested equation a\bigl(a(a(n)+a(n{-}1))\bigr)=a(n). (5) Write the inhomogeneous Beatty sequence of slope c=1/\!\sqrt{2} and shift d as a(n)=\lfloor cn+d\rfloor. The canonical solution ( 2 ) corresponds to d=\sqrt{2}/2 , which is the unique shift for which the strong identity ( 3 ) holds. The weaker triple-nested identity ( 5 ), by contrast, admits a continuous family of shifts. The paper determines this interval sharply for r=2 , and the analogous interval for r=3 . Theorem 3 . Let c=1/\!\sqrt{2} and I=[\sqrt{2}/2,\;2(\sqrt{2}-1)] . The sequence defined by a(n)=\lfloor cn+d\rfloor satisfies ( 5 ) for all n\geq 2 if and only if d\in I . The analogous theorem for r=3 , stated and proved in Section 4.6 , gives a(a(a(n)+a(n{-}1)+a(n{-}2)))=a(n)\quad\text{for all }n\geq 3\iff d\in I_{3}=\Bigl[\frac{\sqrt{3}+3}{6},\;\frac{5\sqrt{3}-3}{6}\Bigr]. Both intervals are proved sharp by the same method, namely a local analysis of the four combinatorial regimes induced by the Sturmian rotation combined with equidistribution of the irrational orbit. Convergents of c play no role in the proof. The right endpoint d=2(\sqrt{2}{-}1) for r=2 admits a simple algebraic form. At this boundary the strong identity fails on a sparse defect set. We prove (Theorem 24 ) that this defect set is the return-time set of the Sturmian rotation \theta\mapsto\{\theta+c\} to the interval [1{-}c,1/2] , which explains every failure by absorption into a repeat of a_{\mathrm{B}} . The three-distance theorem then yields three gap values \{3,4,7\} . Numerical evidence suggests that the gap sequence

Read the complete text