A288723 First sequence of a Kolakoski 3-Ouroboros, i.e., sequence of 1s, 2s and 3s that begins a chain of three distinct sequences where successive run-length encodings produce seq(1) -> seq(2) -> seq(3) -> seq(1).

1, 1, 2, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 3, 1, 1, 2, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 3, 3, 1, 1

Offset: 1

Author

Anthony Sand, Jun 14 2017

Keywords

• nonn

Comments

The Kolakoski sequence, A000002, is its own run-length encoding: if you write down the lengths of the runs of 1 and 2, the same sequence reappears, i.e., A000002 = runlength(A000002). Next, runlength(A025142) = A025143 and runlength(A025143) = A025142. The run-lengths of the sequence above yield a second sequence whose run-lengths yield a third sequence whose run-lengths yield the original sequence:

seq(1) = 1,1,2,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,3,...

seq(2) = 2,2,2,3,1,1,2,2,3,3,3,1,1,1,2,3,1,2,2,3,3,1,1,2,2,2,3,1,1,2,2,2,3,3,3,...

seq(3) = 3,1,2,2,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,...

It seems possible to create arbitrarily long chains of distinct integer sequences, seq(1), seq(2)..seq(n), in which runlength(seq(i)) = seq(i+1) for (i=1,n-1) and runlength(seq(n)) = seq(1). When n=5, one possible chain is:

seq(1) = 1,1,2,2,3,3,4,4,4,5,5,5,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,...

seq(2) = 2,2,2,3,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,...

seq(3) = 3,3,3,3,4,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,4,5,1,1,2,2,3,3,3,...

seq(4) = 4,4,4,4,4,5,1,1,2,2,3,3,3,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,...

seq(5) = 5,1,2,2,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,...

When n=10, one possible chain begins and ends:

seq(1) = 1,1,2,2,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,10,...

[...]

seq(10) = 10,1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10,10,10,10,10,...

These chains might be called Kolakoski n-Ouroboroi, after the legendary serpent Ouroboros that bites its own tail. This sequence, A288723, is the first of one possible 3-Ouroboros, but any set of three distinct integers can seed a 3-Ouroboros. If the seed is (2,3,5), the 3-Ouroboros is:

seq(1) = 2,2,2,3,3,3,5,5,5,2,2,2,3,3,3,5,5,5,5,5,2,2,2,2,2,3,3,3,3,3,5,5,5,5,5,...

seq(2) = 3,3,3,3,3,5,5,5,5,5,2,2,3,3,5,5,5,2,2,2,3,3,3,3,3,5,5,5,5,5,2,2,2,2,2,...

seq(3) = 5,5,2,2,3,3,5,5,5,2,2,2,3,3,3,5,5,5,5,5,2,2,2,2,2,3,3,3,3,3,5,5,2,2,3,3,...

For n > 3, the integer set can repeat integers if the same integer does not occur consecutively or at the beginning and end of the set. If the seed is (1,2,1,3), the 4-Ouroboros is:

seq(1) = 1,1,2,1,1,1,3,1,2,1,1,3,1,1,1,2,2,2,1,3,1,1,2,1,3,1,1,1,2,2,2,1,1,1,...

seq(2) = 2,1,3,1,1,1,2,1,3,3,1,1,2,1,1,1,3,3,3,1,1,1,2,1,1,3,3,1,2,1,1,1,3,3,3,...

seq(3) = 1,1,1,3,1,1,2,2,1,3,3,3,1,2,2,1,1,3,3,1,2,2,2,1,1,1,3,1,1,2,1,3,1,1,1,...

seq(4) = 3,1,2,2,1,3,1,2,2,2,1,3,3,1,2,1,1,1,3,1,2,1,1,3,3,1,1,2,1,1,1,3,1,2,2,...

The existence of Kolakoski p-Ouroboros sequences for any positive integer p is proved in my paper 'What Is the Long Range Order in the Kolakoski Sequence?' from 1997. - Michel Dekking, Feb 05 2018

Examples

			Write down the run-lengths of the sequence, or the lengths of the runs of 1s, 2s and 3s. This yields a second and different sequence of 1s, 2s and 3s, A288724. The run-lengths of this second sequence yield a third and different sequence, A288725. The run-lengths of this third sequence yield the original sequence. For example, bracket the runs of distinct integers, then replace the original digits with the run-lengths to create the second sequence:
(1,1), (2,2), (3,3), (1,1,1), (2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2,2,2), (3), (1), (2), (3,3), (1,1,1), (2), (3,3), (1,1), (2,2,2), ... -> 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 2, 2, 3, ...
Apply the same process to the second sequence and the third sequence appears:
(2,2,2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2), (3), (1), (2,2), (3,3), (1,1), (2,2,2), (3), (1,1), (2,2,2), (3,3,3), (1), (2), (3), ... -> 3, 1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, ...
Apply the same process to the third sequence and the original sequence reappears:
(3), (1), (2,2), (3,3), (1,1,1), (2,2,2), (3), (1), (2), (3,3), (1,1,1), (2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2,2,2), (3), (1), ... -> 1, 1, 2, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, ...
		

References

• F. M. Dekking: "What is the long range order in the Kolakoski sequence?" in: The Mathematics of Long-Range Aperiodic Order, ed. R. V. Moody, Kluwer, Dordrecht (1997), pp. 115-125.

Links

• Georg Fischer, Table of n, a(n) for n = 1..2000 (recovered b-file, Jan 16 2019)
• F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, Report 95-100, Technische Universiteit Delft, 1995.
• Wikipedia, Ouroboros, the serpent that bites its own tail.

Crossrefs

Cf. A000002, A025142, A025143. The second and third sequences in this 3-Ouroboros are A288724 and A288725.