Meta-Automatic Sequences

John M. Campbell Department of Mathematics and Statistics Dalhousie University Halifax, NS B3H 4R2 Canada

                    jh241966@dal.ca

Benoît Cloitre 19, rue Louise Michel 92300 Levallois-Perret France

                 benoit7848c@yahoo.fr

Abstract

Nested (or meta-Fibonacci) recurrences, such as the recurrence used to define Hofstadter’s Q-sequence, along with the digit-based recurrences that underlie automatic sequences are of interest from both number-theoretic and combinatorial points of view. In this direction, Allouche and Shallit showed how the frequency sequence of a variant of the Q-sequence is 2-automatic. This inspires us to introduce what may be seen as a natural combination of the recurrences for meta-Fibonacci and automatic sequences, by introducing the concept of a meta-automatic sequence. We exhibit two binary meta-automatic sequences M_{1} and M_{2} whose defining recurrences do not satisfy the Allouche-Shallit automaticity criterion directly, and this is formalized in our paper. For each of these integer sequences M_{1} and M_{2}, we prove explicit DFAO evaluations, together with 4-uniform morphisms, and we also consider the factor complexities of these sequences.

1 Introduction

A nested recurrence is a recurrence in which a term a(n) is defined using values of a at indices that themselves depend on earlier values of the sequence. The classical example is Hofstadter’s Q-sequence [20, p. 137], indexed in the On-Line Encyclopedia of Integer Sequences [30] as \underline{A005185}, defined by Q(1) = Q(2) = 1 and

Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2))  (1)

for n > 2. Recurrences as in (1) are also known as meta-Fibonacci recurrences. Other examples of integer sequences satisfying nested recurrences include the sequence \underline{A244477} studied by Golomb [18]. Many problems concerning Hofstadter’s Q-sequence and its generalizations remain open to this day. Notably, it is not known whether or not Q(n) is even defined for all n > 0.

In contrast to nested recurrences, digit-based recurrences (also called divide-and-conquer recurrences) define a(k^{t}n + j) for j ∈ {0, 1, …, k^{t} − 1} as a function of previously computed values a(k^{t′}n′ + j′) with t′ < t and j′ ∈ {0, 1, …, k^{t′} − 1}. Digit-based recurrences can be used to define automatic sequences [3, 9], which appear in many areas of number theory, computer science, and combinatorics.

Allouche and Shallit [4] showed that the frequency sequence of a variant of Hofstadter’s Qsequence satisfies a digit-based recurrence, and, moreover, is 2-automatic. They also proved an automaticity criterion [4, Theorem 2.2] reviewed in Section 1.2 below. This inspires us to introduce the concept of a meta-automatic sequence, which may, informally, be thought of as “combining” the concepts of meta-Fibonacci and automatic sequences. This is formalized below. For example, in contrast to a rule such as a(4n + 2) = a(2n) used to define an automatic sequence, we consider rules such as

a(4n + 2) = a(2n + 1 − a(n)),  (2)

in which the argument of a on the right-hand side depends on the value a(n). A recurrence of the form suggested in (2) would not, in general, satisfy the Allouche-Shallit automaticity criterion, since the argument on the right is not of the required polynomial form.

The idea of combining automatic and meta-Fibonacci recurrences is motivated by past work on meta-Fibonacci sequences, in addition to the above referenced work by Allouche and Shallit [4]. We point to references on the Hofstadter Q-sequence [16, 17, 19, 27], on variants and generalizations of the Hofstadter Q-sequence [1, 2, 5, 12, 14, 32], and on meta-Fibonacci sequences [7, 8, 10, 11, 13, 15, 21, 22, 23, 28, 31].

1.1 Outline

A formal definition of a meta-automatic sequence is given in Section 2. A meta-automatic recurrence may, after simplification, reduce to a digit-based recurrence, in which case the Allouche-Shallit criterion applies directly. We formalize, in this paper, how meta-automatic sequences are not necessarily reducible in this way.

A binary sequence a : ℕ_{0} → {0, 1} is said to be balanced if

a(2n) + a(2n + 1) = 1 (n ≥ 0).  (3)

The binary sequences under consideration in this paper are, for the most part, balanced. In a related way, much of this paper makes use of the additive operation underlying the field 𝔽_{2} = {0, 1}, letting ⊕ denote this operation, which may be referred to as XOR, with 0 ⊕ 0 = 1 ⊕ 1 = 0 and 0 ⊕ 1 = 1 ⊕ 0 = 1. For balanced binary sequences, Lemma 5 gives the identity

a(2n + 1 − a(n)) = a(2n + 1) ⊕ a(n).

We prove that balanced, binary, meta-automatic sequences are, for the cases covered in Lemma 6, ultimately periodic. To obtain non-periodic examples, we therefore work with base-4 recurrences. We consider:

• The integer sequence M_{1} (\underline{A392736}), defined via a base-4 recurrence in which one of the rules in the recurrence is nested in the sense outlined above. After applying Lemma 5 below, the pair (M_{1}(n), b(n)), for b(n) defined in (8) below, yields a 4-state DFAO (Section 3).

• The integer sequence M_{2} (\underline{A391614}), defined via a base-4 recurrence in which both of the rules in the recurrence are nested in the sense outlined above. After applying Lemma 5, the pair (M_{2}(n), M_{2}(2n + M_{2}(n))) obeys an affine rule over 𝔽_{2}^{2} with linear part ( \begin{matrix}0 & 1 \\ 1 & 1 \end{matrix} ). The sequence satisfies M_{2}(n) = t(q(n)), where q is an explicit bit-masking operator and t is the Thue-Morse sequence (Theorem 26).

Although M_{1} and M_{2} both have 4-state DFAOs, we have that M_{2} admits the evaluation M_{2}(n) = t(q(n)), whereas M_{1} is described by means of the pair (M_{1}(n), b(n)). Their factorcomplexity functions, studied in Section 5, also differ. For each of the sequences M_{1} and M_{2}, we give a base-4 DFAO (MSB-first) and an explicit 4-uniform morphism, and we also investigate the factor complexity functions for M_{1} and M_{2} in Section 5.

1.2 Preliminaries

For background on automatic sequences, we refer to the texts of Allouche and Shallit [3] and of Shallit [29]. We proceed with the following definition, which may be used, as below, to define automatic sequences.

Definition 1. Let U = (U(n))_{n≥0} denote an infinite sequence. The k-kernel of (U(n))_{n≥0} [3, p. 185] is

K_{k}(U) = {(U_{k^{i}n+j})_{n≥0} : i ≥ 0 and 0 ≤ j < k^{i}} .

For k ≥ 2, a k-automatic sequence is a sequence U = (U(n))_{n≥0} such that K_{k}(U) is finite. Equivalently, the sequence U is k-automatic if there exists a DFAO such that, upon inputting the base-k representation of n, this DFAO outputs U(n). See Allouche and Shallit’s text [3] for details. A prototypical instance of an automatic sequence is the Thue-Morse sequence t : ℕ_{0} → {0, 1} defined so that t(0) = 0 and

t(2n) = t(n), t(2n + 1) = 1 − t(n) (n ≥ 0).

Equivalently, t(n) = s_{2}(n) mod 2, where s_{2}(n) is the sum of the binary digits of n, noting that the balanced condition in (3) holds. We introduce, in this paper, a variant of an automaticity criterion due to Allouche and Shallit [4], which we now recall.

Let U = (U(n))_{n≥0} denote a sequence, and let α denote an integer. Adopting notation from Allouche and Shallit’s work [4], for n ≥ −α, we write U^{α} in place of the sequence given by

U^{α} := U(n + α).

Similarly, letting q and i and j be positive integers, we write U_{q,i,j} in place of the sequence defined by

U_{q,i,j}(n) = U (q^{i}n + j)  (4)

for n ≥ 0. Moreover, for integers q ≥ 2 and t ≥ 1, we write s(q, t) = \frac{1−q^{t+1}}{1−q} in place of the number of pairs (i, j) of integers i and j such that 0 ≤ i ≤ t and 0 ≤ j ≤ q^{i} − 1. Fix an ordering of these pairs (i, j), with (0, 0) appearing first, and write the corresponding sequences as U_{1} = U, U_{2}, …, U_{s(q,t)}. The choice of ordering plays no role in what follows. We also let m(q, t) = q^{t+1} − 1.

Theorem 2. (Allouche and Shallit, 2012) Let the terms of (U(n))_{n≥0} be in a finite set A, and let q ≥ 2 denote an integer. Then U is q-automatic if there are nonnegative integers t, a, b, and n_{0} together with a family {f_{j} : j = 0, 1, …, m(q, t)} of functions from A^{a+b+s(q,t)} to A such that

U(q^{t+1}n + j) = f_{j}(U^{−a}(n), …, U^{−1}(n), U^{0}(n), U^{1}(n), …,

U^{b}(n), U_{2}(n), U_{3}(n), …, U_{s(q,t)}(n))

for all n ≥ n_{0} and for all j ∈ {0, 1, …, m(q, t)} [4].

2 Meta-automatic sequences

Let q > 0, i_{0} > 0, and j_{0} ≥ 0 be integers. For some v ≥ 0, and for indices k ∈ {1, 2, …, v}, let c_{k}, i_{k} > 0, and j_{k} ≥ 0 be integers, with i_{k} < i_{0} for all k. By analogy with (4), and assuming that the codomain of U is contained in ℕ_{0}, we write

U_{q,i_{0},j_{0},c_{1},i_{1},j_{1},...,c_{v},i_{v},j_{v}}(n) = U(q^{i_{0}}n + j_{0} + c_{1}U(q^{i_{1}}n + j_{1}) + ⋯ + c_{v}U(q^{i_{v}}n + j_{v})).

The following definition may be thought of as formalizing the intuition behind recurrences as in (2).

Definition 3. Suppose that each term of (U(n))_{n≥0} is in a finite subset A of ℕ_{0}, and let q ≥ 2 be an integer. The sequence U is q-meta-automatic if there exist nonnegative integers t, a, b, n_{0} together with a family {f_{j} : j = 0, 1, …, m(q, t)} of functions to A, with domains as below, such that, for all n ≥ n_{0} and all j ∈ {0, 1, …, m(q, t)}, the value U(q^{t+1}n + j) equals f_{j} evaluated at the tuple

(U^{−a}(n), …, U^{−1}(n), U^{0}(n), U^{1}(n), …, U^{b}(n),

U_{q,i_{0}^{(1)},j_{0}^{(1)},c_{1}^{(1)},i_{1}^{(1)},j_{1}^{(1)},...,c_{v_{1}}^{(1)},i_{v_{1}}^{(1)},j_{v_{1}}^{(1)}}(n), …,

U_{q,i_{0}^{(w)},j_{0}^{(w)},c_{1}^{(w)},i_{1}^{(w)},j_{1}^{(w)},...,c_{vw}^{(w)},i_{vw}^{(w)},j_{vw}^{(w)}}(n))

for some w ≥ 0 and integers i_{k_{1}}^{(k_{2})} ≤ t, j_{k_{1}}^{(k_{2})}, and c_{k_{1}}^{(k_{2})}, where the domain of f_{j} is A^{a+b+w+1}.

Example 4. Define (T (n))_{n≥0} by T (0) = 0 and

T (2n) = T (n − T (n − 1)) for n ≥ 1, and
T (2n + 1) = 1 − T (n) for n ≥ 0.

Then (T (n))_{n≥0} is 2-meta-automatic in the sense of Definition 3. For n ≥ 1, this sequence agrees with the OEIS sequence \underline{A039982}, which was defined without nested recurrences.

Lemma 5. If a is balanced, then

a(2n + a(n)) = a(2n) ⊕ a(n) and a(2n + 1 − a(n)) = a(2n + 1) ⊕ a(n),

for all n ≥ 0.

Proof. The first identity follows from (3) by case analysis on a(n) ∈ {0, 1}, and similarly for the second.

2.1 Base-4 recurrences

We now record a result that motivates the use of base-4 recurrences in the sequel. We let

a(2n) = a(n + a(n)) or a(2n) = a(n + 1 − a(n)),

and we let a(2n + 1) = 1 − a(2n). In both cases, we obtain ultimate periodicity, as we now show.

Lemma 6. Let a : ℕ_{0} → {0, 1} be balanced.

(a) If a(2n) = a(n + a(n)) for all n ≥ 0, then a(0) = 0 and a is ultimately 2-periodic, with

a(2n) = 0,  a(2n + 1) = 1  (n ≥ 2).

(b) If a(2n) = a(n + 1 − a(n)) for all n ≥ 0, then a(0) = 1 and a is ultimately 2-periodic,

with

a(2n) = 1,  a(2n + 1) = 0  (n ≥ 2).

Proof.

(a) Taking n = 0 gives a(0) = a(a(0)). If a(0) = 1, then balance gives us that a(1) = 0, and hence a(0) = a(1) = 0, a contradiction. Thus a(0) = 0 and a(1) = 1.

Write b_{m} = a(2m), so that balance gives that a(2m + 1) = 1 − b_{m}. Using a(2n) = a(n + a(n)) with n = 2m, we obtain

b_{2m} = a(4m) = a(2m+a(2m)) = a(2m+b_{m}) = \begin{cases}a(2m) = b_{m}, & if b_{m} = 0; \\ a(2m + 1) = 1 − b_{m} = 0, & if b_{m} = 1. \end{cases}

So we have that b_{2m} = 0 for all m ≥ 0.

Now, using a(2n) = a(n + a(n)) with n = 2m + 1 and a(2m + 1) = 1 − b_{m}, we get

b_{2m+1} = a(4m + 2) = a(2m + 1 + a(2m + 1)) = a(2m + 2 − b_{m}) =

\begin{cases}a(2m + 2) = b_{m+1}, & if b_{m} = 0; \\ a(2m + 1) = 0, & if b_{m} = 1. \end{cases}

We claim that b_{m} = 0 for all m ≥ 2. This holds for m = 2, since b_{2} = 0, and for m = 3 because the above identity with m = 1 gives b_{3} = b_{2} if b_{1} = 0, and b_{3} = 0 if b_{1} = 1; in either case b_{3} = 0 since b_{2} = 0. Now let m ≥ 4. If m is even then b_{m} = b_{2r} = 0. If m is odd, write m = 2r + 1 with r ≥ 1. If b_{r} = 1 then b_{m} = 0; if b_{r} = 0 then b_{m} = b_{r+1}, and r + 1 < m, so by induction b_{r+1} = 0. Hence b_{m} = 0 for all m ≥ 2, i.e., a(2n) = 0 for all n ≥ 2. The balance condition in (3) then gives a(2n + 1) = 1 for all n ≥ 2.

(b) This follows from (a) by complementing: if a satisfies (b) then ā(n) = 1−a(n) satisfies (a), and vice versa.

Lemma 6 leads us to consider base-4 recurrences such that the balance identity in (3) is preserved.

2.2 A non-nested case

Fix a(0) = 0 and a(1) = 1, and define

a(4n) = F (n), a(4n + 1) = 1 − F (n), a(4n + 2) = G(n), a(4n + 3) = 1 − G(n), (5)

so that a(2n) + a(2n + 1) = 1 holds automatically. The sequences studied in this paper arise as specializations of (5). We first consider a sequence (Q(n))_{n≥0} whose recurrence is not nested, but which is used in the sequel.

Definition 7. The Thue-Morse Quarto sequence Q : ℕ_{0} → \{0, 1\} (\underline{A298952}, where we use the convention Q(0) = 0 rather than a(0) = 1 as in the OEIS entry) is defined by Q(0) = 0, Q(1) = 1, and

Q(4n) = Q(n),  Q(4n + 1) = 1 − Q(n),
Q(4n + 2) = Q(2n),  Q(4n + 3) = 1 − Q(2n).

The sequence Q is 4-automatic. It is computed by the 3-state DFAO with states in {A, B, C}, initial state A, and output τ(A) = τ(B) = 0, τ(C) = 1, shown in Figure 1. This DFAO corresponds to the 4-uniform morphism

A ↦ ACBC, B ↦ BCCB, C ↦ CBBC,

along with a coding such that τ(A) = τ(B) = 0 and τ(C) = 1.

A/0 B/0 C/1 00, 3 0, 3 21, 3 1, 2 1, 2

Figure 1: DFAO for Q (MSB-first). State labels are state/output. The initial state is A.

Proposition 8. Define d : ℕ_{0} → {0, 1} so that d(0) = 0 and d(n) = ⌊log_{2} n⌋ mod 2 for n ≥ 1. Then

Q(n) = t(n) ⊕ d(n) (n ≥ 0).

Proof. The cases n = 0, 1 are immediate. For n ≥ 1 and r ∈ {0, 1, 2, 3}, since ⌊log_{2}(4n+r)⌋ = 2 + ⌊log_{2} n⌋, we have d(4n + r) = d(n) for all r. We also use t(4n + r) = t(n) ⊕ t(r), and we proceed by induction.

Case r = 0: Q(4n) = Q(n) = t(n) ⊕ d(n) and t(4n) ⊕ d(4n) = t(n) ⊕ d(n).

Case r = 1: Q(4n+1) = 1⊕Q(n) = 1⊕t(n)⊕d(n) and t(4n+1)⊕d(4n+1) = (1⊕t(n))⊕d(n).

Case r = 2: Q(4n+2) = Q(2n). By induction, Q(2n) = t(2n)⊕d(2n) = t(n)⊕(d(n)⊕1) = 1⊕t(n)⊕d(n). Also t(4n+2) = t(2n+1) = 1⊕t(n), so t(4n+2)⊕d(4n+2) = (1⊕t(n))⊕d(n).

Case r = 3: Q(4n+3) = 1⊕Q(2n) = t(n)⊕d(n), and t(4n+3)⊕d(4n+3) = t(n)⊕d(n).

3 The sequence M_{1}

Definition 9. Define M_{1}(0) = 0 and M_{1}(1) = 1. For n ≥ 1, set

M_{1}(4n) = M_{1}(n),  M_{1}(4n + 1) = 1 − M_{1}(n).  (6)

For n ≥ 0, set

M_{1}(4n + 2) = M_{1}(2n + 1 − M_{1}(n)),  M_{1}(4n + 3) = 1 − M_{1}(2n + 1 − M_{1}(n)). (7)

Lemma 10. The sequence M_{1}(n) is well-defined for all n ≥ 0 and satisfies M_{1}(2n) + M_{1}(2n + 1) = 1.

Proof. Well-definedness follows by induction on m. For m = 4n + r, the right-hand sides in (6) reduce to indices < m; for (7), the nested argument 2n + 1 − M_{1}(n) ∈ {2n, 2n + 1} < 4n + 2 ≤ m. Balance follows from (5), since M_{1}(4n + 1) = 1 − M_{1}(4n) and M_{1}(4n + 3) = 1 − M_{1}(4n + 2).

Remark 11. Since M_{1} is balanced, Lemma 5 gives

M_{1}(2n + 1 − M_{1}(n)) = M_{1}(2n + 1) ⊕ M_{1}(n),

so (7) is equivalent to the non-nested relation M_{1}(4n + 2) = M_{1}(2n + 1) ⊕ M_{1}(n).

3.1 A 4-state DFAO

Define

b(n) := M_{1}(2n + 1 − M_{1}(n)),  (8)

and consider the pair s(n) := (M_{1}(n), b(n)). Informally, the following result gives us that the pair s(4n + r) depends only on s(n), for r ∈ {0, 1, 2, 3} and for n ≥ 1, disregarding the trivial n = 0 case whereby M_{1}(0) = 0.

Lemma 12. Let x = M_{1}(n) and y = b(n), and let n ≥ 1. Then

s(4n) = (x, y),  (9)
s(4n + 1) = (1 ⊕ x, x ⊕ y),  (10)
s(4n + 2) = (y, 1 ⊕ x), and  (11)
s(4n + 3) = (1 ⊕ y, x ⊕ y ⊕ 1).  (12)

Proof. By Lemma 10 and Lemma 5, we have y = b(n) = M_{1}(2n + 1) ⊕ M_{1}(n) = (1 − M_{1}(2n)) ⊕ x, so that

M_{1}(2n) = 1 ⊕ x ⊕ y, M_{1}(2n + 1) = x ⊕ y.

Case r = 0. The first coordinate is M_{1}(4n) = M_{1}(n) = x. The latter coordinate satisfies b(4n) = M_{1}(8n + 1 − M_{1}(4n)) = M_{1}(8n + 1 − x). If x = 0, then b(4n) = M_{1}(8n + 1) = M_{1}(4(2n) + 1) = 1 − M_{1}(2n) = 1 − (1 ⊕ x ⊕ y) = 1 − (1 ⊕ y) = y. If x = 1, then b(4n) = M_{1}(8n) = M_{1}(4(2n)) = M_{1}(2n) = 1 ⊕ x ⊕ y = y. In both cases, we find that (9) holds.

Case r = 1. The first coordinate is M_{1}(4n+1) = 1−x = 1⊕x. The latter coordinate satisfies b(4n+1) = M_{1}(8n+2+x). If x = 0, then b(4n+1) = M_{1}(8n+2) = M_{1}(4(2n)+2) = b(2n). Using the property that b(2n) = M_{1}(4n + 1 − M_{1}(2n)), together with M_{1}(2n) = 1 ⊕ y, this yields b(2n) = M_{1}(4n + y). So, if y = 0, then M_{1}(4n) = x = 0, and if y = 1, then M_{1}(4n + 1) = 1 − x = 1, so that b(4n + 1) = y. Similarly, if x = 1, then b(4n + 1) = M_{1}(8n + 3) = M_{1}(4(2n) + 3) = 1 − b(2n). With M_{1}(2n) = y, b(2n) = M_{1}(4n + 1 − y), we find that if y = 0, then 1 − M_{1}(4n + 1) = x = 1, and if y = 1, then 1 − M_{1}(4n) = 1 − x = 0, so that b(4n + 1) = 1 ⊕ y. Consequently, we obtain that (10) holds.

Case r = 2. The first coordinate is M_{1}(4n + 2) = b(n) = y. The latter coordinate satisfies b(4n+2) = M_{1}(8n+5−y). If y = 0, then M_{1}(8n+5) = M_{1}(4(2n+1)+1) = 1−M_{1}(2n+1) = 1⊕(x⊕y) = 1⊕x. If y = 1, then M_{1}(8n+4) = M_{1}(4(2n+1)) = M_{1}(2n+1) = x⊕y = 1⊕x. In both cases, we see that (11) holds.

Case r = 3. The first coordinate is M_{1}(4n+3) = 1−y = 1⊕y. The latter coordinate satisfies b(4n + 3) = M_{1}(8n + 6 + y). If y = 0, then M_{1}(8n + 6) = M_{1}(4(2n + 1) + 2) = b(2n + 1). Since M_{1}(2n + 1) = x, b(2n + 1) = M_{1}(4n + 3 − x). So, if x = 0, then M_{1}(4n + 3) = 1 ⊕ y = 1; if x = 1, then M_{1}(4n + 2) = y = 0; so b(4n + 3) = x ⊕ y ⊕ 1. If y = 1, then M_{1}(8n + 7) = M_{1}(4(2n + 1) + 3) = 1 − b(2n + 1). Since M_{1}(2n + 1) = x ⊕ 1, we find that b(2n + 1) = M_{1}(4n + 2 + x). So, if x = 0, then 1 − M_{1}(4n + 2) = 1 − y = 0; if x = 1, then 1 − M_{1}(4n + 3) = y = 1, so that b(4n + 3) = x ⊕ y ⊕ 1. This gives us the desired relation in (12).

Theorem 13. The sequence M_{1} is 4-automatic and is computed (MSB-first, base 4) by the DFAO with states {0, 1, 2, 3}, initial state 0, output map τ(0) = τ(2) = 0, τ(1) = τ(3) = 1, and transition table

\begin{matrix}δ & 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 1 & 2 \\ 1 & 1 & 2 & 3 & 0 \\ 2 & 2 & 3 & 0 & 1 \\ 3 & 3 & 0 & 2 & 3 \end{matrix}

Proof. Lemma 12 gives four 𝔽_{2}-affine transition rules:

\begin{matrix}(x, y) & ⟶^{0} (x, y), & (x, y) & ⟶^{1} (1 ⊕ x, x ⊕ y), \\ (x, y) & ⟶^{2} (y, 1 ⊕ x), & (x, y) & ⟶^{3} (1 ⊕ y, x ⊕ y ⊕ 1). \end{matrix}

Encoding the states as 0 = (0, 1), 1 = (1, 1), 2 = (0, 0), 3 = (1, 0), these yield the stated transition table. The initial state is s(0) = (M_{1}(0), b(0)) = (0, M_{1}(1)) = (0, 1), corresponding to state 0. The output reads the first coordinate x = M_{1}(n).

0/0 1/1 2/0 3/1 0000, 3 1, 2 113323221

Figure 2: DFAO for M_{1} (4 states, base 4, MSB-first). State labels are state/output. The initial state is 0.

Remark 14. The four transition rules of the DFAO of M_{1} are 𝔽_{2}-affine in (x, y); the same is true for M_{2} (Section 4). For each of the sequences Q, M_{1}, and M_{2}, the affine form is a consequence of Lemma 5.

The defining recurrence of M_{1} is not directly an instance of Theorem 2, since the argument 2n + 1 − M_{1}(n) in the nested recurrence in (7) depends on the value M_{1}(n). The b-sequence defined in (8) removes this dependence. Furthermore, Lemma 5 gives us that

M_{1}(4n + 2) = M_{1}(2n + 1) ⊕ M_{1}(n).

The XOR identity is a direct consequence of Lemma 5, since M_{1} is balanced.

Remark 15. By contrast, Allouche and Shallit [4] show that the frequency sequence F (n) of the Hofstadter variant V = Q_{1,4} satisfies a recurrence of the form F (2a) = g(F (a − 2), F (a − 1), F (a), F (a + 1)) with fixed shifts. This satisfies the required conditions in Theorem 2. In our setting, the sequences we consider themselves, as opposed to associated frequency sequences, are meta-automatic. In this direction, Lemma 5 provides a key tool, for our purposes.

Corollary 16. The coding τ: 0, 2 ↦ 0 and 1, 3 ↦ 1 applied to the fixed point of the 4-uniform morphism

0 → 0112, 1 → 1230, 2 → 2301, 3 → 3023

starting from 0 produces the sequence M_{1}.

Proof. For each state q, the morphism image is δ(q, 0) δ(q, 1) δ(q, 2) δ(q, 3), read from the transition table of Theorem 13.

4 The sequence M_{2}

Definition 17. Define M_{2}(0) = 0 and M_{2}(1) = 1. For n ≥ 1, set

M_{2}(4n) = M_{2}(2n + M_{2}(n)),  M_{2}(4n + 1) = 1 − M_{2}(4n).  (13)

For n ≥ 0, set

M_{2}(4n + 2) = M_{2}(2n + 1 − M_{2}(n)),  M_{2}(4n + 3) = 1 − M_{2}(4n + 2). (14)

Theorem 18. The sequence M_{2} is well-defined and satisfies (3).

Proof. Well-definedness follows by induction as in Lemma 10. For the recurrence rules associated with the arguments 4n and 4n + 1, we have n ≥ 1, so 2n + M_{2}(n) ≤ 2n + 1 < 4n. For the arguments 4n + 2 and 4n + 3, the nested argument satisfies 2n + 1 − M_{2}(n) ≤ 2n + 1 < 4n + 2. Balance is immediate from the complementary definitions in (13)–(14).

Define the pair

s(n) := (M_{2}(n), M_{2}(2n + M_{2}(n))) ∈ 𝔽_{2}^{2}.  (15)

Lemma 19. If s(n) = (x, y), then

M_{2}(2n) = x ⊕ y, M_{2}(2n + 1) = x ⊕ y ⊕ 1.

Proof. If x = 0, then y = M_{2}(2n); if x = 1, then y = M_{2}(2n + 1), and balance gives that M_{2}(2n) = 1 − y. The identities follow.

Theorem 20. Writing s(n) = (x, y), we have

s(4n) = (y, x ⊕ y),
s(4n + 1) = (y ⊕ 1, x ⊕ y),
s(4n + 2) = (y ⊕ 1, x ⊕ y ⊕ 1),
s(4n + 3) = (y, x ⊕ y ⊕ 1).

Consequently M_{2} is 4-automatic with at most 4 states.

Proof. The case n = 0 is immediate from the initial values M_{2}(0) = 0 and M_{2}(1) = 1. We may therefore assume n ≥ 1 whenever a rule for 4n or 4n + 1 is used. Write s(n) = (x, y) so that M_{2}(2n) = x ⊕ y and M_{2}(2n + 1) = x ⊕ y ⊕ 1.

Case r = 0. The first coordinate is given by M_{2}(4n) = M_{2}(2n + x). By Lemma 19, we have that M_{2}(2n) = x⊕y and M_{2}(2n+1) = x⊕y ⊕1. In both cases, for x = 0 or x = 1, a direct check gives that M_{2}(2n+x) = y. For the second coordinate M_{2}(8n+y), we see that if y = 0, then M_{2}(8n) = M_{2}(4(2n)) = M_{2}(2 · 2n + M_{2}(2n)), and, since M_{2}(2n) = x ⊕ y = x, this equals M_{2}(4n+x). Simplifying both cases gives x. If y = 1, then M_{2}(8n+1) = 1−M_{2}(8n), and, by the same analysis as before, we get x ⊕ 1. In both sub-cases the second coordinate equals x ⊕ y. Therefore, we obtain

s(4n) = (y, x ⊕ y).

Case r = 1. The first coordinate is given by M_{2}(4n + 1) = 1 − M_{2}(4n) = 1 − y = y ⊕ 1.

For the second coordinate of s(4n+1), by definition, this is M_{2}(2(4n+1)+M_{2}(4n+1)) = M_{2}(8n+2+(y ⊕1)). When y = 0, we have M_{2}(8n+3) = M_{2}(4(2n)+3) = 1−M_{2}(2(2n)+ 1 − M_{2}(2n)). Since M_{2}(2n) = x, this equals 1 − M_{2}(4n + 1 − x) = x ⊕ y for both values of x. When y = 1, we have M_{2}(8n + 2) = M_{2}(2(2n) + 1 − M_{2}(2n)). Since M_{2}(2n) = x ⊕ 1, this equals M_{2}(4n + x) = x ⊕ y for both values of x. The second coordinate is therefore x ⊕ y in both cases. Therefore

s(4n + 1) = (y ⊕ 1, x ⊕ y).

Case r = 2. For the first coordinate M_{2}(4n + 2) = M_{2}(2n + 1 − x), Lemma 5 gives M_{2}(2n + 1) ⊕ x = (x ⊕ y ⊕ 1) ⊕ x = y ⊕ 1.

For the second coordinate of s(4n + 2), we find that M_{2}(2(4n + 2) + M_{2}(4n + 2)) = M_{2}(8n+4+(y⊕1)). Since M_{2}(2n+1) = x⊕1, we have M_{2}(8n+4) = M_{2}(4n+3) = 1−(y⊕1) for both values of x. When y = 0, this gives M_{2}(8n+4) = 0, so M_{2}(8n+5) = 1 = x⊕y ⊕1. When y = 1, since M_{2}(2n + 1) = x, we get M_{2}(8n + 4) = M_{2}(4n + 2 + x) = x ⊕ y ⊕ 1 by a direct case check. In both cases the second coordinate is x ⊕ y ⊕ 1. It then follows that

s(4n + 2) = (y ⊕ 1, x ⊕ y ⊕ 1).

Case r = 3. The first coordinate is given by M_{2}(4n+3) = 1−M_{2}(4n+2) = 1−(y ⊕1) = y.

For the second coordinate of s(4n + 3), we have that M_{2}(2(4n + 3) + M_{2}(4n + 3)) = M_{2}(8n + 6 + y). Since M_{2}(2n + 1) = x ⊕ 1, the identity M_{2}(8n + 6) = M_{2}(2(2n + 1) + 1 − M_{2}(2n+1)) gives M_{2}(8n+6) = x⊕y⊕1 by a direct two-case check on x; this handles y = 0. For y = 1, since M_{2}(2n + 1) = x, the same formula yields 1 − M_{2}(4n + 2 + x) = x ⊕ y ⊕ 1. The second coordinate is x ⊕ y ⊕ 1 in both cases. Consequently, we have that

s(4n + 3) = (y, x ⊕ y ⊕ 1).

Each transition has the form (x, y) ↦ A\binom{x}{y}+v(d) over 𝔽_{2}, confirming the affine structure.

Remark 21. The linear part (x, y) ↦ (y, x ⊕ y) is given by multiplication by the matrix

A = (\begin{matrix}0 & 1 \\ 1 & 1 \end{matrix}) ∈ GL_{2}(𝔽_{2}),

which has order 3 (indeed A^{3} = I). The translation vectors are v(0) = \binom{0}{0}, v(1) = \binom{1}{0}, v(2) = \binom{1}{1}, v(3) = \binom{0}{1}.

Theorem 22. The sequence M_{2} is computed (MSB-first, base 4) by the DFAO with states {0, 1, 2, 3}, initial state 0, output τ(0) = τ(2) = 0, τ(1) = τ(3) = 1, and transition table

\begin{matrix}δ & 0 & 1 & 2 & 3 \\ 0 & 0 & 1 & 3 & 2 \\ 1 & 2 & 3 & 1 & 0 \\ 2 & 3 & 2 & 0 & 1 \\ 3 & 1 & 0 & 2 & 3 \end{matrix}

where the encoding is 0 = (0, 0), 1 = (1, 0), 2 = (0, 1), 3 = (1, 1).

Proof. This follows directly from the affine transitions in Theorem 20 applied to each encoded state. The initial state is s(0) = (0, 0), corresponding to state 0.

0/0 1/1 2/0 3/1 0213100332312012

Figure 3: DFAO for M_{2} (4 states, base 4, MSB-first). State labels are state/output. The initial state is 0.

Corollary 23. The coding τ: 0, 2 ↦ 0 and 1, 3 ↦ 1 applied to the fixed point of the 4-uniform morphism

0 → 0132, 1 → 2310, 2 → 3201, 3 → 1023

starting from 0 produces the sequence M_{2}.

Remark 24. The four letters of the alphabet correspond to the states (x, y) ∈ 𝔽_{2}^{2} of the affine automaton (Theorem 20) via

0 = (0, 0), 1 = (1, 0), 2 = (0, 1), 3 = (1, 1).

With this identification, the image σ_{M_{2}}(r) lists the four successive states visited when the current state is r and the digits d ∈ {0, 1, 2, 3} are read in order, and the coding τ(r) is the first coordinate of the state. Under the relabeling a = 0, b = 2, c = 1, d = 3, the morphism reads a → acdb, b → dbac, c → bdca, d → cabd, with τ(a) = τ(b) = 0 and τ(c) = τ(d) = 1. This labeling is used in the right-special factor analysis below.

The defining recurrence of M_{2} is not directly an instance of Theorem 2, since the argument 2n + M_{2}(n) in the nested recurrence in (13) and the argument 2n + 1 − M_{2}(n) in (14) depend on the value M_{2}(n). This together with the sequence M_{2}(2n + M_{2}(n)) used in the pair (15) yields the system of recurrences in Theorem 20. Furthermore, Lemma 5 gives us that

M_{2}(4n) = M_{2}(2n) ⊕ M_{2}(n), M_{2}(4n + 2) = M_{2}(2n + 1) ⊕ M_{2}(n).

The XOR identities are direct consequences of Lemma 5, since M_{2} is balanced.

4.1 An explicit digit formula

Write the base-4 expansion n = ∑_{k≥0} d_{k}4^{k} with digits d_{k} ∈ {0, 1, 2, 3}, and write d_{k} = 2j_{k}+i_{k} with i_{k}, j_{k} ∈ {0, 1}.

Theorem 25. We have that

M_{2}(n) = ⨁_{k≡0 (mod 3)}(i_{k} ⊕ j_{k}) ⊕ ⨁_{k≡1 (mod 3)} j_{k} ⊕ ⨁_{k≡2 (mod 3)} i_{k}.

Proof. Let d_{L−1} ⋯ d_{1}d_{0} be the base-4 expansion of n. Since the automaton reads digits MSB-first and the transition has the form s ↦ As + v(d), starting from s(0) = (0, 0) gives

s(n) = ∑_{k=0}^{L−1} A^{k} v(d_{k}) (mod 2).

Since A^{3} = I, the exponent depends only on k mod 3. Computing A^{k}v(d) for k ∈ {0, 1, 2} and each digit d, we obtain

\begin{matrix}d & A^{0}v(d) & A^{1}v(d) & A^{2}v(d) \\ 0 & (0, 0) & (0, 0) & (0, 0) \\ 1 & (1, 0) & (0, 1) & (1, 1) \\ 2 & (1, 1) & (1, 0) & (0, 1) \\ 3 & (0, 1) & (1, 1) & (1, 0) \end{matrix}

Extracting the first coordinate and identifying i_{k} = d_{k} mod 2 and j_{k} = ⌊d_{k}/2⌋ yields the stated formula.

Theorem 26. Write the binary expansion n = ∑_{m≥0} b_{m}2^{m} with b_{m} ∈ {0, 1}, and define

q(n) := ∑_{\begin{matrix}m≥0 \\ m≢2 (mod 3) \end{matrix}} b_{m}2^{m},  (16)

so that q(n) is obtained from n by zeroing the binary digits in positions m ≡ 2 (mod 3). Then

M_{2}(n) = t(q(n)) (n ≥ 0).

Equivalently, if n = ∑_{k≥0} d_{k}4^{k} with d_{k} = 2j_{k} + i_{k}, then q(n) = ∑_{k≥0} d′_{k}4^{k} where

d′_{k} = \begin{cases}d_{k}, & if k ≡ 0 (mod 3); \\ 2j_{k}, & if k ≡ 1 (mod 3); \\ i_{k}, & otherwise. \end{cases}

and M_{2}(n) = t(q(n)).

Proof. In Theorem 25, each base-4 digit d_{k} contributes to M_{2}(n) in a way that depends only on k mod 3: For k ≡ 0 mod 3, we take i_{k} ⊕ j_{k}, for k ≡ 1 mod 3, we take only j_{k}, and for k ≡ 2 mod 3, we take i_{k}. Since i_{k} = b_{2k} and j_{k} = b_{2k+1}, the binary positions m = 2k and m = 2k + 1 are kept or omitted, according to the residue class k mod 3, in the following manner. For k ≡ 0 (mod 3), both positions are kept. For k ≡ 1 (mod 3), the position m = 2k is omitted. For k ≡ 2 (mod 3), the position m = 2k + 1 is omitted. In each of the cases where a position is omitted, the omitted position m satisfies m ≡ 2 (mod 3). Conversely, every value m such that m ≡ 2 (mod 3) falls into one of the two specified cases. Thus, the omitted positions are precisely those such that m ≡ 2 (mod 3), and M_{2}(n) is the parity of the binary digit-sum of q(n) defined in (16), and hence M_{2}(n) = t(q(n)). This gives us, in an equivalent way, the desired base-4 description of q(n).

5 Factor complexity

Let p_{a}(n) denote the number of distinct length-n factors in the infinite word a(0)a(1)a(2) · · ·. A length-n factor u of a is called right-special if both u0 and u1 are factors of a. We write RS_{a}(n) in place of the set of right-special factors of a of length n.

Lemma 27. For every infinite binary word a and every n ≥ 1, we have that

p_{a}(n + 1) − p_{a}(n) = # RS_{a}(n).

Proof. For each length-n factor u, let E_{R}(u) ⊆ {0, 1} be the set of right extensions such that uα occurs in a. Then p_{a}(n + 1) = ∑_{u} |E_{R}(u)| and p_{a}(n) = ∑_{u} 1, so p_{a}(n + 1) − p_{a}(n) = ∑_{u}(|E_{R}(u)| − 1). In the binary case, |E_{R}(u)| − 1 equals 1 if u is right-special and 0 otherwise.

Lemma 28. If a is k-automatic, then the function n ↦ #RS_{a}(n) is k-regular in the sense of Allouche-Shallit [3], and is effectively computable from any DFAO for a. Moreover, if #RS_{a}(n) is bounded, then it is k-automatic.

Proof. The predicate “u is a length-n factor of a” and the predicate “u is right-special” are first-order definable over (ℕ, +, V_{k}) relative to a DFAO for a, so the set of encodings of such pairs is regular. Counting right-special factors of a given length reduces to a finite-automaton computation, giving a k-regular sequence [3, Ch. 16]. A bounded k-regular sequence is kautomatic [3, Theorem 16.1.5].

Several statements in this paper can be certified by the Walnut theorem prover [29], which decides first-order properties of automatic sequences in Presburger arithmetic. This applies to the defining recurrences and the balance of Q, M_{1}, and M_{2} (Sections 3 and 4), and (using Lemma 28) to the right-special factor structure of Q and M_{2} in the present section. The right-special factor verifications for M_{2} use the CCL(S) determinization algorithm of Nicol and Frohme [25]. We give arguments that do not require Walnut wherever this is convenient.

5.1 Factor complexity of Q

We first state a property of the factors of t.

Lemma 29. The set Fac(t) is closed under bitwise complementation: If w ∈ Fac(t), then w̄ ∈ Fac(t).

Proof. The Thue-Morse morphism μ : 0 ↦ 01, 1 ↦ 10 satisfies \overline{μ(w)} = μ(w̄) for every binary word w. Since t = μ^{ω}(0) and both 0 and 1 = ¯0 appear in t, every factor w of μ^{ω}(0) yields w̄ = \overline{μ^{ω}(0)}|_{same position} = μ^{ω}(1)|_{same position}, which is a factor of μ^{ω}(1) = 1 t[1 ∞), hence a factor of t.

Proposition 30. Let J_{n} denote the set of length-n factors of Q that are not factors of t. Then

p_{Q}(n) = p_{t}(n) + |J_{n}|.

Proof. By Proposition 8, on each interval [2^{k}, 2^{k+1}), the sequence Q coincides with t or 1−t, according to the parity of k. The cases give us that a factor of Q of length n is either a factor of t or the complement of a factor of t, which, by Lemma 29, is again a factor of t. In any case, such factors are in Fac(t).

For an interval of the form [2^{k}, 2^{k+1}), suppose that the indices associated with a factor of length n properly contains this interval. This can only occur when its left endpoint is at a position < 2^{k} and its right endpoint is at a position ≥ 2^{k+1} for some k, which forces n ≥ 2^{k}. In every case, such a factor has the form u_{0}ū_{1}u_{2}ū_{3} ⋯ obtained by concatenating consecutive pieces of t with alternating bitwise complementation, where the concatenation u_{0}u_{1}u_{2}u_{3} ⋯ is a factor of t. By Lemma 29, the complementation pattern preserves membership in Fac(t) for the simplest one-boundary case u_{0}ū_{1} if and only if ū_{0}u_{1} ∈ Fac(t), and this need not hold in general. According to the above definition of J_{n}, we have that J_{n} as the set of length-n factors that have at least one index strictly less than 2^{k} and at least one index greater than or equal to 2^{k} and that are not in Fac(t).

Since every factor of t appears in Q, the set of factors of Q of length n is exactly Fac(t) ∩ {0, 1}^{n} ∪ J_{n}, giving us that p_{Q}(n) = p_{t}(n) + |J_{n}|.

Theorem 31. For all k ≥ 4, we have that

p_{Q}(2^{k}) = 13 · 2^{k−2} − 2.

Equivalently, p_{Q}(2^{k}) = p_{t}(2^{k}) + 2^{k−2}, so |J_{2^{k}}| = 2^{k−2}.

Proof. The value p_{t}(2^{k}) = 3 · 2^{k} − 2 is known [6, 24]. By Proposition 30, we have that p_{Q}(2^{k}) = p_{t}(2^{k}) + |J_{2^{k}}|. Also, Lemma 27 gives us that

#RS_{Q}(n) = p_{Q}(n + 1) − p_{Q}(n).  (17)

The right-special count in (17) takes values in {2, 3, 4}, and this is certified for all n ≥ 2 by Walnut. The desired result follows from the recurrence

p_{Q}(2^{k+2}) = 4 p_{Q}(2^{k}) + 6 (k ≥ 4),

with p_{Q}(16) = 50, which has the unique solution p_{Q}(2^{k}) = 13 · 2^{k−2} − 2, also verified computationally for 4 ≤ k ≤ 7.

Remark 32. The set J_{2^{k}} has size 2^{k−2}, so factors in J_{2^{k}} account for one quarter of the length-2^{k} factors of Q beyond those of t.

Since #RS_{Q}(n) ∈ {2, 3, 4} for all n ≥ 1, the values of p_{Q} are determined by the support of each slope.

Lemma 27 is implicit in the following Proposition, according to (18).

Proposition 33. For n ≥ 16, set k = ⌊log_{2} n⌋ and write n = 2^{k} + i with 0 ≤ i < 2^{k}. Then

p_{Q}(n) = \begin{cases}13 · 2^{k−2} − 2, & if i = 0; \\ 4n − 3 · 2^{k−2} − 4, & if 1 ≤ i ≤ 2^{k−1}; \\ 3n + 3 · 2^{k−2} − 3, & if 2^{k−1} < i ≤ 3 · 2^{k−2}; \\ 2n + 5 · 2^{k−1} − 2, & if 3 · 2^{k−2} < i < 2^{k}. \end{cases}

Moreover, we have that

#RS_{Q}(n) = p_{Q}(n + 1) − p_{Q}(n).  (18)

The left-hand side of (18) equals 4 for n ∈ (2^{k}, 3 · 2^{k−1}], and 3 for n ∈ (3 · 2^{k−1}, 7 · 2^{k−2}], and 2 for n ∈ (7 · 2^{k−2}, 2^{k+1}).

Proof. This is certified by Walnut.

By Proposition 33, n + 1 ≤ p_{Q}(n) = O(n) for all n ≥ 1.

5.2 Factor complexity of M_{1} and M_{2}

Proposition 34. We have p_{M_{1}}(n) = Θ(n) and p_{M_{2}}(n) = Θ(n).

Proof. The incidence matrices of the morphisms in Corollaries 16 and 23 are

M_{M_{1}} = (\begin{matrix}1 & 2 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 2 \end{matrix}) ,  M_{M_{2}} = (\begin{matrix}1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}) .  (19)

The incidence matrices in (19) give us that both of the associated morphisms are primitive. A result of Pansiot [26] gives us that the fixed point of a primitive k-uniform morphism has factor complexity O(n), and the same upper bound holds after applying a coding. Neither M_{1} nor M_{2} is ultimately periodic, as can be checked from the DFAOs of Theorems 13 and 22, or certified by Walnut. By the Morse–Hedlund theorem [3, Theorem 10.2.6], the factor complexity of a non-ultimately-periodic word is at least n + 1 for every n ≥ 0. Hence both complexities are Θ(n).

An explicit evaluation of the factor complexity of M_{2} is provided below.

Example 35. We obtain the initial values

p_{M_{1}}(1 … 15) = (2, 4, 6, 9, 12, 17, 22, 28, 34, 40, 46, 52, 58, 64, 70),

and

p_{M_{2}}(1 … 15) = (2, 4, 6, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40, 44).

Proposition 36. For all k ≥ 3, we have that

p_{M_{2}}(2^{k}) = \begin{cases}\frac{5}{2} · 2^{k} − 2, & if 3 | k; \\ 3 · 2^{k} − 2, & otherwise. \end{cases}

Moreover, the recurrence

p_{M_{2}}(2^{k+3}) = 8 p_{M_{2}}(2^{k}) + 14 (k ≥ 3)

holds true.

Proof. This is certified by Walnut.

Since #RS_{M_{2}}(n) ∈ {2, 4}, the values of p_{M_{2}} are determined by the positions at which #RS_{M_{2}}(n) = 4. The following proposition extends Proposition 36 to a complete evaluation.

Proposition 37. We have p_{M_{2}}(1) = 2. For n ≥ 2, set k = ⌊log_{2} n⌋ and r = k mod 3.

Case r = 0: On the interval [2^{k}, 2^{k+1}], we have that

p_{M_{2}}(n) = \begin{cases}2n + (2^{k−1} − 2), & if 2^{k} ≤ n ≤ 2^{k} + 1; \\ 4n − (3 · 2^{k−1} + 4), & if 2^{k} + 1 ≤ n ≤ 7 · 2^{k−2} + 1; \\ 2n + (2^{k+1} − 2), & if 7 · 2^{k−2} + 1 ≤ n ≤ 2^{k+1}. \end{cases}

Case r = 1: On the interval [2^{k}, 2^{k+1}], we have that

p_{M_{2}}(n) = \begin{cases}2n + (2^{k} − 2), & if 2^{k} ≤ n ≤ 2^{k} + 1; \\ 4n − (2^{k} + 4), & if 2^{k} + 1 ≤ n ≤ 3 · 2^{k−1} + 1; \\ 2n + (2^{k+1} − 2), & if 3 · 2^{k−1} + 1 ≤ n ≤ 2^{k+1}. \end{cases}

Case r = 2: On the interval [2^{k}, 2^{k+1}], we have that

p_{M_{2}}(n) = 2n + (2^{k} − 2).

Proof. This is certified by Walnut.

6 Conclusion

Consider replacing a(2n) + a(2n + 1) = 1 by a(3n) + a(3n + 1) + a(3n + 2) = 2, with a taking values in {0, 1}. This gives rise to expressions of the form a(3n + r − a(n)), and the analogue of Lemma 5 converts each such expression into a fixed-argument expression. A small number of initial configurations produce 3-automatic binary sequences with small DFAOs; we plan to treat this family separately.

7 Acknowledgments

The authors thank the anonymous referee for a careful reading of the manuscript and for helpful suggestions. The authors also thank Gandhar Joshi for independently testing the Walnut files. Claude (Anthropic) was used as a computational assistant, in particular for exploratory computations, for suggesting candidate formulas later checked by independent scripts, and for checking consistency between the manuscript, the Python script, and the Walnut files. The mathematical content, the proofs, and the final wording are the authors’ own. The first author thanks Jean-Paul Allouche, Karl Dilcher, and Jeffrey Shallit for useful feedback related to this paper.

8 Minimal DFAO sizes

Minimal DFAO sizes for the meta-automatic sequences considered in this paper are listed in Table 1.

F (n)  G(n)  DFAO Nested  Notes
a(n)  a(n)  2  0  Thue-Morse
a(n)  a(2n)  3  0  Q (Thue-Morse Quarto)
a(n)  a(2n + 1)  2  0  Thue-Morse
a(n)  a(2n + a(n))  4  1
a(n)  a(2n + 1 − a(n))  4  1  M_{1}
a(2n)  a(n)  4  0
a(2n)  a(2n)  —  0  ultimately periodic
a(2n)  a(2n + 1)  2  0  Thue-Morse
a(2n)  a(2n + a(n))  3  1
a(2n)  a(2n + 1 − a(n))  3  1
a(2n + 1)  a(n)  5  0
a(2n + 1)  a(2n)  3  0  complement of Q
a(2n + 1)  a(2n + 1)  5  0
a(2n + 1)  a(2n + a(n))  5  1
a(2n + 1)  a(2n + 1 − a(n))  5  1
a(2n + a(n))  a(n)  4  1
a(2n + a(n))  a(2n)  4  1
a(2n + a(n))  a(2n + 1)  4  1
a(2n + a(n))  a(2n + a(n))  4  2
a(2n + a(n))  a(2n + 1 − a(n))  4  2  M_{2}
a(2n + 1 − a(n)) a(n)  5  1
a(2n + 1 − a(n)) a(2n)  4  1
a(2n + 1 − a(n)) a(2n + 1)  5  1
a(2n + 1 − a(n)) a(2n + a(n))  5  2
a(2n + 1 − a(n)) a(2n + 1 − a(n))  5  2

Table 1: Minimal DFAO size for each specialization. The column “Nested” counts the number of branch rules (F and G) whose right-hand side contains an expression of the form a( · ± a(n)). Boldface marks the three sequences studied in this paper.

References

[1] A. Alkan, On a generalization of Hofstadter’s Q-sequence: a family of chaotic generational structures, Complexity 2018 (2018), Article ID 8517125.

[2] A. Alkan, N. Fox, and O. O. Aybar, On Hofstadter heart sequences, Complexity (2017), Article ID 2614163.

[3] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

[4] J.-P. Allouche and J. Shallit, A variant of Hofstadter’s sequence and finite automata, J. Aust. Math. Soc. 93 (2012), 1–8.

[5] B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter’s Q-sequence, J. Integer Sequences 10 (2007), Article 07.7.1.

[6] S. Brlek, Enumeration of factors in the Thue-Morse word, Discrete Appl. Math. 24 (1989), 83–96.

[7] M. Cai and S. M. Tanny, How the shift parameter affects the behavior of a family of meta-Fibonacci sequences, J. Integer Sequences 11 (2008), Article 08.3.6.

[8] J. Callaghan, J. J. Chew, III, and S. Tanny, On the behavior of a family of meta-Fibonacci sequences, SIAM J. Discrete Math. 18 (2005), 794–824.

[9] A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.

[10] B. Dalton, M. Rahman, and S. Tanny, Spot-based generations for meta-Fibonacci sequences, Exp. Math. 20 (2011), 129–137.

[11] C. Deugau and F. Ruskey, Complete k-ary trees and generalized meta-Fibonacci sequences, Fourth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, September 18–22, 2006, Institut Ilie Cartan, Nancy, France, Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings Series Volume AG (2006), 203–214.

[12] F. M. Dekking, On Hofstadter’s G-sequence, J. Integer Sequences 26 (2023), Article 23.9.2.

[13] N. D. Emerson, A family of meta-Fibonacci sequences defined by variable-order recursions, J. Integer Sequences 9 (2006), Article 06.1.8.

[14] N. Fox, The behavior of a three-term Hofstadter-like recurrence with linear initial conditions, J. Integer Sequences 27 (2024), Article 24.7.4.

[15] N. Fox, Linear recurrent subsequences of generalized meta-Fibonacci sequences, J. Difference Equ. Appl. 22 (2016), 1019–1026.

[16] N. Fox, A new approach to the Hofstadter Q-recurrence, Integers 20A (2020), A8.

[17] N. Fox, Quasipolynomial solutions to the Hofstadter Q-recurrence, Integers 16 (2016), A68.

[18] S. W. Golomb, Discrete chaos: sequences satisfying “strange” recursions, unpublished manuscript, c. 1990. Cached copy available at https://oeis.org/A005185/a005185_

1.pdf.

[19] R. J. Hendel, Quasi-periods for the Hofstadter Q function, Fibonacci Quart. 53 (2015), 112–123.

[20] D. R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid, Basic Books, 1979.

[21] A. Isgur and M. Rahman, On variants of Conway and Conolly’s meta-Fibonacci recursions, Electron. J. Combin. 18 (2011), Paper 96.

[22] A. Isgur, D. Reiss, and S. Tanny, Trees and meta-Fibonacci sequences, Electron. J. Combin. 16 (2009), Research Paper 129, 40.

[23] B. Jackson and F. Ruskey, Meta-Fibonacci sequences, binary trees and extremal compact codes, Electron. J. Combin. 13 (2006), Research Paper 26, 13.

[24] A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theoret. Comput. Sci. 63 (1989), 333–348.

[25] J. Nicol and M. Frohme, Deconstructing subset construction: reducing while determinizing, in Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2026), Part II, Lect. Notes in Comp. Sci., Vol. 16506, Springer, 2026.

[26] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, in Automata, Languages and Programming: Proc. ICALP 1984, Lect. Notes in Comp. Sci., Vol. 172, Springer, 1984, pp. 380–389.

[27] K. Pinn, Order and chaos in Hofstadter’s Q(n) sequence, Complexity 4 (1999), 41–46.

[28] F. Ruskey and C. Deugau, The combinatorics of certain k-ary meta-Fibonacci sequences, J. Integer Sequences 12 (2009), Article 09.4.3.

[29] J. Shallit, The Logical Approach to Automatic Sequences, London Math. Soc. Lecture Note Ser. Vol. 482, Cambridge University Press, 2022.

[30] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2025. Available

at https://oeis.org.

[31] B. Sobolewski and M. Ulas, Solutions of certain meta-Fibonacci recurrences, Acta Arith. 209 (2023), 269–289.

[32] S. M. Tanny, A well-behaved cousin of the Hofstadter sequence, Discrete Math. 105 (1992), 227–239.

2020 Mathematics Subject Classification: Primary 11B85; Secondary 68Q45, 68R15. Keywords: automatic sequence, nested recurrence, Thue-Morse sequence, DFAO, binary sequence.

(Concerned with sequences \underline{A005185}, \underline{A039982}, \underline{A244477}, \underline{A298952}, \underline{A391614}, and \underline{A392736}.)

Received March 2 2026; revised version received May 26 2026. Published in Journal of Integer Sequences, June 4 2026.

Return to Journal of Integer Sequences home page.