Kolakoski sequence
Encyclopedia
In mathematics
, the Kolakoski sequence is an infinite list that begins with
The rules for generating this sequence are as follows:
1) The only numbers allowed are 1 and 2
2) Each number tells us how many numbers to append to the sequence
2a) 1 tells us to append one more number
2b) 2 tells us to append two more numbers
3) We can have no more than two of the same number in sequence
3a) This is because if we write 222 that means that somewhere in the sequence it told us to append 3 twos, but the only numbers allowed are 1 and 2
4) Every time we "read" a new number, we alternate between writing 1 and 2
5) A0=1
This is an example of a self-generating sequence, with the first term as 1. Each individual number describes how many numbers to write next. This is called the run of the numbers. To start the sequence we have to write one 2 after the 1 because the 1 tells us to write one number, and because our initial condition "wrote" the one we must alternate by writing the 2. This gives us as our sequence so far (1 2). Next, The 2 tells us that the length, or the run, of the next set of numbers must be 2, but we cannot have any more than two ones or two twos in sequence because that would mean that the sequence told us to write three 2's, which would mean a 3 would have to be in the sequence, which is not allowed. Therefore, we must write 2 1. This gives us our sequence so far (1 2 2 1). The next number in the list is a 2, so we must write two numbers. The next two numbers that we should write is a 1; however, we cannot write three 1's in a row, so we must append 1 2 to the sequence. This gives us our sequence so far (1 2 2 1 1 2). The fourth number in the list is a 1. As we wrote a 2 last we write a 1 now. This gives us our sequence so far (1 2 2 1 1 2 1). The fifth number in the sequence is a 1. As we wrote a 1 before, we must write a 2 now. This gives us our sequence so far (1 2 2 1 1 2 1 2). This continues on. Another explanation for the generation of the Kolakoski sequence is indicated here:
(1) write 1; read it as the number of 1's to write before switching to 2;
(2) write 2; read it as the number of 2's to write before switching back to 1;
(3) so far... 1,2,2; read the new 2 as the number of 1's to write;
(4) so far... 1,2,2,1,1; read the new 1,1 as the number of 2's and then 1's to write;
(5) so far... 1,2,2,1,1,2,1; continue generating forever.
To truly understand how the sequence is generated, follow either of the two examples above and write out the first few terms.
It seems plausible that the density of 1's is 1/2, but this conjecture remains unproved. This and related simply stated unsolved problems are presented at Integer Sequences and Arrays. Attempts to solve them are referenced at MathWorld and sequence at On-Line Encyclopedia of Integer Sequences
. In the unpublished technical report Notes on the Kolakoski Sequence, Chvátal proved that the upper density of 1's is less than 0.50084.
Kolakoski's self-generating sequence has attracted the interest of computer scientists
as well as mathematicians. For example, in A New Kind of Science
, p. 895, Stephen Wolfram
describes the Kolakoski sequence in connection with the history of cyclic tag system
s.
1
2
2 2
1 1 2 2
1 2 1 1 2 2
2 1 1 2 1 2 2 1 1
(and so on, where the initial entries are given by the Kolakoski sequence, and the block lengths in each row are given by the entries in the previous row)
Associated with this array, indexed as (in the On-Line Encyclopedia of Integer Sequences) are many other such arrays, such as , for which it is conjectured that the growth rate of row-length is asymptotic to c(3/2) n for some constant c.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Kolakoski sequence is an infinite list that begins with
- 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,...
The rules for generating this sequence are as follows:
1) The only numbers allowed are 1 and 2
2) Each number tells us how many numbers to append to the sequence
2a) 1 tells us to append one more number
2b) 2 tells us to append two more numbers
3) We can have no more than two of the same number in sequence
3a) This is because if we write 222 that means that somewhere in the sequence it told us to append 3 twos, but the only numbers allowed are 1 and 2
4) Every time we "read" a new number, we alternate between writing 1 and 2
5) A0=1
This is an example of a self-generating sequence, with the first term as 1. Each individual number describes how many numbers to write next. This is called the run of the numbers. To start the sequence we have to write one 2 after the 1 because the 1 tells us to write one number, and because our initial condition "wrote" the one we must alternate by writing the 2. This gives us as our sequence so far (1 2). Next, The 2 tells us that the length, or the run, of the next set of numbers must be 2, but we cannot have any more than two ones or two twos in sequence because that would mean that the sequence told us to write three 2's, which would mean a 3 would have to be in the sequence, which is not allowed. Therefore, we must write 2 1. This gives us our sequence so far (1 2 2 1). The next number in the list is a 2, so we must write two numbers. The next two numbers that we should write is a 1; however, we cannot write three 1's in a row, so we must append 1 2 to the sequence. This gives us our sequence so far (1 2 2 1 1 2). The fourth number in the list is a 1. As we wrote a 2 last we write a 1 now. This gives us our sequence so far (1 2 2 1 1 2 1). The fifth number in the sequence is a 1. As we wrote a 1 before, we must write a 2 now. This gives us our sequence so far (1 2 2 1 1 2 1 2). This continues on. Another explanation for the generation of the Kolakoski sequence is indicated here:
(1) write 1; read it as the number of 1's to write before switching to 2;
(2) write 2; read it as the number of 2's to write before switching back to 1;
(3) so far... 1,2,2; read the new 2 as the number of 1's to write;
(4) so far... 1,2,2,1,1; read the new 1,1 as the number of 2's and then 1's to write;
(5) so far... 1,2,2,1,1,2,1; continue generating forever.
To truly understand how the sequence is generated, follow either of the two examples above and write out the first few terms.
It seems plausible that the density of 1's is 1/2, but this conjecture remains unproved. This and related simply stated unsolved problems are presented at Integer Sequences and Arrays. Attempts to solve them are referenced at MathWorld and sequence at On-Line Encyclopedia of Integer Sequences
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
. In the unpublished technical report Notes on the Kolakoski Sequence, Chvátal proved that the upper density of 1's is less than 0.50084.
Kolakoski's self-generating sequence has attracted the interest of computer scientists
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
as well as mathematicians. For example, in A New Kind of Science
A New Kind of Science
A New Kind of Science is a book by Stephen Wolfram, published in 2002. It contains an empirical and systematic study of computational systems such as cellular automata...
, p. 895, Stephen Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
describes the Kolakoski sequence in connection with the history of cyclic tag system
Tag system
A tag system is a deterministic computational model published by Emil Leon Post in 1943 as a simple form of Post canonical system. A tag system may also be viewed as an abstract machine, called a Post tag machine —briefly, a finite state machine whose only tape is a FIFO queue of unbounded length,...
s.
Kolakoski fan
The Kolakoski fan is the following array:1
2
2 2
1 1 2 2
1 2 1 1 2 2
2 1 1 2 1 2 2 1 1
(and so on, where the initial entries are given by the Kolakoski sequence, and the block lengths in each row are given by the entries in the previous row)
Associated with this array, indexed as (in the On-Line Encyclopedia of Integer Sequences) are many other such arrays, such as , for which it is conjectured that the growth rate of row-length is asymptotic to c(3/2) n for some constant c.