Hofstadterova sekvence - Hofstadter sequence

v matematika, a Hofstadterova sekvence je členem rodiny příbuzných celočíselných sekvencí definovaných nelineární relace opakování.

Sekvence uvedené v Gödel, Escher, Bach: Věčný zlatý cop

První sekvence Hofstadter popsal Douglas Richard Hofstadter ve své knize Gödel, Escher, Bach. V pořadí jejich prezentace v kapitole III o obrázcích a pozadí (sekvence obrázek-obrázek) a kapitole V o rekurzivních strukturách a procesech (zbývající sekvence) jsou tyto sekvence:

Sekvence obrazců a obrazů Hofstadter

Sekvence Hofstadterova čísla (R a S) jsou dvojice komplementární celočíselné sekvence definováno následovně^[1][2]

${displaystyle {egin {aligned} R (1) & = 1 ~; S (1) = 2 R (n) & = R (n-1) + S (n-1), kvadrant n> 1. konec {zarovnáno}}}$

se sekvencí ${displaystyle S (n)}$ definována jako přísně rostoucí řada kladných celých čísel, která nejsou přítomna v ${displaystyle R (n)}$. Prvních pár termínů těchto sekvencí je

R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... (sekvence A005228 v OEIS )

S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... (sekvence A030124 v OEIS )

Sekvence Hofstadter G.

Sekvence Hofstadter G je definována následovně^[3][4]

${displaystyle {egin {aligned} G (0) & = 0 G (n) & = n-G (G (n-1)), quad n> 0.end {aligned}}}$

Prvních pár termínů této sekvence je

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... (sekvence A005206 v OEIS )

Sekvence Hofstadter H.

Sekvence H Hofstadter H je definována následovně^[3][5]

${displaystyle {egin {aligned} H (0) & = 0 H (n) & = n-H (H (H (n-1))), quad n> 0.end {aligned}}}$

Prvních několik termínů této sekvence je

0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, ... (sekvence A005374 v OEIS )

Ženské a mužské sekvence Hofstadter

Ženské (F) a mužské (M) sekvence Hofstadter jsou definovány následovně^[3][6]

${displaystyle {egin {aligned} F (0) & = 1 ~; M (0) = 0 F (n) & = nM (F (n-1)), quad n> 0 M (n) & = nF (M (n-1)), quad n> 0.end {zarovnaný}}}$

Prvních pár termínů těchto sekvencí je

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 )

Sekvence Hofstadter Q

Sekvence Hofstadter Q je definována následovně^[3][7]

${displaystyle {egin {aligned} Q (1) & = Q (2) = 1, Q (n) & = Q (nQ (n-1)) + Q (nQ (n-2)), quad n> 2. konec {zarovnáno}}}$

Prvních několik termínů sekvence je

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 pojmenoval termíny sekvence „Q numbers“;^[3] tedy Q číslo 6 je 4. Prezentace Q sekvence v knize Hofstadter je vlastně první známá zmínka o a sekvence meta-Fibonacci v literatuře.^[8]

Zatímco podmínky Fibonacciho sekvence jsou určeny sečtením dvou předchozích členů, dva předchozí členy čísla Q určují, jak daleko se v posloupnosti Q vrátit zpět, aby našli dva členy, které se mají sečíst. Indexy součtových členů tedy závisí na samotné Q posloupnosti.

Q (1), první prvek sekvence, nikdy není jedním ze dvou termínů přidávaných k vytvoření pozdějšího prvku; podílí se pouze na indexu při výpočtu Q (3).^[9]

Ačkoli se zdá, že pojmy posloupnosti Q plynou chaoticky,^{[3][10][11][12]} stejně jako mnoho meta-Fibonacciho sekvencí lze jeho termíny seskupit do bloků po sobě jdoucích generací.^[13][14] V případě sekvence Q se zobrazí k-tá generace má 2^k členů.^[15][16] Dále s G jsou generací, ke které Q číslo patří, dva pojmy, které se sečtou pro výpočet Q čísla, nazývané jeho rodiče, jsou zdaleka většinou v generaci G - 1 a jen několik generací G - 2, ale nikdy v ještě starší generaci.^[17]

Většina z těchto zjištění jsou empirická pozorování, protože prakticky nic nebylo důsledně prokázáno Q sekvence zatím.^[18][19][20] Není konkrétně známo, zda je posloupnost dobře definována pro všechny n; to znamená, že posloupnost v určitém okamžiku „umře“, protože její generační pravidlo se pokouší odkazovat na termíny, které by koncepčně seděly nalevo od prvního termínu Q (1).^[12][18][20]

Zobecnění Q sekvence

Hofstadter – Huber Q_r,s(n) rodina

20 let poté, co Hofstadter poprvé popsal Q sekvence, on a Greg Huber použil znak Q pojmenovat zevšeobecnění Q sekvence směrem k rodině sekvencí a přejmenoval originál Q sled jeho knihy do U sekvence.^[20]

Originál Q sekvence je zobecněna nahrazením (n - 1) a (n - 2) od (n − r) a (n − s).^[20]

To vede k rodině sekvencí

${displaystyle Q_ {r, s} (n) = {egin {cases} 1, quad 1leq nleq s, Q_ {r, s} (n-Q_ {r, s} (nr)) + Q_ {r, s } (n-Q_ {r, s} (ns)), quad n> s, end {cases}}}$

kde s ≥ 2 a r < s.

S (r,s) = (1,2), originál Q Sequence je členem této rodiny. Zatím jen tři sekvence rodiny Q_r,s jsou známé, jmenovitě U sekvence s (r,s) = (1,2) (což je originál.) Q sekvence);^[20] the PROTI sekvence s (r,s) = (1,4);^[21] a W sekvence s (r, s) = (2,4).^[20] Ukázalo se, že pouze V sekvence, která se nechová tak chaoticky jako ostatní, „neumře“.^[20] Podobně jako originál Q sekvence, prakticky nic dosud nebylo důsledně dokázáno o W sekvenci.^[20]

Prvních několik termínů sekvence V je

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (sekvence A063882 v OEIS )

Prvních pár termínů W sekvence je

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... (sekvence A087777 v OEIS )

Pro další hodnoty (r,s) sekvence dříve či později „umírají“, tj. existuje n pro který Q_r,s(n) není definováno, protože n − Q_r,s(n − r) < 1.^[20]

Pinn F_i,j(n) rodina

V roce 1998 Klaus Pinn, vědec na univerzitě v Münsteru (Německo), a v úzké komunikaci s Hofstadterem navrhl další zobecnění Hofstadterova Q sekvence, kterou Pinn zavolal F sekvence.^[22]

Rodina Pinna F_i,j sekvence je definována takto:

${displaystyle F_ {i, j} (n) = {egin {cases} 1, quad n = 1,2, F_ {i, j} (ni-F_ {i, j} (n-1)) + F_ {i, j} (nj-F_ {i, j} (n-2)), quad n> 2. end {cases}}}$

Pinn tedy zavedl další konstanty i a j které posouvají index pojmů součtu koncepčně doleva (tj. blíže k začátku posloupnosti).^[22]

Pouze F sekvence s (i,j) = (0,0), (0,1), (1,0) a (1,1), z nichž první představuje originál Q sekvence se jeví jako dobře definované.^[22] Na rozdíl od Q(1), první prvky Pinn F_i,j(n) posloupnosti jsou pojmy součtu při výpočtu pozdějších prvků posloupností, když je některá z dalších konstant 1.

Prvních pár termínů Pinna F_0,1 sekvence jsou

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... (sekvence A046699 v OEIS )

Sekvence Hofstadter – Conway 10 000 $

Sekvence Hofstadter – Conway 10 000 $ je definována následovně^[23]

${displaystyle {egin {aligned} a (1) & = a (2) = 1, a (n) & = a (a (n-1)) + a (na (n-1)), quad n> 2. konec {zarovnáno}}}$

Prvních pár termínů této sekvence je

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, ... (sekvence A004001 v OEIS )

Tato posloupnost získala své jméno, protože John Horton Conway nabídl cenu 10 000 $ každému, kdo by mohl prokázat konkrétní výsledek asymptotické chování. Cena, protože byla snížena na 1 000 $, byla nárokována společností Collin Mallows.^[24] V soukromé komunikaci s Klaus Pinn, Hofstadter později tvrdil, že sekvenci a její strukturu našel asi 10–15 let předtím, než Conway postavil svou výzvu.^[10]

Reference

Zdroje

• Balamohan, B .; Kuznetsov, A .; Tanny, Stephan M. (2007-06-27), „O chování varianty Hofstadterovy Q-sekvence“ (PDF), Journal of Integer SequencesWaterloo, Ontario (Kanada): University of Waterloo, 10, ISSN  1530-7638.
• Emerson, Nathaniel D. (2006-03-17), „Rodina sekvencí meta-fibonacci definovaná rekurzemi s proměnným řádem“ (PDF), Journal of Integer SequencesWaterloo, Ontario (Kanada): University of Waterloo, 9 (1), ISSN  1530-7638.
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: Věčný zlatý cop, Penguin Books, ISBN  0-14-005579-7.
• Pinn, Klaus (1999), „Řád a chaos v Hofstadterově sekvenci Q (n)“, Složitost, 4 (3): 41–46, arXiv:chao-dyn / 9803012v2, doi:10.1002 / (SICI) 1099-0526 (199901/02) 4: 3 <41 :: AID-CPLX8> 3.0.CO; 2-3.
• Pinn, Klaus (2000), „Chaotický bratranec Conwayovy rekurzivní sekvence“, Experimentální matematika, 9 (1): 55–66, arXiv:cond-mat / 9808031, Bibcode:1998.mat. Mat. 8031P.
• Wolfram, Stephen (2002), Nový druh vědy Wolfram Media, Inc., ISBN  1-57955-008-8.