Hofstadterova sekvence

Hofstadterova posloupnost je jednou z rodiny celočíselných posloupností definovaných nelineárními rekurentními vzorci .

Sekvence od Gödela, Eschera, Bacha: tato nekonečná girlanda

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í

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 G sekvence

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 sekvence H

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 )

Hofstadterovy ženské a mužské sekvence

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 Q sekvence

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

Zobecnění Q posloupnosti

Rodina Hofstadter–Huber Q r , s ( n )

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] .

Rodina sekvencí F i , j ( n )

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 A046699

10 000 $ Hofstadter-Conway sekvence

Hofstadter-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] .

Poznámky

  1. ↑ Hofstadter, 1980 , s. 73.
  2. ↑ Weisstein, Eric W. Hofstadter Sekvence  obrázků a obrázků na webu Wolfram MathWorld .
  3. ↑ 1 2 3 4 5 6 Hofstadter, 1980 , str. 137.
  4. ↑ Weisstein, Eric W. Hofstadter G-Sequence  na webu Wolfram MathWorld .
  5. ↑ Weisstein, Eric W. Hofstadter H-Sequence  na webu Wolfram MathWorld .
  6. ↑ Weisstein, Eric W. Hofstadter Mužsko-ženské sekvence  na webu Wolfram MathWorld .
  7. ↑ Weisstein, Q-Sequence Erica W. Hofstadtera  na webu Wolfram MathWorld .
  8. ↑ Emerson, 2006 , str. 1, 7.
  9. ↑ Pinn, 1999 , str. 5–6.
  10. ↑ 12 Pinn , 1999 , s. 3.
  11. ↑ Pinn, 2000 , str. jeden.
  12. ↑ 12 Emerson , 2006 , s. 7.
  13. ↑ Pinn, 1999 , str. 3–4.
  14. ↑ Balamohan, Kuzněcov, Tanny, 2007 , str. 19.
  15. ↑ Pinn, 1999 , str. abstrakt, 8.
  16. ↑ Pinn, 1999 , str. 4–5.
  17. ↑ 12 Pinn , 1999 , s. 2.
  18. ↑ Pinn, 2000 , str. 3.
  19. ↑ 1 2 3 4 5 6 7 8 9 Balamohan, Kuzněcov, Tanny, 2007 , str. 2.
  20. ↑ Balamohan, Kuzněcov, Tanny, 2007 .
  21. ↑ 1 2 3 Pinn, 2000 , str. 16.
  22. ↑ Weisstein, Eric W. Hofstadter-Conway $10,000 sekvence  na webu Wolfram MathWorld .
  23. ↑ Tempel .

Literatura