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
Germany
Abstract:
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