A Recursive Formula for the Kolakoski Sequence \underline{A000002}

Bertran Steinsky Fürbergstrasse 56 5020 Salzburg Austria

              steinsky@finanz.math.tu-graz.ac.at

Abstract We present a recursive formula for the nth term of the Kolakoski sequence. Using this formula, it is easy to find recursions for the number of ones in the first n terms and for the sum of the first n terms of the Kolakoski sequence.

1 Introduction

The Kolakoski sequence K_{n} [6, 7], which we study here, is the unique sequence starting with 1 which is identical to its own runlength sequence. K_{n} is Sloane’s sequence \underline{A000002}. Kimberling asks 5 questions about this sequence on his homepage [5]. The first one is, whether there exists a formula for the nth term of the Kolakoski sequence. For a survey of known properties of the Kolakoski sequence we refer to Dekking [4]. Cloitre wrote the formulas

K_{N} = \frac{3 + (−1)^{n}}{2} and K_{N+1} = \frac{3 − (−1)^{n}}{2} , where N = ∑_{i=1}^{n} K_{i},

in the entry of Sloane’s sequence \underline{A000002}, where we also find block-substitution rules, which where posted by Lagarias. I.e., starting with 22 we have to apply 22 → 2211, 21 → 221, 12 → 211, and 11 → 21, as it was mentioned by Dekking [3, 4]. Culik et al. [2] proposed the double substitution rules σ_{1}(1 → 1, 2 → 11) and σ_{2}(1 → 2, 2 → 22), which are applied alternatingly to each letter of a word. These substitutions can also be found at Allouche et al. [1, p. 336]. Cloitre added the relationship

f_{1}(n) + f_{2}(n) = 1 + ∑_{i=0}^{n−1} f_{2}(i)

to Sloane’s sequence \underline{A054349}, where f_{1}(n) denotes the number of ones and f_{2}(n) denotes the number of twos in the nth string of Sloane’s sequence \underline{A054349}.

2 A Recursive Formula for the Kolakoski Sequence

We will now derive a recursive formula for K_{n}. Let k_{n} = min {j : ∑_{i=1}^{j} K_{i} ≥ n}.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ K_{n} & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 2 \\ k_{n} & 1 & 2 & 2 & 3 & 3 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 9 & 9 & 10 \end{matrix}

Table 1: K_{n} and k_{n}

Lemma 2.1.

k_{n} = k_{n−1} + n − ∑_{i=1}^{k_{n−1}} K_{i}, where n ≥ 2.

Proof. We first notice that

n − 1 ≤ ∑_{i=1}^{k_{n−1}} K_{i} ≤ n.

The left inequality holds by definition and the right one is valid, since if

∑_{i=1}^{k_{n−1}} K_{i} ≥ n + 1

we would have

∑_{i=1}^{k_{n−1}−1} K_{i} ≥ n − 1

which is a contradiction to the minimality of k_{n−1}. So, as the first case, we consider ∑_{i=1}^{k_{n−1}} K_{i} = n − 1 which implies k_{n} = k_{n−1} + 1 = k_{n−1} + n − ∑_{i=1}^{k_{n−1}} K_{i}. In the second case ∑_{i=1}^{k_{n−1}} K_{i} = n leads to k_{n} = k_{n−1} = k_{n−1} + n − ∑_{i=1}^{k_{n−1}} K_{i}.

We notice that Lemma 2.1 holds in general for every sequence, whose only values are 1 and 2.

Lemma 2.2.

k_{n} = k_{n−1} + |K_{n} − K_{n−1}| = 1 + ∑_{i=2}^{n} |K_{i} − K_{i−1}|, where n ≥ 2.

Proof. The following well known construction produces a sequence which is identical to K. Start with K_{1} ones, continue with K_{2} twos, followed by K_{3} ones, and so on. In this construction, after k_{n−1} steps two cases can appear, as described in the proof of Lemma 2.1. The first possibility is that ∑_{i=1}^{k_{n−1}} K_{i} = n − 1, which means that we have constructed n − 1 terms of the sequence. Therefore, by construction, K_{n} must be different from K_{n−1} implying k_{n} − k_{n−1} = |K_{n} − K_{n−1}|. In the second case that ∑_{i=1}^{k_{n−1}} K_{i} = n, it is necessary that K_{k_{n−1}} = 2, for if otherwise ∑_{i=1}^{k_{n−1}−1} K_{i} = n − 1, contradicting the minimality of k_{n−1}. So our construction has added 2 equal numbers at the k_{n−1}th step, such that K_{n} = K_{n−1} and finally k_{n} − k_{n−1} = |K_{n} − K_{n−1}|. The second equality follows by induction.

Corollary 2.1 is an implication of Lemma 2.2. Corollary 2.1.

K_{n} ≡ k_{n} (mod 2) or K_{n} = \frac{(−1)^{k_{n}} + 1}{2} + 1 respectively.

Corollary 2.2 uses Lemma 2.1 and Corollary 2.1. Corollary 2.2.

k_{n} = n − \frac{1}{2} ∑_{i=1}^{k_{n−1}} ((−1)^{k_{i}} + 1) , where n ≥ 2.

Corollary 2.3 follows from Corollary 2.2. Corollary 2.3.

k_{n} = k_{n−1} + 1 − \frac{1}{2} (k_{n−1} − k_{n−2}) ((−1)^{k_{k_{n−1}}} + 1) , where n ≥ 3.

Theorem 2.1. For n ≥ 3 we have

K_{n} = K_{n−1} + (3 − 2K_{n−1}) (n − 1+∑_{j=2}^{n−1} |K_{j}−K_{j−1}| ; ∑ ; i=1 K_{i})  (1)

= K_{n−1} + (3 − 2K_{n−1}) (n − 1+∑_{j=2}^{n−1} \frac{K_{j} −K_{j−1}}{3−2K_{j−1}} ; ∑ ; i=1 K_{i})  (2)

= K_{n−1} + (3 − 2K_{n−1}) (1 − \frac{1}{2} \frac{K_{n−1} − K_{n−2}}{3 − 2K_{n−2}} (1 + (−1)^{K_{1+∑{n−1 \atop j=2} \frac{K_{j} −K_{j−1}}{3−2K_{j−1}}}} )) . (3)

Proof. From Lemma 2.1 and Lemma 2.2 we obtain

|K_{n} − K_{n−1}| = n − 1+∑_{j=2}^{n−1} |K_{j}−K_{j−1}| ; ∑ ; i=1 K_{i}

and use the fact that

|K_{n} − K_{n−1}| = \frac{K_{n} − K_{n−1}}{3 − 2K_{n−1}}

to complete the proof of (1) and (2). The third equation (3) follows from Corollary 2.3 and Lemma 2.2.

3 Concluding Remarks

Let s_{n} = ∑_{i=1}^{n} K_{i}, which is Sloane’s sequence \underline{A054353}, o_{n} = |\{1 ≤ j ≤ n : K_{j} = 1\}|, and t_{n} = |\{1 ≤ j ≤ n : K_{j} = 2\}|, which is Sloane’s sequence \underline{A074286}. With Theorem 2.1 and the equations

K_{n} = s_{n} − s_{n−1},
K_{n} = −o_{n} + o_{n−1} + 2, and
K_{n} = t_{n} − t_{n−1} + 1

it is easy to produce recursive formulas for s_{n}, o_{n}, and t_{n}.

By Lemma 2.1, we obtain k_{n} = n − t_{k_{n−1}}, from which it follows that t_{n}/n converges if and only if the limit of k_{n}/n exists. The definition of k_{n} gives the equations k_{s_{n}} = n and k_{s_{n}+1} = n + 1, which yield that the limit of k_{n}/n exists, if and only if s_{n}/n converges. Therefore, if we assume that one of the sequences t_{n}/n, o_{n}/n, k_{n}/n or s_{n}/n converges then all sequences have a limit. If a = lim_{n→∞} t_{n}/n then lim_{n→∞} o_{n}/n = 1 − a, lim_{n→∞} s_{n}/n = 1 + a, and lim_{n→∞} k_{n}/n = 1/(1 + a).

Using the recursion of Corollary 2.3, we computed k_{n}/n up to n = 3·10^{8}. Figure 1 shows k_{n}/n for n from 10^{8} to 3 · 10^{8}, where only each 1000th point is drawn, i.e., the subsequence k_{1000n}/(1000n), for n = 100000, …, 300000. The x-axis is positioned at 2/3.

Figure 1: \frac{k_{n}}{n} for n from 10^{8} to 3 · 10^{8}.

If we assume that the limit of o_{n}/n exists and is equal to 1/2 then k_{n}/n must tend to 2/3. Thus, the graph in Figure 1 does not support the conjecture that o_{n}/n converges to 1/2.

4 Acknowledgement

We thank the referees for fruitful suggestions and Benoit Cloitre for helpful email discussion.

References

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

[2] K. Culik, J. Karhumäki, Iterative devices generating infinite words, Lec. Notes in Comp. Sc. 577 (1992), 531–544.

[3] F. M. Dekking, Regularity and irregularity of sequences generated by automata, Sém. Th. Nombres Bordeaux ‘79-‘80 (1980), 901–910.

[4] F. M. Dekking, What is the long range order in the Kolakoski sequence?, The Mathematics of Long-Range Aperiodic Order, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 489, Kluwer Acad. Publ., Dordrecht (1997), 115–125.

[5] C. Kimberling, http://faculty.evansville.edu/ck6/integer/index.html

[6] W. Kolakoski, Problem 5304: Self Generating Runs, Amer. Math. Monthly 72 (1965), 674.

[7] W. Kolakoski, Problem 5304, Amer. Math. Monthly 73 (1966), 681–682.

2000 Mathematics Subject Classification: Primary 11B83; Secondary 11B85, 11Y55, 40A05. Keywords: Kolakoski sequence, recursion, recursive formula.

(Concerned with sequences \underline{A000002}, \underline{A054349}, \underline{A054353}, and \underline{A074286}.)

Received January 13 2006; revised version received August 19 2006. Published in Journal of Integer Sequences, August 19 2006.

Return to Journal of Integer Sequences home page.