Q-Folge


Q-Folge

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

Inhaltsverzeichnis

Hofstadter-Folgen aus dem Buch Gödel, Escher, Bach: ein Endloses Geflochtenes Band

Die ersten Hofstadter-Folgen wurden von Douglas Robert Hofstadter in seinem Buch Gödel, Escher, Bach 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: [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:[5][6]


\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:[7][8]


\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 (weibliche und männliche Folgen) bezeichnet; die Bezeichnung als verheiratete Folgen kommt im englischen Originaltext nicht vor und ist ein Übersetzungskompromiss.[9] Gleichwohl kann von Hofstadters Einverständnis mit dieser Namensübertragung ausgegangen werden, da der Autor Deutsch spricht und die deutsche Ausgabe durchgesehen hat.[10]

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:[11][12]


\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"[13]; die Q-Zahl von 6 ist also 4. Die Darstellung der Q-Folge in Hofstadters Buch ist die erste bekannte Erwähnung einer Meta-Fibonacci-Folge in der Literatur.[14]

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, wie weit 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.[15]

Obwohl sich die Elemente der Q-Folge chaotisch zu entwickeln scheinen,[16][17][18][19] können ihre Elemente wie diejenige vieler Meta-Fibonacci-Folgen in aufeinanderfolgende Blöcke gruppiert werden, die die Literatur als Generationen bezeichnet.[20][21] Im Fall der Q-Folge hat die k-te Generation 2k Angehörige.[22] 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.[23]

Die meisten dieser Feststellungen sind empirische Beobachtungen, da praktisch keine der Eigenschaften der Q-Folge im strengen Sinn bewiesen sind.[24][25][26]

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.[27][28][29]

Verallgemeinerungen der Q-Folge

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

20 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.[30]

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

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 Qr,s bekannt, nämlich die U-Folge[32] mit (r,s) = (1,2) (die die ursprüngliche Q-Folge darstellt), die V-Folge[33] mit (r,s) = (1,4) und die W-Folge[34] 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.[35] Ähnlich der ursprünglichen Q-Folge wurden bis heute praktisch keine Eigenschaften der W-Folge im strengen Sinn bewiesen.[36]

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 Qr,s(n) nicht definiert ist, weil n-Qr,s(n-r) < 1.[37]

Die Pinn-Fi,j(n)-Familie

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

Die Pinn-Fi,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 &amp;gt; 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).[39]

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.[40] Anders als Q(1) sind die ersten Elemente der Pinn-Fi,j(n)-Folgen Summanden bei der Berechnung weiterer Folgenelemente, wenn eine der zusätzlichen Konstanten 1 ist.

Die ersten Zahlen von Pinns F0,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:[41]


\begin{align}
a(1)&amp;amp;=a(2)=1, \\
a(n)&amp;amp;=a(a(n-1))+a(n-a(n-1)), \quad n&amp;gt;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.[42] Hofstadter äußerte später, er habe die Folge und ihre Struktur ungefähr 10-15 Jahre vor der Auslobung des Conway-Preises gefunden.[43]

Einzelnachweise

  1. Hofstadter (1988) Seite 79
  2. Mathworld: Hofstadter Figure-Figure Sequence
  3. Hofstadter (1988) Seite 148
  4. Mathworld: Hofstadter G-Sequence
  5. Hofstadter (1988) Seite 148
  6. Mathworld: Hofstadter H-Sequence
  7. Hofstadter (1988) Seite 148
  8. Mathworld: Hofstadter Male-Female Sequences
  9. Hofstadter (1980) Seite 137
  10. Hofstadter (1988) Seite 820
  11. Hofstadter (1988) Seite 149
  12. Mathworld: Hofstadter's Q-Sequence
  13. Hofstadter (1988) Seite 149
  14. Emerson (2006) Seiten 1, 7
  15. Pinn (1999) Seiten 5-6
  16. Hofstadter (1988) Seite 149
  17. Pinn (1999) Seite 3
  18. Pinn (2000) Seite 1
  19. Emerson (2006) Seite 7
  20. Pinn (1999) Seiten 3-4
  21. Balamohan et al. (2007) Seite 19
  22. Pinn (1999) Übersicht, Seite 8
  23. Pinn (1999) Seiten 4-5
  24. Pinn (1999) Seite 2
  25. Pinn (2000) Seite 3
  26. Balamohan et al. (2007) Seite 2
  27. Pinn (1999) Seite 2
  28. Emerson (2006) Seite 7
  29. Balamohan et al. (2007) Seite 2
  30. Balamohan et al. (2007) Seite 2
  31. Balamohan et al. (2007) Seite 2
  32. Balamohan et al. (2007) Seite 2
  33. Balamohan et al. (2007) ganzer Artikel
  34. Balamohan et al. (2007) Seite 2
  35. Balamohan et al. (2007) Seite 2
  36. Balamohan et al. (2007) Seite 2
  37. Balamohan et al. (2007) Seite 2
  38. Pinn (2000) Seite 16
  39. Pinn (2000) Seite 16
  40. Pinn (2000) Seite 16
  41. Mathworld: Hofstadter-Conway $10,000 Sequence
  42. Easy as 1 1 2 2 3; Michael Tempel
  43. Pinn (1999) Seite 3

Literatur


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Folge (Pretzschendorf) — Folge ist ein Ortsteil von Colmnitz (Gemeinde Pretzschendorf) im Landkreis Sächsische Schweiz Osterzgebirge. Die Häuslerzeile gehörte 1791 zum Amt Freiberg und war Ortsteil von Niedercolmnitz. Die Grundherrschaft übte das Rittergut Pretzschendorf …   Deutsch Wikipedia

  • Folge — steht für: Wirkung einer Handlung oder eines Geschehens, Konsequenz im logischen Sinne, Abfolge, eine Reihe von aufeinanderfolgenden Dingen oder Ereignissen, Teil einer Serie, oder Episode, in Kunst und Medien; siehe Handlung (Erzählkunst), Folge …   Deutsch Wikipedia

  • Folge — Folge, 1) (Log.), Bestimmung der Gültigkeit eines Gedankens, Urtheils od. Satzes durch einen vorhergehenden (Grund). In der Form eines Satzes aufgestellt, heißt er Folgesatz, im Gegensatz zu Grundsatz, welcher den Grund enthält. Die Art der… …   Pierer's Universal-Lexikon

  • folgę — folgę* {{/stl 13}}{{stl 7}}ZOB. dawać – dać folgę (sobie albo czemuś) {{/stl 7}} …   Langenscheidt Polski wyjaśnień

  • Folge — [Basiswortschatz (Rating 1 1500)] Auch: • Reihenfolge • Ordnung • Konsequenz • Ergebnis • Erfolg • …   Deutsch Wörterbuch

  • Folge — Folge, im eigentlichen Sinne das Verhältnis der logischen Abhängigkeit (s.d.) zwischen Gedanken, Urteilen und Sätzen, das darin besteht, daß ein Gedanke (die F., der Folgesatz) sich aus dem andern (dem Grund oder Grundsatz) ableiten läßt, und daß …   Meyers Großes Konversations-Lexikon

  • Folge — 1. ↑Partita, ↑Sequenz, ↑Serie, ↑Zyklus, 2. Konsequenz …   Das große Fremdwörterbuch

  • Folge (Mathematik) — Als Folge oder Sequenz wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das… …   Deutsch Wikipedia

  • Folge — Nachwirkung; Konsequenz; Ergebnis; Folgeerscheinung; Effekt; Abfolge; Sequenz; Reihe; Aufeinanderfolge; Rangfolge; Serie; Reihenfolge; …   Universal-Lexikon

  • Folge (3), die — 3. Die Folge, plur. die n, von dem folgenden Zeitworte folgen. 1. Der Zustand, da eine Person oder Sache auf die andere folgt, ohne Plural. 1) Der Zustand, da eine Sache immer auf die andere folget, eine Reihe. Die Folge der Töne. Die schnelle… …   Grammatisch-kritisches Wörterbuch der Hochdeutschen Mundart

  • Folge — Fọl·ge1 die; , n; 1 eine Reihe von Dingen, die in zeitlich (relativ) kurzen Abständen nacheinander kommen ≈ Reihenfolge: Die Tonleiter ist eine Folge von Tönen innerhalb einer Oktave; Die Autos auf der Autobahn fuhren in dichter Folge || K:… …   Langenscheidt Großwörterbuch Deutsch als Fremdsprache