www.wikidata.de-de.nina.az

Hofstadter Folge In der Mathematik sind die n Angehörige einer Familie ganzzahliger Folgen die durch nichtlineare Differ

Hofstadter-Folge

In der Mathematik sind die Hofstadter-Folgen Angehörige einer Familie ganzzahliger Folgen, die durch nichtlineare Differenzengleichungen beschrieben werden.

Hofstadter-Folgen aus dem Buch Gödel, Escher, Bach Bearbeiten

Die ersten Hofstadter-Folgen wurden von Douglas Richard Hofstadter in seinem Buch Gödel, Escher, Bach: ein Endloses Geflochtenes Band beschrieben. In der Reihenfolge ihrer Einführung in Kapitel III: Figur und Hintergrund (Figur-Figur-Folge) und Kapitel V: Rekursive Strukturen und Prozesse (restliche Folgen):

Hofstadters Figur-Figur-Folgen Bearbeiten

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen sind wie folgt beschrieben:

Die Folge {S(n)} wird dabei beschrieben als Folge der positiven ganzen Zahlen, die nicht in der Folge {R(n)} enthalten sind. Die ersten Zahlen dieser Folgen sind:

Hofstadters G-Folge Bearbeiten

Hofstadters G-Folge ist wie folgt beschrieben:

Die ersten Zahlen dieser Folge sind:

Hofstadters H-Folge Bearbeiten

Hoftstadters H-Folge ist wie folgt beschrieben:

Die ersten Zahlen dieser Folge sind:

Hofstadters „verheiratete Folgen“ Bearbeiten

Hofstadters „verheiratete Folgen“ sind wie folgt beschrieben:

Diese Folgen werden in englischer Sprache entsprechend der US-amerikanischen Originalausgabe von Hofstadters Buch als “Female (F) and Male (M) sequences” (dt. weibliche und männliche Folgen) bezeichnet; die Bezeichnung als verheiratete Folgen kommt im englischen Originaltext nicht vor und ist ein Übersetzungskompromiss. Gleichwohl kann von Hofstadters Einverständnis mit dieser Namensübertragung ausgegangen werden, da er Deutsch spricht und die deutsche Ausgabe seines Buches durchgesehen hat.

Die ersten Zahlen dieser Folgen sind:

Hofstadters Q-Folge Bearbeiten

Hofstadters Q-Folge ist wie folgt beschrieben:

Die ersten Zahlen dieser Folge sind:

Hofstadter nennt die Elemente dieser Folge -Zahlen; die Q-Zahl von 6 ist also 4. Die Darstellung der -Folge in Hofstadters Buch ist die erste bekannte Erwähnung einer Meta-Fibonacci-Folge in der Literatur.

Während die Elemente der Fibonacci-Folge durch das Summieren der beiden jeweils vorhergehenden Elemente bestimmt werden, bestimmen die beiden jeweils vorhergehenden Elemente einer -Zahl, um wie viele Elemente in der Q-Folge zurückgegangen werden soll, um zu den beiden Summanden zu gelangen. Daher hängen die Indizes dieser beiden Summanden von der -Folge selbst ab.

, das erste Element der Folge (die erste -Zahl), ist im Verlauf der Berechnung von Elementen der Q-Folge niemals als Summand an der Berechnung weiterer Elemente der Folge beteiligt; es wird allein verwendet, um den Index zu berechnen, mit dem auf das zweite Element der Folge Bezug genommen wird.

Obwohl sich die Elemente der -Folge chaotisch zu entwickeln scheinen, können ihre Elemente wie diejenigen vieler Meta-Fibonacci-Folgen in aufeinanderfolgende Blöcke gruppiert werden, die die Literatur als Generationen bezeichnet. Im Fall der -Folge hat die -te Generation Angehörige. Wenn außerdem die Generation angibt, der eine -Zahl angehört, dann sind die Summanden dieser -Zahl, die als Eltern bezeichnet werden, bei weitem am häufigsten in der Generation () angesiedelt und nur einige wenige in der Generation (), niemals jedoch in einer noch früheren Generation.

Die meisten dieser Feststellungen sind empirische Beobachtungen, da praktisch keine der Eigenschaften der -Folge im strengen Sinn bewiesen ist.

Es ist insbesondere unbekannt, ob die Folge für alle wohldefiniert ist, das heißt, ob die Folge irgendwo abbricht, weil ihre Produktionsregel versucht, sich auf Elemente zu beziehen, die sich konzeptuell links vom ersten Element befinden müssten.

Verallgemeinerungen der Q-Folge Bearbeiten

Hofstadter-Huber-Qr,s(n)-Familie Bearbeiten

Zwanzig Jahre nachdem Hofstadter die -Folge zum ersten Mal beschrieben hatte, verwendeten er und Greg Huber den Buchstaben , um eine Verallgemeinerung der -Folge zu einer Familie von Folgen zu bezeichnen. Die ursprüngliche -Folge aus seinem Buch benannten sie in -Folge um.

Die ursprüngliche -Folge wird verallgemeinert, indem () und () jeweils durch () und () ersetzt werden.

Dies führt zu der Folgenfamilie

wobei und ist.

Mit ist die ursprüngliche Q-Folge eine Angehörige dieser Familie. Bisher sind nur drei Folgen der Familie bekannt, nämlich die -Folge mit (die die ursprüngliche -Folge darstellt), die -Folge mit und die -Folge mit . Nur für die -Folge, die sich nicht so chaotisch wie die anderen verhält, ist bewiesen, dass sie nicht abbricht. Ähnlich der ursprünglichen -Folge wurden bis heute praktisch keine Eigenschaften der -Folge im strengen Sinn bewiesen.

Die ersten Zahlen der -Folge sind:

Die ersten Zahlen der -Folge sind:

Für andere Werte von brechen die Folgen früher oder später ab, d. h., es existiert ein für das nicht definiert ist, weil .

Pinn-Fi,j(n)-Familie Bearbeiten

1998 schlug Klaus Pinn, Wissenschaftler an der Westfälischen Wilhelms-Universität in Münster und in engem Kontakt mit Hofstadter, eine andere Verallgemeinerung von Hofstadters -Folge vor, die Pinn -Folgen nannte.

Die Pinn--Familie ist wie folgt beschrieben:

Pinn führte also die zusätzlichen Konstanten und ein, die den Index der Summanden konzeptuell nach links verschiebt (also näher an den Folgenanfang).

Nur die -Folgen mit und , deren erste die ursprüngliche -Folge darstellt, erscheinen wohldefiniert. Anders als sind die ersten Elemente der Pinn--Folgen Summanden bei der Berechnung weiterer Folgenelemente, wenn eine der zusätzlichen Konstanten 1 ist.

Die ersten Zahlen von Pinns -Folge sind:

Hofstadter-Conway-10.000-Dollar-Folge Bearbeiten

Die Hofstadter-Conway-10.000-Dollar-Folge ist wie folgt beschrieben:

Die ersten Zahlen dieser Folge sind:

Diese Folge erhielt ihren Namen durch einen von John Horton Conway ausgelobten Preis in Höhe von 10.000 Dollar für denjenigen, der bestimmte Merkmale ihres asymptotischen Verhaltens zeigen konnte. Das zwischenzeitlich auf 1.000 Dollar reduzierte Preisgeld wurde Collin Mallows zuerkannt. Hofstadter äußerte später, er habe die Folge und ihre Struktur ungefähr 10–15 Jahre vor der Auslobung des Conway-Preises gefunden.

Literatur Bearbeiten

  • B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behaviour of a Variant of Hofstadter’s Q-Sequence. In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 2007, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]).
  • Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]).
  • Douglas Richard Hofstadter: Gödel, Escher, Bach: an Eternal Golden Braid. Vintage Books, New York 1980, ISBN 0-465-02656-7.
  • Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X.
  • Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 41–46, arxiv:chao-dyn/9803012v2.
  • Klaus Pinn: A Chaotic Cousin of Conway’s Recursive Sequence. In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 55–66, arxiv:conat/9808031.
  • S. Plouffe, Neil J. A. Sloane: The Encyclopedia of Integer Sequences. Academic Press, San Diego 1995, ISBN 0-12-558630-2.
  • Neil J. A. Sloane: The On-Line Encyclopedia of Integer Sequences. In: Notices of the American Mathematical Society. Band 50, Nr. 8, 2003, S. 912 (ams.org [PDF; 92 kB]).

Einzelnachweise Bearbeiten

  1. Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 79.
  2. Mathworld: Hofstadter Figure-Figure Sequence
  3. ↑ Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 148.
  4. Mathworld: Hofstadter G-Sequence
  5. Mathworld: Hofstadter H-Sequence
  6. Mathworld: Hofstadter Male-Female Sequences
  7. Douglas Richard Hofstadter: Gödel, Escher, Bach: an Eternal Golden Braid. Vintage Books, New York, NY, USA 1980, ISBN 0-465-02656-7, S. 137.
  8. Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 820.
  9. ↑ Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 149.
  10. Mathworld: Hofstadter’s Q-Sequence
  11. ↑ Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638, S. 1, 7 (cs.uwaterloo.ca [PDF]).
  12. Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 5–6, arxiv:chao-dyn/9803012v2.
  13. ↑ Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 3, arxiv:chao-dyn/9803012v2.
  14. Klaus Pinn: A Chaotic Cousin of Conway’s Recursive Sequence. In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 1, arxiv:conat/9808031.
  15. Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 3–4, arxiv:chao-dyn/9803012v2.
  16. B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behaviour of a Variant of Hofstadter’s Q-Sequence. In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638, S. 19 (cs.uwaterloo.ca [PDF]).
  17. Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. Übersicht, 8, arxiv:chao-dyn/9803012v2.
  18. Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 4–5, arxiv:chao-dyn/9803012v2.
  19. ↑ Klaus Pinn: Order and Chaos in Hofstadter’s Q(n) Sequence. In: Complexity. Band 4, 1999, S. 2, arxiv:chao-dyn/9803012v2.
  20. Klaus Pinn: A Chaotic Cousin of Conway’s Recursive Sequence. In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 3, arxiv:conat/9808031.
  21. ↑ B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behaviour of a Variant of Hofstadter’s Q-Sequence. In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638, S. 2 (cs.uwaterloo.ca [PDF]).
  22. Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638, S. 7 (cs.uwaterloo.ca [PDF]).
  23. B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behaviour of a Variant of Hofstadter’s Q-Sequence. In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]).
  24. ↑ Klaus Pinn: A Chaotic Cousin of Conway’s Recursive Sequence. In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 16, arxiv:conat/9808031.
  25. Mathworld: Hofstadter-Conway $10,000 Sequence
  26. Michael Tempel: (Memento vom 2. März 2008 im Internet Archive).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Mathematik sind die Hofstadter Folgen Angehorige einer Familie ganzzahliger Folgen die durch nichtlineare Differenzengleichungen beschrieben werden Inhaltsverzeichnis 1 Hofstadter Folgen aus dem Buch Godel Escher Bach 1 1 Hofstadters Figur Figur Folgen 1 2 Hofstadters G Folge 1 3 Hofstadters H Folge 1 4 Hofstadters verheiratete Folgen 1 5 Hofstadters Q Folge 2 Verallgemeinerungen der Q Folge 2 1 Hofstadter Huber Qr s n Familie 2 2 Pinn Fi j n Familie 3 Hofstadter Conway 10 000 Dollar Folge 4 Literatur 5 EinzelnachweiseHofstadter Folgen aus dem Buch Godel Escher Bach BearbeitenDie ersten Hofstadter Folgen wurden von Douglas Richard Hofstadter in seinem Buch Godel Escher Bach ein Endloses Geflochtenes Band beschrieben In der Reihenfolge ihrer Einfuhrung in Kapitel III Figur und Hintergrund Figur Figur Folge und Kapitel V Rekursive Strukturen und Prozesse restliche Folgen Hofstadters Figur Figur Folgen Bearbeiten Hofstadters Figur Figur auch R und S Folgen sind wie folgt beschrieben 1 2 R 1 1 S 1 2 R n R n 1 S n 1 n gt 1 displaystyle begin aligned R 1 amp 1 S 1 2 R n amp R n 1 S n 1 quad n gt 1 end aligned nbsp Die Folge S n wird dabei beschrieben als Folge der positiven ganzen Zahlen die nicht in der Folge R n enthalten sind Die ersten Zahlen dieser Folgen sind R 1 3 7 12 18 26 35 45 56 69 83 98 114 131 150 170 191 213 236 260 Folge A005228 in OEIS S 2 4 5 6 8 9 10 11 13 14 15 16 17 19 20 21 22 23 24 25 Folge A030124 in OEIS Hofstadters G Folge Bearbeiten Hofstadters G Folge ist wie folgt beschrieben 3 4 G 0 0 G n n G G n 1 n gt 0 displaystyle begin aligned G 0 amp 0 G n amp n G G n 1 quad n gt 0 end aligned nbsp Die ersten Zahlen dieser Folge sind 0 1 1 2 3 3 4 4 5 6 6 7 8 8 9 9 10 11 11 12 12 Folge A005206 in OEIS Hofstadters H Folge Bearbeiten Hoftstadters H Folge ist wie folgt beschrieben 3 5 H 0 0 H n n H H H n 1 n gt 0 displaystyle begin aligned H 0 amp 0 H n amp n H H H n 1 quad n gt 0 end aligned nbsp Die ersten Zahlen dieser Folge sind 0 1 1 2 3 4 4 5 5 6 7 7 8 9 10 10 11 12 13 13 14 Folge A005374 in OEIS Hofstadters verheiratete Folgen Bearbeiten Hofstadters verheiratete Folgen sind wie folgt beschrieben 3 6 F 0 1 M 0 0 F n n M F n 1 n gt 0 M n n F M n 1 n gt 0 displaystyle begin aligned F 0 amp 1 M 0 0 F n amp n M F n 1 quad n gt 0 M n amp n F M n 1 quad n gt 0 end aligned nbsp Diese Folgen werden in englischer Sprache entsprechend der US amerikanischen Originalausgabe von Hofstadters Buch als Female F and Male M sequences dt weibliche und mannliche Folgen bezeichnet die Bezeichnung als verheiratete Folgen kommt im englischen Originaltext nicht vor und ist ein Ubersetzungskompromiss 7 Gleichwohl kann von Hofstadters Einverstandnis mit dieser Namensubertragung ausgegangen werden da er Deutsch spricht und die deutsche Ausgabe seines Buches durchgesehen hat 8 Die ersten Zahlen dieser Folgen sind F 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 Folge A005378 in OEIS M 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 Folge A005379 in OEIS Hofstadters Q Folge Bearbeiten Hofstadters Q Folge ist wie folgt beschrieben 9 10 Q 1 Q 2 1 Q n Q n Q n 1 Q n Q n 2 n gt 2 displaystyle begin aligned Q 1 amp Q 2 1 Q n amp Q n Q n 1 Q n Q n 2 quad n gt 2 end aligned nbsp Die ersten Zahlen dieser Folge sind 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 Folge A005185 in OEIS Hofstadter nennt die Elemente dieser Folge Q displaystyle Q nbsp Zahlen 9 die Q Zahl von 6 ist also 4 Die Darstellung der Q displaystyle Q nbsp Folge in Hofstadters Buch ist die erste bekannte Erwahnung einer Meta Fibonacci Folge in der Literatur 11 Wahrend die Elemente der Fibonacci Folge durch das Summieren der beiden jeweils vorhergehenden Elemente bestimmt werden bestimmen die beiden jeweils vorhergehenden Elemente einer Q displaystyle Q nbsp Zahl um wie viele Elemente in der Q Folge zuruckgegangen werden soll um zu den beiden Summanden zu gelangen Daher hangen die Indizes dieser beiden Summanden von der Q displaystyle Q nbsp Folge selbst ab Q 1 displaystyle Q 1 nbsp das erste Element der Folge die erste Q displaystyle Q nbsp Zahl ist im Verlauf der Berechnung von Elementen der Q Folge niemals als Summand an der Berechnung weiterer Elemente der Folge beteiligt es wird allein verwendet um den Index zu berechnen mit dem auf das zweite Element der Folge Bezug genommen wird 12 Obwohl sich die Elemente der Q displaystyle Q nbsp Folge chaotisch zu entwickeln scheinen 9 13 14 11 konnen ihre Elemente wie diejenigen vieler Meta Fibonacci Folgen in aufeinanderfolgende Blocke gruppiert werden die die Literatur als Generationen bezeichnet 15 16 Im Fall der Q displaystyle Q nbsp Folge hat die k displaystyle k nbsp te Generation 2 k displaystyle 2 k nbsp Angehorige 17 Wenn ausserdem g displaystyle g nbsp die Generation angibt der eine Q displaystyle Q nbsp Zahl angehort dann sind die Summanden dieser Q displaystyle Q nbsp Zahl die als Eltern bezeichnet werden bei weitem am haufigsten in der Generation g 1 displaystyle g 1 nbsp angesiedelt und nur einige wenige in der Generation g 2 displaystyle g 2 nbsp niemals jedoch in einer noch fruheren Generation 18 Die meisten dieser Feststellungen sind empirische Beobachtungen da praktisch keine der Eigenschaften der Q displaystyle Q nbsp Folge im strengen Sinn bewiesen ist 19 20 21 Es ist insbesondere unbekannt ob die Folge fur alle n displaystyle n nbsp wohldefiniert ist das heisst ob die Folge irgendwo abbricht weil ihre Produktionsregel versucht sich auf Elemente zu beziehen die sich konzeptuell links vom ersten Element Q 1 displaystyle Q 1 nbsp befinden mussten 19 22 21 Verallgemeinerungen der Q Folge BearbeitenHofstadter Huber Qr s n Familie Bearbeiten Zwanzig Jahre nachdem Hofstadter die Q displaystyle Q nbsp Folge zum ersten Mal beschrieben hatte verwendeten er und Greg Huber den Buchstaben Q displaystyle Q nbsp um eine Verallgemeinerung der Q displaystyle Q nbsp Folge zu einer Familie von Folgen zu bezeichnen Die ursprungliche Q displaystyle Q nbsp Folge aus seinem Buch benannten sie in U displaystyle U nbsp Folge um 21 Die ursprungliche Q displaystyle Q nbsp Folge wird verallgemeinert indem n 1 displaystyle n 1 nbsp und n 2 displaystyle n 2 nbsp jeweils durch n r displaystyle n r nbsp und n s displaystyle n s nbsp ersetzt werden 21 Dies fuhrt zu der Folgenfamilie Q r s n 1 1 n s Q r s n Q r s n r Q r s n Q r s n s n gt s displaystyle Q r s n begin cases 1 quad 1 leq n leq s Q r s n Q r s n r Q r s n Q r s n s quad n gt s end cases nbsp wobei s 2 displaystyle s geq 2 nbsp und r lt s displaystyle r lt s nbsp ist Mit r s 1 2 displaystyle r s 1 2 nbsp ist die ursprungliche Q Folge eine Angehorige dieser Familie Bisher sind nur drei Folgen der Familie Q r s displaystyle Q r s nbsp bekannt namlich die U displaystyle U nbsp Folge 21 mit r s 1 2 displaystyle r s 1 2 nbsp die die ursprungliche Q displaystyle Q nbsp Folge darstellt die V displaystyle V nbsp Folge 23 mit r s 1 4 displaystyle r s 1 4 nbsp und die W displaystyle W nbsp Folge 21 mit r s 2 4 displaystyle r s 2 4 nbsp Nur fur die V displaystyle V nbsp Folge die sich nicht so chaotisch wie die anderen verhalt ist bewiesen dass sie nicht abbricht 21 Ahnlich der ursprunglichen Q displaystyle Q nbsp Folge wurden bis heute praktisch keine Eigenschaften der W displaystyle W nbsp Folge im strengen Sinn bewiesen 21 Die ersten Zahlen der V displaystyle V nbsp Folge sind 1 1 1 1 2 3 4 5 5 6 6 7 8 8 9 9 10 11 11 11 Folge A063882 in OEIS Die ersten Zahlen der W displaystyle W nbsp Folge sind 1 1 1 1 2 4 6 7 7 5 3 8 9 11 12 9 9 13 11 9 Folge A087777 in OEIS Fur andere Werte von r s displaystyle r s nbsp brechen die Folgen fruher oder spater ab d h es existiert ein n displaystyle n nbsp fur das Q r s n displaystyle Q r s n nbsp nicht definiert ist weil n Q r s n r lt 1 displaystyle n Q r s n r lt 1 nbsp 21 Pinn Fi j n Familie Bearbeiten 1998 schlug Klaus Pinn Wissenschaftler an der Westfalischen Wilhelms Universitat in Munster und in engem Kontakt mit Hofstadter eine andere Verallgemeinerung von Hofstadters Q displaystyle Q nbsp Folge vor die Pinn F displaystyle F nbsp Folgen nannte 24 Die Pinn F i j displaystyle F i j nbsp Familie ist wie folgt beschrieben F i j n 1 n 1 2 F i j n i F i j n 1 F i j n j F i j n 2 n gt 2 displaystyle F i j n begin cases 1 quad n 1 2 F i j n i F i j n 1 F i j n j F i j n 2 quad n gt 2 end cases nbsp Pinn fuhrte also die zusatzlichen Konstanten i displaystyle i nbsp und j displaystyle j nbsp ein die den Index der Summanden konzeptuell nach links verschiebt also naher an den Folgenanfang 24 Nur die F displaystyle F nbsp Folgen mit i j 0 0 0 1 1 0 displaystyle i j 0 0 0 1 1 0 nbsp und 1 1 displaystyle 1 1 nbsp deren erste die ursprungliche Q displaystyle Q nbsp Folge darstellt erscheinen wohldefiniert 24 Anders als Q 1 displaystyle Q 1 nbsp sind die ersten Elemente der Pinn F i j n displaystyle F i j n nbsp Folgen Summanden bei der Berechnung weiterer Folgenelemente wenn eine der zusatzlichen Konstanten 1 ist Die ersten Zahlen von Pinns F 0 1 displaystyle F 0 1 nbsp Folge sind 1 1 2 2 2 3 4 4 4 4 5 6 7 8 8 8 8 8 8 9 Folge A055748 in OEIS Hofstadter Conway 10 000 Dollar Folge BearbeitenDie Hofstadter Conway 10 000 Dollar Folge ist wie folgt beschrieben 25 a 1 a 2 1 a n a a n 1 a n a n 1 n gt 2 displaystyle begin aligned a 1 amp a 2 1 a n amp a a n 1 a n a n 1 quad n gt 2 end aligned nbsp Die ersten Zahlen dieser Folge sind 1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12 Folge A004001 in OEIS Diese Folge erhielt ihren Namen durch einen von John Horton Conway ausgelobten Preis in Hohe von 10 000 Dollar fur denjenigen der bestimmte Merkmale ihres asymptotischen Verhaltens zeigen konnte Das zwischenzeitlich auf 1 000 Dollar reduzierte Preisgeld wurde Collin Mallows zuerkannt 26 Hofstadter ausserte spater er habe die Folge und ihre Struktur ungefahr 10 15 Jahre vor der Auslobung des Conway Preises gefunden 13 Literatur BearbeitenB Balamohan A Kuznetsov Stephan M Tanny On the Behaviour of a Variant of Hofstadter s Q Sequence In Journal of Integer Sequences Band 10 Nr 7 University of Waterloo 2007 ISSN 1530 7638 cs uwaterloo ca PDF Nathanial D Emerson A Family of Meta Fibonacci Sequences Defined by Variable Order Recursions In Journal of Integer Sequences Band 9 Nr 1 University of Waterloo 2006 ISSN 1530 7638 cs uwaterloo ca PDF Douglas Richard Hofstadter Godel Escher Bach an Eternal Golden Braid Vintage Books New York 1980 ISBN 0 465 02656 7 Douglas Richard Hofstadter Godel Escher Bach ein Endloses Geflochtenes Band 11 Auflage Klett Cotta Stuttgart 1988 ISBN 3 608 93037 X Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 41 46 arxiv chao dyn 9803012v2 Klaus Pinn A Chaotic Cousin of Conway s Recursive Sequence In Experimental Mathematics Band 9 Nr 1 2000 S 55 66 arxiv conat 9808031 S Plouffe Neil J A Sloane The Encyclopedia of Integer Sequences Academic Press San Diego 1995 ISBN 0 12 558630 2 Neil J A Sloane The On Line Encyclopedia of Integer Sequences In Notices of the American Mathematical Society Band 50 Nr 8 2003 S 912 ams org PDF 92 kB Einzelnachweise Bearbeiten Douglas Richard Hofstadter Godel Escher Bach ein Endloses Geflochtenes Band 11 Auflage Klett Cotta Stuttgart 1988 ISBN 3 608 93037 X S 79 Mathworld Hofstadter Figure Figure Sequence a b c Douglas Richard Hofstadter Godel Escher Bach ein Endloses Geflochtenes Band 11 Auflage Klett Cotta Stuttgart 1988 ISBN 3 608 93037 X S 148 Mathworld Hofstadter G Sequence Mathworld Hofstadter H Sequence Mathworld Hofstadter Male Female Sequences Douglas Richard Hofstadter Godel Escher Bach an Eternal Golden Braid Vintage Books New York NY USA 1980 ISBN 0 465 02656 7 S 137 Douglas Richard Hofstadter Godel Escher Bach ein Endloses Geflochtenes Band 11 Auflage Klett Cotta Stuttgart 1988 ISBN 3 608 93037 X S 820 a b c Douglas Richard Hofstadter Godel Escher Bach ein Endloses Geflochtenes Band 11 Auflage Klett Cotta Stuttgart 1988 ISBN 3 608 93037 X S 149 Mathworld Hofstadter s Q Sequence a b Nathanial D Emerson A Family of Meta Fibonacci Sequences Defined by Variable Order Recursions In Journal of Integer Sequences Band 9 Nr 1 University of Waterloo 2006 ISSN 1530 7638 S 1 7 cs uwaterloo ca PDF Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 5 6 arxiv chao dyn 9803012v2 a b Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 3 arxiv chao dyn 9803012v2 Klaus Pinn A Chaotic Cousin of Conway s Recursive Sequence In Experimental Mathematics Band 9 Nr 1 2000 S 1 arxiv conat 9808031 Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 3 4 arxiv chao dyn 9803012v2 B Balamohan A Kuznetsov Stephan M Tanny On the Behaviour of a Variant of Hofstadter s Q Sequence In Journal of Integer Sequences Band 10 Nr 7 University of Waterloo 27 Juni 2007 ISSN 1530 7638 S 19 cs uwaterloo ca PDF Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S Ubersicht 8 arxiv chao dyn 9803012v2 Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 4 5 arxiv chao dyn 9803012v2 a b Klaus Pinn Order and Chaos in Hofstadter s Q n Sequence In Complexity Band 4 1999 S 2 arxiv chao dyn 9803012v2 Klaus Pinn A Chaotic Cousin of Conway s Recursive Sequence In Experimental Mathematics Band 9 Nr 1 2000 S 3 arxiv conat 9808031 a b c d e f g h i B Balamohan A Kuznetsov Stephan M Tanny On the Behaviour of a Variant of Hofstadter s Q Sequence In Journal of Integer Sequences Band 10 Nr 7 University of Waterloo 27 Juni 2007 ISSN 1530 7638 S 2 cs uwaterloo ca PDF Nathanial D Emerson A Family of Meta Fibonacci Sequences Defined by Variable Order Recursions In Journal of Integer Sequences Band 9 Nr 1 University of Waterloo 2006 ISSN 1530 7638 S 7 cs uwaterloo ca PDF B Balamohan A Kuznetsov Stephan M Tanny On the Behaviour of a Variant of Hofstadter s Q Sequence In Journal of Integer Sequences Band 10 Nr 7 University of Waterloo 27 Juni 2007 ISSN 1530 7638 cs uwaterloo ca PDF a b c Klaus Pinn A Chaotic Cousin of Conway s Recursive Sequence In Experimental Mathematics Band 9 Nr 1 2000 S 16 arxiv conat 9808031 Mathworld Hofstadter Conway 10 000 Sequence Michael Tempel Easy as 1 1 2 2 3 Memento vom 2 Marz 2008 imInternet Archive Abgerufen von https de wikipedia org w index php title Hofstadter Folge amp oldid 208064542