What is Kolakoski Sequence

The Kolakoski Sequence is named after William Kolakoski. He described the Sequence in 1965. William Kolakoski was an American artist and recreational mathematician.

He had many interests in arts, philosophy and mathematics but chose fine art at college because he felt he could study mathematics and philosophy independently.

It is also known as the Oldenburger-kolakoski Sequence, as Rufus Oldenburger discussed it before Kolakoski in 1939. Rufus Oldenburger was also an American mathematician and mechanical engineer.

Introduction with Kolakoski Sequence

The Sequence is similar to Gijswijt, but it counts the longest run of single terms.
Kolakoski Sequence can be defined as: –

It is an infinite sequence of symbols {1,2} or in other words; we can say that it is a self-describing sequence that consists of “blocks” of single and double 1s and 2s, where a (“Block” can be a single digit or pair of digits) that is different from the digit (or pair of digits) in the preceding block.

The first few values of the KOLAKOSKI Sequence are: –

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1…

Read More: What is the Riemann Hypothesis in Simple Terms?

Explanation of Kolakoski Sequence

Let us know the explanation of these terms: –

1. The first term of the Sequence is 1 by definition.
2. The single 1 means that a block of length one follows the first block.
3. So the next block should be 2, which gives Sequence 12.
4. Now, the 2 means that the next (third) block will have length two, so append 11, which gives the Sequence 1211.
5. Now, we have added two 1s, so the fourth and fifth blocks have a length of one each, giving 12112 and then 121121.
6. When we add 21, we obtain 121121221.
7. When we add 221, we obtain 12112122122112, and so on, giving the sequence 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2.
8. Finally, the Sequence after successive iterations is 1, 12, 1211, 121121, 121121221, …………………..

And so on…………………….

Each symbol occurs in a sequence of identical elements of either one or two consecutive terms, which proves the lengths of these runs give precisely the same Sequence.

Read More: What is Look and Say Sequence?

Let us understand with a brief explanation: –

• 1,2 (length of the sequence l = 2; sum of terms s = 3)
• 1,2,2 (l = 3, s = 5)
• 1,2,2,1,1 (l = 5, s = 7)
• 1,2,2,1,1,2,1 (l = 7, s = 10)
• 1,2,2,1,1,2,1,2,2,1 (l = 10, s = 15)
• 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 (l = 15, s = 23)

And the Sequence keeps going on like that…………..

Properties Of Kolakoski Sequence

1. Density of the kolakoski Sequence is ½ (however, it is not proven)
2. Simple cyclic tag system (a kind of computational model)
3. Similarity to Gijswijt’s Sequence (it counts the longest run of single terms instead of counting the longest run of blocks of terms of any length).
4. Linear Algorithm

Note: -The Kolakoski sequence generates a run (a sequence of identical elements) of one or two future terms. The first 1 of the Sequence generates a run of “1”, and the first 2 generates a run of “22”, which includes itself also, then the second 2 generates a run of “11”; and so on.

Each number in the Sequence is the length of the next run to be generated, and the element to be generated alternates between 1 and 2.

Read More: All About Golomb Sequence

Examples on Kolakoski Sequence:

Now, we will solve questions related to the Kolakoski sequence: –

1. A positive integer n is given to you; you must find the first n terms of the Kolakoski sequence.

Case 1 = If n is 3, which means
Input = 3
The output will be, or the first n terms of the Sequence will be 1,2,2.

Case 2 = If n is 5, which means
Input = 5
The output will be, or the first n terms of the Sequence will be 1,2,2,1,1.

Practice

1. A positive integer n = 6 is given to you; what will be the first n terms of the Kolakoski sequence?