A Space-Efficient Algorithm for Calculating the Digit Distribution in the Kolakoski Sequence
Fakultät für Mathematik
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,
(Concerned with sequences
Received October 12 2011;
revised versions received March 9 2012; June 25 2012.
Published in Journal of Integer Sequences, June 26 2012.
Journal of Integer Sequences home page