Conway-Folge

Die Conway-Folge ist eine nach dem britischen Mathematiker John Horton Conway benannte mathematische Folge. Sie wurde erstmals 1986 von John Conway publiziert. (Lit.: Conway, 1986).

Die Conway-Folge findet man sehr oft als Knobelaufgabe wieder. Dabei werden meistens die ersten paar Folgenglieder offengelegt und der Rätselkandidat aufgefordert, die Folge fortzusetzen. Auf Grund der recht ungewöhnlichen Definition der Folge hat dies einiges Potential zum Kopfzerbrechen.

Definition

Die Glieder der Folge werden auf eine für die Mathematik recht kuriose Art und Weise rekursiv definiert. Das nächste Folgenglied wird hierbei nicht durch Berechnungen aus seinem Vorgänger, sondern durch eine Beschreibung dessen Darstellung im Dezimalsystem bestimmt. Startwert ist stets eine positive natürliche Zahl d, üblicherweise d = 1. Zur Bestimmung des Folgegliedes bestimmt man die maximale Länge der Blöcke gleicher Ziffern in der Darstellung des Vorgängers und schreibt die Häufigkeit und Ziffer für jeden Block hintereinander. Die so geschriebene Zahl ist das nächste Folgenglied.

Veranschaulichung der Definition für d = 1

n	Vorgänger	n-tes Folgeglied
1	---	1
2	eine Eins	11
3	zwei Einsen	21
4	eine Zwei, eine Eins	1211
5	eine Eins, eine Zwei, zwei Einsen	111221
6	drei Einsen, zwei Zweien, eine Eins	312211
	usw.

Conway-Folge für verschiedene Anfangswerte

d	Reihe
1	1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ...
2	2, 12, 1112, 3112, 132112, 1113122112, 311311222112, ...
3	3, 13, 1113, 3113, 132113, 1113122113, 311311222113, ...

Mathematische Eigenschaften

• Die Länge der Folge divergiert für alle Startwerte d mit Ausnahme der 22 gegen $\infty$ und wächst sehr schnell. Die Dezimaldarstellung des 70. Folgengliedes für d = 1 hat bereits 179,691,598 Stellen. Asymptotisch wächst die Länge der Folgenglieder mit der Geschwindigkeit Θ(λⁿ). Hierbei bezeichnet $\lambda \approx 1{,}303577\ldots$ die so genannte Conway-Konstante.
• Für d = 22 hingegen sind alle Glieder der Folge identisch, sie ist also stationär.
• Für d = 1 (und viele andere Werte) enthält die Folge stets nur die Ziffern 1, 2 und 3, wobei niemals die Ziffernfolge ...333... vorkommt.

Weblinks

• Mathworld Infos zur Conway-Folge (englisch)
• Conway-Folge in der On-Line Encyclopedia of Integer Sequences (englisch)

Literatur

• John Horton Conway: The Weird and Wonderful Chemistry of Audioactive Decay. Eureka 46, 1986, Seiten 5–18
• Clifford Stoll: Kuckucksei – Der hochrangige NSA-Mitarbeiter Robert Morris gibt Clifford Stoll die ersten Glieder der Conway-Folge als Zahlenrätsel, das Stoll nicht lösen kann.