Hofstadter-Folge

Hofstadters Figur-Figur- (auch: R-und-S-) Folgen sind wie folgt 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)} 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 ist wie folgt 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 ist wie folgt 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“ sind wie folgt 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 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.[7] Gleichwohl kann von Hofstadters Einverständnis mit dieser Namensübertragung ausgegangen werden, da er Deutsch spricht und 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 ist wie folgt 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]

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 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[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]

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)