1. Introduction

The Kolakoski sequence ^[13], with named so in 1965 but used for the first time in 1935 by Oldenburger ^[16], is the unique sequence beginning with 1 and which is invariant by the run-length encoding operation It starts as follows: 12211212212211211221211…. This sequence is also known as the Sloane’s sequence A000002 ^[17]. It has been investigated by many authors using different technics (see ^{[1, 3, 5, 4, 7, 20, 21, 22]} for instance). In particular, Kimberling ^[12] asked many questions about this sequence. We try here to find the way to give answers to the two most known of them: The first, is asking whether the density of the letter 2 in the word defined by

has an asymptotic limit when n goes to ∞ ? and if this limit exists, is it equal to 1/2 ? This question is also known as the Keane’s conjecture ^[11]. Shallit ^[18] classified this question in the twelfth position in his list of some Open Problems in concern with the automatic sequences. No answer to this attractive question has been given until now. Chvàtal ^[6], used the structure of some special graphs and established that

Kupin ^[14], used the Gouldon-Jackson’s method and obtain

Bordellès ^[2], applied the Dirichlet’s pigeonhole principle and got a better bound:

In this paper, we will present a recursive formula connecting the density of 2’s with some differences between terms of even and odd indices. This formula seems to support Keane’s conjecture.

The second question we investigate here, looks for an explicit expression of the term Steinsky ^[23] and Fédou ^[9] found two equivalent recursive formulas which give according to Using an inductif argument, Bordellès ^[2] presented a relation between and defined by: We will try, in this paper, to improve these results by reducing the number of data we need to compute We shall use a certain smaller than Furthermore, we derive a simple expression of using this time, the integer part of the truncated rational .

2. Notation

We first introduce some definitions and notation:

Let be the input alphabet set and let be the set of all finite words over We let denote the run-length encoding operator, such that if is an element of then will be the new word containing lengths of blocs of similar digits, in the initial word As an example,

We now define the two useful primitives and in the same way than Oldenburger ^[16], Sing ^{[20, 21]}, Dekking ^[8], Fédou ^[9] and Huang ^[10] by:

If is an element of then (resp ) will be the unique word starting from the left by 1 (resp ), consisting of, exactly elements and satisfying the encoding condition: For instance, and As a consequence, if we let denote, for every the word then Here, is the partial sum and also the Sloane’s sequence A054353 defined by:

and as it has been used by Bordellès ^[2]. Therefore, the infinite Oldenburger-Kolakoski word can be seen as a fixed point of the function Shallit ^[19] has defined K as a fixed point of some extendable homomorphism, such as on 12, since we can write:

More generally, for every , we can extend as follows:

Table 1. How the 1’s of W_n are transformed by Δ₁^-1

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View next table

Table 2. How the 2’s of W_n are transformed by Δ₁^-1

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

View next table

We also need to define the double sequence by :

On the other hand, for each and we associate the set of elements in such that:

for We will write in a symbolic way, what we call the index notation:

The existence of is supported by Theorem 2 below. We also define the cardinals:

As an example, we have and

In the end, let us remark that, when we integrate by applying , every letter of this word, will be transformed in a bloc whose the index of the last element is as illustrated by Table 1 and Table 2. More generally, after each integration using , each will give a bloc whose last element, in the extreme right, is .

3. A Recursive Formula for the Density of 2’s in the Kolakoski Sequence

We now begin by presenting a useful connection between , the density of 2’s in the word , and some linear combination of

Lemma 1. For every :

Proof. For the first, there are two cases: if is even, then the number of odd indices in is equal to the number of even ones. If is odd, the number of odd indices is greater than the evens since the first term has an odd index. We will refer to this equation by “the index balance sheet in ”.

We write now the same equation for :

As the elements of are created by the integration of using the operator, this balance sheet equation, will not take into account the blocs of two similar elements in since they consist of an odd and an even index and do not have any impact on the balance sheet of indices. So, only the elements created by 1’s, as illustrated by Table 1 and Table 2, similar to those used by Nilsson ^[15] to perform his algorithm, will be useful in the final equation. This restriction allows us to get the desired equation. To prove the third relation, We just write the “index balance sheet” for just after eliminating all the blocs whose number of elements is even.

Theorem 2. for all we have

Proof. Let be an integer ≥ 1.

We begin by making useful connections between the four sequences:

and which represent respectively, the number of 2s in the word the number of 1s, the density of 2s and the partial sum

Using the fact that We find that

which becomes as follows:

Bordellès et Al. ^[2], proved this equation using an induction on . We now use the index notation and get:

The proof is finally achieved, by using the index balance sheet equation for , given in Lemma 1. For the third equality, we replace by in the second equation to obtain:

If we take now a look at the second line of Table 1 and Table 2, we can see that, only blocs of single 1’s in have to be taken into account. The conclusion is then, easily derived. To prove the fourth, We replace this time, by and find:

Finally, a quick look at the third line of Table 1 and Table 2 gives the expected result.

As a conclusion, we proved that, for each we can compute and so on, only from some elements between and This possibility is the answer to the existence of the sequence

Corollary 3. For each integer n ≥ 1 fixed and i ≥ 0, we define the following sequences by:

Then, Theorem 2 allows us to write:

1.

2.

3.

4.

More generally, we can show by induction that for each

The two coefficients and take quickly changing values and signum.

On the other hand, for enough great integer i, we have

and

Hence, the sequence increases at least exponentially. Finally, as a conclusion, we can say that the answer to Keane’s conjecture, depends on the signum of the sequence If this signum is always changing, it means that the sequence has no limit or goes to zero, i.e., the frequency of 2’s goes to .

4. A New Formula for the n^th Term K_n

At first, we will present a simple recursive formula, which computes from the input values, and

In the second part of this section, we will try to improve this result.

Lemma 4. For every integer

Proof. We consider the decimal numbers defined by :

for every Hence, by integration using the operator we find a new rational :

also given by

and then, using the fact that the Kolakoski-Oldenburger constant , is a fixed point of , we will have

from which we extract the digit using the integer part: [ ].

In the end, let us remark that this recursive computation of , depicted of its interesting mathematical side, takes too much time and obviously need to be improved.

Lemma 5. For every n ≥ 2, there exist two unique integers p and q, both > 0 such that:

Proof. Let be an integer and assume that for every Then, in the best case, there will exist and This is not possible since

For the second, the basics of he proof come from the following two cases: for each and then or , which gives

We will now derive a second recursive formula for using less input parameters.

Theorem 6. Let and let be the unique integer, such that

Then we have if

if and

if

Proof. For each let us remember that

Using the integration operator we obtain

and

When goes to infinity, the three series , and , converge absolutely to the same limit , namely, the Oldenburger-Kolakoski constant 0, 1221121221..... . So, by identification of the coefficients in the base, we derive the expression of , according to the value of the difference

We now try to simplify the expressions we got above.

Theorem 7. Let and let be the unique integer, such that: then,

Proof. We separate the three cases: or 2 or 3 and use Table 1 and Table 2. We find almost easily that if then and if then These two conditions can be replaced by

Finally, to include also the almost trivial case we unify all the expressions in the following unique one:

Download as

• PPT
  PowerPoint Slide
• PNG
  Larger image(png format)

Veiw figureFigures index

•  NEW
  View larger figure in new window

Figure 1. Signum variation of the product for different values of n

Table 3. Comparison between n,k_n and k_n'

Download as

PowerPoint Slide

Larger image(png format)

• Tables index

Veiw figure

View current table in a new window

View previous table

5. Concluding Remarks

Our attempt to respond to the Keane’s conjecture, does not allow us to give a final answer. However, the Corollary 3 seems clearly to support this hypothesis, since, in the left-hand side of its equations, the term increases at least exponentially with while the right hand side does not and can not have a constant signum as illustrated by the graph in Figure 1. It contains a complicated linear combination of terms which are generated nearly randomly by the integration operator as seen in Corollary 3. In the future, we will focus our work, to investigate deeply this last assertion. On the other hand, to answer the question about the explicit expression of term let us begin by saying that the self-describing nature of the Oldenburger-Kolakoski sequence, makes it impossible to predict from only. What we can just do, is to give an expression of according to where p is as smaller as we can. We have shown that, we can take verifying This value is clearly smaller than, found by Steinsky ^[23] and presented by Bordellès ^[2]. We will try to improve this result by looking for simple expressions and much smaller values of like those satisfying with In this case, will be not far from as illustrated in Table 3.

Acknowledgments

The author would like to thank the referees for their careful reading of the manuscript and the fruitful suggestions they provided, and Assim for helpful discussion.

References

[1]	J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge Univ. Press, Cambridge, 2003.
	In article		View Article
[2]	O. Bordellès and B. Cloitre, Bounds for the Kolakoski Sequence, Journal of Integer Sequences, Vol. 14 (2011).
	In article
[3]	S. Brlek, S. Dulucq, A. Ladouceur, and L. Vuillon, Combinatorial properties of smooth infinite words, Theor. Comp. Sci. 352 (2006), 306-317.
	In article		View Article
[4]	K. Culik, J. Karhumäki, Iterative devices generating infinite words, Lec. Notes in Comp. Sc. 577 (1992), 531-544.
	In article
[5]	A. Carpi, On repeated factors in C∞-words, Inf. Process. Lett. 52 (1994), 289-294.
	In article		View Article
[6]	V. Chvàtal, Notes on the Kolakoski sequence, DIMACS Technical Report, 93-84. (1994).
	In article
[7]	The Kolakoski Transform of words, Inf. Process. Lett. 52 (1994), 289-294.
	In article		View Article
[8]	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 Maths. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht (1997), 115-125.
	In article
[9]	J. M. Fédou and G. Fici, Some Remarks on Differentiable Sequences and Recursivity, Journal of Integer Sequences, Vol. 13 (2010).
	In article
[10]	Y. Huang, The Complexity of Cbω-words of the form ωχω, Theoritical Computer Science, Vol. 410 (2009), 4892-4904.
	In article		View Article
[11]	Keane and C. Series (eds.), Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 1991, pp. 35-70.
	In article
[12]	C.Kimberling,https://faculty.evansville.edu/ck6/integer/index.html.
	In article
[13]	W. Kolakoski, Problem 5304: Self Generating Runs, Amer. Math. Monthly 72 (1965), 674.
	In article
[14]	E. J. Kupin and E. S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, arXiv:0809.2776 [math. CO] Sept 16, 2008.
	In article
[15]	F. M. Dekking, What is the long range order in the Kolakoski sequence?, The Mathematics of Long-Range A eriodic Order, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 489, Kluwer Acad. Publ., Dordrecht (1997), 115-125.
	In article
[16]	Rufus Oldenburger, Exponent trajectories in symbolic dynamics, Trans Amer. Math. Soc. 46 (1939), 453-466.
	In article		View Article
[17]	N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically at https://oeis.org.
	In article
[18]	J. Shallit, Open Problems in Automata Theory:An Idiosyncratic View, School of Computer Science.
	In article
[19]	J. Shallit, Emerging Applications of Number Theory. Springer Verlag Coll. The IMA Volumes in Ms and its Applications (n◦ 109), (1999), 547-570.
	In article
[20]	B. Sing, More Kolakoski sequences, Integers A14, 11B (2011).
	In article
[21]	B. Sing, Spektrale Eigenschaften der Kolakoski-Sequenzen, Diploma thesis, Universit¨at T¨ubingen, (2002).
	In article
[22]	R. Steacy. Structure in the Kolakoski sequence. Bull. European Assoc. Theor. Comput. Sci., No. 59, (1996), 173-182.
	In article
[23]	B. Steinsky, A recursive formula for the Kolakoski sequence, J. Integer Seq. 9 (2006), Article 06.3.7.
	In article