sequence

MATHS BITE: The Kolakoski Sequence

The Kolakoski sequence is an infinite sequence of symbols {1,2} that is its own “run-length encoding“. It is named after mathematician Willian Kolakoski who described it in 1965, but further research shows that it was first discussed by Rufus Oldenburger in 1939.

This self-describing sequence consists of blocks of single and double 1s and 2s. Each block contains digits that are different from the digit in the preceding block.

To construct the sequence, start with 1. This means that the next block is of length 1. So we require that the next block is 2, giving the sequence 1, 2. Continuing this infinitely gives us the Kolakoski sequence: 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, etc.

M x

Advertisements

Maths Bite: Conway’s Constant

Look-and-Say Sequences

A Look-and-Say sequence was first introduced and analysed by John Conway. An example of such series is:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211….

To generate the next number in the sequence from the previous term, read off the digits of the previous number, counting the number of digits in groups of the same digit. For example:

  • 1 is read as ‘one 1’ = 11
  • 11 is read as ‘two 1s’ = 21
  • 21 is read as ‘one 2, one 1’ = 1211

If we start with any digit x from 0 to 9, then x will remain the last digit of the sequence. When x does not equal 1, the sequence is as follows:

x, 1x, 111x, 311x, 13211x, 111312211x, 31131122211x…

The Conway sequence, named by Vardi in 1991, is a look-and-say sequence with the starting digit 3.

Growth in Length and Conway’s Constant

The terms of the sequence eventually grow in length about 30% per generation. If Ln denotes the number of digits in the n-th term of the sequence, the limit of the ratio

\frac{L_{n + 1}}{L_n}

is Conway’s constant:

\lim_{n \to \infty}\frac{L_{n+1}}{L_{n}} = \lambda

where λ = 1.303577269034…

 

Source: Wikipedia

Conway’s constant is the unique positive real root of the following polynomial:

\begin{align}
&\,\,\,\,\,\,\,  x^{71}   &&  &&- x^{69}   &&- 2x^{68}  &&- x^{67}   &&+ 2x^{66}  &&+ 2x^{65}  &&+ x^{64}   &&- x^{63} \\
&- x^{62}  &&- x^{61}   &&- x^{60}   &&- x^{59}   &&+ 2x^{58}  &&+ 5x^{57}  &&+ 3x^{56}  &&- 2x^{55}  &&- 10x^{54} \\
&- 3x^{53} &&- 2x^{52}  &&+ 6x^{51}  &&+ 6x^{50}  &&+ x^{49}   &&+ 9x^{48}  &&- 3x^{47}  &&- 7x^{46}  &&- 8x^{45}  \\
&- 8x^{44} &&+ 10x^{43} &&+ 6x^{42}  &&+ 8x^{41}  &&- 5x^{40}  &&- 12x^{39} &&+ 7x^{38}  &&- 7x^{37}  &&+ 7x^{36}  \\
&+ x^{35}  &&- 3x^{34}  &&+ 10x^{33} &&+ x^{32}   &&- 6x^{31}  &&- 2x^{30}  &&- 10x^{29} &&- 3x^{28}  &&+ 2x^{27}  \\
&+ 9x^{26} &&- 3x^{25}  &&+ 14x^{24} &&- 8x^{23}  && &&- 7x^{21}  &&+ 9x^{20}  &&+ 3x^{19}  &&- 4x^{18}  \\
&- 10x^{17} &&- 7x^{16} &&+ 12x^{15} &&+ 7x^{14}  &&+ 2x^{13}  &&- 12x^{12} &&- 4x^{11}  &&- 2x^{10}  &&+ 5x^9     \\
& &&+ x^7      &&- 7x^6    &&+ 7x^5     &&- 4x^4     &&+ 12x^3    &&- 6x^2     &&+ 3x       &&- 6
\end{align}

 

Let me know if you’re enjoying these Math Bites? M x