Hacker News

by Ryan Harman

Kolakoski Sequence (en.wikipedia.org)

60 points by surprisetalk 6 days ago

MontyCarloHall 6 hours ago

For those not getting this immediately (I sure didn't):

              _____________
   sequence   1 2 2 1 1 2 1 2 2 1
   run lens   1 2-- 2-- 1 1 2-- 1
Read out the bottom sequence of run lengths, and be amazed that it's the same as the first 7 digits as the top sequence. Extend the bottom to continue to recapitulate the top sequence, and add terms to the top sequence accordingly to reflect the run lengths in the bottom sequence. Repeat infinitely.

AnotherGoodName 5 hours ago

Can't you trivially force this to happen for any sequence?

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

Goes to

1, 3, 3, 3, 2... Etc.

I could extend this trivially too since the bottom sequence trails the sequence we write up top. If i wanted another '2' down the bottom whatever number i choose up top i just write twice right?

So there's nothing about this particular sequence? I can just create any such sequences trivially; Whenever you start a new count, choose a random number and repeat for a many times as needed for the trailing sequence to match the top sequence.

It seems that this particular variant is uninteresting in the broader picture right? I could write another similar one

2, 2, 1, 1, 2, 1

2, 2, 1, 1, ... etc.

I don't get the specialness here?

MontyCarloHall 5 hours ago

>Can't you trivially force this to happen for any sequence?

No, because there's no deterministic way to infinitely extend that sequence. In your first example:

   1 3 3 3 2 2 2 1 1 1 4 4 x x y y
   1 3---- 3---- 3---- 2-- 2-- 2--
What are the values of x and y?

>Whenever you start a new count, choose a random number and repeat for a many times as needed for the trailing sequence to match the top sequence.

You answered your own question. The Kolakoski sequence is special because it does not just pick a random number: the sequence is deterministically encoded by the run lengths, and vice versa.

AnotherGoodName 5 hours ago

nwellnhof 5 hours ago

There's a fascinating way to generate the Kolakoski sequence with bit fiddling: https://11011110.github.io/blog/2016/10/14/kolakoski-sequenc...

vindex10 5 hours ago

Is it a coincidence that it is number 2 in the OEIS?)

globalnode 15 minutes ago

does it repeat? or is it like pi? -- oh the wiki says its an infinite sequence. that might be handy for generating pseudo random numbers i guess. i wonder if theres a function that generates the correct digit at position n? doh, wiki says theres a recursive formula for the i'th term.