Some Remarks on Differentiable Sequences and Recursivity

Jean-Marc Fédou and Gabriele Fici^{1}

Laboratoire d’Informatique, Signaux et Systèmes de Sophia-Antipolis

UMR6070 - CNRS et Université de Nice-Sophia Antipolis 2000, route des Lucioles 06903 Sophia-Antipolis Cedex France

                    fedou@i3s.unice.fr
                    fici@i3s.unice.fr

Abstract We investigate the recursive structure of differentiable sequences over the alphabet

{1, 2}. We derive a recursive formula for the (n + 1)-th symbol of a differentiable sequence, which yields to a new recursive formula for the Kolakoski sequence. Finally, we show that the sequence of absolute differences of consecutive symbols of a differentiable sequence u is a morphic image of the run-length encoding of u.

1 Introduction

In 1965, W. Kolakoski [9] proposed the following problem:

“Describe a simple rule for constructing the sequence:

K = 12211212212211211221211212211211212212211212212 ⋯

What is the n-th term? Is the sequence periodic?” This sequence, called now the Kolakoski sequence, is in fact the unique sequence starting

with 1 and identical to its own run-length encoding.

The Kolakoski sequence has been investigated in many papers [1, 3–8, 10–13]. Although the non-periodicity of the sequence was shown immediately, the problem of finding a good formula for the n-th term is still open, and is related to other open problems. The most famous open problems on the Kolakoski sequence (up to now) are as follows: Is the sequence recurrent? Is the frequency of 1’s and 2’s asymptotically the same? Is the set of factors of the sequence closed under reversal and/or swap of the symbols?

1The second author acknowledges the support of an Exchange Grant on the program “AutoMathA:

Automata, from Mathematics to Applications” of the European Science Foundation.

The Kolakoski sequence K (sequence \underline{A000002} in Sloane’s database) and the sequence k (sequence \underline{A078880}) obtained from the former by deleting the first symbol are the unique fixed point of the run-length encoding operator Δ. A sequence u over the alphabet {1, 2} such that Δ(u) is still a sequence over {1, 2} is called a differentiable sequence. The problems stated above for the Kolakoski sequence remain unsolved for the wider class of sequences that are differentiable arbitrary many times, called smooth sequences [1,2].

In this paper we study the recursive relationship between any differentiable sequence u and its run-length encoding Δ(u). We start by defining, for any differentiable sequence u, the sequences φ_{n}(u) and γ_{n}(u). The sequence φ_{n}(u) is defined by φ_{n}(u) = |Δ(u_{1}u_{2} ⋯ u_{n})|. In other words, φ_{n}(u) is equal to 1 plus the number of symbol changes in u_{1}u_{2} ⋯ u_{n}. The sequence γ_{n}(u) is defined by γ_{n}(u) = |u_{n+1} − u_{n}|.

The sequences φ_{n}(K), φ_{n}(k) and γ_{n}(K) are known (sequences \underline{A156253}, \underline{A156351}, and \underline{A156728} respectively).

Remark 1. We shall write φ_{n}, γ_{n} instead of φ_{n}(u), γ_{n}(u) when no confusion arises.

In Theorem 3.1 we derive a recursive formula for γ_{n}

γ_{n} = 1 − (u′_{φ_{n}} − 1)γ_{n−1}

where u′ = Δ(u). This formula yields to recursive formulas for u and φ(u) (Corollaries 3.2 and 3.3)

u_{n+1} = 3 − u_{n} + (u′_{φ_{n}} − 1)(u_{n} − u_{n−1})
φ_{n+1} = φ_{n} + 1 − (u′_{φ_{n}} − 1)(φ_{n} − φ_{n−1})

When u = K_{1}K_{2} ⋯ is the Kolakoski sequence, our recursive formula gives

K_{n+1} = 3 − K_{n} + (K_{φ_{n}} − 1)(K_{n} − K_{n−1})

A different approach allows us to derive an alternative recursive formula for the n + 1-th term of a differentiable sequence. Indeed, in Theorem 3.4, we prove that

u_{n+1} = u_{n} + (3 − 2u_{n}) (n + 1 − ∑_{i=1}^{φ_{n}} u′_{i})

When u is the Kolakoski sequence, this latter formula is equivalent to one of Steinsky [13], obtained with different techniques.

As a last result, in Lemma 3.5, we show that for any differentiable sequence u, the sequence γ_{n} is a morphic image of the sequence Δ(u), under the morphism μ : 1 ↦ 1, 2 ↦ 01.

2 Differentiable sequences

An alphabet, denoted by Σ, is a finite set of symbols. A sequence over Σ is a sequence of symbols from Σ. The length of a finite sequence u is denoted by |u|. A right-infinite sequence over Σ is a non-ending sequence of symbols from Σ. Formally, a right-infinite sequence is a function f : ℕ ⟼ Σ. For an abuse of notation, we shall often write f_{n} for f(n).

A run in a sequence u is a maximal block of consecutive identical symbols.

Let u be a sequence over Σ. Then u can be uniquely written as a concatenation of consecutive runs of the symbols of Σ, i.e. u = x_{1}^{i_{1}}x_{2}^{i_{2}}x_{3}^{i_{3}} ⋯, with x_{j} ∈ Σ, x_{j} ≠ x_{j+1} and i_{j} > 0. The run-length encoding of u, noted Δ(u), is the sequence of exponents i_{j}, i.e. Δ(u) = i_{1}i_{2}i_{3} · · ·.

Remark 2. From now on we set Σ = {1, 2}.

We say that a sequence u over Σ is differentiable if Δ(u) is still a sequence over Σ. Since Σ = {1, 2} we have that u is differentiable if and only if neither 111 nor 222 appear in u.

In the sequel we note Δ(u) = u′_{1}u′_{2} ⋯ for u a differentiable sequence.

Definition 2.1. A right-infinite sequence u over Σ is a smooth sequence if it is differentiable arbitrary many times over Σ.

The most famous examples of smooth sequences are the Kolakoski sequences:

k = 2211212212211211221211212211211212212211212212 ⋯

and

K = 1k = 12211212212211211221211212211211212212211212212 ⋯

which are the fixed points of Δ.

The following lemma is a straightforward consequence of the definition of Δ.

Lemma 2.1. Let uv be a differentiable sequence. Then Δ(uv) = Δ(u)Δ(v) if and only if the last symbol of u and the first symbol of v are different.

Let u = u_{1}u_{2}u_{3} ⋯ be a finite or infinite sequence over Σ. We define the two functions Δ_{1}^{−1} and Δ_{2}^{−1} by:

Δ_{1}^{−1}(u) = 1^{u_{1}}2^{u_{2}}1^{u_{3}} ⋯
Δ_{2}^{−1}(u) = 2^{u_{1}}1^{u_{2}}2^{u_{3}} ⋯

In such a way, u = Δ(Δ_{x}^{−1}(u)) for any x ∈ Σ.

Remark 3. Let u = u_{1}u_{2} ⋯ u_{n} be a sequence over Σ. Then for every x ∈ Σ

|Δ_{x}^{−1}(u_{1}u_{2} ⋯ u_{n})| = ∑_{i=1}^{n} u_{i}

3 Recursivity

Let u = u_{1}u_{2} ⋯ be a differentiable sequence. We define, for every n > 0

φ_{n}(u) = |Δ(u_{1}u_{2} ⋯ u_{n})|

The definition of Δ directly implies that φ_{n}(u) is equal to 1 plus the number of symbol changes in u_{1}u_{2} ⋯ u_{n}. With our notation:

φ_{n}(u) = φ_{n−1}(u) + |u_{n} − u_{n−1}| = 1 + ∑_{i=1}^{n−1} |u_{i+1} − u_{i}|  (1)

for every n > 1.

We also define, for every n > 0

γ_{n}(u) = |u_{n+1} − u_{n}|

Example 1. The sequences φ_{n}(K), φ_{n}(k) and γ_{n}(K) are present in the Sloane’s database as sequence \underline{A156253}, \underline{A156351}, and \underline{A156728} respectively. The first values of these sequences are reported in Table 1.

Let u = u_{1}u_{2} ⋯ be a (right infinite) differentiable sequence and let u′ = Δ(u) = u′_{1}u′_{2} ⋯ be its run-length encoding. For any n > 0 the two sequences Δ(u_{1}u_{2} ⋯ u_{n}) and u′_{1}u′_{2} ⋯ u′_{φ_{n}} are equal if and only if u_{n+1} ≠ u_{n}, as a consequence of Lemma 2.1. If instead u_{n} = u_{n+1} then u_{n} ≠ u_{n−1} since u is differentiable, and hence the last symbol of Δ(u_{1} ⋯ u_{n}) is equal to 1, while u′_{φ_{n}} = 2.

In other words, if u_{n} = u_{n−1} then clearly u_{n+1} ≠ u_{n} since u is differentiable. If instead u_{n} ≠ u_{n−1} then u_{n+1} = u_{n} when u′_{φ_{n}} = 2, while u_{n+1} ≠ u_{n} when u′_{φ_{n}} = 1. We thus have

Theorem 3.1. Let u = u_{1}u_{2} ⋯ be a differentiable sequence. Then for every n > 0

γ_{n} = 1 − (u′_{φ_{n}} − 1)γ_{n−1}  (2)

Remark 4. Since Σ = {1, 2}, one has that, ∀x, y ∈ Σ, y = x + (3 − 2x)|y − x|. From the previous remark and from Equation 2 we have

Corollary 3.2. Let u = u_{1}u_{2} ⋯ be a differentiable sequence. Then for every n > 0

u_{n+1} = 3 − u_{n} + (u′_{φ_{n}} − 1)(u_{n} − u_{n−1})  (3)

And from Equations 1 and 2 we derive

Corollary 3.3. Let u = u_{1}u_{2} ⋯ be a differentiable sequence. Then for every n > 0

φ_{n+1} = φ_{n} + 1 − (u′_{φ_{n}} − 1)(φ_{n} − φ_{n−1})  (4)

Example 2. When u is the Kolakoski sequence K, Equation 3 gives

K_{n+1} = 3 − K_{n} + (K_{φ_{n}} − 1)(K_{n} − K_{n−1})  (5)

We now give another recursive formula for the n+1-th symbol of a differentiable sequence.

Theorem 3.4. Let u = u_{1}u_{2} ⋯ be a differentiable sequence. Then for every n > 0

u_{n+1} = u_{n} + (3 − 2u_{n}) (n + 1 − ∑_{i=1}^{φ_{n}} u′_{i})  (6)

Proof. If u_{n} = u_{n+1} then φ_{n} = φ_{n+1}, so Δ_{u_{1}}^{−1}(u′_{1} ⋯ u′_{φ_{n}}) = Δ_{u_{1}}^{−1}(u′_{1} ⋯ u′_{φ_{n+1}}) = u_{1}u_{2} ⋯ u_{n+1}. Hence, by Remark 3, ∑_{i=1}^{φ_{n}} u′_{i} = n + 1.

If instead u_{n} ≠ u_{n+1} then, by Lemma 2.1, Δ(u_{1} ⋯ u_{n}) = u′_{1} ⋯ u′_{φ_{n}}, which implies that Δ_{u_{1}}^{−1}(u′_{1} ⋯ u′_{φ_{n}}) = u_{1}u_{2} ⋯ u_{n}. Hence, again by Remark 3, ∑_{i=1}^{φ_{n}} u′_{i} = n.

Thus

|u_{n+1} − u_{n}| = n + 1 − ∑_{i=1}^{φ_{n}} u′_{i}

The claim then follows from Remark 4.

Example 3. For u = K, Equation 6 becomes

K_{n+1} = K_{n} + (3 − 2K_{n}) (n + 1 − ∑_{i=1}^{φ_{n}} K_{i})  (7)

Equation 7 can be found in a paper of Steinsky [13], where φ_{n}(K) is replaced by ρ_{n}(K) = min {j : ∑_{i=1}^{j} K_{i} ≥ n}. But it is easy to see that for any differentiable sequence u one has

φ_{n} = min {j : ∑_{i=1}^{j} u′_{i} ≥ n}.

We now show that, for any differentiable sequence u, the sequence γ_{n}(u) is a morphic image of the sequence Δ(u).

Lemma 3.5. Let μ be the morphism defined on Σ by

μ : \{ \begin{matrix}1 & ⟼ 1 \\ 2 & ⟼ 01 \end{matrix}

and let v_{n} be the sequence μ(Δ(u)). Then v_{n} = γ_{n}.

Proof. It is sufficient to prove that the sequences v_{n} and γ_{n} have the same partial sums. We have two cases: Case 1. u_{n} ≠ u_{n+1}. Then, by Lemma 2.1, Δ(u_{1} ⋯ u_{n}) = u′_{1} ⋯ u′_{φ_{n}}. From the definition of μ, one has ∑_{i=1}^{n} v_{i} = |u′_{1} ⋯ u′_{φ_{n}}| = φ_{n}.

Case 2. u_{n} = u_{n+1}. This implies that u′_{φ_{n}} = 2 and so ∑_{i=1}^{n} v_{i} = ∑_{i=1}^{n−1} v_{i}. On the other hand, we must have u_{n−1} ≠ u_{n} and therefore, arguing as in Case 1, we obtain ∑_{i=1}^{n−1} v_{i} = |u′_{1} ⋯ u′_{φ_{n−1}}| = φ_{n−1} = φ_{n} − 1.

In summary, we have ∑_{i=1}^{n} v_{i} = φ_{n} − 1 + γ_{n}.

On the other hand, by Equation 1, we have ∑_{i=1}^{n} γ_{i} = ∑_{i=1}^{n−1} γ_{i} + γ_{n} = φ_{n} − 1 + γ_{n}.

4 Conclusion

The main purpose of this paper was to unify the description of various sequences described in the Sloane’s database and related to the Kolakoski sequence. We showed that, indeed, all these sequences or recurrences can be easily deduced from more general equalities holding for any differentiable sequence. Unfortunately, it appears that all these results are finally only another way to write the definition of differentiability of a sequence over the alphabet {1, 2}. Thus, the challenge to find a formula for the n-th symbol of the Kolakoski sequence without the knowledge of the preceding symbols is still open.

Table 1: First values of the sequences K, φ(K), φ(k), γ(K), corresponding, respectively, to Sloane’s database entries \underline{A000002}, \underline{A156253}, \underline{A156351}, and \underline{A156728} .

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ K & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & 2 & 1 & 1 & 2 & 1 & 1 & 2 & 2 & 1 & 2 & 1 & 1 & 2 & 1 \\ φ(K) & 1 & 2 & 2 & 3 & 3 & 4 & 5 & 6 & 6 & 7 & 8 & 8 & 9 & 9 & 10 & 11 & 11 & 12 & 12 & 13 & 14 & 15 & 15 & 16 & 17 \\ φ(k) & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 5 & 6 & 7 & 7 & 8 & 8 & 9 & 10 & 10 & 11 & 11 & 12 & 13 & 14 & 14 & 15 & 16 & 17 \\ γ(K) & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \end{matrix}

References

[1] S. Brlek and A. Ladouceur. A note on differentiable palindromes. Theor. Comput. Sci. 302 (1–3) (2003), 167–178.

[2] S. Brlek, S. Dulucq, A. Ladouceur, and L. Vuillon. Combinatorial properties of smooth infinite words. Theor. Comput. Sci. 352 (1) (2006), 306–317.

[3] A. Carpi. Repetitions in the Kolakovski [sic] sequence. Bull. European Assoc. Theor. Comput. Sci., No. 50, (1993), 194–196.

[4] A. Carpi. On repeated factors in C^{∞}-words. Inform. Process. Lett. 52 (1994), 289–294.

[5] V. Chvátal. Notes on the Kolakoski sequence. Technical Report 93-84, DIMACS, March 1994. Revised.

[6] K. Culik II, J. Karhumäki, and A. Lepistö. Alternating iteration of morphisms and the Kolakovski [sic] sequence. In G. Rozenberg and A. Salomaa, editors, Lindenmayer Systems, pp. 93–103. Springer-Verlag, 1992.

[7] F. M. Dekking. What is the long range order in the Kolakoski sequence? In R. V. Moody, editor, The Mathematics of Long-Range Aperiodic Order, Vol. 489 of NATO ASI Ser., Ser. C., Math. Phys. Sci., pp. 115–125. Kluwer, 1997.

[8] C. Kimberling. Advanced problem 6281. Amer. Math. Monthly 86 (1979), 793.

[9] W. Kolakoski. Elementary problem 5304. Amer. Math. Monthly 72 (1965), 674. Solution in Amer. Math. Monthly 73 (1966), 681–682.

[10] A. Lepistö. Repetitions in Kolakoski sequence. In G. Rozenberg and A. Salomaa, editors, Developments in Language Theory, pp. 130–143. World Scientific, 1994.

[11] G. Paun. How much Thue is Kolakovski [sic]? Bull. European Assoc. Theor. Comput. Sci., No. 49, (February 1993), 183–185.

[12] R. Steacy. Structure in the Kolakoski sequence. Bull. European Assoc. Theor. Comput. Sci., No. 59, (1996), 173–182.

[13] B. Steinsky. A recursive formula for the Kolakoski sequence \underline{A000002}. J. Integer Seq. 9 (3) (2006), Article 06.3.7.

2010 Mathematics Subject Classification: Primary 68R15; Secondary 11Y55, 11B83. Keywords: Kolakoski sequence, integer sequences, differentiable sequences, smooth sequences, combinatorics of words.

(Concerned with sequences \underline{A000002}, \underline{A078880}, \underline{A156253}, \underline{A156351}, and \underline{A156728}.)

Received December 8 2009; revised version received February 25 2010. Published in Journal of Integer Sequences, February 25 2010.

Return to Journal of Integer Sequences home page.