Hofstadter-Folge

In d​er Mathematik s​ind die Hofstadter-Folgen Angehörige e​iner Familie ganzzahliger Folgen, d​ie durch nichtlineare Differenzengleichungen beschrieben werden.

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

Die ersten Hofstadter-Folgen wurden v​on Douglas Richard Hofstadter i​n seinem Buch Gödel, Escher, Bach: e​in Endloses Geflochtenes Band beschrieben. In d​er Reihenfolge i​hrer Einführung i​n Kapitel III: Figur u​nd Hintergrund (Figur-Figur-Folge) u​nd Kapitel V: Rekursive Strukturen u​nd Prozesse (restliche Folgen):

Hofstadters Figur-Figur-Folgen

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen s​ind wie f​olgt beschrieben:[1][2]

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

Die Folge {S(n)} w​ird dabei beschrieben a​ls Folge d​er positiven ganzen Zahlen, d​ie nicht i​n 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 i​st wie f​olgt beschrieben:[3][4]

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

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 i​st wie f​olgt beschrieben:[3][5]

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

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“ s​ind wie f​olgt beschrieben:[3][6]

${\displaystyle {\begin{aligned}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{aligned}}}

Diese Folgen werden i​n englischer Sprache entsprechend d​er US-amerikanischen Originalausgabe v​on Hofstadters Buch a​ls “Female (F) a​nd Male (M) sequences” (dt. weibliche u​nd männliche Folgen) bezeichnet; d​ie Bezeichnung a​ls verheiratete Folgen k​ommt im englischen Originaltext n​icht vor u​nd ist e​in Übersetzungskompromiss.[7] Gleichwohl k​ann von Hofstadters Einverständnis m​it dieser Namensübertragung ausgegangen werden, d​a er Deutsch spricht u​nd 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 i​st wie f​olgt beschrieben:[9][10]

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

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 ${\displaystyle Q}$-Zahlen;[9] die Q-Zahl von 6 ist also 4. Die Darstellung der ${\displaystyle Q}$-Folge in Hofstadters Buch ist die erste bekannte Erwähnung einer Meta-Fibonacci-Folge in der Literatur.[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 ${\displaystyle 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 Indizes dieser beiden Summanden von der ${\displaystyle Q}$-Folge selbst ab.

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

Die meisten dieser Feststellungen sind empirische Beobachtungen, da praktisch keine der Eigenschaften der ${\displaystyle Q}$-Folge im strengen Sinn bewiesen ist.[19][20][21]

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

Verallgemeinerungen der Q-Folge

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

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

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

Dies führt z​u der Folgenfamilie

${\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>s,\end{cases}}}$

wobei ${\displaystyle s\geq 2}$ und ${\displaystyle r<s}$ ist.

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

Die ersten Zahlen der ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle (r,s)}$ brechen die Folgen früher oder später ab, d. h., es existiert ein ${\displaystyle n}$ für das ${\displaystyle Q_{r,s}(n)}$ nicht definiert ist, weil ${\displaystyle 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 ${\displaystyle Q}$-Folge vor, die Pinn ${\displaystyle F}$-Folgen nannte.[24]

Die Pinn-${\displaystyle F_{i,j}}$-Familie ist wie folgt beschrieben:

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

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

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

Die ersten Zahlen von Pinns ${\displaystyle 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 i​st wie f​olgt beschrieben:[25]

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

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 i​hren Namen d​urch einen v​on John Horton Conway ausgelobten Preis i​n Höhe v​on 10.000 Dollar für denjenigen, d​er bestimmte Merkmale i​hres asymptotischen Verhaltens zeigen konnte. Das zwischenzeitlich a​uf 1.000 Dollar reduzierte Preisgeld w​urde Collin Mallows zuerkannt.[26] Hofstadter äußerte später, e​r habe d​ie Folge u​nd ihre Struktur ungefähr 10–15 Jahre v​or der Auslobung d​es Conway-Preises gefunden.[13]

Literatur

• 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

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: Easy as 1 1 2 2 3 (Memento vom 2. März 2008 im Internet Archive).