The generalized Kolakoski sequence is the generalization of the Kolakoski sequence where you don't need to restrict yourself to 1,2 but can instead use any a,b pair.
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) ...
Here's an execution for 2, 3. When a != 1 we use a as the extra numbers instead of b:
 1 | 2 2(1) ...
 2 | 2 2(0) 2(1) ...
 3 | 3 2(1) 2(0) 2(1) ...
 4 | 3 2(0) 2(0) 2(1) ...
 5 | 2 3(2) 2(1) 2(0) 2(0) ...
 6 | 2 3(1) 2(1) 2(0) 2(1) ...
 7 | 2 3(0) 2(1) 2(0) 2(1) ...
 8 | 3 3(2) 2(0) 2(0) 2(1) ...
 9 | 3 3(1) 2(0) 2(0) 2(1) ...
10 | 3 3(0) 2(0) 2(0) 2(1) ...
11 | 2 2(1) 3(2) 2(1) 2(0) 2(1) ...
12 | 2 2(0) 3(2) 2(1) 2(0) 2(1) ...
13 | 3 2(1) 3(1) 2(1) 2(0) 2(1) ...
14 | 3 2(0) 3(1) 2(1) 2(0) 2(1) ...
15 | 2 2(1) 3(0) 2(1) 2(0) 2(1) ...
16 | 2 2(0) 3(0) 2(1) 2(0) 2(1) ...
17 | 3 3(2) 3(2) 2(0) 2(0) 2(1) ...
Furthermore, note that if a = 1, then the a, b sequence is a subset of the b, a sequence e.g.:
1, 2 = [1, 2, 2, 1, 1, 2, 1, ...]
2, 1 = [   2, 2, 1, 1, 2, 1, ...]
therefore we can always make a not be 1 by switching the pair and then using the generalized algorithm with a != 1.

Ancestors (8)

  1. Integer sequence
  2. Numeric function
  3. Function by signature
  4. Function (mathematics)
  5. Formalization of mathematics
  6. Area of mathematics
  7. Mathematics
  8. Home

Incoming links (2)

View article source

Discussion (0)

New discussion

There are no discussions about this article yet.

Articles by others on the same topic (1)

Kolakoski sequence by Wikipedia Bot 0
View more
The Kolakoski sequence is an infinite sequence of integers that is defined recursively. It is notable because it is self-generating and consists only of the integers 1 and 2. The sequence begins with 1 and is constructed by reading the lengths of groups of 1s and 2s as specified by the terms of the sequence itself. The construction process goes as follows: 1. Start with the initial term: \( 1 \).
Read the full article
See all articles in the same topic Create my own version