Journal of Integer Sequences, Vol. 15 (2012), Article 12.6.7

A Space-Efficient Algorithm for Calculating the Digit Distribution in the Kolakoski Sequence

Johan Nilsson
Fakultät für Mathematik
Universität Bielefeld
Postfach 100131
33501 Bielefeld


With standard algorithms for generating the classical Kolakoski sequence, the numerical calculation of the digit distribution uses a linear amount of space. Here, we present an algorithm for calculating the distribution of the digits in the classical Kolakoski sequence that uses logarithmic space and still runs in linear time. The algorithm is easily adaptable to generalized Kolakoski sequences.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000002 A071820 A195206 A195211.)

Received October 12 2011; revised versions received March 9 2012; June 25 2012. Published in Journal of Integer Sequences, June 26 2012.

Return to Journal of Integer Sequences home page