Interview problem!
Solutions:
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.
1 2(0) 1(1)The starting state is:which means that it implicitly contains infinitely many The actual algorithm will of course omit as many trailing
2 | 2 2(1) 2(1) 2(1) 2(1) ...2(1) at the end which we abbreviate just as:2 | 2 2(1) ...2(1) as it can.The update rules are:Note that both rules don't overlap so that each update is always determined by only one of them at a time.
- go left to right:
- flip:continue going left to right.
x(0) y(0) !x((!x)-1) unchanged - repeat:and then stop further updates.
x(0) y(n > 0) x(x-1) y(n - 1)
- flip:
Also the first column is always implicitly
(0).2 | 2 2(1) ...
3 | 2 2(0) 2(1) ...Here we:
2 | 2 2(1) ...
3 | 2 2(0) 2(1) ...
4 | 1 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(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 Furthermore, note that if therefore we can always make
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) ...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, ...]a not be 1 by switching the pair and then using the generalized algorithm with a != 1. Articles by others on the same topic
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.