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

Hofstadters Figur-Figur-Folgen

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen sind wie folgt beschrieben:<ref name="Hofstadter_1988_S79">Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 79. </ref><ref></ref>

<math>

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

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:<ref name="Hofstadter_1988_S148">Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 148. </ref><ref></ref>

<math>

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

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)

Diese Folge erhält man, indem man bei den natürlichen Zahlen 0, 1, 2, 3, … jede Zahl doppelt schreibt, die in der unteren Wijthoff-Folge vorkommt, d. h. 1, 3, 4, …

Hofstadters H-Folge

Hofstadters H-Folge ist wie folgt beschrieben:<ref name="Hofstadter_1988_S148" /><ref></ref>

<math>

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

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:<ref name="Hofstadter_1988_S148" /><ref></ref>

<math>

\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} </math>

Diese Folgen werden in englischer Sprache entsprechend der US-amerikanischen Originalausgabe von Hofstadters Buch als “” (dt. weibliche und männliche Folgen) bezeichnet; die Bezeichnung als verheiratete Folgen kommt im englischen Originaltext nicht vor und ist ein Übersetzungskompromiss.<ref>Douglas Richard Hofstadter: . , New York, NY, USA 1980, ISBN 0-465-02656-7, S. 137. </ref> Gleichwohl kann von Hofstadters Einverständnis mit dieser Namensübertragung ausgegangen werden, da er Deutsch spricht und die deutsche Ausgabe seines Buches durchgesehen hat.<ref>Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 820. </ref>

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:<ref name="Hofstadter_1988_S149">Douglas Richard Hofstadter: Gödel, Escher, Bach: ein Endloses Geflochtenes Band. 11. Auflage. Klett-Cotta, Stuttgart 1988, ISBN 3-608-93037-X, S. 149. </ref><ref></ref>

<math>

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

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 <math>Q</math>-Zahlen;<ref name="Hofstadter_1988_S149" /> die Q-Zahl von 6 ist also 4. Die Darstellung der <math>Q</math>-Folge in Hofstadters Buch ist die erste bekannte Erwähnung einer Meta-Fibonacci-Folge in der Literatur.<ref name="Emerson_2006_S1,7">: . In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638, S. 1, 7 (cs.uwaterloo.ca [PDF]). </ref>

Während die Elemente der Fibonacci-Folge durch das Summieren der beiden jeweils vorhergehenden Elemente bestimmt werden, bestimmen die beiden jeweils vorhergehenden Elemente einer <math>Q</math>-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 <math>Q</math>-Folge selbst ab.

<math>Q(1)</math>, das erste Element der Folge (die erste <math>Q</math>-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.<ref>Klaus Pinn: . In: Complexity. Band 4, 1999, S. 5–6, arxiv:chao-dyn/9803012v2. </ref>

Obwohl sich die Elemente der <math>Q</math>-Folge chaotisch zu entwickeln scheinen,<ref name="Hofstadter_1988_S149" /><ref name="Pinn_1999_S3">Klaus Pinn: . In: Complexity. Band 4, 1999, S. 3, arxiv:chao-dyn/9803012v2. </ref><ref>Klaus Pinn: . In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 1, arxiv:conat/9808031. </ref><ref name="Emerson_2006_S1,7" /> können ihre Elemente wie diejenigen vieler Meta-Fibonacci-Folgen in aufeinanderfolgende Blöcke gruppiert werden, die die Literatur als Generationen bezeichnet.<ref>Klaus Pinn: . In: Complexity. Band 4, 1999, S. 3–4, arxiv:chao-dyn/9803012v2. </ref><ref>B. Balamohan, A. Kuznetsov, Stephan M. Tanny: . In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638, S. 19 (cs.uwaterloo.ca [PDF]). </ref> Im Fall der <math>Q</math>-Folge hat die <math>k</math>-te Generation <math>2^k</math> Angehörige.<ref>Klaus Pinn: . In: Complexity. Band 4, 1999, S. Übersicht, 8, arxiv:chao-dyn/9803012v2. </ref> Wenn außerdem <math>g</math> die Generation angibt, der eine <math>Q</math>-Zahl angehört, dann sind die Summanden dieser <math>Q</math>-Zahl, die als Eltern bezeichnet werden, bei weitem am häufigsten in der Generation (<math>g-1</math>) angesiedelt und nur einige wenige in der Generation (<math>g-2</math>), niemals jedoch in einer noch früheren Generation.<ref>Klaus Pinn: . In: Complexity. Band 4, 1999, S. 4–5, arxiv:chao-dyn/9803012v2. </ref>

Die meisten dieser Feststellungen sind empirische Beobachtungen, da praktisch keine der Eigenschaften der <math>Q</math>-Folge im strengen Sinn bewiesen ist.<ref name="Pinn_1999_S2">Klaus Pinn: . In: Complexity. Band 4, 1999, S. 2, arxiv:chao-dyn/9803012v2. </ref><ref>Klaus Pinn: . In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 3, arxiv:conat/9808031. </ref><ref name="Balamohan_2007_S2">B. Balamohan, A. Kuznetsov, Stephan M. Tanny: . In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638, S. 2 (cs.uwaterloo.ca [PDF]). </ref>

Es ist insbesondere unbekannt, ob die Folge für alle <math>n</math> 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 <math>Q(1)</math> befinden müssten.<ref name="Pinn_1999_S2" /><ref>Nathanial D. Emerson: . In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638, S. 7 (cs.uwaterloo.ca [PDF]). </ref><ref name="Balamohan_2007_S2" />

Verallgemeinerungen der Q-Folge

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

Zwanzig Jahre nachdem Hofstadter die <math>Q</math>-Folge zum ersten Mal beschrieben hatte, verwendeten er und Greg Huber den Buchstaben <math>Q</math>, um eine Verallgemeinerung der <math>Q</math>-Folge zu einer Familie von Folgen zu bezeichnen. Die ursprüngliche <math>Q</math>-Folge aus seinem Buch benannten sie in <math>U</math>-Folge um.<ref name="Balamohan_2007_S2" />

Die ursprüngliche <math>Q</math>-Folge wird verallgemeinert, indem (<math>n-1</math>) und (<math>n-2</math>) jeweils durch (<math>n-r</math>) und (<math>n-s</math>) ersetzt werden.<ref name="Balamohan_2007_S2" />

Dies führt zu der Folgenfamilie

<math>

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} </math>

wobei <math>s\ge 2</math> und <math>r<s</math> ist.

Mit <math>(r,s)=(1,2)</math> ist die ursprüngliche Q-Folge eine Angehörige dieser Familie. Bisher sind nur drei Folgen der Familie <math>Q_{r,s}</math> bekannt, nämlich die <math>U</math>-Folge<ref name="Balamohan_2007_S2" /> mit <math>(r,s)=(1,2)</math> (die die ursprüngliche <math>Q</math>-Folge darstellt), die <math>V</math>-Folge<ref>B. Balamohan, A. Kuznetsov, Stephan M. Tanny: . In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 27. Juni 2007, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]). </ref> mit <math>(r,s) = (1,4)</math> und die <math>W</math>-Folge<ref name="Balamohan_2007_S2" /> mit <math>(r,s) = (2,4)</math>. Nur für die <math>V</math>-Folge, die sich nicht so chaotisch wie die anderen verhält, ist bewiesen, dass sie nicht abbricht.<ref name="Balamohan_2007_S2" /> Ähnlich der ursprünglichen <math>Q</math>-Folge wurden bis heute praktisch keine Eigenschaften der <math>W</math>-Folge im strengen Sinn bewiesen.<ref name="Balamohan_2007_S2" />

Die ersten Zahlen der <math>V</math>-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 <math>W</math>-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 <math>(r,s)</math> brechen die Folgen früher oder später ab, d. h., es existiert ein <math>n</math> für das <math>Q_{r,s}(n)</math> nicht definiert ist, weil <math>n-Q_{r,s}(n-r) < 1</math>.<ref name="Balamohan_2007_S2" />

Pinn-F_i,j(n)-Familie

1998 schlug Klaus Pinn, Wissenschaftler an der Universität Münster und in engem Kontakt mit Hofstadter, eine andere Verallgemeinerung von Hofstadters <math>Q</math>-Folge vor, die Pinn <math>F</math>-Folgen nannte.<ref name="Pinn_2000_S16">Klaus Pinn: . In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 16, arxiv:conat/9808031. </ref>

Die Pinn-<math>F_{i,j}</math>-Familie ist wie folgt beschrieben:

<math>

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} </math>

Pinn führte also die zusätzlichen Konstanten <math>i</math> und <math>j</math> ein, die den Index der Summanden konzeptuell nach links verschiebt (also näher an den Folgenanfang).<ref name="Pinn_2000_S16" />

Nur die <math>F</math>-Folgen mit <math>(i,j) = (0,0), (0,1), (1,0)</math> und <math>(1,1)</math>, deren erste die ursprüngliche <math>Q</math>-Folge darstellt, erscheinen wohldefiniert.<ref name="Pinn_2000_S16" /> Anders als <math>Q(1)</math> sind die ersten Elemente der Pinn-<math>F_{i,j}(n)</math>-Folgen Summanden bei der Berechnung weiterer Folgenelemente, wenn eine der zusätzlichen Konstanten 1 ist.

Die ersten Zahlen von Pinns <math>F_{0,1}</math>-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:<ref></ref>

<math>

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

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 Colin L. Mallows zuerkannt.<ref>Michael Tempel: (Memento vom 2. März 2008 im Internet Archive).</ref> Hofstadter äußerte später, er habe die Folge und ihre Struktur ungefähr 10–15 Jahre vor der Auslobung des Conway-Preises gefunden.<ref name="Pinn_1999_S3" />

Literatur

• B. Balamohan, A. Kuznetsov, Stephan M. Tanny: . In: Journal of Integer Sequences. Band 10, Nr. 7. University of Waterloo, 2007, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]). 
• : . In: Journal of Integer Sequences. Band 9, Nr. 1. University of Waterloo, 2006, ISSN 1530-7638 (cs.uwaterloo.ca [PDF]). 
• Douglas Richard Hofstadter: . 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: . In: Complexity. Band 4, 1999, S. 41–46, arxiv:chao-dyn/9803012v2. 
• Klaus Pinn: . In: Experimental Mathematics. Band 9, Nr. 1, 2000, S. 55–66, arxiv:conat/9808031. 
• S. Plouffe, Neil J. A. Sloane: . Academic Press, San Diego 1995, ISBN 0-12-558630-2. 
• Neil J. A. Sloane: . In: Notices of the American Mathematical Society. Band 50, Nr. 8, 2003, S. 912 (ams.org [PDF; 92 kB]). 

Einzelnachweise

<references />