In der Mathematik ist die Gijswijt-Folge (benannt nach Dion Gijswijt durch Neil Sloane) eine sich selbst beschreibende Folge, bei der jedes Folgenglied der maximalen Anzahl der Wiederholungen eines Endstücks des unmittelbar vorhergehenden Teils der Folge entspricht.
Die Folge beginnt mit:
1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, ... ()
Die Gijswijt-Folge ähnelt der Kolakoski-Folge, doch statt die maximale Anzahl an Wiederholungen einzelner Folgenglieder zu zählen, wird bei der Gijswijt-Folge die maximale Anzahl an Wiederholungen ganzer Blöcke aus Folgengliedern gezählt. Die Gijswijt-Folge ist für ihr erstaunlich langsames Wachstum bekannt. Beispielsweise erscheint die 4 erstmals an 220ster Stelle und die 5 sogar erstmals an etwa ster Stelle.
Definition Die Gijswijt-Folge kann am besten über die Beschreibung als Wort, das sich aus Zeichen des Alphabets der natürlichen Zahlen zusammensetzt, definiert werden.
und , wobei die größte natürliche Zahl ist, sodass das Wort in der Form geschrieben werden kann, wobei und Wörter sind und nicht leer ist.
Die Zahl sei für einen bestimmten Folgenanfang von nun an als dessen „Einrollzahl“ (engl. „curling number“) bezeichnet.
Die Folge ist dabei unabhängig vom Stellenwertsystem; wenn ein Folgenanfang die Einrollzahl 10 hat, so wäre das nächste Folgenglied tatsächlich die Zahl 10 als solche und nicht etwa eine 1 gefolgt von einer 0.
Erklärung Die Gijswijt-Folge beschreibt sich selbst: Jedes Folgenglied entspricht der Einrollzahl der bisherigen Folge.
Einrollzahl Die Einrollzahl gibt die maximale Anzahl der Wiederholungen eines Endstücks der bisherigen Folge an. Endet die bisherige Folge beispielsweise mit... 3, 2, 1, 1, 2, 1, 1, 2, 1, 1so ist das nächste Folgenglied mindestens 3, weil sich der Block „2, 1, 1“ am Ende der Folge dreimal wiederholt. Zwar wiederholt sich am Ende der Folge auch das Zeichen 1 immerhin zweimal, bei der Einrollzahl geht es aber um die maximale Anzahl an Wiederholungen, weswegen diese Wiederholung irrelevant ist. Endet das Anfangsstück der Folge hingegen auf... 3, 2, 2, 1, 1, 4, 1, 1, 1, 1, 4so ist das nächste Folgenglied 1, weil kein Endstück mehr als einmal „wiederholt“ wird (sofern keine Wiederholungen über das gezeigte Endstück hinaus vorliegen). Zwar wiederholt sich die 1 viermal hintereinander, da diese Wiederholung jedoch nicht unmittelbar am Ende der Folge liegt, ist diese für die Einrollzahl irrelevant.
Anfängliche Folgenwerte Definitionsgemäß beginnt die Folge mit der Zahl 1. Weil die bisherige Folge nur aus einem Folgenglied besteht, ist die Einrollzahl, und somit das nächste Folgenglied 1. Da sich nun am Ende der bisherigen Folge „1, 1“ die 1 zweimal wiederholt, ist das nächste Folgenglied 2. Weil sich am Ende der Folge „1, 1, 2“ kein Block mehr als einmal „wiederholt“, ist die Einrollzahl, und somit das nächste Folgenglied wieder 1; die Folge nimmt hier erstmalig ab. Auch das fünfte Folgenglied ist nach derselben Begründung wieder 1. Das sechste Folgenglied ist nun aber wieder 2, da sich am Ende der bisherigen Folge „1, 1, 2, 1, 1“ das Zeichen 1 zweimal wiederholt. Das siebte Folgenglied ist ebenso 2, da sich nun das Endstück „1, 1, 2“ der bisherigen Folge „1, 1, 2, 1, 1, 2“ zweimal wiederholt. Weil nun die letzten zwei Folgenglieder 2 waren, spiegelt das achte Folgenglied diese Wiederholung wider und ist daher erneut 2. Da nun die 2 am Ende der bisherigen Folge „1, 1, 2, 1, 1, 2, 2, 2“ dreimal hintereinander vorkommt, ist das neunte Folgenglied erstmals eine 3. Nach diesem Schema können dann alle weiteren Folgenglieder der Gijswijt-Folge bestimmt werden.
Eigenschaften Die bisherige Forschung zur Gijswijt-Folge hält sich stark in Grenzen. Deshalb wurde erst sehr wenig über sie bewiesen und viele Fragen sind bis heute offen.
Mittelwert Wenngleich bekannt ist, dass jede natürliche Zahl irgendwann in der Gijswijt-Folge vorkommt, konnte gezeigt werden, dass die Folge einen endlichen Mittelwert besitzt, dass also der folgende Grenzwert existiert.
.
Gleichermaßen ist bekannt, dass jede natürliche Zahl eine positive asymptotische Dichte in der Folge hat.
Wachstumsrate und erste Vorkommen Im Jahr 2006 bewies Gijswijt, dass die nach ihm benannte Folge jede natürliche Zahl enthält. Die Folge wächst in etwa superlogarithmisch, wobei jede natürliche Zahl erstmals an der Stelle vorkommt, wobei eine von abhängige reelle Zahl ist. Levi van der Pol fand dabei einen Ausdruck für den frühesten Index, an dem eine gegebene positive natürliche Zahl zum ersten Mal vorkommt, in Abhängigkeit von der Konstanten und einer Familie von Konstanten .
Beispielsweise ist die Stelle der ersten 5 gegeben durch
wobei . Diese Zahl entspricht ungefähr
.
Das Endstück „4, 4“ kommt erstmalig am Index
vor.
Diese Zahl hat 108 Ziffern und wurde erstmalig durch van de Pol erwähnt.
Rekursive Struktur Die Gijswijt-Folge kann in diskrete „Block“- und „Klebstoff“-Wörter zerteilt werden, mit Hilfe derer die Folge rekursiv aufgebaut werden kann. Beispielsweise können anfänglich und jeweils als die ersten Block- und Klebstoff-Wörter definiert werden. Es ist ersichtlich, wie sich der Anfang der Folge aus diesen Wörtern zusammensetzen lässt:
Im nächsten Schritt wird die Folge rekursiv aufgebaut. Sei mit das zweite Block-Wort der Folge definiert. Unter Anbetracht der Tatsache, dass die Folge mit anfängt, kann ein weiteres Klebstoff-Wort als definiert werden:
Das Klebstoff-Wort wurde so gewählt, dass auch einen Folgenanfang bildet.
Dieser Vorgang kann unbegrenzt fortgeführt werden, wobei die Folge der Block-Wörter rekursiv durch definiert wird. Das -te Klebstoff-Wort ist dabei das längste Wort nach dem Anfangsstück , das keine 1 enthält. Es wurde überdies bewiesen, dass sich die Gijswijt-Folge auf diese Weise unbegrenzt fortführen lässt – dass also und für jedes endlich lang sind.
Durch geschickte Manipulation der Klebstoff-Wörter in dieser rekursiven Struktur lässt sich – unter anderem – zeigen, dass die Gijswijt-Folge alle natürlichen Zahlen enthält.
Siehe auch
Conway-Folge
Einzelnachweise
Kategorie:Folge ganzer Zahlen Kategorie:Folgen und Reihen