Nilsson algorithm for the Kolakoski sequence

ID: nilsson-algorithm-for-the-kolakoski-sequence

Top articles Latest articles New article in topic
Nilsson algorithm for the Kolakoski sequence by Ciro Santilli 37 2025-11-18
This algorithm is more efficient in space, using only , as it recursively compresses the state required to keep track of what to do next.
Time is still .
The table at maths-people.anu.edu.au/~brent/pd/Kolakoski-UNSW.pdf page 20 has a summary image, but it is hard to understand.
Let's do a step by step version now.
The notation we use is as follows:
1 2 (1) 1 (1)
means that:
  • this is number 2
  • there is 1 occurrence count left
Note that column 1 does not need to keep a count so we use notation such as:
1 2(0) 1(1)
The starting state is:
2 | 2 2(1) 2(1) 2(1) 2(1) ...
which means that it implicitly contains infinitely many 2(1) at the end which we abbreviate just as:
2 | 2 2(1) ...
The actual algorithm will of course omit as many trailing 2(1) as it can.
The update rules are:
  • go left to right:
    • flip:
      x(0)       y(0)
!x((!x)-1) unchanged
      continue going left to right.
    • repeat:
      x(0)   y(n > 0)
x(x-1) y(n - 1)
      and then stop further updates.
Note that both rules don't overlap so that each update is always determined by only one of them at a time.
Also the first column is always implicitly (0).
Use column 2 up once to repeat column 1:
2 | 2 2(1) ...
3 | 2 2(0) 2(1) ...
Here we:
  • switch column 1 because column 2 reached 0 on previous step
  • use column 3 up once to repeat column 2
2 | 2 2(1) ...
3 | 2 2(0) 2(1) ...
4 | 1 2(1) 2(0) 2(1) ...
  • use column 2 up once to repeat 1
2 | 2 2(1) ...
3 | 2 2(0) 2(1) ...
4 | 1 2(1) 2(0) 2(1) ...
5 | 1 2(0) 2(1) 2(0) 2(1) ...
 2 | 2 2(1) ...
 3 | 2 2(0) 2(1) ...
 4 | 1 2(1) 2(0) 2(1) ...
 5 | 1 2(0) 2(0) 2(1) ...
 6 | 2 1(0) 2(1) 2(0) 2(1) ...
 7 | 1 1(0) 2(0) 2(0) 2(1) ...
 8 | 2 2(1) 1(0) 2(1) 2(0) 2(1) ...
 9 | 2 2(0) 1(0) 2(1) 2(0) 2(1) ...
10 | 1 1(0) 1(0) 2(0) 2(0) 2(1) ...
11 | 2 2(1) 2(1) 1(0) 2(1) 2(0) 2(1) ...
12 | 2 2(0) 2(1) 1(0) 2(1) 2(0) 2(1) ...
13 | 1 2(1) 2(0) 1(0) 2(1) 2(0) 2(1) ...
14 | 1 2(0) 2(0) 1(0) 2(1) 2(0) 2(1) ...
15 | 2 1(0) 1(0) 1(0) 2(0) 2(0) 2(1) ...
16 | 1 2(1) 2(1) 2(1) 1(0) 2(1) 2(0) 2(1) ...
Read the full article

New to topics? Read the docs here!