A Slow-Growing Sequence Defined by an Unusual Recurrence

Fokko J. van de Bult and Dion C. Gijswijt Korteweg-de Vries Institute for Mathematics University of Amsterdam Plantage Muidergracht 24 1018 TV Amsterdam Netherlands

John P. Linderman, N. J. A. Sloane,^{1} and Allan R. Wilks AT&T Shannon Labs 180 Park Avenue Florham Park, NJ 07932–0971 USA

                fjvdbult@science.uva.nl
                dion.gijswijt@gmail.com
                 jpl@research.att.com
                 njas@research.att.com
                allan@research.att.com

Abstract

The sequence starts with a(1) = 1; to extend it one writes the sequence so far as XY^{k}, where X and Y are strings of integers, Y is nonempty and k is as large as possible: then the next term is k. The sequence begins 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, … A 4 appears for the first time at position 220, but a 5 does not appear until about position 10^{10^{23}}. The main result of the paper is a proof that the sequence is unbounded. We also present results from extensive numerical investigations of the sequence and of certain derived sequences, culminating with a heuristic argument that t (for t = 5, 6, …) appears for the first time at about position 2 ↑ (2 ↑ (3 ↑ (4 ↑ (5 ↑ … ↑ ((t − 2) ↑ (t − 1)))))), where ↑ denotes exponentiation. The final section discusses generalizations.

1All correspondence should be directed to this author.

1 Introduction

This paper introduces an integer sequence A = a(1), a(2), a(3), … with some remarkable properties. Define the curling number C(U) of a string U = u(1), u(2), …, u(n) over some alphabet Ω to be the largest integer k ≥ 1 such that

U = X \underbrace{Y Y ⋯ Y}_{k copies} = XY^{k} ,  (1)

where X and Y are strings over Ω and Y is nonempty. Our sequence is defined by

a(1) = 1, a(n + 1) = C(a(1), …, a(n)) for n ≥ 1 .  (2)

Then a(2) = C(1) = 1, since we can only take X to be the empty string ϵ, Y = 1 and k = 1; a(3) = C(1, 1) = 2, by taking X = ϵ, Y = 1, k = 2; a(4) = C(1, 1, 2) = 1, by taking X = 1, 1, Y = 2, k = 1 (as this example shows, there may be more than one choice for Y); and so on. The first 220 terms of A are shown in Tables 1 and 2.

To avoid any possible confusion, for example with the “Say What You See” sequence studied in [3], we emphasize that the curling number does not depend on the decimal representation of its arguments. For example, if U = (8, 9, 10, 11, 11, 11), C(U) = 3.

1 1 \underline{2}
1 1 2 \underline{2} \underline{2} \underline{3}
1 1 2
1 1 2 2 2 3 \underline{2}
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2 \underline{2} \underline{2} \underline{3} \underline{2} \underline{2} \underline{2} \underline{3} \underline{3} \underline{2}
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2 2 2 3 2 2 2 3 3 2 \underline{2} \underline{2} \underline{3} \underline{2}

Table 1: The first 98 terms of the sequence. In the notation to be introduced in Section 2, the five underlined strings are the glue strings S_{1}^{(1)}, S_{2}^{(1)}, …, S_{5}^{(1)} and the five bold-face strings are T_{2}^{(1)}, T_{3}^{(1)}, …, T_{6}^{(1)}.

1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2 2 2 3 2 2 2 3 3 2
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2
1 1 2
1 1 2 2 2 3
1 1 2
1 1 2 2 2 3 2 2 2 3 2 2 2 3 3 2 2 2 3 2 \underline{2} \underline{2} \underline{3} \underline{2} \underline{2} \underline{2} \underline{3} \underline{3}
\underline{2} \underline{2} \underline{2} \underline{3} \underline{2} \underline{2} \underline{2} \underline{3} \underline{2} \underline{2} \underline{2} \underline{3} \underline{3} \underline{3} \underline{3} \underline{4}

Table 2: Terms 99 through 220 of the sequence, up to the point where the first 4 appears (S_{6}^{(1)} is underlined, T_{7}^{(1)} is shown in bold-face).

In Section 2 we describe the recursive structure of the sequence, in particular explaining the block structure visible in Tables 1 and 2. The proof that this structure is valid is postponed to Section 3, where we give the main results of the paper, Theorems 3.1 and 3.2. Corollary 3.4 shows that the sequence is unbounded.

In Section 4 we give empirical estimates for the lengths of the blocks in the recursive structure, culminating in the estimate that t ≥ 5 appears in the sequence for the first time at about position

2^{234^{·^{·^{·t−1}}}} ,  (3)

a tower of height t − 1. These estimates are based on examination of the first two million terms of the sequence A and of the higher-order sequences A^{(2)}, A^{(3)} and A^{(4)} introduced in Section 2.

The final section is devoted to comments and generalizations. §5.1 discusses a certain plausible “Finiteness Conjecture” that arises from studying curling numbers. §5.2 discusses sequences that are obtained when the “curling number transform” (defined below) is applied to certain well-known sequences. Finally, §5.3 briefly mentions some generalizations of our sequence, including a broad class of extensions suggested by J. Taylor [9].

Although the sequence A grows very slowly, there are certainly familiar sequences with an even slower growth rate, such as the inverse Ackermann function [1], the Davenport-Schinzel sequences [7], or the inverse to Harvey Friedman’s sequence [4]. Nevertheless, we think the combination of slow growth, an unusual definition, and a remarkable recursive structure makes the sequence noteworthy.

The sequence was invented by one of us (D.C.G.) while composing problems for the Dutch magazine Pythagoras. It now appears as sequence A90822 in [8].

Notation

If Ω is a set, Ω^{n} denotes the strings of length n from Ω, Ω^{+} is the set of all nonempty finite strings from Ω, and Ω^{∗} is the set of all finite or infinite strings from Ω, including the empty string ϵ. Strings will usually be denoted by uppercase letters. The elements of a string may or may not be separated by commas, and a string may or may not be enclosed in parentheses. A sequence is an infinite string. The length of U ∈ Ω^{∗} (which may be ∞) will be denoted by l(U).

Products in Ω^{∗} represent concatenation: if U ∈ Ω^{+}, V ∈ Ω^{∗} then UV means U followed by V. We will usually not concatenate two infinite strings. A string U = u(1), …, u(i) is said to be a substring of V = v(1), …, v(j) if there is an r, 0 ≤ r ≤ j − i, such that u(k) = v(k + r) for k = 1, …, i; that is, if the elements of U occur consecutively in V. We say V contains U to indicate that U is a substring of V. Terms such as prefix, suffix, etc., have their usual meanings — see [2] for formal definitions. A sequence U is said to be a subsequence of a sequence V if U can be obtained by deleting terms from V.

Usually Ω will be either the nonnegative integers ℕ = {0, 1, 2, 3, …}, the positive integers ℙ = {1, 2, 3, …}, or the set ℙ_{m} = {m, m + 1, m + 2, …} for some integer m ≥ 1.

Given a sequence U = u(1), u(2), … ∈ Ω^{∗}, its curling number transform is the sequence U_{∗} = u_{∗}(1), u_{∗}(2), … ∈ ℙ^{∗} given by u_{∗}(1) = 1 and

u_{∗}(i) = C(u(1), …, u(i − 1)) for i ≥ 2 .  (4)

It is immediate from the definition (2) that our sequence A is equal to its curling number transform, and in fact is the unique sequence with this property.

2 The recursive structure

We introduce the notation in three stages: informally, more formally and—in Section 3—with a somewhat different emphasis that will be needed to prove the main theorems.

Informally, the sequence A is built up recursively from “blocks” B_{n}^{(1)} that are doubled at each step and are joined together by “glue” strings S_{n}^{(1)}. When the glue strings alone are concatenated together they form a sequence A^{(2)} which has a similar structure to A: it is built up recursively from blocks B_{n}^{(2)} that are repeated three times at each step and are joined together by “second-order glue” strings S_{n}^{(2)}. When the second-order glue strings are concatenated together they form a sequence A^{(3)} which in turn has a similar structure, but now the blocks B_{n}^{(3)} are repeated four-fold at each step; and so on. The proof that this description is correct will be given in the next section.

We now make this description more precise. The following description is correct, and is the best way to think about the sequence. However, we will not know for certain that it is correct until the end of Section 3.

The sequence A is constructed from strings B_{n}^{(1)} and S_{n}^{(1)}, n ≥ 1, which we call “blocks” and “glue,” respectively. The initial block is B_{1}^{(1)} = 1; the second block is B_{2}^{(1)} = B_{1}^{(1)}B_{1}^{(1)}S_{1}^{(1)} = 1 1 2, where S_{1}^{(1)} = 2; the third block is

B_{3}^{(1)} = B_{2}^{(1)}B_{2}^{(1)}S_{2}^{(1)}
= 1 1 2 1 1 2 2 2 3 ,

where S_{2}^{(1)} = 2 2 3, and so on, the n-th block for n ≥ 2 being

B_{n}^{(1)} = B_{n−1}^{(1)}B_{n−1}^{(1)}S_{n−1}^{(1)} ,  (5)

where S_{n−1}^{(1)} contains no 1’s. Then for all n ≥ 1, A begins with B_{n}^{(1)} (and hence A = lim_{n→∞} B_{n}^{(1)}).

That is, for all n ≥ 2, A begins with two copies of B_{n−1}^{(1)} followed by a “glue” string S_{n−1}^{(1)} that contains no 1’s. S_{n−1}^{(1)} is terminated by the first 1 that follows the initial B_{n−1}^{(1)}B_{n−1}^{(1)}. Table 1 shows B_{1}^{(1)} through B_{6}^{(1)} (the first row is B_{2}^{(1)}, the first two rows together form B_{3}^{(1)}, …, and the whole table forms B_{6}^{(1)}), and Tables 1 and 2 together form B_{7}^{(1)}. The glue strings S_{1}^{(1)}, S_{2}^{(1)}, …, S_{6}^{(1)} are underlined. By iterating (5) we see that B_{n}^{(1)} can also be written as

B_{n}^{(1)} = B_{n−1}^{(1)}B_{n−2}^{(1)} ⋯ B_{1}^{(1)}B_{1}^{(1)}S_{1}^{(1)}S_{2}^{(1)} ⋯ S_{n−1}^{(1)} .  (6)

The terminating string S_{1}^{(1)}S_{2}^{(1)} ⋯ S_{n−1}^{(1)} (denoted by T_{n}^{(1)} in Section 3) is shown in bold-face in Tables 1 and 2 for n = 2, …, 7.

In Section 4 we state some conjectures about the lengths of the blocks B_{n}^{(1)} and of the glue strings S_{n−1}^{(1)}. Assuming these conjectures are correct, l(S_{n−1}^{(1)}) is much less than l(B_{n−1}^{(1)}), and consequently l(B_{n}^{(1)}) is roughly twice l(B_{n−1}^{(1)}).

2 2 2 \underline{3}
2 2 2 3
2 2 2 3 \underline{3}
2 2 2 3
2 2 2 3
2 2 2 3 3
2 2 2 3
2 2 2 3
2 2 2 3 3 \underline{3} \underline{3} \underline{4}
2 2 2 3
2 2 2 3
2 2 2 3 3
2 2 2 3
2 2 2 3
2 2 2 3 3
2 2 2 3
2 2 2 3
2 2 2 3 3 3 3 4
2 2 2 3
2 2 2 3
2 2 2 3 3
2 2 2 3
2 2 2 3
2 2 2 3 3
2 2 2 3
2 2 2 3
2 2 2 3 3 3 3 4 \underline{3}

Table 3: The first 127 terms of the second-order sequence A^{(2)} (the successive second-order glue strings S_{1}^{(2)}, S_{2}^{(2)}, S_{3}^{(2)}, S_{4}^{(2)} are underlined; the strings T_{2}^{(2)}, T_{3}^{(2)}, T_{4}^{(2)}, T_{5}^{(2)} are shown in bold-face).

The above decomposition reduces the study of A to the study of the glue strings S_{n}^{(1)}. We define the “second-order sequence” A^{(2)} = a^{(2)}(1), a^{(2)}(2), a^{(2)}(3), … to be the concatenation S_{1}^{(1)}S_{2}^{(1)}S_{3}^{(1)} ⋯ ∈ ℙ_{2}^{∗} of the glue strings. It will be shown later that A^{(2)} can also be defined by

a^{(2)}(1) = 2 ,

a^{(2)}(n + 1) = C^{(2)}(a^{(2)}(1), a^{(2)}(2), …, a^{(2)}(n)) for n ≥ 1 ,  (7)

where we define

C^{(m)}(U) = max{m, C(U)}  (8)

for m ≥ 1. That is, if C(U) = k is less than m it is “promoted” to m (we will say more about “promotion” at the end of Section 3). Of course C^{(1)} = C.

The first 127 terms of A^{(2)} are shown in Table 3, and the reader can verify that they may indeed be obtained by starting with 2 and repeatedly applying the map C^{(2)}.

It is remarkable that A^{(2)} has a similar structure to A, only now the blocks are repeated three times. That is, if we define B_{1}^{(2)} = 2, then for all n ≥ 2, A^{(2)} begins with a block

B_{n}^{(2)} = B_{n−1}^{(2)}B_{n−1}^{(2)}B_{n−1}^{(2)}S_{n−1}^{(2)} ,  (9)

consisting of three copies of B_{n−1}^{(2)} followed by a “second-order glue” string S_{n−1}^{(2)} ∈ ℙ_{3}^{∗} that contains no 1’s or 2’s and is terminated by the first number less than 3 that follows the initial B_{n−1}^{(2)}B_{n−1}^{(2)}B_{n−1}^{(2)}. Table 3 shows B_{5}^{(2)} (as well as B_{1}^{(2)} through B_{4}^{(2)}). The glue strings S_{1}^{(2)}, S_{2}^{(2)}, S_{3}^{(2)}, S_{4}^{(2)} are underlined. B_{n}^{(2)} ends with the string S_{1}^{(2)}S_{2}^{(2)} ⋯ S_{n−1}^{(2)} (denoted by T_{n}^{(2)} in Section 3); these strings are shown in bold-face in Table 3 for n = 2, …, 5.

Again we have a conjectured estimate (see Section 4) for the lengths of the glue, which implies that l(B_{n}^{(2)}) is roughly three times l(B_{n−1}^{(2)}).

This analysis reduces the study of A^{(2)} to the study of the second-order glue strings S_{n}^{(2)}, and these, when concatenated, form the third-order sequence A^{(3)}, which in turn has a similar structure. And so on!

3 The main theorems

In this section we establish our main theorems, which will show that the description of the sequence given in Section 2 is correct. To do this we must introduce our notation very carefully. The following definitions (temporarily) supersede those in Section 2. For m ≥ 1, the mth-order sequence A^{(m)} = a^{(m)}(1), a^{(m)}(2), a^{(m)}(3), … ∈ ℙ_{m}^{∗} is defined by

a^{(m)}(1) = m ,
a^{(m)}(i + 1) = C^{(m)}(a^{(m)}(1), …, a^{(m)}(i)) for i ≥ 1 ,  (10)

where C^{(m)} is defined in (8). Note that A^{(1)} is our sequence A. Theorem 3.1 will show that A^{(m+1)} is the concatenation of the glue strings for A^{(m)}.

For m ≥ 1, n ≥ 1, the blocks B_{n}^{(m)} ∈ ℙ_{m}^{∗} and the glue strings S_{n}^{(m)} ∈ ℙ_{m+1}^{∗} are defined recursively, and independently of the A^{(m)}. Corollary 3.4 will show that all the strings B_{n}^{(m)}, S_{n}^{(m)} and T_{n}^{(m)} (defined below) are in fact finite, but at this point we do not know that, and the definitions must allow for the possibility that some of these strings may be infinite.

The recursion for the blocks is

B_{1}^{(m)} = m ,  (11)

and, for n ≥ 1,

B_{n+1}^{(m)} = \{ \begin{matrix}(B_{n}^{(m)})^{m+1}S_{n}^{(m)} , & if l(B_{n}^{(m)}) < ∞; \\ B_{n}^{(m)} , & if l(B_{n}^{(m)}) = ∞; \end{matrix}  (12)

where S_{n}^{(m)} will be constructed from B_{n}^{(m)}. If l(B_{n}^{(m)}) = ∞, S_{i}^{(m)} = ϵ for i ≥ n. If l(B_{n}^{(m)}) < ∞, consider the sequence s_{n}^{(m)}(1), s_{n}^{(m)}(2), s_{n}^{(m)}(3), … ∈ ℙ_{m}^{∗} defined by

s_{n}^{(m)}(1) = C^{(m)}((B_{n}^{(m)})^{m+1}) ,
s_{n}^{(m)}(i + 1) = C^{(m)}((B_{n}^{(m)})^{m+1}s_{n}^{(m)}(1) ⋯ s_{n}^{(m)}(i)) for i ≥ 1 .  (13)

Clearly s_{n}^{(m)}(1) ≥ m + 1. If there is an integer i ≥ 1 such that s_{n}^{(m)}(i + 1) < m + 1, choose the smallest such i, and set

S_{n}^{(m)} = s_{n}^{(m)}(1), s_{n}^{(m)}(2), …, s_{n}^{(m)}(i) ∈ ℙ_{m+1}^{+} ,  (14)

but if no such i exists set

S_{n}^{(m)} = s_{n}^{(m)}(1), s_{n}^{(m)}(2), … ∈ ℙ_{m+1}^{∗} .  (15)

In the latter case S_{n}^{(m)} and B_{n+1}^{(m)} are infinite.

The T_{n}^{(m)} are defined as follows. For n ≥ 1, if S_{1}^{(m)}, …, S_{n}^{(m)} are finite we set

T_{n+1}^{(m)} = S_{1}^{(m)} ⋯ S_{n}^{(m)} ∈ ℙ_{m+1}^{+} ,  (16)

while if S_{1}^{(m)}, …, S_{n−1}^{(m)} are finite but S_{n}^{(m)} is infinite, we still use (16) and define

T_{i}^{(m)} = T_{n+1}^{(m)}  (17)

for i ≥ n + 2. In the latter case all the T_{i}^{(m)} for i ≥ n + 1 are infinite. Note that T_{1}^{(m)} is always undefined.

The lengths of these strings (which may be infinite) are denoted by

β^{(m)}(n) = l(B_{n}^{(m)}) ,  (18)
σ^{(m)}(n) = l(S_{n}^{(m)}) ,  (19)
τ^{(m)}(n) = l(T_{n}^{(m)}) .  (20)

We also let B^{(m)} = b^{(m)}(1), b^{(m)}(2), b^{(m)}(3), … = lim_{n→∞} B_{n}^{(m)}. This is well defined since each B_{n}^{(m)} starts with B_{n−1}^{(m)}.

We will require three lemmas.

Lemma 3.1. For m ≥ 1, if A^{(m)} contains a string U^{t+1} ∈ ℙ_{m}^{+} for some t ≥ m, then U ∈ ℙ_{t}^{+}.

Proof. If t = m the claim is trivially true, so we may assume t ≥ m + 1. Suppose, on the contrary, that U ∉ ℙ_{t}^{+}. Then we may write U = GiH for G, H ∈ ℙ_{m}^{∗} and some i with m ≤ i ≤ t − 1. Thus A contains GiH GiH … GiH (t + 1 copies). But the final i is preceded by t copies of iHG, so the final i must be at least t, by definition of A^{(m)}, a contradiction.

Lemma 3.2. For m ≥ 1, n ≥ 2, (a) T_{n}^{(m)} is a suffix of B_{n}^{(m)}, and (b) this is the only occurrence of T_{n}^{(m)} as a substring of B_{n}^{(m)}.

Proof. Fix m ≥ 1. It follows by iterating (12) that

B_{n+1}^{(m)} = (B_{n}^{(m)})^{m}(B_{n−1}^{(m)})^{m} ⋯ (B_{1}^{(m)})^{m}B_{1}^{(m)}S_{1}^{(m)}S_{2}^{(m)} ⋯ S_{n−1}^{(m)}S_{n}^{(m)}
= (B_{n}^{(m)})^{m}(B_{n−1}^{(m)})^{m} ⋯ (B_{1}^{(m)})^{m}B_{1}^{(m)}T_{n+1}^{(m)} ,  (21)

provided all of S_{1}^{(m)}, S_{2}^{(m)}, …, S_{n}^{(m)} are finite. If S_{1}^{(m)}, S_{2}^{(m)}, …, S_{n−1}^{(m)} are finite but S_{n}^{(m)} is infinite, (21) is still true, but

B_{i}^{(m)} = B_{n+1}^{(m)}, T_{i}^{(m)} = T_{n+1}^{(m)} for i ≥ n + 2 .  (22)

Assertion (a) follows at once. To show (b) we use induction on n. The base case, n = 2, is true because T_{2}^{(m)} = m + 1 and B_{2}^{(m)} = (m^{m+1}, m + 1). If T_{n+1}^{(m)} is infinite and has two occurrences in B_{n+1}^{(m)}, they are both suffixes of B_{n+1}^{(m)}, implying that T_{n+1}^{(m)} is a suffix of itself, and hence is a periodic sequence. But this is impossible: let M_{0} be the maximal element of T_{n+1}^{(m)}. After sufficiently many terms the curling number given by (13) would produce a term exceeding M_{0}, a contradiction. On the other hand, suppose that all the S_{n}^{(m)} are finite. If T_{n+1}^{(m)} also occurs in B_{n+1}^{(m)} other than as a suffix, it must be a substring of a block B_{j}^{(m)} in (21), for some j with 2 ≤ j ≤ n, for otherwise it would contain the m at the beginning of a block. Write B_{j}^{(m)} = UT_{n+1}^{(m)}V = UT_{j}^{(m)}S_{j}^{(m)} ⋯ S_{n}^{(m)}V for some U ∈ ℙ_{m}^{+} and V ∈ ℙ_{m}^{∗}. But l(S_{j}^{(m)} ⋯ S_{n}^{(m)}) > 0, so T_{j}^{(m)} occurs as a non-suffix in B_{j}^{(m)}, a contradiction to the induction hypothesis. Remark. It follows from the above proof that, for any r with 1 ≤ r ≤ m + 1, any finite substring (B_{n}^{(m)})^{r} in (21) contains exactly r copies of T_{n}^{(m)}, each one occurring at the end of a B_{n}^{(m)}. The copies are disjoint.

Lemma 3.3. For m ≥ 1, n ≥ 2, suppose that k = b^{(m)}(i) ≥ m + 1 with 1 ≤ i ≤ β^{(m)}(n). Then there exists a Y such that b^{(m)}(1), …, b^{(m)}(i − 1) = XY^{k}. Moreover, let Y satisfy this condition with l(Y) minimal and suppose m ∈ Y. Then Y = B_{j}^{(m)} for some j with 1 ≤ j ≤ n − 1.

Proof. We fix m ≥ 1, and will prove the result for all n by induction. The base case n = 2 is immediate, since B_{2}^{(m)} = (m^{m+1}, m + 1). Supposing the result holds for some n ≥ 2, we will show it holds for n + 1. If B_{n}^{(m)} is infinite then the result also holds for n + 1, by (12), so we may assume that B_{n}^{(m)} is finite. Then B_{n+1}^{(m)} = (B_{n}^{(m)})^{(m+1)}S_{n}^{(m)}, by (12). We must show that the result holds for all positions β^{(m)}(n) < i ≤ β^{(m)}(n + 1).

If i is a position in (B_{n}^{(m)})^{m+1}, we may write i = rβ^{(m)}(n) + s ≤ (m + 1)β^{(m)}(n), for 1 ≤ r ≤ m, 1 ≤ s ≤ β^{(m)}(n). Then b^{(m)}(i) = b^{(m)}(s) and by induction we know that in the first B_{n}^{(m)} we can write b^{(m)}(1), …, b^{(m)}(s − 1) = XY^{k}, and if the minimal Y contains an m then it equals B_{j}^{(m)} for some j with 1 ≤ j ≤ n − 1. Therefore this Y (and no shorter string) can also be used at position i, and thus the statement holds.

If i = (m + 1)β^{(m)}(n) + 1 then the part preceding i is (B_{n}^{(m)})^{m+1}, and from (13) we have

k = b^{(m)}(i) = s_{n}^{(m)}(1) = C^{(m)}((B_{n}^{(m)})^{m+1}) ≥ m + 1 .

So certainly one Y exists with b^{(m)}(1), …, b^{(m)}(i − 1) = XY^{k}. We must show that if the minimal Y satisfying this property contains an m, then this Y = B_{j}^{(m)} for some j ≤ n. If Y contains an m, then it contains T_{n}^{(m)} as a substring, since the last m in B_{n+1}^{(m)} occurs before the T_{n}^{(m)} in the last copy of B_{n}^{(m)}. Therefore the string Y^{k} contains at least k ≥ m + 1 copies of T_{n}^{(m)}. It follows from the Remark below Lemma 3.2 that k = m + 1 and Y = B_{n}^{(m)}.

If i > (m + 1)β^{(m)}(n) + 1 we see by the definition of S_{n}^{(m)} that again a Y exists. If Y contains an m, then it must properly contain the T_{n}^{(m)} in the final copy of B_{n}^{(m)}. But in the last of the k copies of Y the copy of T_{n}^{(m)} is followed by an integer larger than m, whereas in the earlier k − 1 copies it was followed by the first element of B_{n}^{(m)}, which is m. This is a contradiction, and shows that in this case Y cannot contain an m.

Note that, by definition of S_{n−1}^{(m)}, the Y^{k} for the first element of S_{n}^{(m)} extends further back (towards the beginning of the sequence) than the start of B_{n}^{(m)}, and thus contains an m. Therefore we see that the situation described in the penultimate paragraph of the above proof is indeed the case and we may conclude that

s_{n}^{(m)}(1) = m + 1 for all m ≥ 1, n ≥ 1 .  (23)

At this point we can already see that the concatenation of the glue strings is equal to the next A sequence:

Theorem 3.1. Suppose m ≥ 1. For all n ≥ 2, T_{n}^{(m)} is a prefix of A^{(m+1)}, or equals A^{(m+1)} if T_{n}^{(m)} is infinite.

Proof. Again we fix m and use induction on n. For n = 2 the result is trivial. Supposing the result holds for some n ≥ 2, we will show it holds for n+1. If T_{n}^{(m)} is infinite then clearly the result holds for T_{n+1}^{(m)}, so assume that T_{n}^{(m)} is finite.

Write (B_{n}^{(m)})^{m+1} = UT_{n}^{(m)} for some U ∈ P_{m}^{+}. We know that S_{n}^{(m)} begins with m + 1 = s_{n}^{(m)}(1) = C^{(m)}(UT_{n}^{(m)}) = C^{(m+1)}(UT_{n}^{(m)}) = C^{(m+1)}(T_{n}^{(m)}). The last equality holds because dropping the U can only decrease the value, but it is already equal to its minimal value of m + 1. By the induction hypothesis, T_{n}^{(m)} is a prefix of A^{(m+1)}, and therefore T_{n}^{(m)}s_{n}^{(m)}(1) is a prefix of A^{(m+1)}. For i ≥ 1, as long as s_{n}^{(m)}(i) ≥ m + 1, we have

s_{n}^{(m)}(i + 1) = C^{(m)}(UT_{n}^{(m)}s_{n}^{(m)}(1) ⋯ s_{n}^{(m)}(i))
= C^{(m+1)}(UT_{n}^{(m)}s_{n}^{(m)}(1) ⋯ s_{n}^{(m)}(i))
= C^{(m+1)}(T_{n}^{(m)}s_{n}^{(m)}(1) ⋯ s_{n}^{(m)}(i)) .

The second equality holds because s_{n}^{(m)}(i) ≥ m + 1. The third equality holds because Y^{k} for s_{n}^{(m)}(i + 1) goes back no further than the beginning of T_{n}^{(m)}, as we saw in the proof of the previous lemma. Hence T_{n+1}^{(m)} = T_{n}^{(m)}S_{n}^{(m)} is a prefix of A^{(m+1)}, as required.

Theorem 3.2. For all m ≥ 1, the sequences A^{(m)} and B^{(m)} coincide.

Proof. Fix m ≥ 1. We will show by induction on n that, for all n ≥ 1, B_{n}^{(m)} is a prefix of A^{(m)} or is all of A^{(m)} if B_{n}^{(m)} is infinite. This will establish the theorem.

The cases n = 1 and n = 2 are immediate, since B_{1}^{(m)} = m, B_{2}^{(m)} = (m^{m+1}, m + 1). So assume the truth of the induction hypothesis up to and including some n ≥ 2.

If B_{n}^{(m)} is infinite the result follows from (12), so we may assume that B_{n}^{(m)} and hence T_{n}^{(m)} are finite. We wish to show that B_{n+1}^{(m)} = (B_{n}^{(m)})^{m+1}S_{n}^{(m)} is a prefix of A^{(m)}. If this is not true, the first discrepancy between B_{n+1}^{(m)} and A^{(m)} occurs in the substring (B_{n}^{(m)})^{m+1}, by the definition of S_{n}^{(m)}. Let i ≥ β^{(m)}(n) + 1 be the first position in (B_{n}^{(m)})^{m+1} at which a^{(m)}(i) ≠ b^{(m)}(i). Our goal is to show that the existence of i leads to a contradiction.

We may write i = jβ^{(m)}(n) + r with 1 ≤ j ≤ m and 1 ≤ r ≤ β^{(m)}(n). Then i is also minimal with respect to the condition that a^{(m)}(i) ≠ a^{(m)}(r). Let a^{(m)}(1), …, a^{(m)}(i − 1) = XY^{k} with k maximal and l(Y) minimal. Then a^{(m)}(i) = max{m, k}.

We consider two cases, depending on whether or not a^{(m)}(i) is at the beginning of one of the B_{n}^{(m)} blocks, i.e. whether r = 1 or r ≥ 2.

First, suppose r = 1; then we need to prove that a^{(m)}(i) = a^{(m)}(1) = m. This follows by definition of S_{n−1}^{(m)} if j = 1; so assume j ≥ 2, and that k = a^{(m)}(i) ≥ m + 1. Using (21) we may write a^{(m)}(1), …, a^{(m)}(i − 1) = (B_{n}^{(m)})^{j} = (B_{n}^{(m)})^{j−1}UmT_{n}^{(m)} for some U ∈ ℙ_{m}^{∗}. If T_{n}^{(m)} is a proper suffix of Y^{k} then m ∈ Y, which implies that T_{n}^{(m)} is a proper suffix of Y and therefore (B_{n}^{(m)})^{j} contains at least m + 1 copies of T_{n}^{(m)}, contradicting the Remark following Lemma 3.2. On the other hand, if Y^{k} were a suffix of T_{n}^{(m)}, this would contradict the fact that S_{n−1}^{(m)} is followed by an element ≤ m.

Second, suppose that r ≥ 2. Let L = a^{(m)}(1), …, a^{(m)}(r − 1) and write L = X_{∗}Y_{∗}^{k_{∗}} with k_{∗} maximal and l(Y_{∗}) minimal. Then a^{(m)}(r) =max{m, k_{∗}}. By the definition of i, a^{(m)}(i) > a^{(m)}(r) ≥ m. Hence a^{(m)}(i) = k ≥ m + 1. To have a^{(m)}(i) > a^{(m)}(r), L must be a suffix of Y^{k}, so m ∈ Y and therefore, by Lemma 3.1, k is at most m + 1 and therefore is equal to m + 1. Hence k_{∗} ≤ m.

The situation, then, is that (B_{n}^{(m)})^{j}L is a prefix of A^{(m)}. We are supposing that we can achieve a^{(m)}(i) = m + 1 by allowing L to be a suffix of Y^{m+1}. Noting that T_{n}^{(m)} is a suffix of (B_{n}^{(m)})^{j}, by (21), we distinguish two cases, depending on the relationship between T_{n}^{(m)}L and Y^{m+1}.

(i) Suppose that T_{n}^{(m)}L is a suffix of Y^{m+1}. We know m ∈ Y and m ∉ T_{n}^{(m)}, so Y^{m+1} contains at least m disjoint copies of T_{n}^{(m)}. Hence j = m, and there are exactly m disjoint copies, by the Remark following Lemma 3.2. This means that each copy of T_{n}^{(m)} straddles the end of one copy of Y and the beginning of the next (if not, T_{n}^{(m)} is wholly contained in Y, and so there are m + 1 copies of T_{n}^{(m)} in the sequence before position i, which is a contradiction since there are only m copies, one in each of the m copies of B_{n}^{(m)} and none so far in the next copy of B_{n}^{(m)} that we are building), and hence that Y is a proper suffix of T_{n}^{(m)}L. Write T_{n}^{(m)} = V W where W is the intersection of T_{n}^{(m)} and the last (or (m + 1)-st) copy of Y, and write B_{n}^{(m)} = UT_{n}^{(m)}, using (21). If m ≥ 2 it is easy to complete the proof. We have Y = W L = W UV, so L = UV and therefore i > l(Y^{m+1}) = (m + 1)l(W UV) = (m + 1)l(UV W) = (m + 1)β^{(m)}(n), contradicting the definition of i.

Suppose then that m = 1. Again L is a proper suffix of Y and Y is a proper suffix of T_{n}^{(1)}L. Write Y = W L, and let s ≥ 2 be the first element of Y. Let this element s in the second copy of Y be preceded by s copies of some string Y′ with l(Y′) minimal.

Suppose that Y′ does not contain a 1. Since Y does contain a 1 (L starts with a 1), Y^{′s} is a suffix of the first copy of Y, and hence also of the second copy of Y. This contradicts the minimality of l(Y), since then l(Y′) < l(Y).

So we may assume that 1 ∈ Y′, hence by Lemma 3.3 we know that

Y′ = B_{κ}^{(1)} for some κ < n. Now T_{κ}^{(1)} is a suffix of Y^{2} and since L starts with a 1, T_{κ}^{(1)} is also a suffix of L. By Lemma 3.2, B_{κ}^{(1)} is also a suffix of L. Suppose B_{κ}^{(1)} = L. Then W L is a suffix of Y′Y′ = LL (look at the first copy of Y = W L and remember Y′Y′ begins with a 1) and hence W is a suffix of L. But then W^{2} is a suffix of T_{n}^{(1)}, contradicting the fact that L starts with a 1.

So we may assume that B_{κ}^{(1)} is a strict suffix of L. But now l(Y) > l(L) ≥ 2l(B_{κ}^{(1)}). (Indeed, if l(L) < 2l(B_{κ}^{(1)}), then we know that L is a prefix of B_{n}^{(1)}, by definition, B_{κ}^{(1)}B_{κ}^{(1)} is also a prefix of B_{n}^{(1)}, and so L is a strict prefix of B_{κ}^{(1)}B_{κ}^{(1)}; but L has T_{κ}^{(1)} as a suffix, so by Lemma 3.2, L = B_{κ}^{(1)}, a contradiction.) But now (B_{κ}^{(1)})^{2} is a suffix of Y, contradicting the minimality of Y.

(ii) Suppose on the other hand that Y^{m+1} is a suffix of T_{n}^{(m)}L. Since no Y is contained in T_{n}^{(m)} (remember that m ∈ Y), Y^{m} is a suffix of L and the first element, t, of Y is in T_{n}^{(m)} with t ≥ m + 1. Therefore the first element of the second Y is also t and since (B_{n}^{(m)})^{j}L is a prefix of A^{(m)}, Y ends with U^{t} for some U. Hence U^{t} is a suffix of L, which contradicts the fact that k_{∗} = m. This completes the proof.

Corollary 3.3. The sequence A^{(m)} contains every integer ≥ m.

Proof. From Theorem 3.1 we know that, for m ≥ 2, n ≥ 2, T_{n}^{(m−1)} is a prefix of A^{(m)}, so, for a given m, either

A^{(m)} = S_{1}^{(m−1)}S_{2}^{(m−1)} ⋯ S_{n}^{(m−1)}

if some S_{n}^{(m−1)} is infinite, or

A^{(m)} = S_{1}^{(m−1)}S_{2}^{(m−1)}S_{3}^{(m−1)} ⋯

if all S_{n}^{(m−1)} are finite. Also, by Theorem 3.2, B_{n+1}^{(m−1)} is a prefix of A^{(m−1)}, so from (12), if some S_{n}^{(m−1)} is infinite, A^{(m−1)} contains

S_{1}^{(m−1)}, S_{2}^{(m−1)}, …, S_{n}^{(m−1)} ,

or if all S_{n}^{(m−1)} are finite, A^{(m−1)} contains S_{1}^{(m−1)}, S_{2}^{(m−1)}, …, S_{n}^{(m−1)} for all n. In either case (and this is the key point), every prefix of A^{(m)} is a subsequence of A^{(m−1)}. Repeating this argument shows that every prefix of every A^{(j)} is a subsequence of A^{(m)} if j ≥ m.

Since A^{(j)} begins with j, A^{(m)} contains every integer j ≥ m.

Corollary 3.4. The strings B_{n}^{(m)}, S_{n}^{(m)} and T_{n}^{(m)} have finite length.

Proof. The first occurrence of an integer in A^{(m)} is necessarily followed by an m. Since we saw in the previous corollary that A^{(m)} contains infinitely many different integers, it follows that all S_{n}^{(m)} are finite. This implies that B_{n}^{(m)} and T_{n}^{(m)} are also finite.

Promotion

In the definition of A^{(m)}, (10), let us say that a^{(m)}(i) is promoted if either i = 1 or C(a^{(m)}(1), …, a^{(m)}(i − 1)) < m. If we know which elements in A^{(m+1)} are promoted, we can recover A^{(m)} from A^{(m+1)}. To make this precise, we define the strings D_{i}^{(m)} ∈ ℙ_{m}^{+} by D_{0}^{(m)} = m and, for i > 0,

D_{i}^{(m)} = \{ \begin{matrix}D_{i−1}^{(m)}a^{(m+1)}(i) , & if a^{(m+1)}(i) is not promoted ; \\ (D_{i−1}^{(m)})^{m+1} a^{(m+1)}(i) , & if a^{(m+1)}(i) is promoted . \end{matrix}  (24)

Since D_{i}^{(m)} starts with D_{i−1}^{(m)}, we can define the limiting sequence D^{(m)} = lim_{i→∞} D_{i}^{(m)}. Then it can be shown that:

Theorem 3.5. For all m ≥ 1, the sequences A^{(m)} and D^{(m)} coincide.

Sketch of proof. By Theorem 3.1, A^{(m+1)} = S_{1}^{(m)}S_{2}^{(m)} · · ·. The promoted elements a^{(m+1)}(i_{1}), a^{(m+1)}(i_{2}), … of A^{(m+1)} are precisely the initial elements of the S_{k}^{(m)}. Indeed, by definition of S_{k}^{(m)}, the first element of S_{k}^{(m)} is promoted.

To see the reverse, let a^{(m)}(i) = t ≥ m+1, with (m+1)β^{(m)}(k)+1 < i ≤ β^{(m)}(k+1). That is, we are in the first copy of S_{k}^{(m)}. It suffices to show that when a^{(m)}(1) ⋯ a^{(m)}(i) = XY^{t}, Y^{t} lies completely inside T_{k+1}^{(m)}; that is, Y does not contain an m. This follows since otherwise XY^{t} contains t ≥ m + 1 copies of T_{k}, contradicting Lemma 3.2.

We now show by induction that D_{i_{k}−1}^{(m)} = B_{k}^{(m)} (k = 1, 2, …). For k = 1 this is obvious: D_{0}^{(m)} = B_{1} = m. Let k ≥ 2. Then

D_{i_{k}}^{(m)} = (D_{i_{k}−1}^{(m)})^{m+1}a^{(m+1)}(i_{k}) = (B_{k}^{(m)})^{m+1}a^{(m+1)}(i_{k}) .  (25)

Hence

D_{i_{k+1}−1}^{(m)} = (B_{k}^{(m)})^{m+1}a^{(m+1)}(i_{k}) ⋯ a^{(m+1)}(i_{k+1} − 1)  (26)
= (B_{k}^{(m)})^{m+1}S_{k}^{(m)} = B_{k+1}^{(m)} .  (27)

4 Estimates for the rate of growth

In this section we take an experimental approach, and record a series of observations about the sequence. These observations appear to be correct, but we have been unable to prove them, so we state them as conjectures. In §4.1 we study the lengths of the glue strings S_{n}^{(m)}. Although these lengths are somewhat irregular, it appears that they can be “smoothed” so as to become much more regular “ruler” sequences, whose peak values will be denoted by ρ^{(m)}(n). In §4.2 we describe a “tabular” construction for the higher-order sequences A^{(2)}, A^{(3)}, … which leads to a recurrence relating the ρ^{(m)}(n), β^{(m)}(n) and σ^{(m)}(n). Sections 4.3, 4.4 and 4.5 contain estimates for β^{(m)}(n), ρ^{(m)}(n) and τ^{(m)}(n). Finally, in §4.6, we use these estimates to determine where each number t ≥ 1 appears for the first time in our sequence A.

4.1 Ruler sequences and smoothing

It appears that the sequence σ^{(m)} = σ^{(m)}(1), σ^{(m)}(2), σ^{(m)}(3), … giving the lengths of the glue strings S_{n}^{(m)} is essentially a “ruler” sequence, in the sense that σ^{(m)}(n) essentially depends only on the (m + 1)-adic valuation of n.

For positive integers m, n, define the m-adic valuation of n, |n|_{m}, to be the highest power of m dividing n. The classical example of a ruler sequence is the sequence r = r(1), r(2), r(3), … given by

r(n) = |n|_{2} + 1 .  (28)

The first 32 terms are

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6

where the new record entries, shown in bold-face, occur at powers of 2. For much more about this sequence, including an extensive bibliography, see entry A1511 in [8].

The initial values of σ^{(1)}, …, σ^{(4)} are shown in Table 4, and the record entries in σ^{(1)}, …, σ^{(10)} in Table 5. Let π^{(m)}(j) (j ≥ 0) denote the j-th record in σ^{(m)}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ σ^{(1)}(n) & 1 & 3 & 1 & 9 & 4 & 24 & 1 & 3 & 1 & 9 & 4 & 67 & 1 & 3 & 1 & 9 \\ σ^{(2)}(n) & 1 & 1 & 3 & 1 & 1 & 3 & 1 & 1 & 9 & 1 & 1 & 3 & 1 & 1 & 3 & 1 \\ σ^{(3)}(n) & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 10 \\ σ^{(4)}(n) & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 3 & 1 \\ n & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 \\ σ^{(1)}(n) & 4 & 24 & 1 & 3 & 1 & 9 & 4 & 196 & 3 & 1 & 9 & 4 & 24 & 1 & 3 & 1 \\ σ^{(2)}(n) & 1 & 9 & 1 & 1 & 3 & 1 & 1 & 3 & 1 & 1 & 32 & 1 & 3 & 1 & 1 & 3 \\ σ^{(3)}(n) & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 10 \\ σ^{(4)}(n) & 1 & 1 & 1 & 11 & 1 & 1 & 1 & 1 & 3 & 1 & 1 & 1 & 1 & 3 & 1 & 1 \\ n & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 \\ σ^{(1)}(n) & 9 & 4 & 68 & 3 & 1 & 9 & 4 & 24 & 1 & 3 & 1 & 9 & 4 & 581 & 3 & 1 \end{matrix}

Table 4: Values of σ^{(1)}(n) for n ≤ 48 and σ^{(2)}(n), σ^{(3)}(n), σ^{(4)}(n), for n ≤ 32, with record entries shown in bold-face.

m \ j 0 1 2 3  4  5  6  7  8  9
1 1 3 9 24 67 196  581 1731 5180 15534
2 1 3 9 32 119 463 1837 7332 29307 117203
3 1 3 10 42 200 983 4892 24434 122141
4 1 3 11 55 315 1872 11205 67195
5 1 3 12 70 471 3273 22883
6 1 3 13 87 673 5355 42805
7 1 3 14 106 927 8309 74740
8 1 3 15 127 1239 12351 123463
9 1 3 16 150 1615 17721
10 1 3 17 175 2061 24683

Table 5: Values of π^{(m)}(j), the j-th record in sequence σ^{(m)}. The smoothed record values ρ^{(m)}(j) are obtained by reducing the italicized entries by 1. The next three terms in the first row are 46578 , 139713 , 419116 , and the next term in the m = 2 row is 468785. The missing entries in this table have not been calculated, although we predict that the entries on or below the diagonal m = j are given by (43) and the entries just above this diagonal by (44).

As can be seen from Table 4, σ^{(1)} is not quite as regular as the ruler sequence r. However:

Conjecture 4.1. If the sequence σ^{(1)} is “smoothed” by replacing every instance of 4 by the pair of numbers 3, 1, every 9 by 8, 1, every 25 by 24, 1, and so on, σ^{(1)} becomes a ruler sequence r^{(1)} given by

r^{(1)}(n) = ρ^{(1)}(|n|_{2}) ,  (29)

in which the first 64 terms are

1 3 1 8 1 3 1 24 1 3 1 8 1 3 1 67
1 3 1 8 1 3 1 24 1 3 1 8 1 3 1 195
1 3 1 8 1 3 1 24 1 3 1 8 1 3 1 67
1 3 1 8 1 3 1 24 1 3 1 8 1 3 1 580

and where the record values (shown in bold-face) ρ^{(1)}(0), ρ^{(1)}(1), … are

1, 3, 8, 24, 67, 195, 580, 1730, 5179, 15533, 46578, 139712, 419115, ….  (30)

The numbers i in σ^{(1)} that are to be replaced by i − 1, 1 to get r^{(1)} are

4, 9, 25, 68, 196, 581, 1731, 5180, 15534, 46579, 139713, 419116, …,  (31)

The numbers that need to be smoothed, given in (31), are one greater than the numbers in (30), except that 2 is missing. The records in the smoothed sequence r^{(1)}, (30), either agree with or are one less than the terms in the first row of Table 5.

The sequences σ^{(m)} for m ≥ 2 appear to need less smoothing than σ^{(1)} to make them into ruler sequences. In the range of our tables, σ^{(2)} needs to be smoothed by replacing every 32 by 31, 1, and every 7332 by 7331, 1; σ^{(3)} by replacing every 200 by 199, 1; σ^{(4)} by replacing every 1872 by 1871, 1; and so on. If r^{(m)} denotes the smoothed version of σ^{(m)} and ρ^{(m)}(j) the j-th record in the smoothed version (see Table 5) then we have, for all m ≥ 1, n ≥ 1,

r^{(m)}(n) = ρ^{(m)}(|n|_{m+1}) .  (32)

The lengths β^{(m)}(n) of the blocks are given by (from (12), (18))

β^{(m)}(1) = 1 ,
β^{(m)}(n + 1) = (m + 1)β^{(m)}(n) + σ^{(m)}(n) for n ≥ 1 .  (33)

The initial values of β^{(1)}(n), …, β^{(6)}(n) are shown in Table 6.

\begin{matrix}m \ n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 1 & 3 & 9 & 19 & 47 & 98 & 220 & 441 \\ 2 & 1 & 4 & 13 & 42 & 127 & 382 & 1149 & 3448 \\ 3 & 1 & 5 & 21 & 85 & 343 & 1373 & 5493 & 21973 \\ 4 & 1 & 6 & 31 & 156 & 781 & 3908 & 19541 & 97706 \\ 5 & 1 & 7 & 43 & 259 & 1555 & 9331 & 55989 & 335935 \\ 6 & 1 & 8 & 57 & 400 & 2801 & 19608 & 137257 & 960802 \end{matrix}

Table 6: Lengths β^{(m)}(n) of the blocks B_{n}^{(m)}.

4.2 The tabular construction

The appearance of ruler sequences can be partially explained if we present the construction of the higher-order sequences A^{(2)}, A^{(3)}, …, in a tabular format. In this construction we keep track not only of the actual value A^{(m)}(n) = max{m, k} (cf. (10)) but also whether the promotion rule was invoked (if k < m we indicate this by drawing a circle around the entry) and the length of the shortest Y that was used to compute k if k ≥ m (shown as a subscript; if the promotion rule was invoked the subscript is 0). This tabular construction will also suggest a recurrence that relates ρ^{(m)}(n + 1), β^{(m+1)}(n + 1) and σ^{(m+1)}(n + 1).

We will construct A^{(2)} as an example. We start by making a small table of the glue strings S_{n}^{(2)} for n ≤ 10 — see Table 7. (We already saw S_{1}^{(2)}, …, S_{4}^{(2)} in Table 3.)

\begin{matrix}n & S_{n}^{(2)} \\ 1 & 3 \\ 2 & 3 \\ 3 & 3 3 4 \\ 4 & 3 \\ 5 & 3 \\ 6 & 3 3 4 \\ 7 & 3 \\ 8 & 3 \\ 9 & 3 3 4 3 3 3 3 4 4 \\ 10 & 3 \end{matrix}

Table 7: The first few glue strings S_{n}^{(2)}.

We know from Section 3 that A^{(2)} = lim_{n→∞} B_{n}^{(2)} = lim_{n→∞} T_{n}^{(1)} = S_{1}^{(1)}S_{2}^{(1)} ⋯ and that

B_{n+1}^{(2)} = (B_{n}^{(2)})^{3}S_{n}^{(2)}. Table 8 shows the beginning of the construction of A^{(2)}.

The aim is to understand how A^{(2)} breaks into the consecutive S_{n}^{(1)} glue strings for A^{(1)}. To do this, a version of A^{(2)} is produced in which terms that are obtained by promotion are circled, and where the subscript on each term is either 0 for a circled term or else gives the length of the shortest Y that can be used to compute that term. The circled terms will be the first terms of each of the glue strings S_{n}^{(1)} of A^{(1)}. Most of the circling and subscripting work is done by a few simple rules. However, the rules occasionally give the wrong answer and a few corrections may need to be made by hand at the end of each round. It is the presence of these adjustments that makes our sequence hard to analyze.

We start with B_{1}^{(2)} = \begin{matrix}2 \\ ◯ \end{matrix}_{0}. The rules for going from B_{n}^{(2)} to B_{n+1}^{(2)} are as follows:

(i) Write B_{n}^{(2)} as a single string, and construct a three-rowed array in which each row is a copy of B_{n}^{(2)}, omitting all circles from the third row. This three-rowed array (after S_{n}^{(2)} is appended in step (iii)) will form B_{n+1}^{(2)} when read as a single string. (When constructing A^{(m)} we make m copies of B_{n}^{(m)} and omit the circles from the m-th copy.) (ii) The subscripts in rows 2 and 3 are the same as in row 1, except that terms in row 3 that are under circled terms in row 2 have their subscripts changed to l(B_{n}^{(2)}).

(iii) Append S_{n}^{(2)} to the end of row 3. The first term of S_{n}^{(2)} receives the subscript l(B_{n}^{(2)}). The subscripts on the remaining terms of S_{n}^{(2)} must be computed separately—they can be obtained from the tabular construction of A^{(m+1)}. (iv) Finally, a few circles in row 2 may need to be omitted and their subscripts recomputed, as well as the subscripts on the same terms in row 3.

In Table 8, rules (i)–(iii) give the correct answers for B_{2}^{(2)} and B_{3}^{(2)}. But in B_{4}^{(2)} four terms (marked with asterisks in Table 8) must be corrected. The first entry in row 2 of B_{4}^{(2)} is \begin{matrix}2 \\ ◯ \end{matrix}_{0}. However, row 1 ends with 3 3 = S_{1}^{(2)}S_{2}^{(2)} = Y^{2}, with a Y of length 1, so that 2 did not need to be promoted and we must change \begin{matrix}2 \\ ◯ \end{matrix}_{0} to 2_{1}. The fifth entry in row 2 of B_{4}^{(2)} is \begin{matrix}2 \\ ◯ \end{matrix}_{0}. But it is preceded by

3 2 2 2 3 3 2 2 2 3 = S_{1}^{(2)}B_{2}^{(2)}S_{2}^{(2)}B_{2}^{(2)} = Y^{2} ,

with a Y of length 5, so we must change \begin{matrix}2 \\ ◯ \end{matrix}_{0} to 2_{5}. The corresponding entries in row 3, presently both equal to 2_{13}, also get changed to 2_{1} and 2_{5} respectively.

B_{1}^{(2)} = \begin{matrix}2 \\ ◯ \end{matrix}_{0}
B_{2}^{(2)} = \begin{matrix}2 \\ ◯ \end{matrix}_{0}
\begin{matrix}2 \\ ◯ \end{matrix}_{0}
2_{1} 3_{1}
B_{3}^{(2)} = \begin{matrix}2 \\ ◯ \end{matrix}_{0} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1}
\begin{matrix}2 \\ ◯ \end{matrix}_{0} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1}
2_{4} 2_{4} 2_{1} 3_{1} 3_{4}
B_{4}^{(2)} = \begin{matrix}2 \\ ◯ \end{matrix}_{0} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1} \begin{matrix}2 \\ ◯ \end{matrix}_{0} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1} 2_{4} 2_{4} 2_{1} 3_{1} 3_{4}
\begin{matrix}2 \\ ◯ \end{matrix}_{0}^{∗} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1} \begin{matrix}2 \\ ◯ \end{matrix}_{0}^{∗} \begin{matrix}2 \\ ◯ \end{matrix}_{0} 2_{1} 3_{1} 2_{4} 2_{4} 2_{1} 3_{1} 3_{4}
2_{13}^{∗} 2_{13} 2_{1} 3_{1} 2_{13}^{∗} 2_{13} 2_{1} 3_{1} 2_{4} 2_{4} 2_{1} 3_{1} 3_{4} 3_{13} 3_{1} 4_{1}

Table 8: Tabular construction of A^{(2)}.

When we extend Table 8 to B_{10}^{(2)}, we find that in all only ten circles need to be removed. After B_{4}^{(2)}, the next changes are at B_{7}^{(2)}, where two circles get removed because of the splittings S_{4}^{(2)}S_{5}^{(2)} = 3 3 = Y^{2}, with a Y of length 1, and S_{4}^{(2)}B_{5}^{(2)}S_{5}^{(2)}B_{5}^{(2)} = Y^{2} with a Y of length 128. But not all instances of such splittings cause circles in the table to be removed, and not all circle-removals arise in this way. It seems difficult to explain exactly where corrections to the table are required.

However, the corrections are rare, and still fewer corrections are needed for larger values of m.

Since A^{(2)} is also lim_{n→∞} T_{n}^{(1)}, we can read off the lengths of the glue strings S_{n}^{(1)} from the

table. Look at the lengths of the strings (in B_{4}^{(2)}) between one circle and the next: these are 1, 3, 1, 9, 4, 24, . . .. exactly the values of σ^{(1)}(1), σ^{(1)}(2), … (cf. Table 4). If we do not make the corrections needed in step (iv), we instead get the smoothed lengths 1, 3, 1, 8, 1, 3, 1, 24, . . .. These observations lead to our conjectured recurrence. For example, note that the string in B_{4}^{(2)} from the last circled entry to the end has length 24 (which is ρ^{(1)}(3)) and is made up of the last string in B_{3}^{(2)} (length 8, which is ρ^{(1)}(2)) plus the whole of B_{3}^{(2)} (length 13, which is β^{(2)}(3)), plus S_{3}^{(2)} (length 3, which is σ^{(2)}(3)). More generally, we have: Conjecture 4.2. For m ≥ 1,

ρ^{(m)}(0) = 1 ,
ρ^{(m)}(n + 1) = ρ^{(m)}(n) + β^{(m+1)}(n + 1) + σ^{(m+1)}(n + 1) for n ≥ 0 .  (34)

This recurrence is supported by all the data, although we do not have a proof.

4.3 Estimates for the lengths β^{(m)}(n) of the blocks

In this section we first prove formulas (36), (37), (38), which give the exact value of β^{(m)}(n) in the parabolic region 1 ≤ n ≤ (m + 1)^{2} − 1 for m ≥ 1. We then give conjectural estimates for β^{(m)}(n) (indicated by ≈), (39) and (40), which apply for all m and n.

We take (33) as our starting point. For m ≥ 1, σ^{(m)}(n) and r^{(m)}(n) coincide for 1 ≤ n ≤ (m + 1)^{2} − 1, and in that range are given by

σ^{(m)}(n) = r^{(m)}(n) = \{ \begin{matrix}1 , & if m + 1 does not divide n; \\ 3 , & if m + 1 divides n . \end{matrix}  (35)

By iterating (33) and using (35) we find: Lemma 4.1. For m ≥ 1 and 1 ≤ n ≤ (m + 1)^{2} − 1,

β^{(m)}(n) = \frac{(m + 1)^{n} − 1}{m} + 2 \frac{(m + 1)^{n−1} − (m + 1)^{v}}{(m + 1)^{m+1} − 1} ,  (36)

where v ∈ {0, 1, …, m} is given by n − 1 ≡ v mod m + 1.

In particular, for 1 ≤ n ≤ m + 1 we have v = n − 1 and so

β^{(m)}(n) = \frac{(m + 1)^{n} − 1}{m} ,  (37)

and for m + 2 ≤ n ≤ 2m + 2 we have v = n − m − 2 and

β^{(m)}(n) = \frac{(m + 1)^{n} + 2(m + 1)^{n−m−1} − 2(m + 1)^{n−m−2} − 1}{m} .  (38)

Equation (37) explains the entries on or below the diagonal n = m + 1 in Table 6, (38) explains the entries in the “wedge” m + 2 ≤ n ≤ 2m + 2, and (36) the entries in the whole parabolic region bounded by n ≤ (m + 1)^{2} − 1.

The right-hand side of (36) is also a good approximation to β^{(m)}(n) for fixed m ≥ 2 and n ≥ (m + 1)^{2}. The case m = 1 is special, because of the greater differences between σ^{(m)}(n) and r^{(m)}(n) when m = 1. However, calculations show that β^{(1)}(n) is well-approximated by

β^{(1)}(n) ≈ ε_{1} 2^{n−1} ,  (39)

where ε_{1} = 3.48669886 . . ..

For our applications, the approximation

β^{(m)}(n) ≈ ε_{m} (m + 1)^{n−1} for m ≥ 1, n ≥ 1  (40)

(consistent with (36)–(39)) will be adequate, where ε_{m} is a constant on the order of 1.

4.4 Estimates for the records ρ^{(m)}(n)

We now apply (34) to estimate ρ^{(m)}(n). Except for (41), the formulas in this section are conjectural. Again using (35), we find that

ρ^{(m)}(n) = \frac{m(n + 1 + 2u) + β^{(m+1)}(n + 1)}{m + 1}  (41)

for 0 ≤ n ≤ (m + 2)^{2} − 1, where u = ⌊n/(m + 2)⌋. Eliminating β^{(m+1)}(n + 1) from (34) and (41) we obtain

ρ^{(m)}(n + 1) = (m + 2)ρ^{(m)}(n) + σ^{(m+1)}(n + 1) − m(n + 1 + 2u) .  (42)

In particular, for 0 ≤ n ≤ m + 1, u = 0 and so (41) gives

ρ^{(m)}(n) = \frac{(m + 2)^{n+1} + (n + 1)m(m + 1) − 1}{(m + 1)^{2}} ,  (43)

while for m + 2 ≤ n ≤ 2m + 3, u = 1 and

ρ^{(m)}(n) = \frac{(m + 2)^{n+1} + 2(m + 1)(m + 2)^{n−m−2} + (n + 3)m(m + 1) − 1}{(m + 1)^{2}} .  (44)

Equation (43) matches the smoothed values on or below the diagonal n = m + 1 in Table 5,

(44) matches the values in the “wedge” m + 2 ≤ n ≤ 2m + 3, and (41) matches the values in the whole region bounded by the “parabola” n ≤ (m + 2)^{2} − 1. Equation (44) is in fact a good estimate of ρ^{(m)}(n) for all m and n.

The greatest differences between the exact values π^{(m)}(n) and the smoothed values ρ^{(m)}(n) occur in the first row of Table 5. The ratio of terms π^{(m)}(n + 1)/π^{(m)}(n) in row m of that table rapidly approaches m + 2, and for fixed m we find that

π^{(m)}(n) ≈ λ_{m}(m + 2)^{n} ,  (45)

where approximate values of λ_{m} are

\begin{aligned}m & : & 1 & 2 & 3 & 4 & 5 & 6 & 7 & ⋯ \\ λ_{m} & : & .778 & .447 & .312 & .240 & .194 & .163 & .140 & ⋯ \end{aligned}

Curve-fitting suggests that

λ_{m} ≈ \frac{.956m + 2.11}{(m + 1)^{2}}

which we approximate by

λ_{m} ≈ \frac{m + 2}{(m + 1)^{2}} ,  (46)

leading to

π^{(m)}(n) ≈ \frac{(m + 2)^{n+1}}{(m + 1)^{2}}  (47)

for m fixed and n large.

Since the leading terms in (41), (43) and (44) agree with (47), we will take (47) as our approximation to both π^{(m)}(n) and ρ^{(m)}(n) for all m and n.

4.5 An estimate for τ^{(m)}(n)

From equations (16), (20) we have

τ^{(m)}(n + 1) = ∑_{i=1}^{n} σ^{(m)}(i), n ≥ 1 .  (48)

To simplify the analysis (we are only seeking a crude estimate in this section) we suppose we have reached the end of block B_{n}^{(m)} in A^{(m)}, where n = (m + 1)^{μ} + 1 for some μ ≥ 1. This block ends with the string T_{n}^{(m)} of length τ^{(m)}(n).

Of the (m + 1)^{μ} strings S_{i}^{(m)}, 1 ≤ i ≤ (m + 1)^{μ}, that appear in T_{n}^{(m)}, a fraction \frac{m}{m+1} have |i|_{m+1} = 0 and contribute π^{(m)}(0) to the sum; a fraction \frac{m}{(m+1)^{2}} have |i|_{m+1} = 1 and contribute π^{(m)}(1); and so on. Therefore, from (48),

τ^{(m)}((m + 1)^{μ} + 1) = (m + 1)^{μ} ∑_{i=0}^{μ−1} \frac{m}{(m + 1)^{i+1}} π^{(m)}(i) + π^{(m)}(μ) ,

where the last term accounts for the final glue string S_{n−1}^{(m)}. Using (47) this becomes

τ^{(m)}((m + 1)^{μ} + 1) ≈ \frac{m + 2}{m + 1} ((m + 2)^{μ} − m(m + 1)^{μ−1}) .  (49)

We summarize the discussion in the last two sections in the following:

Conjecture 4.3. After smoothing (cf. Conjecture 4.1), the sequence σ^{(m)} = σ^{(m)}(1), σ^{(m)}(2), … of the lengths of the glue strings in A^{(m)} is a ruler sequence given by (32), where the record values are given by (41) (exact, for n ≤ (m + 2)^{2} − 1) and (47) (approximate, for all m and n). Equation (49) gives an estimate for τ^{(m)}(n).

4.6 The first occurrence of t

We use the above estimates to determine where a number t ≥ 1 appears for the first time in A. We already know from Tables 1 and 2 that a 1 appears at position 1, a 2 at position 3, a 3 at position 9, and a 4 at position 220, so we may assume t ≥ 5.

For fixed t, let x(m) be the position where t appears for the first time in the sequence A^{(m)}, for 1 ≤ m ≤ t. We will successively estimate x(t), x(t−1), …, x(1), working backwards from

A^{(t)} = \underbrace{t, t, …, t}_{t+1 copies}, t + 1, …,

where t appears as the leading term, t + 1 appears for the first time at position t + 2, and t + 2 appears for the first time at position

\frac{(t + 1)^{t+2} + 2t − 1}{t} .  (50)

For example, 3 appears in A at position 9, 4 in A^{(2)} at position 42, and 5 in A^{(3)} at position 343. Thus x(t) = 1, x(t − 1) = t + 1, and

x(t − 2) = \frac{(t − 1)^{t} + 2t − 5}{t − 2} .  (51)

We first consider the case t = 5. Since x(3) = 343, a 5 appears in A^{(2)} for the first time at the end of block B_{i}^{(2)}, where i is such that τ^{(2)}(i) = 343. That is, i is determined (see (48) and Table 4) by the equation

τ^{(2)}(i) = \underbrace{1 + 1 + 3 + 1 + 1 + 3 + 1 + 1 + 9 + ⋯}_{i−1 terms} = 343 .

By direct calculation, i = 80, and again by direct calculation from (33), a 5 appears in A^{(2)} at position

x(2) = β^{(2)}(80) = 77709404388415370160829246932345692180 ,

which is 10^{37.9...}. So 5 appears in A = A^{(1)} at the end of block B_{i}^{(1)}, where i is such that τ^{(1)}(i) = x(2). Setting m = 1 in (49) we get

τ^{(1)}(2^{μ} + 1) = \frac{3}{2} · 3^{μ}(1 − \frac{1}{2}(\frac{2}{3})^{μ}) = x(2) ,

hence μ = 79.0 …, i = 2^{79.0...}. Setting m = 1, n = 2^{79.0...} in (39) we finally obtain

x(1) = β^{(1)}(2^{79.0...}) = ε_{1}2^{2^{79.0...}} = 10^{10^{23.3...}}

for the position of the first 5.

Consider now a general value of t ≥ 6. To find x(t − 3), we must solve (from (51))

τ^{(t−3)}(i) = \frac{(t − 1)^{t} + 2t − 5}{t − 2} .

Setting i = (t − 2)^{μ} + 1 and using (49) we get

\frac{t − 1}{t − 2} ((t − 1)^{μ} − (t − 3)(t − 2)^{μ−1}) = \frac{(t − 1)^{t} + 2t − 5}{t − 2} ,

hence μ ≈ t − 1, and so

x(t − 3) = β^{(3)}((t − 2)^{μ} + 1) = ε_{3}(t − 2)^{(t−2)^{t−1}} .

The ε_{3} may be ignored, since it can be absorbed into the tower of exponentials. The next iteration gives

x(t − 4) = (t − 3)^{(t−3)^{(t−2)^{t−1}}}

and eventually we obtain, for t ≥ 5,

x(1) = 2^{234^{·^{·^{·t−1}}}} ,  (52)

a tower of height t − 1. We formalize this as our final Conjecture 4.4. The number t ≥ 5 appears for the first time in the sequence A at about position (52).

Remark. The position of the first 5 can be estimated more accurately using the tabular construction of Section 4.2, thus avoiding the simplifying assumptions made in Section 4.5. This analysis predicts that the first 5 will appear at about position

ε_{1} × 2^{418090195952691922788353} = 10^{10^{23.09987...}} .

where ε_{1} is given in §4.3. We omit the details.

5 Comments and generalizations

5.1 The Finiteness Conjecture

The proof of Theorem 3.2 would have been simpler if we had known in advance that the glue strings S_{n}^{(m)} were finite. This would follow from the following:

Finiteness Conjecture. For integers m ≥ 2 and r ≥ 1, let x(1), x(2), …, x(r) be a string from ℙ_{m}^{+}. Let x(n + 1) = C(x(1), x(2), …, x(n)) for n ≥ r. Then for some n ≥ r + 1, x(n) < m.

In other words, there is no finite starting string from ℙ_{m}^{r} which extends under repeated application of the map C to an infinite sequence from ℙ_{m}^{∗}. Sooner or later a term less than m must appear.

Although this conjecture seems very plausible, we have not been able to find a proof. If one tries to construct a starting string which extends for a long time without dropping below m one quickly runs into difficulties. Let m_{1} and m_{2} be respectively the smallest and largest values in the starting string. Then no number outside the range [m_{1}, m_{2}] — or in fact any number not in the starting string — may appear in the resulting sequence, for such a number is immediately followed by a 1, terminating the sequence. So if the sequence is infinite it must be bounded.

As an experiment we considered all 2^{n} starting strings of length n ≤ 30 consisting just of 2’s and 3’s, and calculated the lengths of the resulting strings until just before the appearance of the first 1. The maximum and average lengths are shown in Table 9 below.

n Max.  Ave.
1  1 1
2  4 2.75
3  5 3.75
4  8 5.125
5  9 6.2187
6  14 7.5
7  15 8.5703
8  66 10.2734
9  68 11.3828
10  70 12.5293
11 123 13.6099
12 124 14.6658
13 125 15.6683
14 132 16.6957
15 133 17.7047
16 134 18.7168
17 135 19.7206
18 136 20.7278
19 138 21.7304
20 139 22.7341
21 140 23.7353
22 142 24.7372
23 143 25.7379
24 144 26.7388
25 145 27.7391
26 146 28.7396
27 147 29.7398
28 148 30.74
29 149 31.7401
30 150 32.7402

Table 9: Maximum and average length of string produced by any starting sequence of n 2’s and 3’s, stopping when first 1 is reached.

The average length seems to approach n + constant, but the maximum length is harder to understand, and it would be nice to have more data. Does the maximum length continue to grow linearly, or are there further jumps of ever-increasing size? We do not know.

Table 10 shows the starting strings of lengths 2, 4, 6, 8 and 11 (when there are jumps in the maximum length) and the strings of record lengths 4, 8, 14, 66 and 123 that they produce. These five starting strings are unique.

n = 2 Starting string 2 2 produces length 4:

2 2 2 3

n = 4 Starting string 2 3 2 3 produces length 8:

2 3 2 3 2 2 2 3

n = 6 Starting string 2 2 2 3 2 2 produces length 14:

2 2 2 3 2 2 2 3 2 2 2 3 3 2

n = 8 Starting string 2 3 2 2 2 3 2 3 produces length 66:

2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 3 3 2

n = 11 Starting string 2 2 3 2 3 2 2 2 3 2 2 produces length 123:

2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 2 3 2 2 2 3

Table 10: Starting strings of n 2’s and 3’s which extend under the map C for a record number of steps before reaching a 1. Each entry also shows the final string (until just before the first 1 is reached).

5.2 Curling number transforms of other sequences

It is interesting to apply the curling number transform to other sequences, particularly those for which the definition involves properties of substrings. For example, the binary Thue-Morse sequence

\begin{matrix}0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & … \end{matrix}

(A10060 in [8]) has the property that it contains no cubes UUU as substrings (see [2], [5], [6], [8] for further information). Its curling number transform, which naturally contains only 1’s and 2’s, is

\begin{matrix}1 & 1 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 2 \\ 1 & 2 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & … \end{matrix}

(A93914). We leave it to the interested reader to investigate the properties of this sequences and of the other new sequences mentioned below.

There are many examples of ternary sequences which contain no squares, and of course their curling number transforms are simply the all-ones sequence 1. However, the lexicographically earliest sequence from ℙ^{∗} whose transform is 1 is the ruler sequence r (A1511) mentioned in Section 4.4.

We give one further example. The Kolakoski sequence is a sequences of 1’s and 2’s defined by K(1) = 1, K(n) = length of n-th run:

\begin{matrix}1 & 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & … \end{matrix}

(A2 in [8]). This also contains no cubes. The transformed sequence is

\begin{matrix}1 & 1 & 1 & 2 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 1 \\ 1 & 2 & 2 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 2 & 2 & 1 & 2 & 1 & 1 & … \end{matrix}

(A93921).

5.3 Generalizations

In this final section we briefly mention a few of the possible generalizations of the sequence A.

(i) The recurrence (2) may be replaced by a(1) = 1, a(n + 1) = f(C(a(1), …, a(n))) for n ≥ 1, for any suitable function f. For example, f(x) = floor(x/2) produces

\begin{matrix}0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 0 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 2 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 2 & 0 & … \end{matrix}

(A91970), which presumably has an even slower rate of growth than A.

(ii) a(1) = a(2) = 1, a(n + 2) = C(a(1), …, a(n)) for n ≥ 1 produces

\begin{matrix}1 & 1 & 1 & 2 & 3 & 1 & 1 & 1 & 2 & 3 & 1 & 2 & 2 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 4 & 1 & 1 & 1 & … \end{matrix}

(A94006). This has the property that its curling number transform is the same sequence but shifted one place to the left.

(iii) A greedy version of A^{(2)}. Let g(1) = 2. For n ≥ 1, let k = C(g(1), …, g(n)). If k > 1, g(n + 1) = k (as in A^{(2)}), but if k = 1, choose g(n + 1) so that C(g(1), …, g(n + 1)) is maximized. If there is more than one choice for g(n + 1), pick the smallest. The resulting sequence (A94321) is:

\begin{matrix}2 & 2 & 2 & 3 & 3 & 2 & 2 & 2 & 3 & 3 & 2 & 2 & 2 & 3 & 2 & 2 \\ 2 & 3 & 2 & 2 & 2 & 3 & 3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & … \end{matrix}

(iv) A two-dimensional version of A. Define t(i, j), i ≥ 1, j ≥ 1, as follows: t(i, 1) = t(1, i) = a(i). For i, j ≥ 1, t(i + 1, j + 1) = max{k_{1}, k_{2}}, where k_{1} = C(t(i + 1, 1), t(i + 1, 2), …, t(i + 1, j)), k_{2} = C(t(1, j + 1), t(2, j + 1), …, t(i, j + 1)) — see Table 11 (A94781). The first two rows (or columns) give A and the third row (or column) is A^{(2)}.

\begin{matrix}1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 3 & 1 & 1 & 2 & 1 & 1 & … \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 3 & 1 & 1 & 2 & 1 & 1 & … \\ 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 3 & 2 & … \\ 1 & 1 & 3 & 1 & 1 & 3 & 3 & 2 & 1 & 1 & 2 & 1 & 1 & 2 & … \\ 1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 3 & 1 & 2 & 1 & 1 & 2 & … \\ 2 & 2 & 2 & 3 & 2 & 1 & 1 & 2 & 1 & 2 & 3 & 2 & 2 & 3 & … \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & … \end{matrix}

Table 11: A two-dimensional version of the sequence.

(v) J. Taylor [9] has suggested two broad generalizations of the original recurrence. Let ∼ be an equivalence relation on strings of integers of each fixed length. Write

a(1)a(2) ⋯ a(n) = XY_{1}Y_{2} ⋯ Y_{k} ,  (53)

where the Y_{i} are nonempty strings with Y_{1} ∼ Y_{2} ∼ ⋯ ∼ Y_{k} and k is maximal; then a(n + 1) = k. Choosing ∼ to be the identity relation gives A. Taylor has contributed several interesting generalizations of A to [8] obtained from other equivalence relations. For example, if two strings are equivalent if one is a permutation of the other, the resulting sequence is

\begin{matrix}1 & 1 & 2 & 1 & 1 & 2 & 2 & 2 & 3 & 1 & 1 & 2 & 1 & 1 & 2 & 2 \\ 2 & 3 & 2 & 2 & 2 & 3 & 2 & 2 & 2 & 3 & 3 & 2 & 2 & 4 & 1 & 1 & … \end{matrix}

(A91976), which agrees with A for the first 19 terms. But after

1 1 2 1 1 2 2 2 3 1 1 2 1 1 2 2 2 3 2

the next term is now 2, not 1, since we can take U = 1 1 2 1 1, Y_{1} = 2 2 2 3 1 1 2, Y_{2} = 1 1 2 2 2 3 2, where Y_{2} is a permutation of Y_{1}. (vii) More generally, Taylor suggests using a partial order ≺ on integer strings of all lengths (not just strings of the same length), and requiring the Y_{i} in (53) to be nonempty and satisfy Y_{1} ≺ Y_{2} ≺ ⋯ ≺ Y_{k} where k is maximal. For further examples of Taylor’s sequences the reader is referred to the entries A91975 and A92331–A92335 in [8].

Acknowledgements

We thank J. Taylor for telling us about his generalizations of the sequence.

References

[1] W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118–133.

[2] J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

[3] J. H. Conway, The weird and wonderful chemistry of audioactive decay, in T. M. Cover and Gopinath, eds., Open Problems in Communication and Computation, Springer-Verlag, NY, 1987, pp. 173–188.

[4] H. M. Friedman, Long finite sequences, J. Combin. Theory, Ser A, 95 (2001), 102–144.

[5] M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.

[6] A. Salomaa, Jewels of Formal Language Theory, Computer Science Press, Rockville, MD, 1981.

[7] M. Sharir and P. K. Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge Univ. Press, 1995.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/∼njas/sequences/, 1996–2006.

[9] J. Taylor, personal communication.

2000 Mathematics Subject Classification: Primary 11B37. Keywords: recurrence, Friedman sequence, Ackermann function.

(Concerned with sequences \underline{A000002}, \underline{A001511}, \underline{A010060}, \underline{A090822}, \underline{A091408}, \underline{A091409}, \underline{A091410}, \underline{A091411}, \underline{A091412}, \underline{A091413}, \underline{A091579}, \underline{A091586}, \underline{A091587}, \underline{A091588}, \underline{A091787}, \underline{A091799}, \underline{A091839}, \underline{A091970}, \underline{A091970}, \underline{A091975}, \underline{A091976}, \underline{A092331}, \underline{A092332}, \underline{A092333}, \underline{A092334}, \underline{A092335}, \underline{A093914}, \underline{A093921}, \underline{A093955}, \underline{A093956}, \underline{A093957}, \underline{A093958}, \underline{A094006}, \underline{A094321}, and \underline{A094781}.)

Received June 26 2004; revised versions received February 22 2006 and September 13 2006. Published in Journal of Integer Sequences, December 16 2006.

Return to Journal of Integer Sequences home page.