Kolakoski-sekvensen , også kendt som Oldenburger-Kolakoski-sekvensen , er en uendelig sekvens af numrene 1 og 2, der er en løbelængdekodning [1] og en prototype for en uendelig familie af beslægtede sekvenser. Det blev oprindeligt opkaldt efter matematikeren William Kolakoski , som foreslog det i 1965 [2] , men efterfølgende forskning har vist, at det først dukker op i et papir af Rufus Oldenburger ) i 1939 [3] .
Begyndelsen af Kolakoski-sekvensen:
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, ... (sekvens A000002 i OEIS ).
Sekvensen, der består af antallet af cifre, der forekommer i en sekvens i en række, matcher nøjagtigt den oprindelige sekvens:
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 , … 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, …Omvendt genererer hvert tal i Kolakoski-sekvensen de næste et eller to tal, skiftende etere og toere.
Denne selvgenererende egenskab viser, at Kolakoski-sekvensen kan beskrives som en fraktal, det vil sige et matematisk objekt, der koder for sin repræsentation på andre skalaer.
Kolakoski-sekvensen betragtes som aperiodisk [4] , det vil sige, at den ikke har et gentaget mønster.
Kolakoski-sekvensen er prototypen for en uendelig familie af andre sekvenser, hver med sin egen kørselslængdekodning. Nogle af Kolakoski-sekvenserne opført i OEIS er:
Til sættet {1, 3}
1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 3, 3, 1, 3, 3, 3, 1, 1, 1, 3, 3, 3, 1, 3, 1, 3, 3, 3, … (sekvens A064353 i OEIS )
Til sættet {2, 3}
2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 3, 3, 2, 2, 2, 3, 3, … (sekvens A071820 i OEIS )
For sættet {1, 2, 3}
1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 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, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, … (sekvens A079729 i OEIS )
Ligesom Kolakoski-sekvensen for {1,2} returnerer skrivning af løbslængderne den samme sekvens. Generelt kan ethvert sæt af heltal {n 1 , n 2 , n 3 , …, n i } generere en Kolakoski-sekvens, hvis det samme heltal ikke forekommer to gange eller mere i træk og/eller i begyndelsen og slutningen af sæt. For eksempel for sættet {3,1,2}:
3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 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, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, …
Og for sættet {2, 1, 3, 1}:
2, 2, 1, 1, 3, 1, 2, 2, 2, 1, 3, 3, 1, 1, 2, 2, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 3, 3, 1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 3, 3, 3, 1, 1, 1, 2, 1, 3, 1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 2, 2, 1, 1, 1, 3, 3, 3, 1, 2, 2, 1, 3, 1, 1, 1, …
Igen, skrivning af kørselslængderne returnerer den samme sekvens.
Kolakoski-sekvenser kan også oprettes ud fra uendelige sæt af heltal.
For eksempel for sættet {1, 2, 1, 3, 1, 4, 1, 5, ...}:
1, 2, 2, 1, 1, 3, 1, 4, 4, 4, 1, 5, 5, 5, 5, 1, 1, 1, 1, 6, 6, 6, 6, 1, 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 9, 1, 10, 1, 11, 11, 11, 11, 11, 11, 1, 1, 1, 1, 1, 1, 12, 12, 12, 12, 12, 12, 1, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 14, 14, 14, 14, 14, 14, 14, 1, 1, 1, 1, 1, 1, 1, …
Det uendelige sæt {1,2,3,4,5,...} genererer Golomb-sekvensen:
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, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,... ( OEIS -sekvens A001462 )
Kolakoski-sekvensen kan også oprettes ud fra heltal valgt tilfældigt fra et endeligt sæt, med den begrænsning, at det samme tal ikke kan vælges to gange i træk. For et endeligt sæt {1,2,3} er en af de mulige sekvenser:
2, 2, 1, 1, 3, 1, 3, 3, 3, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 3, 3, 2, 1, 3, 2, 2, 3, 3, 2, 2, 3, 1, 3, 1, 1, 1, 3, 3, 3, 1, 1, 3, 2, 2, 2, 3, 3, 1, 1, 3, 3, 3, 1, 1, 1, 3, 3, 1, 1, 2, 2, 2, 3, 1, 1, 1, 3, 1, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 1, 1, 2, 2, 3, 3, 3, 2, 2, 2, 1, 2, 1, 1, 1, …
I det væsentlige er sekvensen baseret på det uendelige sæt {2,1,3,1,3,2,1,2,1,3,2,...}, som er en tilfældig sekvens af 1'ere, 2'ere og 3'ere, hvorfra gentagelser er blevet fjernet.
Ligesom den klassiske Kolakoski-sekvens genererer sig selv, genererer disse to sekvenser hinanden:
1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2, 1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2, 2,... (sekvens A025142 i OEIS )
2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,1,2,1,2,2,1,1,2, 1,1,2,2,1,2,1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,1,2,2,... ( sekvens A025143 i OEIS )
Med andre ord, hvis du nedskriver løbslængderne af den første sekvens, vil den anden blive oprettet, og hvis du skriver løbslængderne af den anden sekvens ud, vil den første blive oprettet.
I den næste kæde af tre løbelængdesekvenser genererer hver følgende:
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,... (sekvens A288723 i OEIS )
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,... (sekvens A288724 i OEIS )
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,... (sekvens A288725 i OEIS )
Sekvenserne bruger heltalssættet {1,2,3}, men hver sekvens starter med et andet element i sættet.
De følgende fem sekvenser danner en lignende kæde ved hjælp af sættet {1,2,3,4,5}:
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,...
2,2,2,3,3,3,4,4,4,5,5,5,1,1,1,1,1,2,2,2,2,3,3,3,3,4, 4,4,4,5,5,5,5,5,...
3,3,3,3,4,4,4,4,5,5,5,5,1,1,1,1,1,2,2,2,2,3,3,3,3,3, 4,5,1,1,2,2,3,3,3,...
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,...
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,...
Men for at skabe en kæde af n elementer, er det ikke nødvendigt at have et sæt af n elementer. For eksempel bruger den følgende kæde af fem sekvenser sættet {1, 2}:
2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2, 1,1,2,1,1,2,2,1,...
1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1, 2,1,1,2,2,1,2,2,...
1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1, 2,1,1,2,2,1,2,1,...
1,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1, 2,2,1,2,1,1,2,1,...
1,1,2,1,2,2,1,1,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,...
Hver sekvens er unik, og udførelseslængderne for hver genererer medlemmerne af den næste sekvens i kæden. Heltalssættene, der bruges til at skabe kæden, kan også være af forskellige størrelser. Fra sættene {1,2} og {1,2,3,4,5} genereres følgende sekvenser:
1,2,2,1,1,2,2,2,1,1,1,2,2,2,2,1,1,1,1,1,1,2,1,2,2,1, 1,2,2,2,...
1,2,2,3,3,4,5,1,1,2,2,3,3,4,5,1,2,2,3,3,4,4,5,5,1, 2,3,4,5,...
Det virker plausibelt, at brøkdelen af enerne i den klassiske Kolakoski-sekvens er 1/2, men denne formodning forbliver ubevist. [4] Václav Chvátal beviste, at den øvre grænse for brøkdelen af enheder er mindre end 0,50084 [5] . John Nilson brugte den samme metode med meget mere regnekraft til at opnå en grænse på 0,500080 [6] .
Selvom de første 3×10 8 værdier af sekvensen blev brugt i beregningerne, konvergerer dens tæthed tilsyneladende til en værdi lidt forskellig fra 1/2, men senere beregninger viste, at udvidelsen af sekvensen i de første 10 13 værdier afviger fra brøkdelen af enheder 1/2 mindre og mindre, så vi kan forvente, at den begrænsende brøkdel af enheder faktisk er 1/2 [7] .
I antikolakoski-sekvensen matcher længden af løbene af enere og toere aldrig medlemmerne af den oprindelige sekvens:
2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 1, 1, … (sekvens A049705 i OEIS ).
2, 1, 1 , 2, 2 , 1, 2, 1, 1 , 2, 1, 1 , 2, 2 , 1, 2, 2 , 1, 1 , 2, 1, 2, 2 , 1, 2, 1, 1 , 2, 2 , 1, … 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, …Som du kan se, er dem i antikolakoski-sekvensen i de positioner, hvor toerne er i den klassiske Kolakoski-sekvens, og omvendt.
Kolakoski-konstanten er defineret i binær notation som følger. Ved hver binær position efter decimaltegnet er der et 1, hvis den tilsvarende position i den klassiske Kolakoski-sekvens er en to, og 0, hvis en enhed [8] . Den første enhed i sekvensen ignoreres. På denne måde
0,11001011011001001101001011001001011… 2 = 0,7945071927794792762403624156360456462… 10 .