Hofstadterova posloupnost je jednou z rodiny celočíselných posloupností definovaných nelineárními rekurentními vzorci .
První Hofstadterovy sekvence popsal Douglas Hofstadter ve své knize Gödel, Escher, Bach . Sekvence jsou uvedeny v pořadí jejich prezentace v kapitole III o obrázcích a pozadí (sekvence obrázek-obrázek) av kapitole V o rekurzivních strukturách a procesech (jiné sekvence).
Hofstadterovy sekvence kreslení a kreslení ( R a S ) jsou párem komplementárních celočíselných sekvencí . Posloupnost { R } je definována následovně [1] [2]
a sekvence {S( n )} je definována jako přísně rostoucí posloupnost kladných celých čísel, která nejsou přítomna v {R( n )}. Několik prvních členů těchto sekvencí
R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... ( sekvence OE22 A005 ) S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... ( sekvence OEIS A030124 )Hofstadterova sekvence G je definována následovně [3] [4]
Několik prvních členů této sekvence
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... ( sekvence OEIS A005206 )Hofstadterova posloupnost H je definována následovně [3] [5]
Několik prvních členů této sekvence
0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... ( sekvence OEIS A005374 )Samčí (F) a mužské (M) Hofstadterovy sekvence jsou definovány následovně [3] [6]
Několik prvních členů těchto sekvencí
F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... (sekvence A005378 v OEIS ) M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (sekvence A005379 v OEIS )Hofstadterova posloupnost Q je definována následovně [3] [7] :
Několik prvních členů této sekvence
1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (sekvence A005185 v OEIS )Hofstadter nazval členy posloupnosti „Q-čísla“ [3] . Šesté číslo Q je tedy 4. Zobrazení Q posloupnosti v Hofstadterově knize je ve skutečnosti první zmínkou o Fibonacciho metasekvencích v literatuře [8] .
Zatímco Fibonacciho čísla se určují součtem dvou předchozích členů, předchozí dva členy Q posloupnosti určují, jak daleko zpět musíte jít, abyste sečetli členy posloupnosti. Indexy pro sčítání jsou dány stejnou posloupností Q.
Q(1), první prvek sekvence, se používá pouze k výpočtu Q(3) [9] .
Přestože Q sekvence vypadá chaoticky [3] [10] [11] [12] , stejně jako mnoho dalších Fibonacciho meta-sekvencí lze její členy seskupovat do bloků [13] [14] . Pro posloupnost Q má k -tý blok 2 k členů [15] . Navíc pro g , které patří do bloku, do kterého Q-číslo patří, jsou dva členy používané k výpočtu Q-čísla, nazývané rodiče, většinou v bloku g − 1 a jen několik členů je v bloku g − 2, ale nikdy v dřívějších blocích [16] .
Většina z těchto nálezů jsou empirická pozorování, zatímco nic nebylo dokázané rigorózně o Q sekvenci doposud [17] [18] [19] . Zejména není známo, zda je sekvence dobře definovaná pro všechna n . To znamená, zda posloupnost v určitém okamžiku "umře" pokusem použít člen posloupnosti nalevo od prvního člena Q(1). [12] [17] [19]
Příklad pro pochopení algoritmu:
například je nutné dosadit hodnoty Q(1) = 1, Q(2)=1 (podmínkou).
Q(3) = Q(3-1)+Q(3-1) = Q(2)+ Q(2) = 2
Q(4) = (Q(4-Q(3))+Q(4-Q(2)) = Q(4-2)+Q(4-1) = Q(2)+Q(3) = 1+2=3
20 let po Hofstadterově popisu sekvence Q použili Hofstadter a Greg Huber symbol Q ke zobecnění sekvence Q na rodinu sekvencí a původní sekvence Q byla přejmenována na sekvenci U [19] .
Původní posloupnost Q je zobecněna nahrazením ( n − 1) a ( n − 2) za ( n − r ) respektive ( n − s ) [19] .
Výsledkem byla rodina sekvencí
kde s ≥ 2 a r < s .
Pro ( r , s ) = (1,2) získáme původní posloupnost Q , takže je členem této rodiny. V současné době jsou známy pouze tři posloupnosti rodiny Q r , s , a to posloupnost U s ( r , s ) = (1,2) (původní posloupnost Q ) [19] , posloupnost V s ( r , s ) = (1 ,4) [20] a posloupnost W s (r,s) = (2,4) [19] . Pouze u posloupnosti V , která se nechová tak chaoticky jako ostatní dvě, je dokázáno, že „neumírá“ [19] . Stejně jako původní posloupnost Q , ani u posloupnosti W nebylo nic striktně dokázáno [19] .
Několik prvních členů sekvence V
1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... ( sekvence OEIS A063882 )Několik prvních členů posloupnosti W
1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... ( sekvence OEIS A087777 )Pro ostatní hodnoty ( r , s ) sekvence dříve nebo později „umřou“, tzn. existuje n , pro které je hodnota Qr , s ( n ) není definováno, protože n − Qr , s ( n − r ) < 1 [19] .
V roce 1998 Klaus Pinn, vědec z univerzity v Münsteru (Německo), v úzkém kontaktu s Hofstadterem, navrhl další zobecnění Hofstadterovy Q sekvence a výsledné sekvence nazval F - sekvencemi [21] .
Rodina Pinnových sekvencí F i , j je definována takto:
Pinn tedy zavedl další konstanty i a j , které posouvají indexy sčítaných členů doleva (tedy blíže k začátku posloupnosti) [21] .
Dobře se ukázaly pouze sekvence F s ( i , j ) = (0,0), (0,1), (1,0) a (1,1), z nichž první je původní posloupnost Q . definováno [21] . Na rozdíl od Q (1) se první prvky Pinnových sekvencí F i , j ( n ) používají k výpočtu ostatních prvků v posloupnosti, pokud je jedna z dalších konstant 1.
Prvních několik členů sekvence F 0,1 Pinn
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... OEIS sekvence A046699Hofstadter-Conwayova sekvence 10 000 $ je definována následovně [22]
Několik prvních členů posloupnosti
1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (sekvence A004001 v OEIS )Sekvence dostala své jméno, protože John Horton Conway oznámil bonus 10 000 $ každému, kdo by mohl prokázat určitý výsledek o asymptotickém chování sekvence. Cenu sníženou na 1 000 $ získal Collin Mallows [23] . V soukromém rozhovoru s Klausem Pinnem Hofstadter později tvrdil, že našel sekvenci a její strukturu asi 10-15 let před Conwayovým oznámením ceny [10] .