Fast algorithms for the Kolakoski sequence

Abstract: 

The Kolakoski sequence 1221121221221121122…1221121221221121122… is the unique countable {1,2}{1,2}-sequence k1k2k3…k1k2k3… such that k1=1k1=1, whose jj-th block has length kjkj. We shall briefly survey what is known and conjectured about this sequence.

Define the Kolakoski discrepancy function δ(n):=∑1≤j≤n(−1)kjδ(n):=∑1≤j≤n(−1)kj. It is an open question whether δ(n)=o(n)δ(n)=o(n), i.e. whether the density of 11's in kk is 1212.

Nilsson (2012) gave an algorithm for computing k1…knk1…kn (and hence δ(n)δ(n)) in time T=O(n)T=O(n) and space S=O(logn)S=O(log⁡n). We shall describe an algorithm that computes δ(n)δ(n) faster, using a space-time tradeoff. Ignoring logarithmic factors, it is conjectured that the algorithm runs in time T=O((2/3)dn+2d)T=O((2/3)dn+2d) using space S=O(2d)S=O(2d).  Taking d≈log(n)/log(3)d≈log⁡(n)/log⁡(3), this gives T=O(nα)T=O(nα) and S=O(nα)S=O(nα) for α=log(2)/log(3)≈0.631α=log⁡(2)/log⁡(3)≈0.631.

Using our algorithm, we have computed δ(n)δ(n) for various n≤5×1017n≤5×1017.  The results are in agreement with those of Rao (2012), who used a different algorithm, and provide numerical evidence for the conjecture that δ(n)=O(n1/2)δ(n)=O(n1/2).

[This is joint work with Judy-anne Osborn.]