Secvența Hofstadter

Secvența Hofstadter este una dintr-o familie de secvențe întregi definite prin formule recurente neliniare .

Secvențe din Gödel, Escher, Bach: această ghirlandă nesfârșită

Primele secvențe Hofstadter au fost descrise de Douglas Hofstadter în cartea sa Gödel, Escher, Bach . Secvențele sunt prezentate în ordinea prezentării lor în Capitolul III despre figuri și fundal (secvență Figura-Figură) și în Capitolul V despre structuri și procese recursive (alte secvențe).

Secvențele de desen-desen ale lui Hofstadter

Secvențele Hofstadter Drawing-Drawing ( R și S ) sunt o pereche de secvențe întregi complementare . Secvența { R } este definită după cum urmează [1] [2]

iar secvența {S( n )} este definită ca o secvență strict crescătoare de numere întregi pozitive care nu sunt prezente în {R( n )}. Primii termeni ai acestor secvențe

R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 170, 191, 213, 236, 260, ... ( secvența OEIS A005228 ) S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... ( secvența OEIS A030124 )

Secvența G a lui Hofstadter

Secvența G Hofstadter este definită după cum urmează [3] [4]

Primii termeni ai acestei secvențe

0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... ( secvența OEIS A005206 )

Secvența Hofstadter H

Secvența Hofstadter H este definită după cum urmează [3] [5]

Primii termeni ai acestei secvențe

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

Secvențele feminine și masculine ale lui Hofstadter

Secvențele Hofstadter feminine (F) și masculine (M) sunt definite după cum urmează [3] [6]

Primii termeni ai acestor secvențe

F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... (secvența A005378 în OEIS ) M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (secvența A005379 în OEIS )

Secvența Q a lui Hofstadter

Secvența Hofstadter Q este definită după cum urmează [3] [7] :

Primii termeni ai acestei secvențe

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (secvența A005185 în OEIS )

Hofstadter a numit termenii secvenței „numere Q” [3] . Astfel, al 6-lea număr al lui Q este 4. Reprezentarea secvenței Q în cartea lui Hofstadter este, de fapt, prima mențiune a meta-secvențelor Fibonacci în literatură [8] .

În timp ce numerele Fibonacci sunt determinate prin însumarea celor doi termeni anteriori, cei doi termeni anteriori ai secvenței Q determină cât de departe trebuie să mergeți pentru a lua termenii secvenței la suma. Indicii pentru însumare sunt dați de aceeași secvență Q.

Q(1), primul element al secvenței, este folosit doar pentru a calcula Q(3) [9] .

Deși secvența Q pare haotică [3] [10] [11] [12] , la fel ca multe alte meta-secvențe Fibonacci, membrii ei pot fi grupați în blocuri [13] [14] . Pentru secvența Q, blocul k -al are 2 k membri [15] . Mai mult, pentru g care aparține blocului căruia îi aparține numărul Q, cei doi termeni folosiți pentru calcularea numărului Q, numiți părinți, sunt în mare parte în blocul g  − 1 și doar câțiva membri sunt în blocul g  − 2, dar niciodată în blocurile anterioare [16] .

Cele mai multe dintre aceste constatări sunt observații empirice, deoarece nimic nu a fost dovedit riguros cu privire la secvența Q până în prezent [17] [18] [19] . În special, nu se știe dacă secvența este bine definită pentru toți n . Adică, secvența „moare” la un moment dat încercând să folosească membrul secvenței din stânga primului membru al lui Q(1). [12] [17] [19]


Un exemplu pentru a înțelege algoritmul:

de exemplu, este necesar să înlocuiți valorile Q(1) = 1, Q(2)=1 (prin condiție).

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

Generalizări ale secvenței Q

Familia Hofstadter–Huber Q r , s ( n )

La 20 de ani după descrierea de către Hofstadter a secvenței Q , Hofstadter și Greg Huber au folosit simbolul Q pentru a generaliza secvența Q la o familie de secvențe, iar secvența originală Q a fost redenumită secvența U [19] .

Secvența originală Q se generalizează prin înlocuirea ( n  − 1) și ( n  − 2) cu ( n  −  r ) și respectiv ( n  −  s ) [19] .

Acest lucru a dus la o familie de secvențe

unde s  ≥ 2 și r  <  s .

Pentru ( r , s ) = (1,2) obținem șirul inițial Q , astfel încât să fie membru al acestei familii. În prezent, sunt cunoscute doar trei secvențe din familia Q r , s , și anume, secvența U cu ( r , s ) = (1,2) (secvența originală Q ) [19] , șirul V cu ( r , s ) ) = (1 ,4) [20] și o secvență W cu (r,s) = (2,4) [19] . Numai pentru secvența V , care nu se comportă la fel de haotic ca celelalte două, se demonstrează că nu „moare” [19] . Ca și secvența originală Q , nimic nu a fost dovedit strict pentru șirul W [19] .

Câțiva primii termeni ai secvenței V

1, 1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... ( secvența OEIS A063882 )

Câțiva primii termeni ai secvenței W

1, 1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 9, 13, 11, 9, ... ( secvența OEIS A087777 )

Pentru alte valori ( r , s ) secvențele „mor” mai devreme sau mai târziu, adică. există n pentru care valoarea lui Qr , s ( n ) este nedefinit deoarece n  −  Qr , s ( n  −  r ) < 1 [19] .

O familie de secvențe F i , j ( n )

În 1998, Klaus Pinn, un om de știință de la Universitatea din Münster (Germania), în strâns contact cu Hofstadter, a propus o altă generalizare a secvenței Q a lui Hofstadter și a numit secvențele rezultate F - secvențe [21] .

Familia de secvențe Pinn Fi, j este definită după cum urmează:

Astfel, Pinn a introdus constante suplimentare i și j , care deplasează indicii termenilor însumați la stânga (adică mai aproape de începutul secvenței) [21] .

Numai secvențele F cu ( i , j ) = (0,0), (0,1), (1,0) și (1,1), dintre care prima este șirul original Q , se dovedesc a fi bine- definit [21] . Spre deosebire de Q ( 1 ), primele elemente ale secvențelor Pinn Fi , j ( n ) sunt folosite pentru a calcula celelalte elemente din secvență dacă una dintre constantele suplimentare este 1.

Primii termeni ai secvenței F 0,1 Pinn

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 6, 7, 8, 8, 8, 8, 9, 10, 10, 11, ... secvența OEIS A046699

Secvența Hofstadter-Conway de 10.000 USD

Secvența Hofstadter-Conway de 10.000 USD este definită după cum urmează [22]

Primii termeni ai secvenței

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (secvența A004001 în OEIS )

Secvența și-a primit numele deoarece John Horton Conway a anunțat un bonus de 10.000 de dolari oricui ar putea demonstra un anumit rezultat despre comportamentul asimptotic al secvenței. Premiul, redus la 1.000 de dolari, a revenit lui Collin Mallows [23] . Într-o conversație privată cu Klaus Pinn, Hofstadter a susținut mai târziu că a găsit secvența și structura ei cu aproximativ 10-15 ani înainte de anunțarea de către Conway a premiului [10] .

Note

  1. ↑ Hofstadter, 1980 , p. 73.
  2. ^ Weisstein , Eric W. Hofstadter Figure-Figure Sequence  pe site- ul Wolfram MathWorld .
  3. ↑ 1 2 3 4 5 6 Hofstadter, 1980 , p. 137.
  4. ^ Weisstein , Eric W. Hofstadter G-Sequence  pe site- ul Wolfram MathWorld .
  5. ^ Weisstein , Eric W. Hofstadter H-Sequence  pe site- ul Wolfram MathWorld .
  6. ^ Weisstein , Eric W. Hofstadter Secvențe masculin-femeie  pe site- ul Wolfram MathWorld .
  7. ^ Weisstein , Q-Sequence a lui Eric W. Hofstadter pe site- ul Wolfram MathWorld . 
  8. ↑ Emerson, 2006 , p. 1, 7.
  9. ↑ Pinn, 1999 , p. 5–6.
  10. ↑ 12 Pinn , 1999 , p. 3.
  11. ↑ Pinn, 2000 , p. unu.
  12. ↑ 12 Emerson , 2006 , p. 7.
  13. ↑ Pinn, 1999 , p. 3–4.
  14. ↑ Balamohan, Kuznetsov, Tanny, 2007 , p. 19.
  15. ↑ Pinn, 1999 , p. abstract, 8.
  16. ↑ Pinn, 1999 , p. 4–5.
  17. ↑ 12 Pinn , 1999 , p. 2.
  18. ↑ Pinn, 2000 , p. 3.
  19. ↑ 1 2 3 4 5 6 7 8 9 Balamohan, Kuznetsov, Tanny, 2007 , p. 2.
  20. ↑ Balamohan, Kuznetsov, Tanny, 2007 .
  21. ↑ 1 2 3 Pinn, 2000 , p. 16.
  22. ^ Weisstein , Eric W. Hofstadter-Conway Secvență de 10.000 USD  pe site- ul web Wolfram MathWorld .
  23. ↑ Tempel .

Literatură