Kolakoski Word

Kolakoski Word

The classical Kolakoski sequence [K65] was first studied by Oldenburger [O39], where it appears as the unique solution to the problem of a trajectory on the alphabet \(\{1,2\}\) which is identical to its exponent trajectory.

See http://en.wikipedia.org/wiki/Kolakoski_sequence

It uses cython implementation inspired from the 10 lines of C code written by Dominique Bernardi and shared during Sage Days 28 in Orsay, France, in January 2011. The alphabet must be (1,2).

EXAMPLES:

sage: from slabbe import KolakoskiWord
sage: K = KolakoskiWord()
sage: K
word: 1221121221221121122121121221121121221221...

The cython implementation is much faster than the python one:

sage: K = KolakoskiWord()
sage: K[10^6]      # takes 0.02 seconds
2
sage: K = words.KolakoskiWord()
sage: K[10^6]      # not tested : takes too long
2

TESTS:

We make sure both implementation correspond for the prefix of length 100:

sage: Kb = KolakoskiWord()
sage: Kp = words.KolakoskiWord()
sage: Kp[:100] == Kb[:100]
True

REFERENCES:

[K65]William Kolakoski, proposal 5304, American Mathematical Monthly 72 (1965), 674; for a partial solution, see “Self Generating Runs,” by Necdet Üçoluk, Amer. Math. Mon. 73 (1966), 681-2.
[O39]R. Oldenburger, Exponent trajectories in dynamical systems, Trans. Amer. Math. Soc. 46 (1939), 453–466.

AUTHORS:

  • Sébastien Labbé (February 2011) - Added a Cython implementation which was easily translated from the 10 lines of C code written by Dominique Bernardi and shared during Sage Days 28 in Orsay. Needs review at #13346 since too long time…
class slabbe.kolakoski_word.KolakoskiWord(parent=None)

Bases: slabbe.kolakoski_word_pyx.WordDatatype_Kolakoski, sage.combinat.words.infinite_word.InfiniteWord_class

Constructor. See documentation of WordDatatype_Kolakoski for more details.

EXAMPLES:

sage: from slabbe import KolakoskiWord
sage: K = KolakoskiWord()
sage: K
word: 1221121221221121122121121221121121221221...

TESTS:

Pickle is supported:

sage: K = KolakoskiWord()
sage: loads(dumps(K))
word: 1221121221221121122121121221121121221221...

Kolakoski word (datatype)

class slabbe.kolakoski_word_pyx.WordDatatype_Kolakoski

Bases: object

Word datatype class for the Kolakoski word.

This is a cython implementation inspired from the 10 lines of C code written by Dominique Bernardi and shared during Sage Days 28 in Orsay, France, in January 2011.

INPUT:

  • parent - the parent

EXAMPLES:

sage: from slabbe.kolakoski_word_pyx import WordDatatype_Kolakoski
sage: parent = Words([1,2])
sage: K = WordDatatype_Kolakoski(parent)
sage: K
<slabbe.kolakoski_word_pyx.WordDatatype_Kolakoski object at ...>
sage: K[0]
1
sage: K[1]
2