Sekvence hledej a řekni

Sekvence Look-and-Say  je posloupnost čísel, která začíná takto:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,… (sekvence A005150 v OEIS ).

Každé následující číslo je generováno z předchozího zřetězením číslice, která tvoří skupinu shodných číslic, a počtu číslic v této skupině, pro každou skupinu shodných číslic v čísle. Například:

• 1 se čte jako „jedna jednotka“, tedy 11
• 11 se čte jako „dvě jednotky“, tedy 21
• 21 se čte jako „jedna dvě, jedna jednotka“, tedy 1211
• 1211 se čte jako „jedna jednotka, jedna dvě, dvě jednotky“, tedy 111221
• 111221 se čte jako „tři jedničky, dvě dvojky, jedna jednotka“, tedy 312211
• 312211 se čte jako „jedna tři, jedna jedna, dva dva, dvě jedničky“, tj. 13112221

Sekvenci look-and-tell navrhl John Conway [1] .

Pro libovolnou číslici d , kromě jedné, jako počáteční, má posloupnost tvar:

d , 1 d , 111 d , 311 d , 13211 d , 111312211 d , 31131122211 d , …

Základní vlastnosti

Růst

Sekvence roste donekonečna. Ve skutečnosti bude jakákoli varianta sekvence s celočíselným semenem růst donekonečna. Výjimkou je sekvence:

22, 22, 22, 22, 22, … (sekvence A010861 v OEIS ).

Omezení počtu použitých číslic

V posloupnosti se nevyskytují žádné jiné číslice než 1, 2 a 3, pokud počáteční číslo neobsahuje jiné číslice nebo skupinu více než tří číslic [2] .

Délkový růst čísel

V průměru čísla rostou o 30 % na iteraci. Jestliže označuje délku n-tého členu posloupnosti, pak existuje limita vztahu :

.

Zde λ = 1,303577269034… je Conwayova konstanta [2] . Stejný výsledek je platný pro jakoukoli variantu sekvence s jiným semenem než 22.

Polynom vracející Conwayovu konstantu

Conwayova konstanta je jediným kladným skutečným kořenem polynomu:

Ve svém původním článku dělá Conway tu chybu, že píše „−“ místo „+“ před . Ale hodnota λ uvedená v jeho článku je správná [3] .

Popularizace

Sekvence Look-and-Say je také známá jako Morrisova číselná sekvence podle kryptografa Roberta Morrise . Někdy označované jako „kukaččí vejce“ kvůli hádance „Jaké je další číslo v sekvenci 1, 11, 21, 1211, 111221?“, kterou popsal Morris v knize Clifforda Stolla Kukaččí vejce.

Variace

Existuje mnoho variant pravidel pro vytváření sekvencí look-and-tell. Například sekvence "hrachový vzor". Od Look-and-Say se liší tím, že k získání nového čísla v něm musíte počítat všechny stejné číslice. Počínaje číslem 1 dostaneme: 1, 11 (jedna jedna), 21 (dvě jedničky), 1211 (jedna dvě, jedna jedna), 3112 (tři jedničky, jedna dvě), 132112 (jedna tři, dvě jedničky, jedna dvě) , 312213 (tři 1, dvě 2, jedna 3) atd. Výsledkem je, že posloupnost přejde do cyklu dvou čísel 23322114 a 32232114. [4]

Existuje další možnost, která se liší od "hrachového vzoru" tím, že čísla se počítají ve vzestupném pořadí, a ne tak, jak se objevují. Začneme-li od jedničky, dostaneme sekvenci: 1, 11, 21, 1112, 3112, 211213, 312213, ...

Tyto sekvence mají výrazné rozdíly od Look-and-Say. Na rozdíl od Conwayovy sekvence daný termín v "hrachovém vzoru" jednoznačně neidentifikuje předchozí termín. Délka čísel v "hrachovém vzoru" je omezená a pro b-ární číselný systém nepřesahuje 2b a dosahuje 3b pro velká počáteční čísla (například "sto jednotek").

Vzhledem k tomu, že tato sekvence je nekonečná a její délka je omezená, musí se nakonec opakovat podle Dirichletova principu . V důsledku toho jsou tyto sekvence vždy periodické.

Viz také

• Kolakoskiho sekvence
• Gheesweet sekvence

Poznámky

1. ↑ John Horton Conway. Podivná a úžasná chemie audioaktivního rozpadu   // Eureka . - 1986. - Leden ( sv. 46 ). - str. 5-16 . Archivováno z originálu 11. října 2014.
2. ↑ 12 Oscar Martin . Look-and-Say Biochemistry: Exponenciální RNA a vícevláknová DNA //  American Mathematical Monthly. - 2006. - Sv. 113 , č. 4 . - str. 289-307 . — ISSN 0002-9890 . Archivováno z originálu 24. prosince 2006.  
3. ↑ Ilan Vardi. Výpočetní rekreace v Mathematice.
4. ↑ Generátor vzestupných vzorů hrachu . Získáno 9. srpna 2018. Archivováno z originálu 17. října 2016. (neurčitý)