A Slow Relative of Hofstadter’s Q-Sequence

Nathan Fox Department of Mathematics Rutgers University 110 Frelinghuysen Rd. Piscataway, NJ 08854 USA

                 fox@math.rutgers.edu

Abstract

Hofstadter’s Q-sequence remains an enigma fifty years after its introduction. Initially, the terms of the sequence increase monotonically by 0 or 1 at a time. But the 12th term exceeds the 11th by two, and monotonicity fails shortly thereafter. In this paper, we add a third term to Hofstadter’s recurrence in the most natural way. We show that this new recurrence, along with a suitable initial condition that naturally generalizes Hofstadter’s initial condition, generates a sequence whose terms all increase monotonically by 0 or 1 at a time. Furthermore, we give a complete description of the resulting frequency sequence, which allows the nth term of our sequence to be efficiently computed. We conclude by showing that our sequence cannot be easily generalized.

1 Introduction

The Hofstadter Q-sequence [4] is defined by the nested recurrence Q(n) = Q(n−Q(n−1))+ Q(n − Q(n − 2)) with the initial conditions Q(1) = Q(2) = 1. The first 11 terms of this sequence, \underline{A005185} in the OEIS [9], are

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, …

These terms increase monotonically with successive differences either 0 or 1. But, Q(12) = 8, ending the successive difference property. Not long thereafter, Q(15) = 10 and Q(16) = 9, ending the monotonicity. Calculating more terms leads one to the resignation that the Hofstadter Q-sequence is anything but well-behaved. While there appear to be some patterns in the sequence, all such observation are as-yet purely emprical. Essentially nothing has been rigorously proven about this sequence. Most critically, nobody has been able to prove that Q(n) even exists for all n. If Q(n − 1) ≥ n for some n, then evaluating Q(n) would require knowing Q(k) for some k ≤ 0. Since Q is only defined for positive indices, Q(n) (and all subsequent terms) would fail to exist in this case. If a sequence is finite because of behavior like this, we say that the sequence dies.

Hofstadter and Huber [5, 1] investigated the following familiy of recurrences, which generalize the Hofstadter Q-recurrence. For integers 0 < r < s, define

Q_{r,s}(n) = Q_{r,s}(n − Q_{r,s}(n − r)) + Q_{r,s}(n − Q_{r,s}(n − s)).

They explored these recurrences experimentally for various initial conditions. This work led them to conjecture that the sequences reulting from an all-ones initial condition always die, except for (r, s) ∈ {(1, 1), (1, 4), (2, 4)}. The case (1, 1) is the Q-sequence, and the case (2, 4), often called the W -sequence, displays even wilder behavior than the Q-sequence (\underline{A087777} in the OEIS). The sequence resulting from (r, s) = (1, 4), on the other hand, behaves much more regularly. This sequence, known as the V -sequence (\underline{A063882} in the OEIS), was proven to be monotone increasing by 0 or 1 at a time [1]. This growth property is known in the literature as slow.

There has been substantial research concerning slow Hofstadter-like sequences. The most famous example is perhaps the Hofstadter-Conway $10000 Sequence (\underline{A004001} in the OEIS), given by A(n) = A(A(n − 1)) + A(n − A(n − 1)) with A(1) = A(2) = 1. Conway notably offered a $10000 prize for an analysis of the behavior of this sequence. Colin Mallows solved this problem a few years later [8]. Another prototypical example is Conolly’s [2] recurrence C(n) = C(n − C(n − 1)) + C(n − 1 − C(n − 2)) with C(1) = C(2) = 1 as the initial condition (\underline{A046699} in the OEIS). There are many examples of slow sequences that generalize Conolly’s recurrence [3, 7], some of which have combinatorial interpretations involving counting leaves in tree structures [7]. In addition, given a slow Hofstadter-like sequence, it is possible to generate an infinite family of slow sequences with similar recurrences [6].

Most of the known examples of slow sequences have at least one of the following properties:

• An inner recursive call with a positive coefficient (like the first A(n−1) in the Hofstadter-Conway recurrence).

• A “shift” in at least one of the recurrence terms (like the −1 in the second term in Conolly’s recurrence).

In fact, the only ones that have neither property are the V -sequence and sequences constructed from it [6]. We decided to search for additional slow, Hofstadter-like sequences without these properties. The investigation of Hofstadter and Huber empirically rules out two-term recurrences, so we began our search by considering the generic 3-term recurrence

Q_{r,s,t}(n) = Q_{r,s,t}(n − Q_{r,s,t}(n − r)) + Q_{r,s,t}(n − Q_{r,s,t}(n − s)) + Q_{r,s,t}(n − Q_{r,s,t}(n − t)) with integers 0 < r < s < t. The all-ones initial condition proved fruitless in our investigation. However, the initial conditions V (1) = 1, V (2) = 2, V (3) = 3, V (4) = 4 generate the V -sequence as well (offset by 3 terms) [1]. Thus, we focused our search on slow sequences with initial conditions of the form Q_{r,s,t}(i) = i for i ≤ t. This allowed us to find the sequence with (r, s, t) = (1, 2, 3). In this paper, we prove that this sequence is slow. In fact, we completely characterize the terms of this sequence and exhibit an efficient algorithm (polylogarithmic in the index n; polynomial bit complexity) for computing the n^{th} term. In particular, each term of this sequence appears at most twice, in contrast to the V -sequence, whose terms appear at most three times [1]. In Section 2, we examine this sequence and prove our results about it. Then in Section 3, we discuss some future directions, and we show that one potential generalization of our sequence fails to yield other slow sequences.

2 Our sequence

We consider the sequence defined by the recurrence

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

and the initial conditions B(1) = 1, B(2) = 2, B(3) = 3, B(4) = 4, B(5) = 5. The first few terms of this sequence (\underline{A278055} in the OEIS) are

1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 14, 15, 15, 16, 17, 17, 18, 18, 19, 20, 21, 21, …

The main thing we wish to prove is the following:

Theorem 1. For all n, B(n) − B(n − 1) ∈ {0, 1}. In other words, the sequence (B(n))_{n≥1} is slow.

We actually prove considerably more than just Theorem 1. We completely determine the structure of this sequence. In the terms listed above, each positive integer appears no more than twice (and at least once). We show that this is the case for all numbers, and we completely characterize which numbers repeat.

We make use of the following auxiliary sequence (a_{i})_{i≥1}. Let a_{1} = 3, and for i ≥ 2, let a_{i} = 3a_{i−1} − 1. (This is sequence \underline{A057198} in OEIS.) This sequence has the closed form a_{i} = \frac{5}{2}3^{i−1} + \frac{1}{2}. Also, define a sequence of sets S_{i} = \{k · 3^{i} + a_{i} : k > 0, k ∈ ℤ\}, and let

S = ⋃_{i≥1} S_{i}.

We have the following theorem.

Theorem 2. Let m be a positive integer. If m ∈ S, then m appears in the B-sequence twice. Otherwise, m appears once. Furthermore, the B-sequence is monotone increasing.

Theorem 2 implies Theorem 1, since Theorem 2 asserts both that the sequence is monotone and that each positive integer appears in the sequence. Throughout the rest of this section, we will end up proving Theorem 2, and consequently Theorem 1, by induction. In doing so, we frequently assume that Theorem 2 holds up to some point. To make this clear, we define the following indexed families of propositions (where m and n are positive integers):

• Let P_{m} denote the proposition “For all integers 1 ≤ m′ ≤ m, if m′ ∈ S, then m′ appears in the B-sequence twice. Otherwise, m′ appears once. Furthermore, the B-sequence is monotone increasing as long as its terms are at most m.” In this way, P_{m} is essentially the statement “Theorem 2 holds through value m.”

• Let T_{n} denote the proposition “The first n terms of the B-sequence are monotone increasing. Furthermore, for all m appearing as one of these first n terms, if m ∈ S, then m appears in these first n terms twice (unless this second occurrence would be in position n + 1). Otherwise, m appears once.” In this way, T_{n} is essentially the statement “Theorem 2 holds through index n.”

It should be clear from these definitions that the following three statements are equivalent:

• Theorem 2 is true.

• P_{m} holds for all m ≥ 1.

• T_{n} holds for all n ≥ 1.

We first show that the sets S_{i} are pairwise disjoint.

Lemma 3. Let i and j be positive integers. If i ≠ j, then S_{i} ∩ S_{j} = ∅.

Proof. Suppose for a contradiction that, for some integers i, j ≥ 1 with i ≠ j, k_{1} · 3^{i} + a_{i} = k_{2} · 3^{i+j} + a_{i+j}. Then

a_{i+j} − a_{i} = k_{1} · 3^{i} − k_{2} · 3^{i+j} = 3^{i}(k_{1} + k_{2} · 3^{j}).

In particular, a_{i+j} − a_{i} must be divisible by 3^{i}.

But, using the closed form,

a_{i+j} − a_{i} = (\frac{5}{2} · 3^{i+j−1} + \frac{1}{2}) − (\frac{5}{2} · 3^{i−1} + \frac{1}{2}) = \frac{5}{2} (3^{i+j−1} − 3^{i−1})

= \frac{5}{2} · 3^{i−1} (3^{j} − 1) .

This is clearly not divisible by 3^{i}, a contradiction. Therefore, no such i and j can exist, so there is at most one i ≥ 1 such that m ≡ a_{i} (mod 3^{i}), as required.

For a value m, we examine the number of values less than m that are repeated. Define R(m, i) = max (0, ⌊\frac{m−a_{i}−1}{3^{i}}⌋). This floored quantity counts the pairs (k, i) such that k · 3^{i} + a_{i} < m. If P_{m} holds, then this is also the number of repeated values m′ < m with m′ ∈ S_{i}. If we now let

R(m) = ∑_{i=1}^{∞} R(m, i),

we have that R(m) is the total number of repeated values less than m (provided that P_{m} holds.) This sum converges because only the logarithmically many terms with a_{i} − 1 ≤ m are nonzero.

We now have the following lemmas.

Lemma 4. Let m be a positive integer. Suppose P_{m−1} holds. Then B(m+R(m)−1) = m−1, and B(m + R(m)) ≥ m. (In other words m + R(m) − 1 is the last index in our sequence with value at most m − 1.)

Proof. The number of terms before the first occurrence of a term greater than or equal to m is at least m − 1, since each number smaller than m must appear at least once. The first occurrence of such a term is “delayed” by 1 index for every smaller value that is repeated. The number of such repeated values is R(m). So, there are m − 1 + R(m) terms before the first occurrence of a term greater than or equal to m. This means that the last occurrence of m − 1 is in position m + R(m) − 1, as required.

An immediate consequence of Lemma 4 is that B(m + R(m)) in fact equals m, provided that P_{m} holds.

Lemma 5. Let m be a multiple of 3. If m−1 ∈ S_{i} for i ≥ 2, then R(m, i) = R(\frac{m}{3}, i − 1)+1. Otherwise, R(m, i) = R(\frac{m}{3}, i − 1).

Proof. The lemma is clearly true if a_{i} + 1 ≥ m, so we can assume without loss of generality that a_{i} + 1 < m and thereby ignore the max in the definition of R(m, i) when proving this lemma.

We have

R(m, i) = ⌊\frac{m − a_{i} − 1}{3^{i}}⌋ = ⌊\frac{m}{3^{i}} − \frac{a_{i} + 1}{3^{i}}⌋

and

R(\frac{m}{3}, i − 1) = ⌊ \frac{\frac{m}{3} − a_{i−1} − 1}{3^{i−1}}⌋ = ⌊\frac{m}{3^{i}} − \frac{a_{i−1} + 1}{3^{i−1}}⌋ .

Since a_{i} = \frac{5}{2} · 3^{i−1} + \frac{1}{2},

\frac{a_{i} + 1}{3^{i}} = \frac{5}{6} + \frac{1}{2 · 3^{i}}

and

\frac{a_{i−1} + 1}{3^{i−1}} = \frac{5}{6} + \frac{1}{2 · 3^{i−1}} .

The first of these definitely smaller, so R(m, i) ≥ R(\frac{m}{3}, i − 1). Furthermore, the above fractions differ by \frac{1}{3^{i}}, so R(m, i) ≤ R(\frac{m}{3}, i − 1) + 1.

The only way they can be unequal is if there is some integer ℓ such that

\frac{m}{3^{i}} − \frac{a_{i−1} + 1}{3^{i−1}} < ℓ ≤ \frac{m}{3^{i}} − \frac{a_{i} + 1}{3^{i}}.

Since the bounds differ by \frac{1}{3^{i}} and they have common denominator 3^{i}, this can only happen if ℓ = \frac{m}{3^{i}} − \frac{a_{i}+1}{3^{i}}. This gives that m − a_{i} + 1 = ℓ · 3^{i}, or m − 1 = ℓ · 3^{i} + a_{i} for some integer ℓ. Since a_{i} + 1 < m, we must have ℓ ≥ 1. So, for R(m, i) = R(\frac{m}{3}, i − 1) + 1, we obtain that m − 1 ∈ S_{i}, as required.

Lemma 6. Let m be a multiple of 3. Then

\frac{m}{3} + R(\frac{m}{3}) = \begin{cases}R(m) + 1, & if m − 1 ∈ S; \\ R(m) + 2, & if m − 1 ∉ S. \end{cases}

Proof. As a consequence of Lemma 5 and Lemma 3,

R(m) = \begin{cases}R(m, 1) + R(\frac{m}{3}) , & if m − 1 ∉ S; \\ R(m, 1) + R(\frac{m}{3}) + 1, & if m − 1 ∈ S. \end{cases}

We also have

R(m, 1) = ⌊\frac{m − a_{1} − 1}{3}⌋ = ⌊\frac{m − 4}{3}⌋ = \frac{m}{3} − 2.

Substituting this into the above and rearranging terms gives the required form.

Lemma 7. Let m be a multiple of 3. Then m − 1 ∈ S if and only if \frac{m}{3} ∈ S.

Proof. (⟹) Suppose m − 1 ∈ S. Then m − 1 = k · 3^{i} + a_{i} for some positive integers k and i. Then m = k · 3^{i} + a_{i} + 1. But, a_{i} = 3a_{i−1} − 1, so m = k · 3^{i} + 3a_{i−1}. This means

that \frac{m}{3} = k · 3^{i−1} + a_{i−1}, so \frac{m}{3} ∈ S_{i−1} ⊆ S.

(⟸) Suppose \frac{m}{3} ∈ S. Then \frac{m}{3} = k · 3^{i} + a_{i} for some positive integers k and i. Then m = 3k · 3^{i} + 3a_{i}. But, a_{i+1} = 3a_{i} − 1, so m = k · 3^{i+1} + a_{i+1} + 1. This means that

m − 1 = k · 3^{i+1} + a_{i+1}, so m − 1 ∈ S_{i+1} ⊆ S.

Lemma 8. Let m ≥ 6 be a multiple of 3. Suppose P_{m−1} holds. Then if m − 1 repeats we have B(R(m) + 1) = \frac{m}{3}. If m − 1 does not repeat we have B(R(m) + 1) = \frac{m}{3} − 1. In both cases we have

\begin{cases}B(R(m) + 2) = \frac{m}{3}; \\ B(R(m) + 3) = \frac{m}{3} + 1. \end{cases}

Proof. We look at the two cases separately. m − 1 repeats: Then m − 1 ∈ S. So, by Lemma 6, R(m) + 1 = \frac{m}{3} + R(\frac{m}{3}). By Lemma 4,

B(R(m)+1) = \frac{m}{3}. Furthermore, by Lemma 7, \frac{m}{3} ∈ S (and hence repeats), so B(R(m)+ 2) = \frac{m}{3} as well. Since values appear at most twice, we then have B(R(m)+3) = \frac{m}{3} +1, as required.

m − 1 does not repeat: Then m − 1 ∉ S. So, by Lemma 6, R(m) + 2 = \frac{m}{3} + R(\frac{m}{3}). By Lemma 4, B(R(m) + 2) = \frac{m}{3} and B(R(m) + 1) = \frac{m}{3} − 1. Furthermore, by Lemma 7, \frac{m}{3} ∉ S (and hence does not repeat), so B(R(m) + 3) = \frac{m}{3} + 1.

We are now ready to prove Theorem 2.

Proof. The proof is by induction on n, the index in the sequence. For the base case, observe that each term in the initial condition appears once, and no such term in in S.

Now, suppose that T_{n−1} holds, and suppose that we wish to show that B(n) = m for some m ≥ 6. Also, suppose that P_{m−1} holds. There are seven cases to consider, which cover all possibilities. (Note that no repeated term is congruent to 1 mod 3, since a_{1} is divisible by 3 and a_{i} ≡ 2 (mod 3) for all i ≥ 2.)

m ≡ 0 (mod 3), first occurrence, m − 1 not repeated: In this case, m − 1 ∉ S and, by Lemma 4, n = m + R(m). We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) − (m − 1)) + B(m + R(m) − (m − 2))

+ B(m + R(m) − (m − 3)) = B(R(m) + 1) + B(R(m) + 2) + B(R(m) + 3)

= (\frac{m}{3} − 1) + \frac{m}{3} + (\frac{m}{3} + 1)

= m,

as required.

m ≡ 0 (mod 3), first occurrence, m − 1 repeated: In this case, m − 1 ∈ S and, by Lemma 4, n = m + R(m). We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) − (m − 1)) + B(m + R(m) − (m − 1))

+ B(m + R(m) − (m − 2)) = B(R(m) + 1) + B(R(m) + 1) + B(R(m) + 2)

= \frac{m}{3} + \frac{m}{3} + \frac{m}{3}

= m,

as required. m ≡ 0 (mod 3), second occurrence, m − 1 not repeated: In this case, m − 1 ∉ S and,

by Lemma 4, n = m + R(m) + 1. We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) + 1 − m) + B(m + R(m) + 1 − (m − 1))

+ B(m + R(m) + 1 − (m − 2)) = B(R(m) + 1) + B(R(m) + 2) + B(R(m) + 3)

= (\frac{m}{3} − 1) + \frac{m}{3} + (\frac{m}{3} + 1)

= m,

as required.

m ≡ 0 (mod 3), second occurrence, m − 1 repeated: In this case, m − 1 ∈ S and, by Lemma 4, n = m + R(m) + 1. We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) + 1 − m) + B(m + R(m) + 1 − (m − 1))

+ B(m + R(m) + 1 − (m − 1)) = B(R(m) + 1) + B(R(m) + 1) + B(R(m) + 2)

= \frac{m}{3} + \frac{m}{3} + \frac{m}{3}

= m,

as required.

m ≡ 1 (mod 3): In this case, m − 1 is divisible by 3 and therefore definitely repeats (since a_{1} = 3). This also means that R(m − 1) = R(m) − 1. By Lemma 4, n = m + R(m). We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) − (m − 1)) + B(m + R(m) − (m − 1))

+ B(m + R(m) − (m − 2)) = B(R(m) + 1) + B(R(m) + 1) + B(R(m) + 2) = B(R(m − 1) + 2) + B(R(m − 1) + 2) + B(R(m − 1) + 3)

= \frac{m − 1}{3} + \frac{m − 1}{3} + (\frac{m − 1}{3} + 1)

= m,

as required. m ≡ 2 (mod 3), first occurrence: In this case, m−2 is divisible by 3 and therefore definitely

repeats. This also means that R(m − 2) = R(m) − 1. By Lemma 4, n = m + R(m). We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) − (m − 1)) + B(m + R(m) − (m − 2))

+ B(m + R(m) − (m − 2)) = B(R(m) + 1) + B(R(m) + 2) + B(R(m) + 2) = B(R(m − 2) + 2) + B(R(m − 2) + 3) + B(R(m − 2) + 3)

= \frac{m − 2}{3} + (\frac{m − 2}{3} + 1) + (\frac{m − 2}{3} + 1)

= m,

as required.

m ≡ 2 (mod 3), second occurrence: In this case, m ∈ S, so R(m + 1) = R(m) + 1. Also, R(m − 2) = R(m) − 1. By Lemma 4, n = m + R(m) + 1. We have (using Lemma 8)

B(n) = B(n − B(n − 1)) + B(n − B(n − 2)) + B(n − B(n − 3))

= B(m + R(m) + 1 − m) + B(m + R(m) + 1 − (m − 1))

+ B(m + R(m) + 1 − (m − 2)) = B(R(m) + 1) + B(R(m) + 2) + B(R(m) + 3) = B(R(m − 2) + 2) + B(R(m − 2) + 3) + B(R(m + 1) + 2)

= \frac{m − 2}{3} + (\frac{m − 2}{3} + 1) + (\frac{m + 1}{3})

= m,

as required.

We have the following corollary.

Corollary 9. We have

lim_{n→∞} \frac{B(n)}{n} = \frac{2}{3}.

Proof. If B(n) = m, then n = m + R(m) or n = m + R(m) + 1. So, it suffices to show that

lim_{m→∞} \frac{m}{m + R(m)} = \frac{2}{3},

for which it is sufficient to show that

lim_{m→∞} \frac{R(m)}{m} = \frac{1}{2}.

For each i ≥ 1, we have

lim_{m→∞} \frac{R(m, i)}{m} = \frac{1}{3^{i}} .

So,

lim_{m→∞} \frac{R(m)}{m} = lim_{m→∞} \frac{1}{m} ∑_{i=1}^{∞} R(m, i)

= ∑_{i=1}^{∞} lim_{m→∞} \frac{R(m, i)}{m}

= ∑_{i=1}^{∞} \frac{1}{3^{i}}

= \frac{1}{2},

as required.

To prove Corollary 9, it would have sufficed to prove that the limit exists. Based on the form of the recurrence defining the B-sequence, this limit must be \frac{2}{3} if it exists [3].

2.1 Algorithm for computing the sequence

Theorem 2 leads to an efficient algorithm for calculating B(n). For a given m and i, computing R(m, i) requires only elementary arithmetic operations. So, R(m, i) can be computed in polynomial time in the number of bits representing m and i. Since only logarithmically many terms in the sum for R(m) are nonzero, this means that R(m) itself can be computed efficiently.

To compute B(n), we seek an m such that n = m + R(m). It may be the case that no such m exists, in which case we need to be able to say that no such m exists, and we need to find m such that n = m + R(m) + 1. This task can be done efficiently using a binary search. We know that B(n) ≤ n, so for an initial upper bound on m we can use n (and we can use 1 as a lower bound). So, in at most O(log(n)) steps, we can either find an m so that n = m + R(m) or show that none exists. In the latter case, the final lower bound we find for m is such that n = m + R(m) + 1. The total running time of this algorithm is polylogarithmic in n, or, equivalently, polynomial in the number of bits used to represent n.

3 Beyond our sequence

According to the work of Isgur et al. [6], our B-sequence is the fundamental member of an infinite family of slow sequences with similar recurrences. (The next one satisfies the recurrence B′(n) = B′(n−B′(n−2))+B′(n−B′(n−4))+B′(n−B′(n−6)).) As mentioned in the introduction, this family and the family resulting from the V -sequence comprise the only known examples of slow Hofstadter-like sequences with all recurrence terms of the form D(n − D(n − i)) for some i. The author has conducted a search for other such sequences without finding another (nontrivial) example. An obvious idea would be to generalize the B-recurrence to the k-term recurrence

B_{k}(n) = ∑_{i=1}^{k} B_{k}(n − B_{k}(n − i))  (1)

(where B_{3} is the B-recurrence and B_{2} is the Q-recurrence). If k = 1, the initial condition B_{1}(1) = 1 generates the all-ones sequence, which, while technically slow, is not particularly interesting. Unfortunately, we have the following result:

Theorem 10. The B-sequence is the only nontrivial slow sequence resulting from a recurrence B_{k} with an initial condition of the form B_{k}(i) = i for all i ≤ N for some N.

The bulk of the Theorem 10 follows from the following proposition:

Proposition 11. Suppose k ≥ 4. The sequence generated by Equation (1) with the initial condition B_{k}(i) = i for all i < \frac{k^{2}+k}{2} satisfies

B_{k}(\frac{1}{2}k^{3} + \frac{1}{2}k^{2} + 2k + 1) = B_{k}(\frac{1}{2}k^{3} + \frac{1}{2}k^{2} + 2k) + 2.

In particular, the sequence has a jump of difference 2, so it is not slow.

Proof. For simplicity of notation, let N = \frac{k^{2}+k}{2}. We now show that, for 1 ≤ r ≤ k + 1 and −k ≤ qk + r < (N − k)(k + 1)

B_{k}(N + q(k + 1) + r) = N + qk + r − 1.

We observe that the last k terms of the initial condition correspond to q = −1 and r = 1 through r = k. These all satisfy B_{k}(N + q(k + 1) + r) = N + qk + r − 1, as required. We also have, when q = −1 and r = k + 1,

B_{k}(N) = ∑_{i=1}^{k} B_{k}(N − B_{k}(N − i)) = ∑_{i=1}^{k} B_{k}(N − (N − i))

= ∑_{i=1}^{k} B_{k}(i) = ∑_{i=1}^{k} i = N,

as required.

Now, let q(k + 1) + r > 0 and suppose inductively that

B_{k}(N + q′(k + 1) + r′) = N + q′k + r′ − 1

for all −k ≤ q′(k + 1) + r′ < q(k + 1) + r < (N − k + 1)(k + 1). Using Equation (1), we have

B_{k}(N + q(k + 1) + r)

= ∑_{i=1}^{k} B_{k}(N + q(k + 1) + r − B_{k}(N + q(k + 1) + r − i))

= ∑_{i=1}^{r−1} B_{k}(N + q(k + 1) + r − B_{k}(N + q(k + 1) + r − i))

+ ∑_{i=r}^{k} B_{k}(N + q(k + 1) + r − B_{k}(N + q(k + 1) + r − i))

= ∑_{i=1}^{r−1} B_{k}(N + q(k + 1) + r − (N + qk + r − i − 1))

+ ∑_{i=r}^{k} B_{k}(N + q(k + 1) + r − (N + (q − 1)k + (r − i + k + 1) − 1))

= ∑_{i=1}^{r−1} B_{k}(q + i + 1) + ∑_{i=r}^{k} B_{k}(q + i).

Since q ≤ N − k (and, if q = N − k, then r ≤ k), this equals

∑_{i=1}^{r−1}(i + q + 1) + ∑_{i=r}^{k}(i + q) = r − 1 + qk + ∑_{i=1}^{k} i = N + qk + r − 1,

as required.

Now, for simplicity of notation, let A = (N − k + 1) (k + 1). We now show that, for 0 ≤ r ≤ k − 2, B_{k}(N + A + r) = N + (N − k + 1) k + r − 1. (Note that these values are 1 less than they would be if the previous pattern continued.) Inductively, suppose this holds for all r′ < r. We now apply Equation (1) to calculate

B_{k}(N + A + r)

= ∑_{i=1}^{k} B_{k}(N + A + r − B_{k}(N + A + r − i))

= ∑_{i=1}^{r} B_{k}(N + A + r − B_{k}(N + A + r − i))

+ ∑_{i=r+1}^{k} B_{k}(N + A + r − B_{k}(N + A + r − i))

= ∑_{i=1}^{r} B_{k}(N + A + r − (N + (N − k + 1) k + r − i − 1))

+ ∑_{i=r+1}^{k} B_{k}(N + A + r − (N + (N − k) k + (k + 1 + r − i) − 1))

= ∑_{i=1}^{r} B_{k}(A + i + 1 − (N − k + 1) k) + ∑_{i=r+1}^{k} B_{k}(A + i − (N − k + 1) k)

= ∑_{i=1}^{r} B_{k}(N − k + i + 2) + ∑_{i=r+1}^{k} B_{k}(N − k + i + 1)

= N + ∑_{i=1}^{r} (N − k + i + 2) + ∑_{i=r+1}^{k−1} (N − k + i + 1)

= N + (N − k + 1) k + r − 1,

as required. The above calculation is also valid for r = k − 1, except that B_{k}(N − k + i + 2) would be B_{k}(N + 1) when i = k − 1. Recall that B_{k}(N + 1) = N, rather than N + 1. So, we obtain B_{k}(N + A + k − 1) = N + (N − k + 1)k + k − 3.

We now apply Equation (1) to compute

B_{k}(N + A + k)

= ∑_{i=1}^{k} B_{k}(N + A + k − B_{k}(N + A + k − i))

= B_{k}(N + A + k − B_{k}(N + A + k − 1))

+ ∑_{i=2}^{k} B_{k}(N + A + k − B_{k}(N + A + k − i))

= B_{k}(N + A + k − (N + (N − k + 1) k + k − 3))

+ ∑_{i=2}^{k} B_{k}(N + A + k − (N + (N − k + 1) k + k − i − 1))

= B_{k}(A − (N − k + 1) k + 3) + ∑_{i=2}^{k} B_{k}(A − (N − k + 1) k + i + 1)

= B_{k}(N − k + 4) + ∑_{i=2}^{k} B_{k}(N − k + i + 2)

= B_{k}(N − k + 4) + ∑_{i=2}^{k−2} B_{k}(N − k + i + 2) + B_{k}(N + 1) + B_{k}(N + 2)

= N − k + 4 + ∑_{i=2}^{k−2} (N − k + i + 2) + 2N + 1

= N + (N − k + 1) k + k − 1.

(Observe that these calculations are only valid because k ≥ 4, as otherwise N − k + 4 would be larger than N.) So, we have B_{k}(N + A + k) = B_{k}(N + A + k − 1) + 2. Recalling the values of N and A, we have that N + A + k = \frac{1}{2}k^{3} + \frac{1}{2}k^{2} + 2k + 1, as required.

We now complete the proof of Theorem 10.

Proof. Fix a positive integer N. Consider Equation (1) with the initial condition B_{k}(i) = i for 1 ≤ i ≤ N. Suppose that the sequence we obtain is slow. Clearly, we need N ≥ k, or else B_{k}(N + 1) is undefined. Supposing that N ≥ k, we have

B_{k}(N + 1) = ∑_{i=1}^{k} B_{k}(N + 1 − B_{k}(N + 1 − i))

= ∑_{i=1}^{k} B_{k}(N + 1 − (N + 1 − i)) = ∑_{i=1}^{k} B_{k}(i) = ∑_{i=1}^{k} i = \frac{k^{2} + k}{2} .

So, unless N ∈ \{\frac{k^{2}+k}{2} − 1, \frac{k^{2}+k}{2}\}, we would not have B_{k}(N +1)−B_{k}(N) ∈ \{0, 1\}. According

to Proposition 11, N = \frac{k^{2}+k}{2} − 1 does not result in a slow sequence for k ≥ 4. Similarly, N = \frac{k^{2}+k}{2} does not result in a slow sequence for k ≥ 4, as this sequence is identical to the one for N = \frac{k^{2}+k}{2} − 1 (since the first N terms are the same). So, we must have N ≤ 3. The case N = 1 results in a trivial sequence, N = 2 give the Hofstadter Q-sequence (which is not slow), and N = 3 gives our B-sequence. Therefore, the B-sequence is the only nontrivial slow sequence resulting from Equation (1) with an initial condition of the form B_{k}(i) = i for all i ≤ N for some N, as required.

4 Acknowledgments

I would like to thank Dr. Doron Zeilberger of Rutgers University for introducing me to this area of study and for providing me with useful feedback on this work. I would also like to thank Richard Voepel of Rutgers University for proofreading drafts of this paper and providing me with useful feedback.

References

[1] B. Balamohan, A. Kuznetsov, and S. Tanny, On the behavior of a variant of Hofstadter’s Q-sequence, J. Integer Seq. 10 (2007), 1–29.

[2] B. W. Conolly, Meta-Fibonacci sequences, in S. Vajda, editor, Fibonacci & Lucas Numbers, and the Golden Section, Ellis Horwood Limited, 1989, pp. 127–138.

[3] A. Erickson, A. Isgur, B. W. Jackson, F. Ruskey, and S. M. Tanny, Nested recurrence relations with Conolly-like solutions, SIAM J. Discrete Math. 26 (2012), 206–238.

[4] D. Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.

[5] D. Hofstadter, Curious patterns and nonpatterns in a family of meta-Fibonacci recursions, 2014, talk given at Rutgers Experimental Mathematics Seminar,

   https://vimeo.com/91708646.

[6] A. Isgur, R. Lech, S. Moore, S. Tanny, Y. Verberne, and Y. Zhang, Constructing new families of nested recursions with slow solutions, SIAM J. Discrete Math. 30 (2016), 1128–1147.

[7] A. Isgur, D. Reiss, and S. Tanny, Trees and meta-Fibonacci sequences, Electron. J. Combin. 16 (2009), 1–40.

[8] C. L. Mallows, Conway’s challenge sequence, Amer. Math. Monthly 98 (1991), 5–20.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://www.oeis.org.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11B39. Keywords: nested recurrence, Hofstadter sequence, slow sequence.

(Concerned with sequences \underline{A004001}, \underline{A005185}, \underline{A046699}, \underline{A057198}, \underline{A063882}, \underline{A087777}, and \underline{A278055}.)

Received January 2 2017; revised version received June 26 2017. Published in Journal of Integer Sequences, July 2 2017.

Return to Journal of Integer Sequences home page.