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:

${\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)} 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:

${\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 ist wie folgt beschrieben:

${\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“ sind wie folgt beschrieben:

${\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 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:

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:

${\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 $Q$-Zahlen; 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.

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 Indizes 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.

Obwohl sich die Elemente der $Q$-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 $Q$-Folge hat die $k$-te Generation $2^{k}$ Angehörige. 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.

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

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.

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.

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

Dies führt zu der Folgenfamilie

$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 $s\geq 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 mit $(r,s)=(1,2)$ (die die ursprüngliche $Q$-Folge darstellt), die $V$-Folge mit $(r,s)=(1,4)$ und die $W$-Folge 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. Ähnlich der ursprünglichen $Q$-Folge wurden bis heute praktisch keine Eigenschaften der $W$-Folge im strengen Sinn bewiesen.

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$.

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.

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).

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. 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:

${\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 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

• 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]).