Hofstadters Figur-Figur-Folgen

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen sind wie folgt beschrieben:

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

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

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

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

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

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.

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

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

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.

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.

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.

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

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

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.

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

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