The Growth Rate of Gijswijt’s Sequence

Levi van de Pol Department of Mathematics Utrecht University P.O. Box 80010 3508 TA Utrecht The Netherlands

                      levipol@hotmail.com

Abstract Gijswijt’s sequence consists almost entirely of small positive integers. However, it is known that every positive integer eventually appears in the sequence. In this paper we determine its growth rate. Specifically, we prove that for n = 4, 5, 6, …, the number n occurs for the first time at position 2 ↑ (2 ↑ (3 ↑ (4 ↑ (5 ↑ ⋯ ↑ ((n − 2) ↑ α))))), where ↑ denotes exponentiation, and α ∈ (n − 2, n − 1) is a real number. Our result confirms the growth rate conjectured by van de Bult et al.

1 Introduction

To define Gijswijt’s sequence, we begin with the concept of a curling number, introduced by van de Bult, Gijswijt, Linderman, Sloane, and Wilks [3]. For a finite nonempty string S over an arbitrary alphabet, the curling number of S is the largest integer k such that

S = X \underbrace{Y Y ⋯ Y}_{k copies}

for some strings X and Y, where the string Y must be nonempty. The curling number of S is denoted by C(S). For example, we have C(112112223) = 1. We also have C(222322232223) = 3, since the string 2223 is repeated 3 times. Using this concept, van de Bult et al. constructed a recursive sequence A:

A(1) := 1, A(n + 1) := C(A(1), A(2), …, A(n)) for all n ≥ 1.

This sequence is now known as Gijswijt’s sequence, after Dion Gijswijt, who first defined it [3, p. 4]. The sequence starts with

A = 1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, 1, 2, 1, …

Gijswijt’s sequence can be found as sequence \underline{A090822} in the On-Line Encyclopedia of Integer Sequences (OEIS) [2]. This sequence consists almost entirely of small positive integers. The first time that a 4 occurs is at position 220, and the sequence continues with elements 1, 2, 3, and 4 for millions of entries. However, van de Bult et al. [3, p. 12] proved that all positive integers must occur at some point in Gijswijt’s sequence. After this, they used heuristic arguments to specify the approximate location of the first occurrence of a number n in the sequence [3, Section 4]. For n = 1, 2, 3, 4 this position is respectively 1, 3, 9, 220. These positions form sequence \underline{A091409} in the OEIS. Surprisingly, the first 5 occurs at about position 10^{1023} [3, p. 22]. The decimal (or binary) representation of this number would require zettabytes of storage.

The heuristic arguments by van de Bult et al. led up to a conjecture [3, Conjecture 4.4]. It states that for n ≥ 5, the first occurrence of n in Gijswijt’s sequence is about position

2^{234^{...}n−1} .  (1)

In this tower of exponents, the 2 occurs twice at the base, followed by the exponents 3, 4, …, n − 2, n − 1. From Expression (1) we see that Gijswijt’s sequence has a very slow growth rate.

The goal of this paper is to establish a precise version of the conjecture. We do this by providing explicit upper and lower bounds for the position of the first n in the sequence. Our main result is as follows:

Theorem 1. For all integers n ≥ 4, the first occurrence of n in Gijswijt’s sequence is at position

2^{234^{...}(n−2)α} ,

for a real number α ∈ (n − 2, n − 1) that depends on n.

Take, for example, the number n = 4. The first occurrence in Gijswijt’s sequence is at position 220 = 2^{22.96...}, so α = 2.96 … ∈ (2, 3). Now consider the number n = 6. It

follows from our theorem that the first 6 occurs between the positions 2^{2344} ≈ 10^{10^{10^{121}}}

and 2^{2345} ≈ 10^{1010489}. On the other hand, Theorem 1 is false for n = 3. Gijswijt’s sequence starts with 1, 1, 2, 1, 1, 2, 2, 2, 3 …, so the first 3 occurs at position 9 = 2^{3.1699...}. The exponent 3.1699 … falls outside the interval (1, 2).

This paper is devoted to the proof of Theorem 1. We do this as follows. In Section 2 we recall the ‘recursive structure’ that was found by van de Bult et al. [3, Section 2]. This structure makes Gijswijt’s sequence A = A^{(1)} the first member of a family of sequences A^{(m)}. These sequences are built from finite strings called blocks and glue strings. In Section 3 we show how the positions of first occurrence of n in the various A^{(m)} relate to each other. In Sections 4 and 5 we derive inequalities involving the lengths of the blocks and glue strings. In Section 6 we prove our main result by combining the inequalities into a single expression. Remark 21 explains a strategy to obtain sharper bounds.

Our Section 3 is based on the ideas in van de Bult et al. [3, Section 4.6]. At first glance, the arguments in our Section 4 have nothing to do with their heuristic derivation [3, Section 4]. However, our Section 4 is actually inspired by the ‘tabular construction’ and ‘smoothing’ techniques that they provided. In their Section 4, van de Bult et al. made three other conjectures about related inequalities and the recursive structure [3, Conjectures 4.1–4.3]. These conjectures served mainly as stepping stones towards Expression (1). It might be possible to derive the conjectures from our work, but we prefer to focus on the main result.

1.1 The curling number conjecture

Van de Bult et al. [3] posed another conjecture near the end of their paper [3, Finiteness Conjecture]. In a different paper, Chaffin et al. [1] called this conjecture the curling number conjecture.

Conjecture 2 (The curling number conjecture [1, Conjecture 1]). If one starts with any initial string of integers S, and extends it by repeatedly appending the curling number of the current string, the string will eventually reach 1.

The techniques in this paper are completely unsuitable for proving this conjecture. The curling number conjecture seems harder than the one regarding the growth rate of Gijswijt’s sequence. However, Chaffin et al. [1] made some progress. Among other things, they computationally verified the conjecture for all initial strings with lengths up to 48 that consist only of the digits 2 and 3.

1.2 Notation

We use the term string for a finite list e_{1}, e_{2}, …, e_{l} of positive integers and reserve the term sequence for infinite lists e_{1}, e_{2}, … of positive integers. The objects e_{1}, e_{2}, …, e_{l} are the elements of the string. The length of a string is the number of elements, including duplicates. The empty string ϵ has length 0. We usually omit the commas, so 1222 means 1, 2, 2, 2. We can concatenate strings S = s_{1} ⋯ s_{l} and T = t_{1} ⋯ t_{m} to obtain a new string W = ST = s_{1} ⋯ s_{l}t_{1} ⋯ t_{m}. Similarly, the concatenation W = ST is a sequence when S is a string and T is a sequence. In either case, the string S is a prefix of W and a proper prefix if T is not empty. When W = ST is a string, the string T is a suffix of W and a proper suffix if S is not empty. When W = USV is a string or sequence, the string S is a substring of W. We denote the kth element of S by S(k). Consider strings S_{1}, S_{2}, S_{3}, … such that S_{n} is a proper prefix of S_{n+1} for all n ≥ 1. We define the limit lim_{n→∞} S_{n} as the unique sequence S such that S_{n} is a prefix of S for all n ≥ 1.

For a string X and an integer k ≥ 1, we denote \underbrace{XX ⋯ X}_{k copies} by X^{k}. Now the curling

number of a string S is the largest integer c such that S can be written as XY^{c} with Y nonempty. Van de Bult et al. [3] only defined the curling number of a nonempty string; we additionally define C(ϵ) := 1. Throughout this paper, the expression (m + 1)^{k} can both denote the string (m + 1)^{k} = \underbrace{(m + 1)(m + 1) ⋯ (m + 1)}_{k copies} or the number (m + 1)^{k} =

\underbrace{(m + 1) · (m + 1) · . . . · (m + 1)}_{k copies}. The difference will be clear from the context. We always

use · for multiplication, and no symbol for concatenation.

2 The recursive structure

Van de Bult et al. defined a family of sequences that generalize Gijswijt’s sequence [3, Section 3]. For m ≥ 1, the mth order sequence A^{(m)} is given by

A^{(m)}(1) := m, A^{(m)}(n + 1) := max(m, C(A^{(m)}(1), A^{(m)}(2), …, A^{(m)}(n))) for all n ≥ 1.

Note that A^{(1)} = A. The sequences A^{(2)} and A^{(3)} start as follows:

A^{(2)} = 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, …
A^{(3)} = 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 3, 3, 3, 3, 4, 4, 3, …

These are sequences \underline{A091787} and \underline{A091799} in the OEIS [2]. Van de Bult et al. proved that each sequence A^{(m)}, for m ≥ 1, is built from finite strings B_{t}^{(m)} and S_{t}^{(m)}. The strings B_{t}^{(m)} are called blocks and the strings S_{t}^{(m)} are called glue strings. They satisfy the following relations for t, m ≥ 1:

B_{1}^{(m)} = m
B_{t+1}^{(m)} = \underbrace{B_{t}^{(m)}B_{t}^{(m)} ⋯ B_{t}^{(m)}}_{m+1 copies} S_{t}^{(m)}

A^{(m)} = lim_{t→∞} B_{t}^{(m)}
A^{(m+1)} = S_{1}^{(m)}S_{2}^{(m)}S_{3}^{(m)} ⋯

The limit in the third line means that every block B_{t}^{(m)} is a prefix of A^{(m)}. Therefore we can obtain the sequence A^{(m)} by starting with B_{1}^{(m)}, and then repeatedly applying the second equation. In each iteration, we copy the current block B_{t}^{(m)} for m + 1 times, and then add the glue string S_{t}^{(m)} to find B_{t+1}^{(m)}. Surprisingly, the glue strings used for constructing A^{(m)} can be combined to form the sequence A^{(m+1)}; this is the fourth equation. Note that the blocks B_{t}^{(m)} contain only elements m and higher, while the glue strings S_{t}^{(m)} contain only elements m + 1 and higher.

A few examples are in order. Consider the sequence A^{(2)}. The first prefix blocks are B_{1}^{(2)} = 2, B_{2}^{(2)} = 2223, B_{3}^{(2)} = (2223)^{3}3, B_{4}^{(2)} = ((2223)^{3}3)^{3}334. The associated glue strings are S_{1}^{(2)} = 3, S_{2}^{(2)} = 3, S_{3}^{(2)} = 334. When we concatenate these glue strings we get 33334, which is the prefix B_{2}^{(3)} of A^{(3)}. In turn, the block B_{2}^{(3)} equals (B_{1}^{(3)})^{4}S_{1}^{(3)}. We have B_{1}^{(3)} = 3 and S_{1}^{(3)} = 4. The string S_{1}^{(3)} = 4 is the prefix B_{1}^{(4)} of A^{(4)}.

This structure implies that every element of A^{(m+1)} also occurs in A^{(m)}. Indeed, if x is in A^{(m+1)}, then there is a t such that x is in S_{t}^{(m)}. Therefore, the element x occurs in B_{t+1}^{(m)}, and hence in A^{(m)}. Now from induction we see that for n ≥ m, every element of A^{(n)} occurs in A^{(m)}. Since A^{(n)} starts with n, we conclude that A^{(m)} contains all integers that are at least m. Like Gijswijt’s sequence, the sequences A^{(m)} for m ≥ 2 are also slow-growing; see Remark 22.

Additionally, van de Bult et al. [3] defined strings T_{t}^{(m)} for t, m ≥ 1:

T_{t}^{(m)} := S_{1}^{(m)}S_{2}^{(m)} ⋯ S_{t−1}^{(m)}.

Now it follows that

A^{(m+1)} = lim_{t→∞} T_{t}^{(m)}.

Since T_{t}^{(m)} is a prefix of A^{(m+1)} for all m, t ≥ 1, the strings T_{t}^{(m)} consist of elements m + 1 and higher. Here is a short table for reference:

\begin{matrix}B_{1}^{(m)} & B_{2}^{(m)} & S_{1}^{(m)} & T_{1}^{(m)} & T_{2}^{(m)} \\ m & m^{m+1}(m + 1) & m + 1 & ϵ & m + 1 \end{matrix}

Table 1: Blocks and glue strings for small t and general m.

The strings B_{t}^{(m)} and S_{t}^{(m)} are always nonempty. However, the strings T_{1}^{(m)} are empty for all m. The lengths of

B_{t}^{(m)}, S_{t}^{(m)}, T_{t}^{(m)}

are denoted by respectively

β^{(m)}(t), σ^{(m)}(t), τ^{(m)}(t).

For all m and t, the string B_{t}^{(m)} is a proper prefix of B_{t+1}^{(m)} and the string T_{t}^{(m)} is a proper prefix of T_{t+1}^{(m)}. Therefore the functions β^{(m)}(t) and τ^{(m)}(t) are strictly increasing in t. This is not true for σ^{(m)}(t).

We often use the following property of curling numbers:

Lemma 3. If S is a string with suffix T, then C(S) ≥ C(T).

Proof. Let c := C(T). Then T has a suffix Y^{c} with Y nonempty. It follows that S has suffix Y^{c} as well, so C(S) ≥ c = C(T).

We can now start our derivation of Theorem 1. As a first step we prove three lemmas about the recursive structure.

Lemma 4. For all m ≥ 1 and t ≥ 2, the string mT_{t}^{(m)} is a suffix of B_{t}^{(m)}. This is the only occurrence of T_{t}^{(m)} as a substring of B_{t}^{(m)}.

Proof. We prove the first statement by induction on t. For t = 2, the string mT_{2}^{(m)} = m(m + 1) is a suffix of B_{2}^{(m)} = m^{m+1}(m + 1).

Now suppose that the first statement is true for t = k. Then we use that

B_{k+1}^{(m)} = (B_{k}^{(m)})^{m+1}S_{k}^{(m)}.

By the induction hypothesis, the string B_{k+1}^{(m)} has suffix mT_{k}^{(m)}S_{k}^{(m)}. The suffix equals mT_{k+1}^{(m)} by definition of T_{k+1}^{(m)}. This completes the induction step.

The second statement is van de Bult et al. [3, Lemma 3.2b].

Lemma 5. For all m ≥ 1, the strings T_{t}^{(m)} are exactly the prefixes of A^{(m+1)} with curling number at most m.

Proof. The string T_{1}^{(m)} = ϵ is a prefix of A^{(m+1)} with curling number 1.

For t ≥ 2, the block B_{t+1}^{(m)} is a prefix of A^{(m)}. This block equals (B_{t}^{(m)})^{m+1}S_{t}^{(m)}, so since B_{t}^{(m)}(1) = m, the string B_{t}^{(m)}m is also a prefix of A^{(m)}. Now from the definition of A^{(m)} we obtain that max(m, C(B_{t}^{(m)})) = m, so C(B_{t}^{(m)}) ≤ m. We know by Lemma 4 that T_{t}^{(m)} is a suffix of B_{t}^{(m)}, so Lemma 3 tells us that C(T_{t}^{(m)}) ≤ C(B_{t}^{(m)}) ≤ m.

Conversely, let P be a nonempty prefix of A^{(m+1)} with curling number at most m. Then we can write P = T_{t}^{(m)}Q for some t ≥ 2 and a proper prefix Q of S_{t}^{(m)}. We have S_{t}^{(m)} = QR for a nonempty string R. All elements of R are at least m + 1, in particular the first element R(1). Now the string

(B_{t}^{(m)})^{m+1}QR(1)

is a prefix of B_{t+1}^{(m)}, so it is also a prefix of A^{(m)}. Therefore max(m, C((B_{t}^{(m)})^{m+1}Q)) = R(1) ≥ m + 1, so C((B_{t}^{(m)})^{m+1}Q) ≥ m + 1. Hence the string (B_{t}^{(m)})^{m+1}Q has a nonempty suffix X^{m+1}. By the first part of Lemma 4, the string (B_{t}^{(m)})^{m+1}Q also has suffix mT_{t}^{(m)}Q. Since C(T_{t}^{(m)}Q) = C(P) ≤ m, the string mT_{t}^{(m)}Q must be a suffix of X^{m+1}. Therefore m ∈ X^{m+1}, so m ∈ X. Now it follows that mT_{t}^{(m)}Q is a suffix of X. Therefore T_{t}^{(m)}Q occurs as a substring of (B_{t}^{(m)})^{m+1}. But T_{t}^{(m)}Q contains only elements that are at least m+1, while B_{t}^{(m)}(1) = m. So T_{t}^{(m)}Q is a substring of B_{t}^{(m)}. It follows by the second part of Lemma 4 that the substring T_{t}^{(m)} must occur at the end of B_{t}^{(m)}, so Q is empty. We conclude that P is of the form T_{t}^{(m)} with t ≥ 2.

Lemma 6. For all m ≥ 1 and t ≥ 2, the elements m in B_{t}^{(m)} occur in groups of m + 1 consecutive times m. These groups are always followed by an element m + 1.

Proof. We use induction on t. For t = 2 we have B_{2}^{(m)} = m^{m+1}(m + 1). This is exactly one group of m + 1 consecutive m’s, followed by exactly one element m + 1. Now suppose that the statement holds for t = k. We know that

B_{k+1}^{(m)} = (B_{k}^{(m)})^{m+1}S_{k}^{(m)}.

Each copy of B_{k}^{(m)} contains m’s in groups of m + 1 times m followed by an element m + 1 by the induction hypothesis. The string S_{k}^{(m)} contains no elements m. This finishes the induction step.

3 The function t(m, n)

We now turn our attention to the first occurrence of n in the sequence A^{(m)}, where n ≥ m. We show in Lemma 7 that the first n in A^{(m)} occurs at the end of a block B_{t}^{(m)}. The question is then: what is the value of t? We denote this value by t(m, n).

Lemma 7. For all integers m, n with n ≥ m ≥ 1, the first occurrence of n in A^{(m)} is as the last element of a prefix block B_{t}^{(m)} for some t ≥ 1.

Proof. For n = m, the number m occurs at the beginning of A^{(m)}. This is also at the end of B_{1}^{(m)} = m. Now suppose that n > m. Let t be minimal such that n is in B_{t}^{(m)}. Since n is not an element of B_{t−1}^{(m)}, the first n in A^{(m)} must be in the glue string S_{t−1}^{(m)}. Let B be the prefix of A^{(m)}, ending at the first n. Now (B_{t−1}^{(m)})^{m+1} is a proper prefix of B, and B is a prefix of B_{t}^{(m)}. Since n appears at the end of B and nowhere else in B, we have C(B) = 1. Now by definition of A^{(m)}, the prefix B of A^{(m)} is followed by m. Since m ∉ S_{t−1}^{(m)}, it follows that B = B_{t}^{(m)}. We conclude that the first n in A^{(m)} is the last element of B_{t}^{(m)}.

Hence we can make the following definition:

Definition 8. For all integers m, n with n ≥ m ≥ 1, define t(m, n) as the integer such that the first n in A^{(m)} occurs at the end of prefix block B_{t(m,n)}^{(m)}.

Van de Bult et al. [3, p. 22] deduced that the first occurrence of 5 in A^{(2)} is at the end of the block B_{80}^{(2)}. Therefore it occurs at position β^{(2)}(80). In our new terminology we obtain t(2, 5) = 80. In general, the first occurrence of n in A^{(m)} is at position β^{(m)}(t(m, n)). The values of t(1, n) are given in sequence \underline{A357064} of the OEIS [2].

The function t(m, n) is not only related to the blocks B_{t}^{(m)}, but also to the strings T_{t}^{(m)}:

Lemma 9. For n ≥ m + 1 we have the relation T_{t(m,n)}^{(m)} = B_{t(m+1,n)}^{(m+1)}.

Proof. By Lemma 4, the string T_{t(m,n)}^{(m)} is a suffix of B_{t(m,n)}^{(m)}. It follows by definition of t(m, n)

that the last element of T_{t(m,n)}^{(m)} is n, and that T_{t(m,n)}^{(m)} has no other elements n. Also, the string

T_{t(m,n)}^{(m)} is a prefix of A^{(m+1)}. Therefore the first occurrence of n in A^{(m+1)} is both at the end

of T_{t(m,n)}^{(m)} and at the end of B_{t(m+1,n)}^{(m+1)}; hence the two strings are equal.

Let us consider a few examples.

Example 10. For all m ≥ 1, we have the following:

• t(m, m) = 1 since B_{1}^{(m)} = m.

• t(m, m + 1) = 2 since B_{2}^{(m)} = m^{m+1}(m + 1).

• For n = m + 2, we need the values σ^{(m)}(x) = 1 for x = 1, 2, …, m and σ^{(m)}(m + 1) = 3 by van de Bult et al. [3, Equation 35]. Summing these values, we obtain τ^{(m)}(m + 2) = m + 3. Now T_{m+2}^{(m)} consists of the first m + 3 elements of A^{(m+1)}. It follows that T_{m+2}^{(m)} = (m + 1)^{m+2}(m + 2) = B_{2}^{(m+1)} = B_{t(m+1,m+2)}^{(m+1)}. It follows from Lemma 9 that t(m, m + 2) = m + 2.

Lemma 9 tells us that T_{t(m,n)}^{(m)} = B_{t(m+1,n)}^{(m+1)}. Therefore their lengths are equal:

τ^{(m)}(t(m, n)) = β^{(m+1)}(t(m + 1, n)).  (2)

In Section 4 we prove inequalities between values of the functions τ^{(m)} and β^{(m+1)}. From this we deduce bounds for t(m, n) in terms of t(m + 1, n). We can then combine this for various values of m, to obtain bounds for t(1, n) in terms of t(n − 2, n), which equals n by Example 10. Since the first occurrence of n in Gijswijt’s sequence is at position β^{(1)}(t(1, n)), it remains to bound β^{(1)}(t) in terms of t. We do that in Section 5.

4 Linking β^{(m+1)} and τ^{(m)}

In this section we bound the value of β^{(m+1)}(u) by τ^{(m)}(t) for certain values of t and u. We do this with a series of lemmas that leads up to the inequalities in Lemma 17. Using these inequalities we bound t(m, n) in terms of t(m + 1, n). The result can be found in Proposition 19.

Our strategy is as follows. Fix u, m ≥ 1. We know that every string T_{t}^{(m)} is a prefix of A^{(m+1)}. The string B_{u}^{(m+1)} is also a prefix of A^{(m+1)}. We prove lower and upper bounds for the number of proper prefixes of B_{u}^{(m+1)} that are of the form T_{t}^{(m)}. If there are at least L such proper prefixes, then it follows that β^{(m+1)}(u) ≥ τ^{(m)}(L). If there are at most U such proper prefixes, then we get β^{(m+1)}(u) ≤ τ^{(m)}(U + 1). In Lemma 17 we prove this with L = m · (m + 1)^{u−2} and U = (m + 1)^{u−1}.

In Lemmas 11–13 we analyze the curling numbers of proper prefixes of B_{u}^{(m+1)}, as this determines whether a given prefix can be written as T_{t}^{(m)} via Lemma 5. We combine these results in Lemma 16. This lemma proves that certain proper prefixes of B_{u}^{(m+1)} are of the form T_{t}^{(m)}, and gives restrictions on which proper prefixes can be of the form T_{t}^{(m)}. This gives us lower and upper bounds for the amount of proper prefixes of the form T_{t}^{(m)}, which is exactly what we need.

Recall from Lemma 5 that the strings T_{t}^{(m)} are exactly the prefixes of A^{(m+1)}, and hence of some B_{u}^{(m+1)}, that have curling number at most m. Before investigating these strings further, we study the prefixes of B_{u}^{(m+1)} with curling number at most m + 1. The following lemma gives a characterization of those strings.

Lemma 11. For m, u ≥ 1, the proper prefixes P of B_{u}^{(m+1)} with C(P) ≤ m + 1 are exactly the strings of the form

(B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{2}^{(m+1)})^{a_{2}}(B_{1}^{(m+1)})^{a_{1}}  (3)

with a_{1}, a_{2}, …, a_{u−1} ∈ {0, 1, …, m + 1}.

Proof. By definition of A^{(m+1)}, the prefixes with curling number at most m + 1 are the prefixes that are followed by an element m + 1. Every string B_{u}^{(m+1)} is a prefix of A^{(m+1)}, so the same is true for all proper prefixes of B_{u}^{(m+1)}. We prove by induction on u that these strings have the desired form. For u = 1, the string B_{1}^{(m+1)} = (m + 1) has only one proper prefix ϵ, which is followed by m + 1. This corresponds to Expression (3) since there are no numbers between 1 and u − 1 for u = 1.

Now suppose that the statement holds for u = k. Then we use that

B_{k+1}^{(m+1)} = (B_{k}^{(m+1)})^{m+2}S_{k}^{(m+1)}.

The string B_{k}^{(m+1)} starts with m + 1 while S_{k}^{(m+1)} contains no elements m + 1. Therefore the proper prefixes P of B_{k+1}^{(m+1)} that are followed by m + 1 are of the form

P = (B_{k}^{(m+1)})^{a}P′,

where 0 ≤ a ≤ m + 1 and P′ is a proper prefix of B_{k}^{(m+1)} that is followed by an element m + 1. By the induction hypothesis, the string P′ is of the form

(B_{k−1}^{(m+1)})^{a_{k−1}} ⋯ (B_{2}^{(m+1)})^{a_{2}}(B_{1}^{(m+1)})^{a_{1}}.

Concatenating this to (B_{k}^{(m+1)})^{a} completes the induction step.

To find whether a string (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} can be written as T_{t}^{(m)} for some t, we need to know whether its curling number is at most m, or equal to m + 1. For a large class of strings, we can easily prove that this curling number is exactly m + 1:

Lemma 12. Let m, u ≥ 1, and consider a prefix P := (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} of B_{u}^{(m+1)}, for a_{1}, …, a_{u−1} ∈ {0, 1, …, m+1}. Suppose that a_{i} = m+1 for some i. Then C(P) = m+1.

Proof. By Lemma 11, the string Q := (B_{i−1}^{(m+1)})^{a_{i−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} is a prefix of B_{i}^{(m+1)}. Therefore we can write B_{i}^{(m+1)} = QR. The string (B_{i}^{(m+1)})^{a_{i}}Q is a suffix of P, and (B_{i}^{(m+1)})^{a_{i}}Q is equal to (QR)^{a_{i}}Q = Q(RQ)^{a_{i}} = Q(RQ)^{m+1}. Therefore, we have C(P) ≥ m + 1.

By Lemma 11, this curling number is also at most m + 1. Therefore the curling number is exactly m + 1.

It follows from Lemmas 5 and 12 that all strings (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} where at least one of a_{1}, …, a_{u−1} is equal to m + 1, are not of the form T_{t}^{(m)}. The remaining strings that we have to consider are the strings (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} with a_{i} ∈ {0, 1, …, m} for all i. In the following lemma, we establish that under the condition a_{1} ≠ 0, the curling number of such strings is at most m.

Lemma 13. For m ≥ 1 and u ≥ 2, let

P = (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}}

be a prefix of B_{u}^{(m+1)} with a_{1}, …, a_{u−1} ∈ {0, 1, …, m} and a_{1} ≠ 0. Then we have C(P) ≤ m.

Proof. We prove this by contradiction, so suppose that P has a nonempty suffix of the form X^{m+1}. We can then write

P = (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} = QX^{m+1}.

Since a_{1} ≠ 0, the last element of P is m + 1. Therefore m + 1 is also the last element of X. We now prove a claim about the first elements of X.

Claim 14. The string X has prefix (m + 1)^{k}(m + 2) for some k > 0.

Proof. Since a_{1} ≤ m, the curling number of (B_{1}^{(m+1)})^{a_{1}} = (m + 1)^{a_{1}} is smaller than m + 1. We see that X^{m+1} has to be longer than (m + 1)^{a_{1}} (that is, it has more elements). It follows from Lemma 4 that all strings B_{i}^{(m+1)} with i ≥ 2 end with an element larger than m + 1. Hence X^{m+1} has a suffix l(m+1)^{a_{1}} for some l > m+1. This can only happen when l(m+1)^{a_{1}} is a suffix of X itself. Now P looks like this:

P = (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} = Q \underbrace{… l(m + 1)^{a_{1}}}_{first X} \underbrace{… l(m + 1)^{a_{1}}}_{second X} ⋯ \underbrace{… l(m + 1)^{a_{1}}}_{last X}

By Lemma 6, applied to B_{u}^{(m+1)}, the elements m + 1 in P occur in groups of m + 2 times m+1, followed by an element m+2. Since we cut off the string B_{u}^{(m+1)} at the end of P, there is a possible exception to this at the end of P. When we now consider that the first copy of X in X^{m+1} has suffix l(m + 1)^{a_{1}}, we deduce that the second copy of X (and hence all of them) has prefix (m+1)^{m+2−a_{1}}(m+2). From a_{1} ≤ m it follows that k := m+2−a_{1} > 0.

Next we prove that the first element of X is larger than m + 1, which contradicts the previous claim.

Claim 15. The first element of X is larger than m + 1.

Proof. Define i as the largest integer such that X^{m+1} contains T_{i}^{(m+1)} as a substring. We saw in Claim 14 that X^{m+1} contains an element m + 2 = T_{2}^{(m+1)}. Therefore i ≥ 2. Since X ends with m + 1 and T_{i}^{(m+1)} contains no element m + 1, the string T_{i}^{(m+1)} has to be a substring of X. Therefore X^{m+1} contains at least m + 1 disjoint copies of T_{i}^{(m+1)}.

By Lemma 11, the string P_{i−1} := (B_{i−1}^{(m+1)})^{a_{i−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} is a proper prefix of B_{i}^{(m+1)}. It follows from Lemma 4 that P_{i−1} does not have T_{i}^{(m+1)} as a substring. Again using Lemma 4, the string P_{i} := (B_{i}^{(m+1)})^{a_{i}} ⋯ (B_{1}^{(m+1)})^{a_{1}} contains exactly a_{i} copies of T_{i}^{(m+1)}. Now since a_{i} ≤ m, the string X^{m+1} contains more copies of T_{i}^{(m+1)} than P_{i}. Both X^{m+1} and P_{i} are suffixes of P. Therefore P_{i} is a proper suffix of X^{m+1}.

Let j be the smallest integer larger than i such that a_{j} ≠ 0. Then B_{j}^{(m+1)}P_{i} is a suffix of P. The string B_{j}^{(m+1)} has suffix T_{j}^{(m+1)} by Lemma 4, but X^{m+1} cannot contain T_{j}^{(m+1)} as a substring by definition of i. So X^{m+1} is a proper suffix of T_{j}^{(m+1)}P_{i}. Remembering that P_{i} is a proper suffix of X^{m+1}, it follows that the first element of X^{m+1} lies inside T_{j}^{(m+1)}. Hence this element is larger than m + 1.

Since the two claims contradict each other, the lemma must be true.

Combining the above lemmas, we conclude the following about the strings T_{t}^{(m)}:

Lemma 16. Let m ≥ 1 and u ≥ 2.

(a) For each proper prefix T_{t}^{(m)} of B_{u}^{(m+1)}, there are a_{1}, …, a_{u−1} ∈ {0, 1, …, m} such that T_{t}^{(m)} = (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}}.

(b) For all integers a_{1}, …, a_{u−1} ∈ {0, 1, …, m} with a_{1} ≠ 0, there is a proper prefix T_{t}^{(m)} of B_{u}^{(m+1)} such that (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} = T_{t}^{(m)}.

Proof.

(a) By Lemma 5, the string T_{t}^{(m)} has curling number at most m. Now it follows from Lemma 11 that T_{t}^{(m)} can be written as (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} with a_{1}, …, a_{u−1} ∈ {0, …, m + 1}. By Lemma 12, all these exponents are at most m.

(b) Consider a string (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} with m ≥ 1, a_{1} ≠ 0, and a_{1}, …, a_{u−1} ∈ {0, …, m}. By Lemma 11, this string is a proper prefix of B_{u}^{(m+1)}, and hence of A^{(m+1)}. By Lemma 13, the string has curling number at most m. Now it follows from Lemma 5 that (B_{u−1}^{(m+1)})^{a_{u−1}} ⋯ (B_{1}^{(m+1)})^{a_{1}} is equal to T_{t}^{(m)} for some t.

We can now deduce inequalities between values of β^{(m+1)} and τ^{(m)}. All further estimates are based on the following lemma.

Lemma 17. For all m ≥ 1 and u ≥ 2 we have

τ^{(m)}(m · (m + 1)^{u−2}) ≤ β^{(m+1)}(u) ≤ τ^{(m)}((m + 1)^{u−1} + 1).

When u = m + 3, the second inequality is strict.

Proof. By Lemma 16 (b), the string B_{u}^{(m+1)} has at least m · (m + 1)^{u−2} proper prefixes of the form T_{t}^{(m)}: there is one prefix for every combination of exponents a_{1}, …, a_{u−1} ∈ {0, …, m} with a_{1} ≠ 0. Therefore T_{m·(m+1)^{u−2}}^{(m)} is a prefix of B_{u}^{(m+1)}. This proves the first inequality.

Lemma 16 (a) tells us that the string B_{u}^{(m+1)} has at most (m + 1)^{u−1} proper prefixes of the form T_{t}^{(m)}. Therefore the string T_{(m+1)^{u−1}+1}^{(m)} cannot be a proper prefix of B_{u}^{(m+1)}. Now B_{u}^{(m+1)} must be a prefix of T_{(m+1)^{u−1}+1}^{(m)}. This proves the second inequality.

In case that u = m + 3, consider the (m + 1)^{u−1} proper prefixes from the previous paragraph. One of them is B_{m+2}^{(m+1)}. This string has suffix T_{m+2}^{(m+1)}. From Lemma 5 it follows that T_{m+2}^{(m+1)} = (m + 2)^{m+1}. Now T_{m+2}^{(m+1)} has curling number m + 1, so B_{m+2}^{(m+1)} has curling number at least m + 1. It follows by Lemma 5 that B_{m+2}^{(m+1)} cannot be of the form T_{t}^{(m)}. There are then only (m + 1)^{u−1} − 1 proper prefixes left, so the second inequality is strict.

From these estimates we deduce two propositions that we use in further sections:

Proposition 18. For all m ≥ 1 and t ≥ 2 we have

β^{(m+1)}(⌈log_{m+1}(t)⌉) ≤ τ^{(m)}(t) ≤ β^{(m+1)}(⌈log_{m+1}(t)⌉ + 2).

Proof. Since τ^{(m)} is an increasing function, we have

τ^{(m)}(t) ≥ τ^{(m)}((m + 1)^{⌈log_{m+1}(t)⌉−1} + 1).

Suppose that ⌈log_{m+1}(t)⌉ = 1. Then

τ^{(m)}((m + 1)^{⌈log_{m+1}(t)⌉−1} + 1) = τ^{(m)}(2) = 1 = β^{(m+1)}(1) = β^{(m+1)}(⌈log_{m+1}(t)⌉).

Now suppose that ⌈log_{m+1}(t)⌉ ≥ 2. Then we apply Lemma 17 with u = ⌈log_{m+1}(t)⌉. It follows that τ^{(m)}((m + 1)^{⌈log_{m+1}(t)⌉−1} + 1) ≥ β^{(m+1)}(⌈log_{m+1}(t)⌉). In both cases we obtain that τ^{(m)}(t) ≥ β^{(m+1)}(⌈log_{m+1}(t)⌉).

On the other hand we have

τ^{(m)}(t) ≤ τ^{(m)}(m · (m + 1)^{⌈log_{m+1}(t)⌉}).

By Lemma 17 this is at most β^{(m+1)}(⌈log_{m+1}(t)⌉ + 2).

Proposition 19. For all m ≥ 1 and n ≥ m + 3, we have

m · (m + 1)^{t(m+1,n)−2} ≤ t(m, n) ≤ (m + 1)^{t(m+1,n)−1} + 1.

The second inequality is strict when n = m + 3.

Proof. We apply Lemma 17 to u = t(m + 1, n) with n ≥ m + 3 and m ≥ 1 to see that

τ^{(m)}(m · (m + 1)^{t(m+1,n)−2}) ≤ β^{(m+1)}(t(m + 1, n)) ≤ τ^{(m)}((m + 1)^{t(m+1,n)−1} + 1).

When n = m + 3, we have u = t(m + 1, m + 3) = m + 3 by Example 10, so then the second inequality is strict. Now using Equation (2), we get

τ^{(m)}(m · (m + 1)^{t(m+1,n)−2}) ≤ τ^{(m)}(t(m, n)) ≤ τ^{(m)}((m + 1)^{t(m+1,n)−1} + 1).

Since τ^{(m)} is a strictly increasing function, the same inequalities hold for its arguments.

In this last proposition we connect t(m, n) and t(m + 1, n). The exponential nature of this connection explains the tower of exponents in Theorem 1.

5 Bounds for β^{(m)}(u)

In this section we give an upper bound for β^{(m)}(u), which is the last building block for our main theorem. Van de Bult et al. [3, p. 19] observed from calculations that there are real constants ε_{m} for m ≥ 1 such that for each m, we have β^{(m)}(u) ≈ ε_{m} · (m + 1)^{u−1} as u → ∞. We prove that this is indeed the case.

Intuitively, this can be explained as follows. Since B_{u+1}^{(m)} = (B_{u}^{(m)})^{m+1}S_{u}^{(m)}, we have

β^{(m)}(u + 1) = (m + 1) · β^{(m)}(u) + σ^{(m)}(u).

If σ^{(m)}(u) is relatively small, then it follows that β^{(m)}(u + 1) is approximately equal to (m + 1) · β^{(m)}(u). Iterating this we obtain that β^{(m)}(u) ≈ (m + 1)^{u−1}, and the contributions from the σ^{(m)}(u) give us the extra factor ε_{m}.

As a first step we can use the above equality to deduce that (m+1)·β^{(m)}(u) ≤ β^{(m)}(u+1), so β^{(m)}(u) ≤ \frac{β^{(m)}(u+1)}{m+1}. With induction we obtain the following:

β^{(m)}(t) ≤ \frac{β^{(m)}(u)}{(m + 1)^{u−t}} for all t, u with 1 ≤ t ≤ u.  (4)

Then we see that

\frac{β^{(m)}(t)}{(m + 1)^{t−1}} ≤ \frac{β^{(m)}(u)}{(m + 1)^{u−1}} for all t, u with 1 ≤ t ≤ u.  (5)

Hence, if we can prove that \frac{β^{(m)}(u)}{(m+1)^{u−1}} is bounded as u → ∞, then it follows that \frac{β^{(m)}(u)}{(m+1)^{u−1}} converges for u → ∞. The limit value is then equal to the constant ε_{m}.

We use the inequalities from the previous section to obtain an upper bound for σ^{(m)}: for all m, t ≥ 1 we have

σ^{(m)}(t) ≤ τ^{(m)}(t + 1)
≤ β^{(m+1)}(⌈log_{m+1}(t + 1)⌉ + 2)  (by Proposition 18),

hence

σ^{(m)}(t) ≤ β^{(m+1)}(⌈log_{m+1}(t + 1)⌉ + 2).  (6)

We are now ready to prove the upper bound for β^{(m)}(u).

Lemma 20. Consider the numbers M_{7}, M_{8}, ⋯ ∈ ℝ defined by M_{7} := 4 and M_{k+1} := M_{k} · (1 + 9 · (k + 1)^{1.59}/2^{k}) for k ≥ 7. Then

\frac{β^{(m)}(u)}{(m + 1)^{u−1}} < M_{u} for all m ≥ 1, u ≥ 7.

Proof. We prove by induction on u that the lemma holds for all u ≥ 7. First consider u = 7. From the values of β^{(m)}(t) that van de Bult et al. calculated [3, Table 6], we see that β^{(m)}(7) < 4 · (m + 1)^{6} for m = 1, 2, 3, 4, 5. For m ≥ 6, we know from van de Bult et al. [3, Lemma 4.1, p. 19] that β^{(m)}(7) = \frac{(m+1)^{7}−1}{m} < 4 · (m + 1)^{6}. So the lemma holds for u = 7.

Now suppose that for a fixed k ≥ 7, we have β^{(m)}(k) < M_{k} · (m + 1)^{k−1} for all m ≥ 1. Then we have

\frac{β^{(m)}(k + 1)}{(m + 1)^{k}} = \frac{(m + 1) · β^{(m)}(k)}{(m + 1)^{k}} + \frac{σ^{(m)}(k)}{(m + 1)^{k}}
≤ \frac{β^{(m)}(k)}{(m + 1)^{k−1}} + \frac{β^{(m+1)}(⌈log_{m+1}(k + 1)⌉ + 2)}{(m + 1)^{k}} (by Inequality (6))
< M_{k} + \frac{β^{(m+1)}(⌈log_{m+1}(k + 1)⌉ + 2)}{(m + 1)^{k}}  (induction hypothesis)
≤ M_{k} + \frac{β^{(m+1)}(k)}{(m + 2)^{k−⌈log_{m+1}(k+1)⌉−2} · (m + 1)^{k}}  (by Inequality (4); see below)
< M_{k} + \frac{M_{k} · (m + 2)^{⌈log_{m+1}(k+1)⌉+1}}{(m + 1)^{k}}  (induction hypothesis)
≤ M_{k} · (1 + \frac{(m + 1)^{log_{2}(3)·(⌈log_{m+1}(k+1)⌉+1)}}{(m + 1)^{k}} ) (see below)
≤ M_{k} · (1 + (m + 1)^{log_{2}(3)·(⌈log_{2}(k+1)⌉+1)−k})
≤ M_{k} · (1 + 2^{log_{2}(3)·(⌈log_{2}(k+1)⌉+1)−k})  (see below)
< M_{k} · (1 + 9 · (k + 1)^{1.59}/2^{k})  (see below)
= M_{k+1}.

Here we used that the following four inequalities hold for all k ≥ 7 and m ≥ 1:

⌈log_{m+1}(k + 1)⌉ + 2 ≤ k
log_{m+1}(m + 2) ≤ log_{2}(3)
log_{2}(3) · (⌈log_{2}(k + 1)⌉ + 1) − k ≤ 0
log_{2}(3) < 1.59.

Proving these inequalities is straightforward.

From the lemma and Inequality (5), we obtain that \frac{β^{(m)}(u)}{(m+1)^{u−1}} < M for all m, u ≥ 1, where we define M as 4 · ∏_{k=7}^{∞}(1 + 9 · (k + 1)^{1.59}/2^{k}). Our calculations give M = 96.504 …, so M < 100. Hence

\frac{β^{(m)}(u)}{(m + 1)^{u−1}} < 100  (7)

for all m, u ≥ 1.

In the end we only need bounds for β^{(1)}(u). A lower bound is easy: Inequality (4) gives us that β^{(1)}(u) ≥ 2^{u−1} · β^{(1)}(1) = 2^{u−1}. Hence

2^{u−1} ≤ β^{(1)}(u) < 100 · 2^{u−1}.  (8)

6 The tower of exponents

We combine Proposition 19 and Inequality (8) to prove our main result, which we restate for convenience:

Theorem 1. For all integers n ≥ 4, the first occurrence of n in Gijswijt’s sequence is at position

2^{234^{...}(n−2)α} ,

for a real number α ∈ (n − 2, n − 1) that depends on n.

Proof. The first occurrence of n = 4 is at position 220. This equals 2^{22.96...}.

Now suppose that n ≥ 5. The location of the first n is at position β^{(1)}(t(1, n)). By Inequality (8) this is at least 2^{t(1,n)−1}. We can now repeatedly apply the first part of Proposition 19, which states that

t(m, n) ≥ m · (m + 1)^{t(m+1,n)−2}

for all m ≥ 1 and n ≥ m + 3. Using this for m = 1 yields 2^{t(1,n)−1} ≥ 2^{2t(2,n)−2−1} ≥ 2^{2t(2,n)−3}. We also see that

t(m, n) − 3 ≥ (m + 1)^{t(m+1,n)−3}

for 2 ≤ m ≤ n − 4. Combining this we obtain

2^{2t(2,n)−3} ≥ 2^{234^{...}(n−3)t(n−3,n)−3} .

For m = n − 3, we have

t(n − 3, n) − 3 ≥ (n − 3) · (n − 2)^{t(n−2,n)−2} − 3 = (n − 3) · (n − 2)^{n−2} − 3 > (n − 2)^{n−2}.

Here we used Example 10 which implies that t(n − 2, n) = n. We conclude that the position of the first n is larger than

2^{23^{^{...}^{(n−3)(n−2)n−2}}} .

On the other hand, Inequality (8) tells us that β^{(1)}(t(1, n)) < 100 · 2^{t(1,n)−1}. We can now use the second part of Proposition 19, which gives us that

t(m, n) − 1 ≤ (m + 1)^{t(m+1,n)−1}

for all m ≥ 1 and n ≥ m + 3. By repeatedly using this we see that 100 · 2^{t(1,n)−1} is at most

100 · 2^{23^{^{...}^{(n−3)t(n−3,n)−1}}} .

We apply the proposition again for m = n−3, and this time it is a strict inequality. Therefore we get the upper bound

100 · 2^{23^{^{...}^{(n−3)[(n−2)t(n−2,n)−1−1]}}} = 100 · 2^{23^{^{...}^{(n−3)[(n−2)n−1−1]}}} .

Since n ≥ 5 this is smaller than

2^{23^{^{...}^{(n−2)n−1}}} .

There is some room for improvement:

Remark 21. It is possible to narrow down the interval of α, thereby giving tighter bounds for the position of the first n. This can be done by constructing a closed-form expression for t(n − 3, n). Then Proposition 19 needs to be used one less time for obtaining the tower of exponents.

Remark 22. We could also generalize Theorem 1 to the sequences A^{(m)} for m ≥ 2. That would look something like this: For n large enough, the first occurrence of n in A^{(m)} is at position

(m + 1)^{(m+1)(m+2)^{^{•} ^{•} ^{^{•}(n−2)α}}} ,

for a real number α ∈ (n − 2, n − 1) that depends on m and n. We already have all the ingredients for this: both Proposition 19 and Inequality (7) hold for all m.

7 Acknowledgments

The author would like to thank Gunther Cornelissen and Dion Gijswijt for supervising his bachelor thesis, which eventually led to this paper. He is grateful to the anonymous referees, whose insightful comments and suggestions significantly improved the manuscript. Finally, he thanks Brendan Miller for his helpful comments and for proofreading the English.

References

[1] B. Chaffin, J. P. Linderman, N. J. A. Sloane, and A. R. Wilks, On curling numbers of integer sequences, J. Integer Sequences 16 (2013), Article 13.4.3.

[2] The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, Published electronically at https://oeis.org.

[3] F. J. van de Bult, D. C. Gijswijt, J. P. Linderman, N. J. A. Sloane, and A. R. Wilks, A slow-growing sequence defined by an unusual recurrence, J. Integer Sequences 10 (2007), Article 07.1.2.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 11B83. Keywords: curling number, Gijswijt’s sequence, recurrence, growth rate.

(Concerned with sequences \underline{A090822}, \underline{A091409}, \underline{A091411}, \underline{A091579}, \underline{A091787}, \underline{A091799}, \underline{A091840}, and \underline{A357064}.)

Received January 18 2023; revised versions received May 15 2024; July 26 2025. Published in Journal of Integer Sequences, August 6 2025.

Return to Journal of Integer Sequences home page