On Hofstadter’s G-sequence

F. M. Dekking CWI Amsterdam and Delft University of Technology Faculty EEMCS P.O. Box 5031 2600 GA Delft The Netherlands

                   F.M.Dekking@math.tudelft.nl

Abstract

We characterize the entries of Hofstadter’s G-sequence in terms of the lower and upper Wythoff sequences. This can be used to give a short and comprehensive proof of the equality of Hofstadter’s G-sequence and the sequence of averages of the swapped Wythoff sequences. In a second part we give some results that hold when one replaces the golden mean by other quadratic algebraic numbers. In a third part we prove a close relationship between Hofstadter’s G-sequence and a sequence studied by Avdivpahić and Zejnulahi.

1 Introduction

Hofstadter’s G-sequence G is defined by G(1) = 1, G(n) = n − G(G(n − 1)) for n ≥ 2.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ G(n) & 0 & 1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 9 & 9 & 10 & 11 & 11 \end{matrix}

Table 1: G(n) = \underline{A005206}(n) for n = 0, …, 18.

It was proved in 1988, independently in the two articles [?, ?] that there is a simple expression for Hofstadter’s G-sequence as a slow Beatty sequence, given for n ≥ 0 by

G(n) = ⌊(n + 1)γ⌋,  (1)

where γ = (\sqrt{5} − 1)/2, the small golden mean.

The terminology ‘slow Beatty sequence’ comes from the paper [?] by Kimberling and Stolarsky. Actually, G is not a Beatty sequence: Beatty sequences are sequences (⌊nα⌋) with α a positive real number larger than 1. See, e.g., the papers [?, ?].

The paper by Kimberling and Stolarsky provides the following basic result.

Theorem 1. [Kimberling and Stolarsky] Suppose that γ in (0, 1) is irrational, and let s(n) = ⌊(n + 1)γ⌋ for n ≥ 0. Let A be the set {n ≥ 0 : s(n + 1) = s(n)} and let a(0) < a(1) < ⋯ be the members of A in increasing order. Similarly, let b be the sequence of those n such that s(n + 1) = s(n) + 1. Then a is the Beatty sequence of 1/(1 − γ), and b is the Beatty sequence of 1/γ.

When we apply this result to determine the value of s(n) for a given n, then we need information on two entries, namely s(n) and s(n + 1), and given this information we do not yet know for which m s(n) will be equal to a(m), respectively b(m). The following theorem is more useful in this respect.

Theorem 2. Suppose that γ in (0, 1) is irrational, and let s(n+1) = ⌊nγ⌋ for n ≥ 0. Define L(n) = ⌊\frac{1}{γ}n⌋, and U(n) = ⌊\frac{1}{1−γ} n⌋ for n ≥ 0. Then

s(L(n)) = n, s(U(n)) = \frac{γ}{1 − γ} n

for all n ≥ 0.

Proof. By definition, the sequence L satisfies for n ≥ 0

\frac{1}{γ} n = L(n) + ε_{n}

for some ε_{n} with 0 ≤ ε_{n} < 1. This leads to

s(L(n)) = ⌊(L(n) + 1)γ⌋ = ⌊n + γ(1 − ε_{n})⌋ = n,

since obviously 0 ≤ γ(1 − ε_{n}) < 1.

By definition, the sequence U satisfies for n ≥ 0

\frac{1}{1 − γ} n = U(n) + ε′_{n},

for some ε′_{n} with 0 ≤ ε′_{n} < 1. This leads to

s(U(n)) = ⌊(U(n) + 1)γ⌋ = ⌊\frac{γ}{1 − γ} n + γ(1 − ε′_{n})⌋ = \frac{γ}{1 − γ} n,

since obviously 0 ≤ γ(1 − ε′_{n}) < 1.

It is well-known (see [?]) that if α and β are two real numbers larger than 1, and moreover 1/α + 1/β = 1, then α and β form a complementary Beatty pair, which means that the two sets {⌊nα⌋, n ≥ 1} and {⌊nβ⌋, n ≥ 1} are disjoint, and that their union contains every positive integer. Note that for all γ in (0, 1) the sequences L and U form a complementary Beatty pair, since \frac{1}{γ} > 1, \frac{1}{1−γ} > 1 and (\frac{1}{γ})^{−1} + (\frac{1}{1−γ})^{−1} = 1.

2 Hofstadter and Wythoff

The most famous complementary Beatty pair is obtained by choosing α = φ, and β = φ^{2}, where φ := (1 + \sqrt{5})/2 is the golden mean. The Beatty sequences L(n) = ⌊nφ⌋ and U(n) = ⌊nφ^{2}⌋ for n ≥ 1 are known as the lower Wythoff sequence and the upper Wythoff sequence. The name giving has its origins in the paper [?].

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ L(n) & 1 & 3 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & 16 & 17 & 19 & 21 & 22 & 24 & 25 & 27 & 29 \\ U(n) & 2 & 5 & 7 & 10 & 13 & 15 & 18 & 20 & 23 & 26 & 28 & 31 & 34 & 36 & 39 & 41 & 44 & 47 \end{matrix}

Table 2: L(n) = \underline{A000201}(n) and U(n)=\underline{A001950}(n) for n = 0, …, 18.

We next turn our attention to sequence \underline{A002251}, described as: Start with the nonnegative integers; then swap L(k) and U(k) for all k ≥ 1, where L and U are the lower and upper Wythoff sequences.

This means that this sequence, which we call W, is defined by

W (L(n)) = U(n), W (U(n)) = L(n) for all n ≥ 1.  (2)

Regrettably, the sequence W has been given offset 0 in OEIS. One of the unpleasant consequences of the useless addition of 0 is that sequence \underline{A073869} is not a clean Cesaró average of \underline{A002251}. Another unpleasant consequence is that \underline{A073869} is basically a copy of \underline{A019444}.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ W (n) & 0 & 2 & 1 & 5 & 7 & 3 & 10 & 4 & 13 & 15 & 6 & 18 & 20 & 8 & 23 & 9 & 26 & 28 & 11 \end{matrix}

Table 3: W (n) = \underline{A002251}(n) for n = 0, …, 18.

The sequence W has the remarkable property that the sum of the first n+1 terms is divisible by n+1. This leads to the sequence \underline{A073869}, defined as \underline{A073869}(n) = ∑_{i=0}^{n} W (i)/(n+1).

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\ \overline{W} (n) & 0 & 1 & 1 & 2 & 3 & 3 & 4 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 9 & 9 & 10 & 11 & 11 \end{matrix}

Table 4: \overline{W} (n) = \underline{A073869}(n) for n = 0, …, 18.

The following theorem is a conjecture by Murthy in [?, \underline{A073869}], but is proved in the long paper [?]. We give a new short proof.