Hofstadterin sekvenssi

Hofstadter-sekvenssi on yksi epälineaarisilla toistuvilla kaavoilla määriteltyjen kokonaislukusekvenssien perheestä .

Sekvenssejä Gödeliltä, ​​Escheriltä, ​​Bachilta: tämä loputon seppele

Ensimmäiset Hofstadter-sekvenssit kuvaili Douglas Hofstadter kirjassaan Gödel, Escher, Bach . Sekvenssit on esitetty esitysjärjestyksessä luvussa III kuvioista ja taustasta (Kuva-Kuva-sekvenssi) ja luvussa V rekursiivisista rakenteista ja prosesseista (muut sekvenssit).

Hofstadterin piirustus-piirustussekvenssit

Hofstadter Drawing-Drawing -sekvenssit ( R ja S ) ovat komplementaaristen kokonaislukujonojen pari . Sarja { R } määritellään seuraavasti [1] [2]

ja sekvenssi {S( n )} määritellään tiukasti kasvavaksi positiivisten kokonaislukujen sarjaksi, jota ei ole {R( n )}:ssa. Näiden sekvenssien muutama ensimmäinen termi

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

Hofstadterin G-sekvenssi

Hofstadterin sekvenssi G määritellään seuraavasti [3] [4]

Tämän sarjan muutama ensimmäinen termi

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

Hofstadterin sekvenssi H

Hofstadterin sekvenssi H määritellään seuraavasti [3] [5]

Tämän sarjan muutama ensimmäinen termi

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

Hofstadterin nais- ja miesjaksot

Naaras (F) ja mies (M) Hofstadter-sekvenssit määritellään seuraavasti [3] [6]

Näiden sekvenssien muutama ensimmäinen termi

F: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... (sekvenssi A005378 OEIS : ssä ) M: 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (sekvenssi A005379 OEIS : ssä )

Hofstadterin Q-sekvenssi

Hofstadterin sekvenssi Q määritellään seuraavasti [3] [7] :

Tämän sarjan muutama ensimmäinen termi

1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (sekvenssi A005185 OEIS : ssä )

Hofstadter kutsui sekvenssin termejä "Q-luvuiksi" [3] . Siten Q:n kuudes luku on 4. Q-sekvenssin esitys Hofstadterin kirjassa on itse asiassa ensimmäinen maininta Fibonaccin metasekvensseistä kirjallisuudessa [8] .

Kun Fibonacci-luvut määritetään summaamalla kaksi edellistä termiä, Q-sekvenssin kaksi edellistä termiä määräävät, kuinka kauas taaksepäin sinun on mentävä sekvenssin termien summaamiseksi. Summausindeksit annetaan samalla sekvenssillä Q.

Q(1), sekvenssin ensimmäistä elementtiä, käytetään vain Q(3) laskemiseen [9] .

Vaikka Q-sekvenssi näyttää kaoottiselta [3] [10] [11] [12] , kuten monet muutkin Fibonacci-metasekvenssit, sen jäsenet voidaan ryhmitellä lohkoiksi [13] [14] . Sekvenssille Q k : nnessä lohkossa on 2 k jäsentä [15] . Lisäksi g :lle , joka kuuluu siihen lohkoon, johon Q-luku kuuluu, kaksi Q-luvun laskemiseen käytettyä termiä, joita kutsutaan vanhemmiksi, ovat enimmäkseen lohkossa g  − 1 ja vain muutama jäsen on lohkossa g  −. 2, mutta ei koskaan aikaisemmissa lohkoissa [16] .

Useimmat näistä havainnoista ovat empiirisiä havaintoja, koska Q -sekvenssistä ei ole toistaiseksi todistettu tiukasti [17] [18] [19] . Erityisesti ei tiedetä, onko sekvenssi hyvin määritelty kaikille n :ille . Eli "kuoleeko" sekvenssi jossain vaiheessa yrittämällä käyttää Q(1:n) ensimmäisen jäsenen vasemmalla puolella olevaa sekvenssijäsentä. [12] [17] [19]


Esimerkki algoritmin ymmärtämiseksi:

esimerkiksi arvot Q(1) = 1, Q(2) = 1 on korvattava (ehdon mukaan).

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

Q - sekvenssin yleistykset

Hofstadter–Huber-perhe Q r , s ( n )

20 vuotta sen jälkeen, kun Hofstadter kuvasi sekvenssin Q , Hofstadter ja Greg Huber käyttivät symbolia Q yleistääkseen sekvenssin Q sekvenssiperheeksi, ja alkuperäinen sekvenssi Q nimettiin uudelleen sekvenssiksi U [19] .

Alkuperäinen sarja Q yleistetään korvaamalla ( n  − 1) ja ( n  − 2) ( n  −  r ) ja ( n  −  s ) vastaavasti [19] .

Tämä johti sarjaperheeseen

missä s  ≥ 2 ja r  <  s .

Kohdalle ( r , s ) = (1,2) saadaan alkuperäinen sekvenssi Q , joten se on tämän perheen jäsen. Tällä hetkellä tunnetaan vain kolme sekvenssiä perheestä Q r , s , nimittäin sekvenssi U jossa ( r , s ) = (1,2) (alkuperäinen sekvenssi Q ) [19] , sekvenssi V jossa ( r , s ) ) = (1 ,4) [20] ja sekvenssi W , jossa (r,s) = (2,4) [19] . Vain sekvenssille V , joka ei toimi yhtä kaoottisesti kuin kaksi muuta, on todistettu, ettei se "kuole" [19] . Kuten alkuperäinen sekvenssi Q , mitään ei ole todistettu tarkasti sekvenssille W [19] .

Useita sekvenssin V ensimmäisiä termejä

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

Useita sekvenssin W ensimmäisiä termejä

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

Muille arvoille ( r , s ) sekvenssit "kuolevat" ennemmin tai myöhemmin, ts. on olemassa n , jolle Q :n arvor , s ( n ) on määrittelemätön, koska n  −  Qr , s ( n  −  r ) < 1 [19] .

Sekvenssien perhe F i , j ( n )

Vuonna 1998 Münsterin yliopiston (Saksa) tutkija Klaus Pinn, joka oli läheisessä yhteydessä Hofstadteriin, ehdotti toista yleistystä Hofstadterin Q -sekvenssistä ja kutsui tuloksena olevia sekvenssejä F - sekvensseiksi [21] .

Pinn-sekvenssien perhe F i , j määritellään seuraavasti:

Näin ollen Pinn otti käyttöön lisävakiot i ja j , jotka siirtävät summattujen termien indeksit vasemmalle (eli lähemmäksi sekvenssin alkua) [21] .

Vain sekvenssit F , joissa ( i , j ) = (0,0), (0,1), (1,0) ja (1,1), joista ensimmäinen on alkuperäinen sekvenssi Q , osoittautuvat hyvin- määritelty [21] . Toisin kuin Q (1), Pinn-sekvenssien Fi, j (n) ensimmäisiä alkioita käytetään sekvenssin muiden elementtien laskemiseen , jos yksi lisävakioista on 1 .

Sekvenssin muutama ensimmäinen termi 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 - sekvenssi A046699

10 000 dollaria Hofstadter-Conway-sarja

10 000 dollarin Hofstadter-Conway-sekvenssi määritellään seuraavasti [22]

Sarjan muutama ensimmäinen termi

1, 1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 12, … (sekvenssi A004001 OEIS : ssä )

Sekvenssi sai nimensä, koska John Horton Conway ilmoitti 10 000 dollarin bonuksen jokaiselle, joka pystyi osoittamaan tietyn tuloksen sekvenssin asymptoottisesta käyttäytymisestä. Palkinto, joka on alennettu 1 000 dollariin, meni Collin Mallowsille [23] . Yksityiskeskustelussa Klaus Pinnin kanssa Hofstadter väitti myöhemmin löytäneensä sarjan ja sen rakenteen noin 10-15 vuotta ennen Conwayn palkinnon julkistamista [10] .

Muistiinpanot

  1. ↑ Hofstadter, 1980 , s. 73.
  2. ↑ Weisstein, Eric W. Hofstadter Figuuri-  kuviosekvenssi Wolfram MathWorld -verkkosivustolla .
  3. ↑ 1 2 3 4 5 6 Hofstadter, 1980 , s. 137.
  4. ↑ Weisstein, Eric W. Hofstadter G-Sequence  Wolfram MathWorld -verkkosivustolla .
  5. ↑ Weisstein, Eric W. Hofstadter H-Sequence  Wolfram MathWorld -verkkosivustolla .
  6. ↑ Weisstein, Eric W. Hofstadter Mies-nainen sekvenssit  Wolfram MathWorld -verkkosivustolla .
  7. ↑ Weisstein, Eric W. Hofstadterin Q-sekvenssi  Wolfram MathWorld -verkkosivustolla .
  8. ↑ Emerson, 2006 , s. 1, 7.
  9. ↑ Pinn, 1999 , s. 5–6.
  10. ↑ 12 Pinn , 1999 , s. 3.
  11. ↑ Pinn, 2000 , s. yksi.
  12. ↑ 12 Emerson , 2006 , s. 7.
  13. ↑ Pinn, 1999 , s. 3–4.
  14. ↑ Balamohan, Kuznetsov, Tanny, 2007 , s. 19.
  15. ↑ Pinn, 1999 , s. abstrakti, 8.
  16. ↑ Pinn, 1999 , s. 4–5.
  17. ↑ 12 Pinn , 1999 , s. 2.
  18. ↑ Pinn, 2000 , s. 3.
  19. ↑ 1 2 3 4 5 6 7 8 9 Balamohan, Kuznetsov, Tanny, 2007 , s. 2.
  20. ↑ Balamohan, Kuznetsov, Tanny, 2007 .
  21. ↑ 1 2 3 Pinn, 2000 , s. 16.
  22. ↑ Weisstein, Eric W. Hofstadter-Conway 10 000 dollarin sekvenssi  Wolfram MathWorld -verkkosivustolla .
  23. ↑ Temppeli .

Kirjallisuus