You are here
HomeKolakoski sequence
Primary tabs
Kolakoski sequence
A Kolakoski sequence is a “selfdescribing” sequence $\{k_{n}\}_{{k=0}}^{{\infty}}$ of alternating blocks of 1’s and 2’s, given by the following rules:

$k_{0}=1$.^{1}^{1}Some sources start the sequence at $k_{0}=2$, instead. This only has the effect of shifting the sequence by one position.

$k_{n}$ is the length of the $(n+1)$’th block.
Thus, the sequence begins 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, …
It is conjectured that the density of 1’s in the sequence is 0.5. It is not known whether the 1’s have a density; however, it is known that were this true, that density would be 0.5. It is also not known whether the sequence is a strongly recurrent sequence; this too would imply density 0.5.
Extensive computer experiments strongly support the conjecture. Furthermore, if $o_{n}$ is the number of 1’s in the first $n$ elements, then it appears that $o_{n}=0.5n+O(\log n)$. Note for comparison that for a random sequence of 1’s and 2’s, the number of 1’s in the first $n$ elements is with high probability $0.5n+O(\sqrt{n})$.
To generate rapidly a large number of elements of the sequence, it is most efficient to build a heirarchy of generators for the sequence. If the conjecture is correct, then the depth of this heirarchy is only $O(\log n)$ to generate the first $n$ elements.
Mathematics Subject Classification
11Y55 no label found94A55 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections
Comments
Zeroes versus 2
Simple question. (Perhaps too dumb.) Is there any difference if we change in Kolakoski sequence 2's with zeroes (0)? I guess there are no differences in densities of 1 and 2 (0). They would probably be in terms as sums and such are.
Is a term strongly recurrent sequence already defined somewhere within PlanetMath. If not, it would be fine to explain it a bit.
Re: Zeroes versus 2
Well, I can replace the 2's by 0's, of course, but then the sequence stops being "self describing": 1,0,0,1,1,0,0,... doesn't consist of one 1, then zero 0's, then 0 1's, then one 0, then...
But 1,2,2,1,1,2,2,... *does* consist of one 1, then two 2's, then two 1's, then ...
Regarding "strongly recurrent sequence": no, it's defined nowhere. I've already requested "topological dynamics" and "symbolic dynamics", which are the right contexts in which to develop "recurrent sequence" and "strongly recurrent sequence". Sorry.
Re: Zeroes versus 2
[ariels] thank you for reply. I like very much talking "(almost) ALIVE" about math and even about its the most difficult fields. As a sentence says: Math for the people, by the people... Interesting subject  no doubt. I admit I have to study some more to fully understand this kind of integer sequences. I guess I had missed a term "self describing". Nice. Another "stupid" question. Is such new sequence 1, 0, 0, 1, 1, 0, 0, ... really new or how should I better ask? Yes, there's no doubt this is "some kind" of sequence but, hey... I'll try to define it somehow. Or perhaps this has already been done.
"Recurrent sequence" also sounds very interesting. Best regard.