Kolakoski sekvence - Kolakoski sequence
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1d/Kolakoski_sequence_spiral.svg/300px-Kolakoski_sequence_spiral.svg.png)
v matematika, Kolakoski sekvence, někdy také známý jako Oldenburger-Kolakoski sekvence,[1] je nekonečná posloupnost symbolů {1,2}, což je sekvence vlastních délek běhu kódování délky běhu,[2] a prototyp nekonečné rodiny souvisejících sekvencí. Je pojmenován po rekreační matematik William Kolakoski (1944–1997), který to popsal v roce 1965,[3] ale následný výzkum ukázal, že sekvence byla dříve diskutována Rufus Oldenburger v roce 1939.[1][4]
Definice klasické sekvence Kolakoski
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Kolakoski_run_length.svg/256px-Kolakoski_run_length.svg.png)
Počáteční podmínky sekvence Kolakoski jsou:
Každý symbol se vyskytuje v „běhu“ (sekvenci stejných prvků) jednoho nebo dvou po sobě jdoucích termínů a zápis délky těchto běhů dává přesně stejnou sekvenci:
- 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,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...
- 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, 2 ,...
Popis sekvence Kolakoski je proto reverzibilní. Li K. znamená „sekvenci Kolakoski“, popis č. 1 logicky implikuje popis č. 2 (a naopak):
- 1. Podmínky K. jsou generovány běhy (tj. délkami běhu) K.
- 2. Běhy K. jsou generovány podmínkami K.
Podle toho lze říci, že každý člen Kolakoskiho posloupnosti generuje běh jednoho nebo dvou budoucích členů. První 1 sekvence generuje běh „1“, tj. Sám; první 2 generuje běh "22", který zahrnuje sebe; druhá 2 generuje běh "11"; a tak dále. Každé číslo v pořadí je délka dalšího generovaného běhu a živel které mají být generovány, střídá 1 až 2:
- 1,2 (délka sekvence l = 2; součet podmínek s = 3)
- 1,2,2 (l = 3, s = 5)
- 1,2,2,1,1 (l = 5, s = 7)
- 1,2,2,1,1,2,1 (l = 7, s = 10)
- 1,2,2,1,1,2,1,2,2,1 (l = 10, s = 15)
- 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 (l = 15, s = 23)
Jak je vidět, délka sekvence v každé fázi se rovná součtu termínů v předchozí fázi. Tato animace ilustruje postup:
![Animovaný gif ilustrující, jak jsou pozdější termíny sekvence Kolakoski generovány dřívějšími termíny.](http://upload.wikimedia.org/wikipedia/commons/a/ac/Kolakoski_animated.gif)
Tyto samy generující vlastnosti, které zůstanou, pokud je sekvence zapsána bez počáteční 1, znamenají, že Kolakoski sekvenci lze popsat jako fraktální nebo matematický objekt, který kóduje vlastní reprezentaci v jiných měřítcích.[1] Bertran Steinsky vytvořil rekurzivní vzorec pro i-tý člen posloupnosti[5] ale věří se, že sekvence je neperiodické,[6] to znamená, že její výrazy nemají obecný opakující se vzorec (srov. iracionální čísla jako π a √2 ).
Další samy generující se Kolakoski sekvence
Z konečných celočíselných abeced
Sekvence Kolakoski je prototypem pro nekonečnou rodinu dalších sekvencí, z nichž každá je jejich vlastním kódováním délky běhu. Každá sekvence je založena na tom, co se formálně nazývá abeceda celých čísel. Například výše popsaná klasická sekvence Kolakoski má abecedu {1,2}. Některé z dalších Kolakoski sekvencí uvedených na OEIS jsou:
- S abeceda {1,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,1,1,1,3,3,3,1,3, 3,3,1,1,1,3,3,3,1,3,3,3, ... (sekvence A064353 v OEIS )
- S abecedou {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, ... (sekvence A071820 v OEIS )
- S abecedou {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, ... (sekvence A079729 v OEIS )
Stejně jako v případě sekvence Kolakoski {1,2} vrací zápis délky běhu stejnou sekvenci. Obecněji libovolné abeceda celých čísel, {n1, n2, .. ni}, může vygenerovat sekvenci Kolakoski, pokud se stejné celé číslo nevyskytuje 1) dvakrát nebo více za sebou; 2) na začátku a na konci abecedy. Například abeceda {3,1,2} generuje:
- 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,...
A abeceda {2,1,3,1} generuje:
- 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,...
Opět platí, že zápis délky běhu vrátí stejnou sekvenci.
Z nekonečných celočíselných abeced
Sekvence Kolakoski lze také vytvořit z nekonečných abeced celých čísel, například {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,...
Nekonečná abeceda {1,2,3,4,5, ...} generuje Golombova sekvence:
- 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, ... (sekvence A001462 v OEIS )
Kolakoski sekvenci lze také vytvořit z vybraných celých čísel nahodile z omezené abecedy s omezením, že stejné číslo nelze vybrat dvakrát za sebou. Pokud je konečná abeceda {1,2,3}, je možná jedna sekvence:
- 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,...
Ve skutečnosti je sekvence založena na nekonečné abecedě {2,1,3,1,3,2,1,2,1,3,2, ...}, která obsahuje náhodnou sekvenci 1s, 2s a 3s ze kterých byla odstraněna opakování.
Řetězové sekvence
Zatímco klasická sekvence Kolakoski {1,2} se generuje sama, tyto dvě sekvence se generují navzájem:
- 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, ... (sekvence A025142 v 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, .. (sekvence A025143 v OEIS )
Jinými slovy, pokud napíšete délky běhu první sekvence, vygenerujete druhou; pokud napíšete délku běhu druhého, vygenerujete první. V následujícím řetězci tří sekvencí vygenerují délky běhu další v pořadí 1 → 2 → 3 → 1:
- 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, ... (sekvence A288723 v OEIS )
- 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, ... (sekvence A288724 v OEIS )
- 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, ... (sekvence A288725 v OEIS )
Sekvence používají celočíselnou abecedu {1,2,3}, ale každá začíná v jiném bodě abecedy. Následující pět sekvencí tvoří podobný řetězec pomocí abecedy {1,2,3,4,5}:
- 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, ...
Chcete-li však vytvořit sekvenční řetězec délky l, není nutné mít odlišné celočíselné abecedy velikosti l. Například abecední řada {2,1}, {1,2}, {1,2}, {1,2} a {1,2} je dostatečná pro pětičlánkový řetězec:
- seq (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,2,2,1, ...
- seq (2) = 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, ...
- seq (3) = 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, ...
- seq (4) = 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, ...
- seq (5) = 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, ...
Každá sekvence je jedinečná a délky běhu každé generují podmínky další sekvence v řetězci. Celočíselné abecedy použité ke generování řetězce mohou mít také různé velikosti. Z abecedy {1,2} a {1,2,3,4,5} lze vytvořit zrcadlo Kolakoski (jak by se dalo nazvat dvouřetězcový řetězec):
- seq (1) = 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, ...
- seq (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, ...
Výzkum klasické sekvence
Hustota sekvence
Zdá se pravděpodobné, že hustota 1 s v Kolakoskiho {1,2} sekvenci je 1/2, ale tato domněnka zůstává nepotvrzená.[6] Václav Chvátal prokázal, že horní hustota 1 s je menší než 0,50084.[7] Nilsson použil stejnou metodu s mnohem větším výpočetním výkonem k získání vázaných 0,500080.[8]
Ačkoli výpočty prvních 3 × 108 hodnoty sekvence ukazovaly, že její hustota konverguje k hodnotě mírně odlišné od 1/2,[5] pozdější výpočty, které posílily posloupnost na prvních 1013 hodnoty ukazují odchylku od hustoty 1/2, která se zmenšuje, jak by se dalo očekávat, pokud je mezní hustota ve skutečnosti 1/2.[9]
Spojení se systémy značek
Stephen Wolfram popisuje Kolakoski sekvenci v souvislosti s historií cyklické značkovací systémy.[10]
Jedinečnost sekvence
Některé diskuse o klasické Kolakoski posloupnosti tvrdí, že psáno s počáteční inicializací 1 nebo bez ní, je to „jediná sekvence“, která je vlastním kódováním běhu, nebo jediná taková sekvence, která začíná 1.[11][6] Jak je vidět výše, je to nepravdivé: tyto vlastnosti má nekonečné množství dalších sekvencí. Sekvence Kolakoski {1,2} - a {2,1} jsou však jedinými takovými sekvencemi, které používají pouze celá čísla 1 a 2.
Anti-Kolakoski sekvence
V anti-Kolakoski sekvenci se běhové délky 1 s a 2 s nikdy neshodují s podmínkami původní sekvence:
- 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, ... (sekvence A049705 v 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, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,...
Jak je vidět, délky antikolakoskiho sekvence vracejí sekvenci Kolakoski {1,2}, což znamená, že první může být vytvořena z druhé jednoduchým odečtením. Pokud k (i) je i-tý termín Kolakoski {1,2} -sekvence a ak (i) je i-th termín anti-Kolakoski sekvence, pak ak (i) = 3-k (i), jen se ptám(i) = 3-ak (i).[12] Podobně jako sekvence Kolakoski si tedy sekvence anti-Kolakoski zachovává svoji definiční vlastnost, když je psána bez počátečního termínu, tj. 2.[12]
Kolakoski konstantní
Takzvaný Kolakoski konstanta je vytvořeno odečtením 1 od každého členu Kolakoski {2,1} -sekvence (která začíná 22112122122 ...) a výsledkem je zacházeno binární zlomek.[13]
- 0.11001011011001001101001011001001011... = 2−1 + 2−2 + 2−5 + 2−7 + 2−8 + 2−10 + 2−11 + 2−14 + 2−17 + 2−18 + 2−20 + 2−23 + 2−25 + 2−26 + 2−29... = 0.7945071927794792762403624156360456462...[14]
Algoritmy
Algoritmus pro Kolakoskiho {1,2} sekvenci
Sekvence Kolakoski {1,2} může být generována pomocí algoritmus že v i-tá iterace, načte hodnotu Xi který již byl vydán jako i-tá hodnota sekvence (nebo, pokud žádná taková hodnota ještě nebyla vydána, nastaví se Xi = i). Pak, pokud i je liché, vydává se Xi kopie čísla 1, zatímco pokud i je dokonce, vydává Xi kopie čísla 2. Prvních několik kroků algoritmu je tedy:
- První hodnota ještě nebyla vydána, takže je nastavena X1 = 1 a vydá 1 kopii čísla 1
- Druhá hodnota ještě nebyla vydána, takže je nastavena X2 = 2 a výstup 2 kopie čísla 2
- Třetí hodnota X3 byl ve druhém kroku vydán jako 2, takže odešel 2 kopie čísla 1.
- Čtvrtá hodnota X4 byl ve třetím kroku vydán jako 1, takže výstup 1 kopie čísla 2. atd.
Tento algoritmus trvá lineární čas, ale protože potřebuje odkazovat zpět na dřívější pozice v sekvenci, potřebuje uložit celou sekvenci a zaujmout lineární prostor. Ke generování sekvence v lineárním čase lze použít alternativní algoritmus, který generuje více kopií sekvence při různých rychlostech, přičemž každá kopie sekvence využívá výstup předchozí kopie k určení, co dělat v každém kroku. logaritmický prostor.[9]
Obecný algoritmus pro Kolakoskiho sekvence
Obecně platí, že Kolakoskiho sekvence pro jakoukoli celočíselnou abecedu {n1, n2, .. nj} může být generován algoritmus že v i-tá iterace, načte hodnotu Xi který již byl vydán jako i-tá hodnota sekvence (nebo, pokud ještě nebyla žádná taková hodnota odeslána, nastaví se Xi = ni). V každém kroku výstup ni se upraví podle velikosti abecedy, návrat k n1 když je překročena konečná pozice v abecedě. Prvních několik kroků algoritmu pro abecedu {1,2,3,4} je:
- První hodnota ještě nebyla vydána, takže je nastavena X1 = 1 = n1a vydejte 1 kopii čísla 1
- Druhá hodnota ještě nebyla vydána, takže je nastavena X2 = 2 = n2a vydejte 2 kopie čísla 2
- Třetí hodnota X3 byl ve druhém kroku vydán jako 2, takže výstup 2 kopie 3 = n3.
- Čtvrtá hodnota X4 byl ve třetím kroku vydán jako 3, takže výstup 3 kopie 4 = n4.
- Pátá hodnota X5 byl ve třetím kroku vydán jako 3, takže výstup 3 kopie čísla 1 = n1 = upraveno (5).
- Šestá hodnota X6 byl ve čtvrtém kroku vydán jako 4, takže výstup 4 kopie čísla 2 = n2 = upraveno (6). Atd.
Výsledná sekvence je:
- 1,2,2,3,3,4,4,4,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,1,2, 3,4,4,1,1,2,2,3,3,4,4,4,1,1,1,2,2,2,3,3,3,4,4,4,4, 1,1,1,1,2,2,2,2,3,3,3,3, ... (sekvence A079730 v OEIS )
Algoritmus pro Kolakoski-řetězy
Kolakoskiho řetězce libovolné délky lze generovat jednoduchým algoritmem. Předpokládejme, že si přejete vygenerovat řetězec se 3 sekvencemi, kde termíny seq (i) jsou generovány délkami běhu seq (i + 1) a abeceda je {1,2}. Začněte nastavením prvního členu seq (1), počáteční sekvence v řetězci, na hodnotu 2. Další sekvence v řetězci, seq (2), jejíž délky běhu generují členy seq (1), proto musí mít výrazy (1,1). Proto seq (3), jehož délky běhu generují seq (2) = (1,1), musí mít běhy (1,2). Tady je první fáze algoritmu:
- Fáze 1
- seq (1) = 2
- seq (2) = 1,1
- seq (3) = 1,2
Nyní si všimněte, že délky běhu seq (1) generují podmínky seq (3), což znamená, že podmínky seq (3) generují běhy seq (1). Protože seq (3) = (1,2) po 1. fázi algoritmu, seq (1) se musí v další fázi rovnat (2,1,1). Z tohoto rozšířeného seq (1) lze generovat další běhy (a termíny) seq (2), pak další běhy (a termíny) seq (3):
- Fáze 2
- seq (1) = 2,1,1
- seq (2) = 1,1,2,1
- seq (3) = 1,2,1,1,2
Nyní použijte podmínky seq (3) ve fázi 2 ke generování dalších běhů seq (1) ve fázi 3:
- Fáze 3
- seq (1) = 2,1,1,2,1,2,2
- seq (2) = 1,1,2,1,2,2,1,2,2,1,1
- seq (3) = 1,2,1,1,2,1,1,2,2,1,2,2,1,1,2,1
- Fáze 4
- seq (1) = 2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1
- seq (2) = 1,1,2,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, ...
- seq (3) = 1,2,1,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, ...
- Fáze 5
- seq (1) = 2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1 , 2,2,1,1,2,1,1,2,1,2, ...
- seq (2) = 1,1,2,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, ...
- seq (3) = 1,2,1,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, ...
Sekvence lze nyní znovu uspořádat tak, aby doby běhu seq (i) generovaly podmínky seq (i + 1) (kde seq (3 + 1) = seq (1)):
- seq (1) = 2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,1,1,2,1,2,2,1 , 2,2,1,1,2,1,1,2,1,2, ...
- seq (2) = 1,2,1,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, ...
- seq (3) = 1,1,2,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, ...
Pokud má řetězec 5 sekvencí, získá algoritmus tyto fáze:
- Fáze 1
- seq (1) = 2
- seq (2) = 1,1
- seq (3) = 1,2
- seq (4) = 1,2,2
- seq (5) = 1,2,2,1,1
- Fáze 2
- seq (1) = 2,1,1,2,2,1,2
- seq (2) = 1,1,2,1,2,2,1,1,2,1,1
- seq (3) = 1,2,1,1,2,1,1,2,2,1,2,1,1,2,1
- seq (4) = 1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1
- seq (5) = 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
- Fáze 3
- seq (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,2,2,1, ...
- seq (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,2,2, ...
- seq (3) = 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, ...
- seq (4) = 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, ...
- seq (5) = 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, ...
Nakonec jsou sekvence znovu uspořádány tak, aby doby běhu seq (i) generovaly podmínky seq (i + 1):
- seq (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,2,2,1, ...
- seq (2) = 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, ...
- seq (3) = 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, ...
- seq (4) = 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, ...
- seq (5) = 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, ...
Viz také
- Golombova sekvence - další samy generující sekvence založená na délce běhu
- Gijswijtova sekvence
- Poslechněte si posloupnost
Poznámky
- ^ A b C Sloane, N. J. A. (vyd.). "Sekvence A000002 (Kolakoski sekvence: a (n) je délka n-tého běhu; a (1) = 1; sekvence se skládá pouze z 1 a 2)" ". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.
- ^ Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substituce v dynamice, aritmetice a kombinatorice. Přednášky z matematiky. 1794. Berlín: Springer-Verlag. str. 93. ISBN 3-540-44141-7. Zbl 1014.11015.
- ^ Kolakoski, William (1965). "Problém 5304". Americký matematický měsíčník. 72: 674. doi:10.2307/2313883. Částečné řešení viz Üçoluk, Necdet (1966). "Automaticky generované běhy". Americký matematický měsíčník. 73: 681–682. doi:10.2307/2314839.
- ^ Oldenburger, Rufus (1939). "Trajektorie komponent v symbolické dynamice". Transakce Americké matematické společnosti. 46: 453–466. doi:10.2307/198993. PAN 0000352.
- ^ A b Steinsky, Bertran (2006). "Rekurzivní vzorec pro sekvenci Kolakoski A000002" (PDF). Journal of Integer Sequences. 9 (3). Článek 06.3.7. PAN 2240857. Zbl 1104.11012.
- ^ A b C Kimberling, Clark. „Integer Sequences and Arrays“. University of Evansville. Citováno 2016-10-13.
- ^ Chvátal, Vašek (Prosinec 1993). Poznámky ke Kolakoskiho posloupnosti. Technická zpráva 93-84. DIMACY.
- ^ Nilsson, J. "Dopisové frekvence v Kolakoskiho posloupnosti" (PDF). Acta Physics Polonica A. Citováno 2014-04-24.
- ^ A b Nilsson, Johan (2012). „Prostorově efektivní algoritmus pro výpočet rozdělení číslic v sekvenci Kolakoski“ (PDF). Journal of Integer Sequences. 15 (6): Článek 12.6.7, 13. PAN 2954662.
- ^ Wolfram, Stephen (2002). Nový druh vědy. Champaign, IL: Wolfram Media, Inc. str.895. ISBN 1-57955-008-8. PAN 1920418.
- ^ Bellos, Alex (7. října 2014). „Neil Sloane: muž, který miloval pouze celočíselné sekvence“. Opatrovník. Citováno 13. června 2017.
- ^ A b Anti-Kolakoski sekvence (sekvence délek běhu se nikdy neshoduje se sekvencí samotnou).
- ^ „Kolakoski Sequence at MathWorld“. Citováno 2017-06-16.
- ^ Gerard, Olivier. "Kolakoski konstantní až 25 000 číslic". Citováno 2017-06-16.
Další čtení
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatické sekvence: Teorie, Aplikace, Zobecnění. Cambridge University Press. str.337. ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Dekking, F. M. (1997). „Co je objednávka na dlouhé vzdálenosti v sekvenci Kolakoski?“. In Moody, R. V. (ed.). Sborník NATO Advanced Study Institute, Waterloo, ON, 21. srpna - 1. září 1995. Dordrecht, Nizozemsko: Kluwer. str. 115–125.
- Fedou, J. M .; Fici, G. (2010). „Několik poznámek k odlišitelným sekvencím a rekurzivitě“ (PDF). Journal of Integer Sequences. 13 (3). Článek 10.3.2.
- Keane, M. S. (1991). "Ergodická teorie a podřazení konečného typu". V Bedfordu, T .; Keane, M. (eds.). Ergodická teorie, symbolická dynamika a hyperbolické prostory. Oxford, Anglie: Oxford University Press. str. 35–70.
- Lagarias, J. C. (1992). "Teorie čísel a dynamické systémy". v Burr, S.A. (vyd.). Nepřiměřená účinnost teorie čísel. Providence, RI: American Mathematical Society. str. 35–72.
- Păun, Gheorghe; Salomaa, Arto (1996). "Sekvence automatického čtení". Americký matematický měsíčník. 103: 166–168. doi:10.2307/2975113. Zbl 0854.68082.
- Shallit, Jeffrey (1999). "Teorie čísel a formální jazyky". v Hejhal, Dennis A.; Friedman, Joel; Gutzwiller, Martin C.; Odlyzko, Andrew M. (eds.). Nové aplikace teorie čísel. Na základě jednání z letního programu IMA, Minneapolis, MN, USA, 15. – 26. Července 1996. Objemy IMA v matematice a jejích aplikacích. 109. Springer-Verlag. 547–570. ISBN 0-387-98824-6. Zbl 0919.00047.
externí odkazy
- Weisstein, Eric W. „Kolakoski Sequence“. MathWorld.
- Konstanta Kolakoski na 25 000 číslic, jak ji vypočítal Olivier Gerard v dubnu 1998
- Bellos, Alex. „Kolakoski Sequence“ (video). Brady Haran. Citováno 24. července 2017.