We investigate here the Oldenburger-Kolakoski sequence 
with K1=1. In the first part, we give some expressions of the discrepancy function δ(n) representing the difference between 2s and 1s in K1K2…Kn. The discrepancy could be interpreted as a perturbation of a certain equilibrium. Our main result is a necessary and sufficient condition for the existence of the asymptotic density. In the last section, we present an algorithm to generate the sequence terms and a formula for the term Kn.
The Kolakoski sequence 
with 
defines the unique infinite word 
which does not change by the Run Length Encoding operator 
It starts like this: 122112122122112... Many questions asked by Kimberling 2 about this sequence, are still open. For example, it is conjectured by Keane 1 that asymptotically, there is as many one’s as two’s, which means that the limiting density of 2s is 
Other information in concern with this sequence can be found in the Sloane’s OEIS 3.
We now introduce some definitions and notation.
We let 
and 
denote respectively the run-length encoding operator, defined by the following example, 
and its inverse. The Kolakoski infinite 
word can be seen at the same time as a fixed point of 
and of 
for 
The density of 2s in 
is given by
 |
We define the successive partial sums by
 |
and
 |
We will use the following cardinals 
and 
are respectively the numbers of 1s and 2s in 
and 
with 
having respectively the same parity than 
For instance,
= is the number of 2s in 
with even indices.
is the number of 1s in 
with even index and odd partial sum.
is the number of 2s in 
with even index j, odd partial sum 
and even 
The discrepancy function 
represents the difference between the number of 2s and the number of 1s in the word 
It can be expressed as follows
 |
Proposition 1.
 |
 |
 |
Proof. If we replace 
by 
in the expression of 
use the fact that
 |
we get
 |
 |
 |
From here, we conclude that if the limiting density 
exists and is not 
then the discrepancies 
and 
should have the same sign for large enough n.
In this section, we will consider the integers n such that 
are even
Proposition 2.
 |
 |
Proposition 3.
 |
 |
Proposition 4.
 |
 |
The proof of these propositions is based on the identity 
where we replace 
by 
and 
The discrepancy function can be seen as perturbation of some equilibrium. Hence, 
and 
are three perturbations of three equilibriums and there is no reason they will have same sign. The change of the sign of the discrepancy means that if the density 
has a limit, it will be 
Let 
and 
be the respective densities of 
and 
in 
Proposition 5.
 |
 |
In particular,
 |
Proof. Using the definition of the 2s density, we have
 |
but 
thus
 |
If we assume that the asymptotic density exist and 
, then, as a subsequence, we should have 
and consequently
 |
On the other hand
 |
By the same, we will have
 |
which gives the condition
 |
A natural way to generate the sequence 
is the one based on a first integration using the inverse run-length encoding operator 
The blue ones create ones while the red ones create twos. The blue twos will generate blocs of two ones and the red twos will give blocs of two twos.
 |
 |
To make the algorithm faster, we will use the third integration defined by 
This is illustrated as follows
 |
 |
For 
the multi-run generated by 
after three integrations, will depend on the parity of 
and 
Its length will be 
We can improve the speed of the algorithm with the 
integration but the computations become complex.
 |
 |
So, with 
if we know 
we can generate 
where 
Lemma 6. For every 
 |
 |
Proof. By definition, we have
 |
replacing n by 
we get 
and 
Using the expression of 
given above, the difference yields to
 |
If we replace again n by 
the first identity becomes
 |
which yields to
 |
and finally gives
 |
Proposition 7. Let 
and p the unique integer such that
 |
If we assume known the terms 
then, using the recursive formulas above, we can compute 
and 
and predict the word generated by 
represented by the number 
after three integrations. The difference 
gives the position and the following value of 
 |
Where 
is a number which depends on the parity of 
and 
as illustrated by the table below.
The question about the existence of the limiting density is still unanswered. We just replaced it by an equivalent one concerning the density of even twos. The expressions of the discrepancy presented here show the complexity of Kolakoski sequence and justify why the answer to Keane conjecture is not easy. We believe that is not possible to have an explicit expression of the 
term 
All one can do, is to find 
from some previous terms 
with 
as small as possible. We proved that 
improving the former result 
In the end, the advantage of the algorithm used to generate 
is that, it could be easily generalized and made faster and faster.
The author would like to express his gratitude to the referees for their careful reading of the manuscript and for giving me some of their precious time. I also thank some of my friends for fruitful discussions.
| [1] | Keane and C. Series (eds.), Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 1991, pp. 35-70. | ||
| In article | |||
| [2] | C.Kimberling,http://faculty.evansville.edu/ck6/integer/index.html. | ||
| In article | View Article | ||
| [3] | N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically at http://oeis.org. | ||
| In article | View Article | ||
Published with license by Science and Education Publishing, Copyright © 2018 Abdallah Hammam
This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit
http://creativecommons.org/licenses/by/4.0/
| [1] | Keane and C. Series (eds.), Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford University Press, 1991, pp. 35-70. | ||
| In article | |||
| [2] | C.Kimberling,http://faculty.evansville.edu/ck6/integer/index.html. | ||
| In article | View Article | ||
| [3] | N. J. A. Sloane, The On-line Encyclopedia of Integer Sequences, published electronically at http://oeis.org. | ||
| In article | View Article | ||
