Gijswijtsova sekvence - Gijswijts sequence - Wikipedia

v matematika, Gijswijtova sekvence (pojmenoval podle Dion Gijswijt podle Neil Sloane^[1]) je popisující sebe sekvence kde každý člen počítá maximální počet opakovaných bloků čísel v sekvenci bezprostředně předcházející tomuto členu.

Sekvence začíná:

1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... (sekvence A090822 v OEIS )

Sekvence je v definici podobná jako Kolakoski sekvence, ale namísto počítání nejdelšího běhu jednotlivých termínů počítá sekvence nejdelší běh bloků termínů jakékoli délky. Gijswijtova sekvence je známá svou pozoruhodně nízkou rychlostí růstu. Například první 4 se objeví na 220. termínu a prvních 5 se objeví poblíž ${ displaystyle 10 ^ {10 ^ {23}}}$druhý termín.^[1]

Definice

Proces generování termínů v posloupnosti lze definovat pohledem na posloupnost jako sérii písmen v abeceda z přirozená čísla:

1. ${ displaystyle a (1) = 1}$, a
2. ${ displaystyle a (n + 1) = k}$, kde ${ displaystyle k}$ je největší přirozené číslo takové, že slovo ${ displaystyle a (1) a (2) a (3) ... a (n)}$ lze napsat ve formě ${ displaystyle xy ^ {k}}$ na pár slov ${ displaystyle x}$ a ${ displaystyle y}$, s ${ displaystyle y}$ mající nenulovou délku.

Sekvence je základna -agnostik. To znamená, že pokud je nalezen běh 10 opakovaných bloků, další člen v sekvenci by byl jedno číslo 10, ne 1 následovaný 0.

Vysvětlení

Sekvence začíná 1 podle definice. 1 ve druhém členu pak představuje délku 1 bloku 1 s, který se nachází bezprostředně před ním v prvním členu. 2 ve třetím členu představuje délku 2 bloku 1 s, které jsou v prvním a druhém členu. V tomto bodě se posloupnost poprvé snižuje: 1 ve čtvrtém členu představuje délku 1 bloku 2 s ve třetím členu, stejně jako délku 1 bloku „1, 2“ překlenující druhý a třetí termín. Neexistuje žádný blok jakékoli opakované sekvence bezprostředně předcházející čtvrtému členu, který je delší než délka 1. Blok dvou 1 s v prvním a druhém členu nelze považovat za 4. člen, protože jsou ve 3. členu odděleny jiným číslem .

1 v pátém členu představuje délku 1 „opakujících se“ bloků „1“ a „2, 1“ a „1, 2, 1“ a „1, 1, 2, 1“, které bezprostředně předcházejí před pátým členem. Žádný z těchto bloků se neopakuje více než jednou, takže pátý člen je 1. 2 v šestém členu představuje délku opakovaného bloku 1 s bezprostředně vedoucího k šestému členu, jmenovitě ve 4. a 5. členu. Dvojka v sedmém semestru představuje 2 opakování bloku „1, 1, 2“ trvající termíny 1-3 a poté 4-6. Toto „slovo se třemi čísly“ se vyskytuje dvakrát bezprostředně před sedmým členem - hodnota sedmého členu je tedy 2.

Dvojka v osmém členu představuje délku opakovaného bloku 2 s bezprostředně vedoucího k osmému členu, konkrétně dvojice v šestém a sedmém členu. 3 v 9. členu představuje třikrát opakovaný blok jednoduchých 2s bezprostředně vedoucích k 9. členu, konkrétně dvojice v šestém, sedmém a osmém členu.

Vlastnosti

Pouze omezený výzkum se zaměřil na Gijswijtovu sekvenci. Proto se o sekvenci dokázalo velmi málo a mnoho otevřených otázek zůstává nevyřešených.

Rychlost růstu

Vzhledem k tomu, že 5 se objeví až kolem ${ displaystyle 10 ^ {10 ^ {23}}}$„Techniky vyhledávání hrubou silou by nikdy nenalezly první výskyt výrazu většího než 4. Bylo však prokázáno, že posloupnost obsahuje každé přirozené číslo.^[2] Přesná rychlost růstu není známa, ale předpokládá se její růst superlogaritmicky, s prvním výskytem jakékoli přírodní ${ displaystyle n}$ umístěn blízko ${ displaystyle 2 ^ {2 ^ {3 ^ {4 ^ {5 ^ {. ^ {. ^ {. {n-1}}}}}}}}}$.^[3]

Průměrná hodnota

Ačkoli je známo, že každé přirozené číslo se vyskytuje v konečné poloze v posloupnosti, předpokládá se, že posloupnost může mít konečnou znamenat. Chcete-li to formálně definovat na nekonečné posloupnosti, kde může záležet na přeuspořádání termínů, předpokládáme, že:

${ displaystyle lim _ {n to infty} { frac {1} {n}} součet _ {i = 1} ^ {n} a (i) < infty}$

Stejně tak hustota jakéhokoli daného přirozeného čísla v sekvenci není známo.^[1]

Rekurzivní struktura

Sekvence může být rozdělena na diskrétní sekvence „bloku“ a „lepidla“, které lze použít k rekurzivnímu vytvoření sekvence. Například na základní úrovni můžeme definovat ${ displaystyle B_ {1} = 1}$ a ${ displaystyle S_ {1} = 2}$ jako první blok a sekvence lepidla. Společně vidíme, jak tvoří začátek sekvence:

${ displaystyle B_ {1} B_ {1} S_ {1} = 1,1,2}$

Dalším krokem je rekurzivní sestavení sekvence. Definovat ${ displaystyle B_ {2} = B_ {1} B_ {1} S_ {1}}$. Všimněte si, že sekvence začíná ${ displaystyle B_ {1} B_ {1}}$, můžeme definovat lepicí řetězec ${ displaystyle S_ {2} = 2,2,3}$ který dává:

${ displaystyle B_ {2} B_ {2} S_ {2} = 1,1,2,1,1,2,2,2,3}$

Přidělili jsme ${ displaystyle S_ {2}}$ na konkrétní sekvenci, která dává vlastnost, že ${ displaystyle B_ {2} B_ {2} S_ {2} B_ {2} B_ {2} S_ {2}}$ také se vyskytuje v horní části sekvence.

V tomto procesu lze pokračovat donekonečna ${ displaystyle B_ {n + 1} = B_ {n} B_ {n} S_ {n}}$. Ukázalo se, že můžeme objevit lepicí řetězec ${ displaystyle S_ {n}}$ uvedením toho ${ displaystyle S_ {n}}$ nikdy nebude mít 1 a že se zastaví, jakmile dosáhne první 1, která bude následovat ${ displaystyle B_ {n} B_ {n}}$.^[3] Bylo také prokázáno, že Gijswijtova posloupnost může být vytvořena tímto způsobem na neurčito - tj. ${ displaystyle B_ {n}}$ a ${ displaystyle S_ {n}}$ jsou vždy konečné délky pro všechny ${ displaystyle n}$.^[2]

Chytrá manipulace se sekvencemi lepidla v této rekurzivní struktuře může být použita k prokázání, že Gijswijtova sekvence obsahuje kromě jiných vlastností sekvence všechna přirozená čísla.

Viz také

• Poslechněte si posloupnost
• Kolakoski sekvence
• Autogram

Reference

externí odkazy

• Prvních 50 milionů termínů
• OEIS sekvence A091579 (délky bloků přípon přidružených k A090822) - (délky sekvencí lepidla)

OEIS sekvence A090822 (Gijswijtova sekvence)