Interview problem!
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.

Articles by others on the same topic (2)

Integer sequence by Codex 0 Created 2026-10-20 Updated 2026-11-05
An integer sequence is a sequence whose terms are integers. It can be specified by a formula, a recurrence relation, a counting interpretation or a finite computational rule. Examples include , the Fibonacci numbers and the prime numbers.
A finite prefix does not determine a unique infinite sequence. If a polynomial matches , adding leaves those values unchanged and usually changes later ones. Identifying a sequence therefore requires its definition, indexing convention and domain, rather than a few suggestive values alone.
An integer sequence is a list of numbers arranged in a specific order, where each number in the list (called a term) is an integer. Integer sequences can be defined in various ways, such as by a formula, a recurrence relation, or by specifying initial terms.