Anti-Recurrence Sequences

2025

Read Anti-Recurrence Sequences (2025) 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-2506-13337.txt.

Introduction

Fokkink and Joshi settle an open question about anti-recurrence sequences, a family of number sequences defined by avoiding their own past patterns, in a 2025 paper. Earlier researchers had asked several questions about these sequences, which combine into one broad conjecture: every such sequence can be written as a sum of simple arithmetic progressions and automatic sequences.

The authors prove the conjecture under a restriction on the linear rule that generates the sequence. Their work extends results by Kimberling and Moses, Zaslavsky, and Bosma and co-authors. The catalog record for this paper lists no creator; the text itself names the two authors above.

Catalog record

YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-13337

Browse the full library · About the Tower of Babel

Full text

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

Anti-Recurrence Sequences Abstract We extend previous work on anti-recurrence sequences of Kimberling and Moses, Zaslavsky, and Bosma et al. Kimberling and Moses have formulated several questions on these sequences, which can be combined into the meta-conjecture that anti-recurrence sequences are sums of linear progressions and automatic sequences. We solve this conjecture under a restriction on the linear form that generates the anti-recurrence. Robbert Fokkink Technical University Delft Faculty of Mathematics Mekelweg 4, 2628CD The Netherlands [email protected] Gandhar Joshi School of Mathematics and Statistics The Open University Walton Hall Milton Keynes, MK7 6AA UK [email protected] In a linear recurrence sequence, each term is a linear combination of the ones that came before it. The study of these sequences is a topic in itself [ 4 ] . The first example that jumps to everyone’s mind is the Fibonacci sequence F_{n+1}=F_{n}+F_{n-1}, starting from the initial conditions F_{0}=0 and F_{1}=1 . These numbers have a generative nature. Starting from the immortal Eve, F_{n} is the number of female rabbits in the n -th generation, if each mature female produces the perfect offspring of one female and one male baby rabbit, which mature in the next generation, ready to reproduce. This happens in perfect sync, forever and ever; as a mathematical abstraction, of course. In reality, the average number of babies per litter is 4.5, and female rabbits produce up to ten litters per lifetime [ 2 ] . Recurrence sequences are defined by earlier terms in the sequence. In contrast with this, the anti-recurrence sequences, which we consider in this paper, are defined by earlier terms that are not in the sequence. The anti-Fibonacci numbers start with A_{0}=0 . They extend by the rule The next anti-Fibonacci number is the sum of the two most recent NON-members of the anti-Fibonacci sequence. The first two non-members 1 and 2 add up to the anti-Fibonacci A_{1}=3 . The next two non-members are 4 and 5, which add up to the anti-Fibonacci A_{2}=9 , etc. This sequence is listed under A075326 in the On-Line Encyclopedia of Integer Sequences. 0,3,9,13,18,23,29,33,39,43,49,53,58,63,69,73,78,83,89,93,98,103,109,113,\ldots It was entered into the OEIS by Amarnath Murthy and was named anti-Fibonacci by Douglas Hofstadter in an unpublished note [ 6 ] . He observed that the first difference sequence (1) 3,6,4,5,5,6,4,6,4,6,4,5,5,6,4,5,5,6,4,5,5,6,4,\ldots consists of the two-letter words 64 and 55 , apart from the initial letter 3 . This is A249032 in the OEIS. All numbers with final digit 3 are anti-Fibonaccis, and the other anti-Fibonaccis either end with a 9 or an 8. Hofstadter observed, without giving a proof, that the pattern of 9’s and 8’s can be generated from a period-doubling substitution 9\mapsto 98,\ 8\mapsto 99. The proof was supplied by Thomas Zaslavsky, in another unpublished note [ 14 ] . In particular, he gave an explicit equation for the anti-Fibonacci numbers (2) \text{For all }n\geq 1,\quad\hrefhttps://oeis.org/A075326(n)-5n+2=\texttt{PD}_{n-1}. The period doubling sequence \mathtt{PD}_{n} consists of zeros and ones and is generated by 0\mapsto 01,\ 1\mapsto 00, starting from \mathtt{PD}_{0}=0 . It is entry A096268 in the OEIS. Note that the indexing runs from 0 and not from 1. This is culturally defined. CAUTION: For automatic sequences such as PD , indexing starts at zero. Clark Kimberling and Peter Moses studied the more general class of complementary sequences [ 8 ] , for which anti-recurrence sequences are a special case. They observed some properties of anti-recurrence sequences, which Kimberling entered as conjectures under A265389 , A299409 , A304499 , and A304502 in the OEIS. The conjectures for the first two sequences were verified by Bosma et al. [ 3 ] using Hamoon Mousavi’s automatic theorem prover Walnut [ 10 ] . We settle the other two conjectures on A304499 and A304502 in this paper, again with the assistance of Walnut . These conjectures can be combined into a meta-conjecture, which specifies the discussion in section six of [ 8 ] . It was named the Clergyman’s conjecture in [ 3 ] . Conjecture 1 . Every anti-recurrence sequence is a sum of a linear sequence and an automatic sequence. Our paper is organized as follows. In section 1 we review the basic notions. Section 2 settles the conjectures of Kimberling for A304499 and A304502 using Walnut . In section 3 we extend the results of Bosma et al. and solve the conjecture for anti-bonaccis. Our main result, Theorem 12 in section 4, settles the conjecture under a restriction on the linear form that generates it. We are unable to settle the full conjecture. 1 Definitions, notation, preliminary results All numbers are natural numbers (positive integers) unless stated otherwise. We will write sequences in capitals. Two strictly increasing sequences A_{n} and B_{n} of natural numbers are complementary if every natural number is either in A_{n} or in B_{n} exclusively. Let \mathbf{a}=(a_{1},\ldots,a_{k}) be a positive integral vector of dimension k>1 and all a_{i}>0 . Let f(\mathbf{x})=\mathbf{a}\cdot\mathbf{x} be its associated linear form. We say that A_{n} is an anti-recurrence sequence if (3) A_{n}=f(B_{(n-1)k+1},B_{(n-1)k+2},\ldots,B_{nk})=\sum_{j=1}^{k}a_{j}B_{(n-1)k+j}. The trace \tau of the linear form is \tau=\sum_{i=1}^{m}a_{i}\geq k . In a precise but elaborate naming convention, A_{n} is the anti-recurrence sequence and its complement B_{n} is the non-anti-recurrence sequence . We say that a set \{B_{jk+1},B_{jk+2},\ldots,B_{(j+1)k}) is the B -block that generates A_{j+1} . Note that we use X_{n} both for the sequence and the individual number and the context will make clear what we mean. If numbers \{a,a+1,\ldots,b\} are consecutive, then we say that they form the interval [a,b] . Lemma 2 . Successive anti-recurrence numbers satisfy A_{n+1}-A_{n}\geq k\tau. The above is an equality if the B -blocks for both A_{n+1} and A_{n} are intervals such that their union is also an interval. In particular, the inequality is strict if one block is an interval and the other is not. Proof. Let \mathbf{a}=(a_{1},\ldots,a_{k}) and let B_{n} be the non-anti-recurrence sequence. We have that A_{n}=\sum_{j=1}^{k}a_{j}B_{m+j} for m=k(n-1) and A_{n+1}=\sum_{j=1}^{k}a_{j}B_{k+m+j}. Now B_{k+m+j}-B_{m+j}\geq k since this sequence is increasing. If the B -blocks are consecutive intervals, then this is an equality. If one is an interval and the other is not, then there must be a j such that B_{k+m+j}-B_{m+j}>k . ∎ The mex or minimal excluded value of S\subset\mathbb{N} is \text{mex}(S)=\text{min}\left(\mathbb{N}\setminus S\right). It comes up naturally in anti-recurrences sequences, as observed by Kimberling and Moses. Lemma 3 . A positive linear form \mathbf{a} determines A_{n} and B_{n} . Proof. We need to show that the complementary sequences A_{n} and B_{n} exist and are unique. Let \mathcal{A}_{n}=\{A_{i}\colon i\leq n\} be the initial anti-recurrences and let \mathcal{B}_{kn}=\{B_{j}\colon j\leq kn\} be the initial B -blocks. By induction, we assume that [1,B_{kn}]\subset\mathcal{A}_{n}\cup\mathcal{B}_{kn}. Let b=\text{mex}\left(\mathcal{A}_{n}\cup\mathcal{B}_{kn}\right). The interval [b,b+k-1] has length k and by Lemma 2 can contain at most one number from \mathcal{A}_{n} . If it contains no such number, then [b,b+k-1] must be the B -block from B_{kn+1} up to B_{k(n+1)} since the sequence B_{n} consists of all numbers that are not in A_{n} . If one of the numbers in [b,b+k-1] is in \mathcal{A}_{n} , then the B -block from B_{kn+1} up to B_{k(n+1)} skip that number. In any case, the next B -block from B_{kn+1} up to B_{k(n+1)} is uniquely determined by a mex-rule and generates A_{n+1} . ∎ The linear form \mathbf{a}=(1,1) gives the anti-Fibonaccis. Its

Read the complete text