On Stewart's Choral Sequence

On Stewart’s Choral Sequence Joel Reyes Noche Department of Mathematics and Natural Sciences Ateneo de Naga University Naga City, Camarines Sur, Philippines Abstract We present three alternative ways of defining Stewart’s choral sequence: as the fixed point of a morphism, as a characteristic function, and as a recurrence.

1

Introduction

In 1995, Ian Stewart [1] presented the sequence {s(k)}∞ 0 = 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, . . . , which he calls the choral sequence, as an example of a cube-free (binary) sequence, one that does not contain any subsequences of the form xxx, where x is a sequence of 0’s and 1’s. This is sequence A116178 in Sloane’s Online Encyclopedia of Integer Sequences. Definition 1. We define Stewart’s choral sequence {s(k)}∞ 0 by s(3n) = 0, s(3n + 1) = s(n), and s(3n + 2) = 1 for n ∈ Z∗ = {0, 1, 2, . . .}. Note that the presentation here differs slightly from Stewart’s. (The sequence he presented starts at s(1) and not s(0), and he uses s(3n − 1) = 1 instead of s(3n + 2) = 1.) In this paper, we present three alternative ways of defining Stewart’s choral sequence: as the fixed point of a morphism, as a characteristic function, and as a recurrence.

2

Fixed Point of a Morphism

The representation of Stewart’s choral sequence as the fixed point of a morphism is wellknown. Definition 2. Let the morphism σ be defined by 0 7→ 001, 1 7→ 011. Thus, σ(0) = 001, σ 2 (0) = σ(σ(0)) = 001001011, and so on. Let the fixed point limm→∞ σ m (0) be called σ ∞ (0). Theorem 3. The infinite binary word σ ∞ (0) is the same as Stewart’s choral sequence.

1

Proof. The morphism σ is uniform, that is, the images of all letters have the same length, in this case, 3. Let the morphism σ be iterated at the word 0. Thus, σ m (0) = a(0)a(1) · · · a(3m − 1), where a(n) ∈ {0, 1} for 0 ≤ n ≤ 3m − 1, m ∈ Z∗ , and σ 0 (0) = 0. The morphism σ m+1 (0) maps a(n) to the letters a(3n)a(3n + 1)a(3n + 2), where 0 ≤ n ≤ 3m − 1. Since the morphism σ maps 0 to 001 and 1 to 011, then a(3n) = 0, a(3n + 1) = a(n), and a(3n + 2) = 1 for 0 ≤ n ≤ 3m − 1. The fixed point limm→∞ σ m (0) is the infinite word a(0)a(1) · · ·, where a(3n) = 0, a(3n + 1) = a(n), and a(3n + 2) = 1 for n ∈ Z∗ .

3

Characteristic Function

Definition 4. Let the infinite sequence {b(k)}∞ 0 be defined by  1, if ∃m, n ∈ Z∗ such that k = 3m+1 n + 21 (5 · 3m − 1) ; b(k) = 0, if ∃m, n ∈ Z∗ such that k = 3m+1 n + 21 (3m − 1) . Theorem 5. The sequence {b(k)}∞ 0 is the same as Stewart’s choral sequence.
Proof. Setting m = 0 in b 3m+1 n + 21 (3m − 1)
= 0 yields b(3n) = 0 for all n ∈ Z∗ . Setting m = 0 in b 3m+1 n + 12 (5 · 3m − 1) = 1 yields b(3n + 2) = 1 for all n ∈ Z∗ . To show that b(3n + 1) = b(n) for all n ∈ Z∗ , we first show that if b(n) = 1, then b(3n + 1) = 1, then we show that if b(n) = 0, then b(3n + 1) = 0. Suppose b(k) = 1 where k ∈ Z∗ . Then k = 3m+1 n +
21 (5 · 3m − 1) and 3k + 1 =
1 1 m m+1 5 · 3(m+1) − 1 for some m, n ∈ Z∗ . But by 3 3 n + 2 (5 · 3 − 1) + 1 = 3(m+1)+1 n + 2

Definition 4, b 3(m+1)+1 n + 21 5 · 3(m+1) − 1 = 1. Therefore b(3k + 1) = 1. Now suppose b(k)
= 0 where k ∈ Z∗ . Then k =
3m+1 n + 21 (3m − 1) and 3k + 1 = 3 3m+1 n + 21 (3m − 1) + 1 = 3(m+1)+1 n + 21 3(m+1) − 1 for some m, n ∈ Z∗ . But by Defini

tion 4, b 3(m+1)+1 n + 21 3(m+1) − 1 = 0. Therefore b(3k + 1) = 0.

4

Recurrence

Definition 6. Given a binary word with odd length w = c(0)c(1) · · · c(k − 1)c(k)c(k + 1) · · · c(2k) where c(k) ∈ {0, 1} for k ∈ Z∗ , we define w∗ as w∗ = c(0)c(1) · · · c(k − 1)c(k)c(k + 1) · · · c(2k) where c(k) = 0 if c(k) = 1 and c(k) = 1 if c(k) = 0. Note that if w = 0, then w∗ = 1. The word w∗ is w with the middle letter changed. Definition 7. Define a sequence of binary words by w(m+1) = w(m)w(m)w∗ (m) for m ∈ Z∗ and w(0) = 0. Let the resulting infinite word limm→∞ w(m) be called w(∞). Denote the length of the finite word w by |w|. Note that: 2

1. Since |w(0)| = 1 and |w(m + 1)| = 3|w(m)|, then |w(m)| = 3m . 2. The (k + 1)st letter of w(m), where 0 ≤ k ≤ 3m − 1, is also the (k + 1)st letter of w(m0 ), where m0 > m. Remark 8. For all m ∈ Z∗ , w(m + 1) = w(m) w(m) w∗ (m)
= c(0) · · · c 21 (3m − 1)
· · · c (3m − 1) c(0) · · · c 12 (3m − 1)
· · · c (3m − 1) c(0) · · · c 12 (3m − 1) · · · c (3m − 1)
= c(0) · · · c 21 (3m − 1) · · ·
c (3m − 1) c(3m ) · · · c 12 (3m+1 − 1) · · ·
c (2 · 3m − 1) c(2 · 3m ) · · · c 21 (5 · 3m − 1) · · · c (3m+1 − 1)
Lemma 9. c 21 (3m − 1) = 0 for all m ∈ Z∗


1 1 m+1 m Proof. From Remark 8, c 21 (3m − 1) = c (3 − 1) . For m = 0, c (3 − 1) = 2 2
1 m ∗ c(0) = w(0) = 0. Thus, c 2 (3 − 1) = 0 for all m ∈ Z .
Lemma 10. c 12 (5 · 3m − 1) = 1 for all m ∈ Z∗


Proof. From Remark 8, c 12 (3m −
1) = c 21 (5 · 3m − 1) .
By Lemma 9, c 21 (3m − 1) = 0 for all m ∈ Z∗ . Thus, c 21 (3m − 1) = 1 = c 12 (5 · 3m − 1) for all m ∈ Z∗ .
Lemma 11. c 3m+1 n + 12 (5 · 3m − 1) = 1 for all m, n ∈ Z∗ Proof. From Remark 8, c(k) = c (3m + k) if 3m ≤ 3m + k ≤ 3m+1 − 1 and 3m + k 6= 1 (5 · 3m − 1). That is, the only instance that c(k) 6= c (3m + k) for 0 ≤ k ≤ 2 · 3m − 1 is 2 when k = 12 (3m+1 − 1) (because then c(k) = 0 by Lemma 9 and c (3m + k) = 1 by Lemma 10). So if c(k) = 1 then c(k) = c (3m + k) = 1 for 0 ≤ k ≤ 2 · 3m − 1 and all m ∈ Z∗ . Also, if c(k) = 1 then c (3m+1 + k) = 1 for 0 ≤ k ≤ 2 · 3m+1 − 1 and all m ∈ Z∗ .
Now 1 m (5 · 3m − 1) = 52 ·3m − 21 < 6·3 −1 = 2·3m+1 −1 for all m ∈ Z∗ . Thus, if c
21 (5 · 3m − 1) = 1 2
then c 3m+1 + 12 (5 · 3m −
1) = 1 for all m ∈ Z∗ . But c 21 (5 · 3m − 1) = 1 by Lemma 10, so c 3m+1 + 21 (5 · 3m − 1) = 1 for all
m ∈ Z∗ .
Also, since c 3m+1 + 21 (5 · 3m − 1) = 1 then c
3m+1 + 3m+1 + 12 (5 · 3m − 1) = 1 for all m ∈ Z∗ , and so on. Thus, c 3m+1 n + 21 (5 · 3m − 1) = 1 for all m, n ∈ Z∗ .
Lemma 12. c 3m+1 n + 12 (3m − 1) = 0 for all m, n ∈ Z∗ . Proof. For all m ∈ Z∗ , w(m + 2) = w(m + 1) w(m + 1) w∗ (m + 1)

= c(0) · · · c 21 (3m − 1)
· · · · · · c 21 (3m+1 − 1)
· · · · · · c (3m+1 − 1) c(0) · · · c 12 (3m − 1)
· · · · · · c 21 (3m+1 − 1)
· · · · · · c (3m+1 − 1) c(0) · · · c 12 (3m − 1) · · · · · · c 21 (3m+1 − 1) · · · · · · c (3m+1 − 1)

= c(0) · · · c 12 (3m − 1) · · · · · · c 21
(3m+1 − 1) · · · · · · c (3
m+1 − 1) c(3m+1 ) · · · c 3m+1 + 12 (3m − 1) · · · ·
· · c 21 (3m+2 − 1) · · · · · · c
(2 · 3m+1 − 1) c(2 · 3m+1 ) · · · c 2 · 3m+1 + 12 (3m − 1) · · · · · · c 12 (5 · 3m+1 − 1) · · · · · · c (3m+2 − 1) 3




It can be seen that c 21
(3m − 1) = c 3m+1 + 21 (3m − 1) = c 2 · 3m+1 + 12 (3m − 1) . By Lemma 9, c 12 (3m − 1) = 0. Furthermore, since further iterations do not change these
1 m+1 m terms and ‘copies’ of these terms, c 3 n + 2 (3 − 1) = 0 for all m, n ∈ Z∗ . Theorem 13. The infinite binary word b(0)b(1)b(2) · · · is the same as w(∞). Proof. This follows from Lemmas 11 and 12. Corollary 14. The infinite binary word w(∞) is the same as Stewart’s choral sequence. Proof. This follows from Theorems 5 and 13.

References [1] I. Stewart, Mathematical recreations: The never-ending chess game, Scientific American, 273(4) (1995), 158, 160.

4