A Kolakoski-szekvencia , más néven Oldenburger-Kolakoski-szekvencia , egy végtelen számú 1-es és 2 -es sorozat, amely egy futáshosszúságú kódolás [1] , és egy végtelen rokon sorozatok családjának prototípusa. Eredetileg William Kolakoski matematikusról nevezték el , aki 1965-ben javasolta [2] , de a későbbi kutatások kimutatták, hogy először Rufus Oldenburger ) 1939-ben megjelent cikkében [3] jelenik meg .
A Kolakoski sorozat eleje:
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, ... ( A000002 sorozat az OEIS -ben ).
A sorozat, amely egy sorban előforduló számjegyekből áll, pontosan megegyezik az eredeti sorozattal:
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, …Ezzel szemben a Kolakoski sorozat minden egyes száma generálja a következő egy vagy két számot, váltakozva egyesek és kettesek.
Ez az öngeneráló tulajdonság azt mutatja, hogy a Kolakoski sorozat fraktálként írható le, vagyis olyan matematikai objektumként, amely más léptékű reprezentációját kódolja.
A Kolakoski-szekvenciát aperiodikusnak tekintjük [4] , vagyis nincs ismétlődő mintázata.
A Kolakoski-szekvencia a prototípusa más sorozatok végtelen családjának, amelyek mindegyike saját futáshosszúságú kódolással rendelkezik. Az OEIS-ben felsorolt Kolakoski-szekvenciák közül néhány:
A(z) {1, 3} készlethez
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, … ( A064353 sorozat az OEIS -ben )
A(z) {2, 3} készlethez
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, … ( A071820 sorozat az OEIS -ben )
Az {1, 2, 3} készlethez
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, … ( A079729 sorozat az OEIS -ben )
Az {1,2} Kolakoski sorozatához hasonlóan a futási hosszok írása is ugyanazt a sorozatot adja vissza. Általánosságban elmondható, hogy az {n 1 , n 2 , n 3 , …, n i } egész számok bármelyik halmaza létrehozhat egy Kolakoski-sorozatot, ha ugyanaz az egész szám nem fordul elő kétszer vagy többször egymás után és/vagy a sor elején és végén. készlet. Például a {3,1,2} halmazhoz:
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, …
És a {2, 1, 3, 1} készlethez:
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, …
A futási hosszok írása ismét ugyanazt a sorozatot adja vissza.
Kolakoski sorozatok is létrehozhatók egész számok végtelen halmazából.
Például az {1, 2, 1, 3, 1, 4, 1, 5, ...} halmazhoz:
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, …
Az {1,2,3,4,5,…} végtelen halmaz létrehozza a Golomb sorozatot:
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 - szekvencia A001462 )
A Kolakoski sorozat egy véges halmazból véletlenszerűen kiválasztott egész számokból is létrehozható, azzal a megkötéssel, hogy ugyanazt a számot nem lehet kétszer egymás után kiválasztani. Egy véges {1,2,3} halmaz esetén az egyik lehetséges sorozat:
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, …
Lényegében a sorozat a {2,1,3,1,3,2,1,2,1,3,2,…} végtelen halmazon alapul, amely 1-es, 2-es és 3-as véletlenszerű sorozat, amelyből az ismétlések eltávolítva.
Ahogy a klasszikus Kolakoski szekvencia generálja önmagát, ez a két sorozat generálja egymást:
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,… ( A025142 sorozat az OEIS -ben )
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,… ( A025143 sorozat az OEIS -ben )
Más szóval, ha felírja az első sorozat futási hosszát, akkor létrejön a második, és ha kiírja a második sorozat futáshosszait, akkor az első.
A következő három futáshosszúságú sorozatból álló láncban mindegyik a következőket generálja:
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,… ( A288723 sorozat az OEIS -ben )
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,… ( A288724 sorozat az OEIS -ben )
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,… ( A288725 sorozat az OEIS -ben )
A sorozatok az {1,2,3} egész számkészletet használják, de minden sorozat a halmaz más elemével kezdődik.
A következő öt sorozat hasonló láncot alkot az {1,2,3,4,5} halmaz használatával:
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,…
Egy n elemből álló lánc létrehozásához azonban nem szükséges n elemből álló halmaz. Például a következő öt sorozatból álló lánc az {1, 2} halmazt használja:
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,…
Minden sorozat egyedi, és mindegyik végrehajtási hossza generálja a lánc következő sorozatának tagjait. A lánc létrehozásához használt egész halmazok is különböző méretűek lehetnek. Az {1,2} és {1,2,3,4,5} halmazokból a következő sorozatok jönnek létre:
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,…
Valószínűnek tűnik, hogy a klasszikus Kolakoski-szekvenciában az egyesek törtrésze 1/2, de ez a sejtés bizonyítatlan marad. [4] Václav Chvátal bebizonyította, hogy az egységek törtrészének felső korlátja kisebb, mint 0,50084 [5] . John Nilson ugyanazt a módszert használta, sokkal nagyobb számítási teljesítménnyel, hogy megkapja a 0,500080-as korlátot [6] .
Bár a sorozat első 3×10 8 értékét használtuk a számításokhoz, látszólag sűrűsége az 1/2-től kissé eltérő értékhez konvergál, de a későbbi számítások azt mutatták, hogy az első 10 13 értékben a sorozat bővülése Egyre kevesebbel tér el az egységek törtrészétől 1/2, így arra számíthatunk, hogy az egységek határtörtje valójában 1/2 [7] .
Az antikolakoski szekvenciában az egyesek és kettesek futásainak hossza soha nem egyezik az eredeti sorozat tagjaival:
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, … ( A049705 sorozat az OEIS -ben ).
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, …Amint láthatja, az antikolakoski szekvenciában szereplők azon a helyen vannak, ahol a kettesek a klasszikus Kolakoski sorozatban, és fordítva.
A Kolakoski-konstanst bináris jelöléssel a következőképpen definiáljuk. A tizedesvessző utáni minden bináris pozícióban 1 van, ha a klasszikus Kolakoski sorozat megfelelő pozíciója kettő, és 0, ha egység [8] . A sorozat első egységét figyelmen kívül hagyja. Ily módon
0,11001011011001001101001011001001011… 2 = 0,7945071927794792762403624156360456462… 10 .