Secvența Kolakoski , cunoscută și sub denumirea de secvența Oldenburger-Kolakoski , este o secvență infinită de numere 1 și 2, care este o codificare cu lungime de rulare [1] și un prototip pentru o familie infinită de secvențe înrudite. Inițial a fost numit după matematicianul William Kolakoski , care a propus-o în 1965 [2] , dar cercetările ulterioare au arătat că apare pentru prima dată într-o lucrare a lui Rufus Oldenburger ) în 1939 [3] .
Începutul secvenței Kolakoski:
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, ... (secvența A000002 în OEIS ).
Secvența, formată din numărul de cifre care apar într-o secvență pe rând, se potrivește exact cu secvența originală:
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, …În schimb, fiecare număr din șirul Kolakoski generează următoarele unul sau două numere, alternând unul și doi.
Această proprietate de auto-generare arată că secvența Kolakoski poate fi descrisă ca un fractal, adică un obiect matematic care codifică reprezentarea sa pe alte scale.
Secvența Kolakoski este considerată aperiodă [4] , adică nu are un model repetat.
Secvența Kolakoski este prototipul pentru o familie infinită de alte secvențe, fiecare cu propria sa codificare a lungimii de rulare. Unele dintre secvențele Kolakoski enumerate în OEIS sunt:
Pentru setul {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, … (secvența A064353 în OEIS )
Pentru setul {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, … (secvența A071820 în OEIS )
Pentru setul {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, … (secvența A079729 în OEIS )
Ca și secvența Kolakoski pentru {1,2}, scrierea lungimii rundei returnează aceeași secvență. În general, orice set de numere întregi {n 1 , n 2 , n 3 , …, n i } poate genera o secvență Kolakoski dacă același număr întreg nu apare de două ori sau mai multe la rând și/sau la începutul și sfârșitul a stabilit. De exemplu, pentru setul {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, …
Și pentru setul {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, …
Din nou, scrierea lungimilor de rulare returnează aceeași secvență.
Secvențele Kolakoski pot fi create și din seturi infinite de numere întregi.
De exemplu, pentru mulțimea {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, …
Mulțimea infinită {1,2,3,4,5,...} generează șirul Golomb:
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,… ( secvența OEIS A001462 )
Secvența Kolakoski poate fi creată și din numere întregi alese aleatoriu dintr-o mulțime finită, cu constrângerea că același număr nu poate fi ales de două ori la rând. Pentru o mulțime finită {1,2,3}, una dintre secvențele posibile este:
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, …
În esență, secvența se bazează pe mulțimea infinită {2,1,3,1,3,2,1,2,1,3,2,...}, care este o secvență aleatorie de 1s, 2s și 3s din care repetările au fost eliminate.
La fel cum secvența clasică Kolakoski se generează singură, aceste două secvențe se generează reciproc:
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,... (secvența A025142 în 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,… ( secvența A025143 în OEIS )
Cu alte cuvinte, dacă noti lungimile rundei primei secvențe, a doua va fi creată, iar dacă notezi lungimile rundei celei de-a doua secvențe, prima va fi creată.
În următorul lanț de trei secvențe de lungime de rulare, fiecare generează următoarele:
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,... (secvența A288723 în 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,... (secvența A288724 în 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,... (secvența A288725 în OEIS )
Secvențele folosesc setul întreg {1,2,3}, dar fiecare secvență începe cu un element diferit al mulțimii.
Următoarele cinci secvențe formează un lanț similar folosind setul {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,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,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,...
Cu toate acestea, pentru a crea un lanț de n elemente, nu este necesar să existe un set de n elemente. De exemplu, următorul lanț de cinci secvențe folosește setul {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,…
Fiecare secvență este unică, iar lungimile de execuție ale fiecăreia generează membrii următoarei secvențe din lanț. Seturile întregi utilizate pentru a crea lanțul pot fi, de asemenea, de diferite dimensiuni. Din seturile {1,2} și {1,2,3,4,5} sunt generate următoarele secvențe:
1,2,2,1,1,2,2,2,1,1,1,2,2,2,2,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,...
Pare plauzibil ca fracția celor din secvența clasică Kolakoski să fie 1/2, dar această presupunere rămâne nedovedită. [4] Václav Chvátal a demonstrat că limita superioară pentru fracția de unități este mai mică de 0,50084 [5] . John Nilson a folosit aceeași metodă cu mult mai multă putere de calcul pentru a obține o limită de 0,500080 [6] .
Deși primele 3×10 8 valori ale secvenței au fost utilizate în calcule, se pare că densitatea acesteia converge la o valoare ușor diferită de 1/2, dar calculele ulterioare au arătat că extinderea secvenței în primele 10 13 valori se abate de la fracția de unități cu 1/2 din ce în ce mai puțin, așa că ne putem aștepta ca fracția limită de unități să fie de fapt 1/2 [7] .
În secvența antikolakoski, lungimile rundelor de unu și doi nu se potrivesc niciodată cu membrii secvenței inițiale:
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, … (secvența A049705 în 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, …După cum puteți vedea, cei din secvența antikolakoski sunt în pozițiile în care cei doi sunt în secvența clasică Kolakoski și invers.
Constanta Kolakoski este definită în notație binară după cum urmează. La fiecare poziție binară după virgulă există un 1 dacă poziția corespunzătoare a șirului clasic Kolakoski este un doi și 0 dacă o unitate [8] . Prima unitate a secvenței este ignorată. În acest fel,
0,11001011011001001101001011001001011… 2 = 0,7945071927794792762403624156360456462… 10 .