A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence

• Published in 2011
• Added on 2016-10-14

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

Links

• http://arxiv.org/abs/1110.4228v2
• http://arxiv.org/pdf/1110.4228v2

BibTeX entry

@article{ASpaceEfficientAlgorithmfortheCalculationoftheDigitDistributionintheKolakoskiSequence,
	title = {A Space Efficient Algorithm for the Calculation of the Digit  Distribution in the Kolakoski Sequence},
	abstract = {With standard algorithms for generating the classical Kolakoski sequence, the
numerical calculation of the digit distribution requires a linear amount of
space. Here, we present an algorithm for calculating the distribution of the
digits in the classical Kolakoski sequence, that only requires a logarithmic
amount of space and still runs in linear time. The algorithm is easily
adaptable to generalised Kolakoski sequences.},
	url = {http://arxiv.org/abs/1110.4228v2 http://arxiv.org/pdf/1110.4228v2},
	author = {Johan Nilsson},
	comment = {},
	urldate = {2016-10-14},
	archivePrefix = {arXiv},
	eprint = {1110.4228},
	primaryClass = {math.CO},
	year = 2011
}