Fast algorithms for the Kolakoski sequence

Speaker: 

Richard Brent

Affiliation: 

ANU and University of Newcastle

Date: 

Wed, 16/11/2016 - 1:00pm

Venue: 

RC-4082, The Red Centre, UNSW

Abstract: 

The Kolakoski sequence $1221121221221121122\ldots$ is the unique countable $\{1,2\}$-sequence $k_1k_2k_3\ldots$ such that $k_1=1$, whose $j$-th block has length $k_j$. We shall briefly survey what is known and conjectured about this sequence.

Define the Kolakoski discrepancy function $\delta(n) := \sum_{1\le j \le n}(-1)^{k_j}$. It is an open question whether $\delta(n) = o(n)$, i.e. whether the density of $1$'s in $k$ is $\frac12$.

Nilsson (2012) gave an algorithm for computing $k_1\ldots k_n$ (and hence $\delta(n)$) in time $T = O(n)$ and space $S = O(\log n)$. We shall describe an algorithm that computes $\delta(n)$ faster, using a space-time tradeoff. Ignoring logarithmic factors, it is conjectured that the algorithm runs in time $T = O((2/3)^d n + 2^d)$ using space $S = O(2^d)$.  Taking $d \approx \log(n)/\log(3)$, this gives $T=O(n^\alpha)$ and $S=O(n^\alpha)$ for $\alpha = \log(2)/\log(3)\approx 0.631$.
 
Using our algorithm, we have computed $\delta(n)$ for various $n \le 5\times 10^{17}$.  The results are in agreement with those of Rao (2012), who used a different algorithm, and provide numerical evidence for the conjecture that $\delta(n) = O(n^{1/2})$.

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

School Seminar Series: