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

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 Ⅲ: Figur und Hintergrund (Figur-Figur-Folge) und Kapitel Ⅴ: Rekursive Strukturen und Prozesse (restliche Folgen):

Hofstadters Figur-Figur-Folgen

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen sind wie folgt beschrieben: ^[1][2]

$\begin{align} R(1)&=1\ ;\ S(1)=2 \\ R(n)&=R(n-1)+S(n-1), \quad n>1. \end{align}$

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

Hofstadters G-Folge ist wie folgt beschrieben:^[3][4]

$\begin{align} G(0)&=0 \\ G(n)&=n-G(G(n-1)), \quad n>0. \end{align}$

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

Hoftstadters H-Folge ist wie folgt beschrieben:^[3][5]

$\begin{align} H(0)&=0 \\ H(n)&=n-H(H(H(n-1))), \quad n>0. \end{align}$

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«

Hofstadters »verheiratete Folgen« sind wie folgt beschrieben:^[3][6]

$\begin{align} F(0)&=1\ ;\ M(0)=0 \\ F(n)&=n-M(F(n-1)), \quad n>0 \\ M(n)&=n-F(M(n-1)), \quad n>0. \end{align}$

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.^[7] Gleichwohl kann von Hofstadters Einverständnis mit dieser Namensübertragung 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

Hofstadters Q-Folge ist wie folgt beschrieben:^[9][10]

$\begin{align} Q(1)&=Q(2)=1, \\ Q(n)&=Q(n-Q(n-1))+Q(n-Q(n-2)), \quad n>2. \end{align}$

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-Zahlen^[9]; die Q-Zahl von 6 ist also 4. Die Darstellung der Q-Folge in Hofstadters Buch ist die erste bekannte Erwähnung einer [11]

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

Q(1), das erste Element der Folge (die erste Q-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-Folge chaotisch zu entwickeln scheinen,^{[9][13][14][11]} können ihre Elemente wie diejenige vieler Meta-Fibonacci-Folgen in aufeinanderfolgende Blöcke gruppiert werden, die die Literatur als Generationen bezeichnet.^[15][16] Im Fall der Q-Folge hat die k-te Generation 2^k Angehörige.^[17] Wenn außerdem g die Generation angibt, der eine Q-Zahl angehört, dann sind die Summanden dieser Q-Zahl, die als Eltern bezeichnet werden, bei weitem am häufigsten in der Generation (g-1) angesiedelt und nur einige wenige in der Generation (g-2), niemals jedoch in einer noch früheren Generation.^[18]

Die meisten dieser Feststellungen sind empirische Beobachtungen, da praktisch keine der Eigenschaften der Q-Folge im strengen Sinn bewiesen sind.^[19][20][21]

Es ist insbesondere unbekannt, ob die Folge für alle n 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 Q(1) befinden müssten.^[19][22][21]

Verallgemeinerungen der Q-Folge

Hofstadter-Huber-Q_r,s(n)-Familie

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

Die ursprüngliche Q-Folge wird verallgemeinert, indem (n-1) und (n-2) jeweils durch (n-r) und (n-s) ersetzt werden.^[21]

Dies führt zu der Folgenfamilie

$Q_{r,s}(n) = \begin{cases} 1 , \quad 1 \le n \le s, \\ Q_{r,s}(n-Q_{r,s}(n-r))+Q_{r,s}(n-Q_{r,s}(n-s)), \quad n > s, \end{cases}$

wobei s≥2 und r<s ist.

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

Die ersten Zahlen der V-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-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)

Für andere Werte von (r,s) brechen die Folgen früher oder später ab, d.h. es existiert ein n für das Q_r,s(n) nicht definiert ist, weil n-Q_r,s(n-r) < 1.^[21]

Pinn-F_i,j(n)-Familie

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 Q-Folge vor, die Pinn F-Folgen nannte.^[24]

Die Pinn-F_i,j-Familie ist wie folgt beschrieben:

$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 > 2. \end{cases}$

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

Nur die F-Folgen mit (i,j) = (0,0), (0,1), (1,0) und (1,1), deren erste die ursprüngliche Q-Folge darstellt, erscheinen wohldefiniert.^[24] Anders als Q(1) sind die ersten Elemente der Pinn-F_i,j(n)-Folgen Summanden bei der Berechnung weiterer Folgenelemente, wenn eine der zusätzlichen Konstanten 1 ist.

Die ersten Zahlen von Pinns F_0,1-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

Die Hofstadter-Conway-10.000-Dollar-Folge ist wie folgt beschrieben:^[25]

$\begin{align} a(1)&=a(2)=1, \\ a(n)&=a(a(n-1))+a(n-a(n-1)), \quad n>2. \end{align}$

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 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.^[26] Hofstadter äußerte später, er habe die Folge und ihre Struktur ungefähr 10—15 Jahre vor der Auslobung des Conway-Preises gefunden.^[13]

Einzelnachweise

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. ↑ ^{a b c} 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 0465026567, 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. ↑ ^{a b c} 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. ↑ ^{a b} Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. 9, Nr. 1, University of Waterloo, Waterloo, Ontario (Kanada) 2006, ISSN 1530-7638, S. 1, 7 (http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.pdf).
12. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 4, 1999, S. 5—6, arXiv:chao-dyn/9803012v2.
13. ↑ ^{a b} Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 4, 1999, S. 3, arXiv:chao-dyn/9803012v2.
14. ↑ Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence. In: Experimental Mathematics. 9, Nr. 1, 2000, S. 1, arXiv:conat/9808031.
15. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 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. 10, Nr. 7, University of Waterloo, Waterloo, Ontario (Kanada) 27. Juni 2007, ISSN 1530-7638, S. 19 (http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.pdf).
17. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 4, 1999, S. Übersicht, 8, arXiv:chao-dyn/9803012v2.
18. ↑ Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 4, 1999, S. 4—5, arXiv:chao-dyn/9803012v2.
19. ↑ ^{a b} Klaus Pinn: Order and Chaos in Hofstadter's Q(n) Sequence. In: Complexity. 4, 1999, S. 2, arXiv:chao-dyn/9803012v2.
20. ↑ Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence. In: Experimental Mathematics. 9, Nr. 1, 2000, S. 3, arXiv:conat/9808031.
21. ↑ ^{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. 10, Nr. 7, University of Waterloo, Waterloo, Ontario (Kanada) 27. Juni 2007, ISSN 1530-7638, S. 2 (http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.pdf).
22. ↑ Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. 9, Nr. 1, University of Waterloo, Waterloo, Ontario (Kanada) 2006, ISSN 1530-7638, S. 7 (http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.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. 10, Nr. 7, University of Waterloo, Waterloo, Ontario (Kanada) 27. Juni 2007, ISSN 1530-7638 (http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.pdf).
24. ↑ ^{a b c} Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence. In: Experimental Mathematics. 9, Nr. 1, 2000, S. 16, arXiv:conat/9808031.
25. ↑ Mathworld: Hofstadter-Conway $10,000 Sequence
26. ↑ Easy as 1 1 2 2 3; Michael Tempel

Literatur

• B. Balamohan, A. Kuznetsov, Stephan M. Tanny: On the Behaviour of a Variant of Hofstadter's Q-Sequence. In: Journal of Integer Sequences. 10, Nr. 7, University of Waterloo, Waterloo, Ontario (Kanada) 2007, ISSN 1530-7638 (http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Tanny/tanny3.pdf).
• Nathanial D. Emerson: A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions. In: Journal of Integer Sequences. 9, Nr. 1, University of Waterloo, Waterloo, Ontario (Kanada) 2006, ISSN 1530-7638 (http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Emerson/emerson6.pdf).
• Douglas Richard Hofstadter: Gödel, Escher, Bach: an Eternal Golden Braid. Vintage Books, New York (USA) 1980, ISBN 0465026567.
• Douglas Richard Hofstadter: Gödel, Escher, Bach: ein EndlosesGeflochtenes 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. 4, 1999, S. 41—46, arXiv:chao-dyn/9803012v2.
• Klaus Pinn: A Chaotic Cousin of Conway's Recursive Sequence. In: Experimental Mathematics. 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 0125586302.
• Neil J. A. Sloane: The On-Line Encyclopedia of Integer Sequences. In: Notices of the American Mathematical Society. 50, Nr. 8, 2003, S. 912 (92 kB, http://www.ams.org/notices/200308/comm-sloane.pdf).