Conway-Folge

Die Conway-Folge i​st eine n​ach dem britischen Mathematiker John Horton Conway benannte mathematische Folge. Sie w​urde erstmals 1986 v​on John Conway publiziert. (Lit.: Conway, 1986).

Die Conway-Folge findet m​an sehr o​ft als Knobelaufgabe wieder. Dabei werden meistens d​ie ersten p​aar Folgenglieder offengelegt u​nd der Rätselkandidat aufgefordert, d​ie Folge fortzusetzen. Auf Grund d​er recht ungewöhnlichen Definition d​er Folge h​at dies einiges Potential z​um Kopfzerbrechen.

Aufgrund i​hrer Bildungsweise nannte Conway s​ie audioaktive Folge.

Definition

Die Glieder der Folge werden auf eine für die Mathematik recht kuriose Art und Weise rekursiv definiert. Die Glieder sind hierbei nicht im eigentlichen Sinn als Zahlen im Dezimalsystem anzusehen, sondern lediglich als Ziffernfolgen, aus deren Beschreibung jeweils die Nachfolgerziffernfolge bestimmt wird. Startwert ist stets eine positive natürliche Zahl ${\displaystyle d}$ (beziehungsweise eine beliebige Ziffernfolge), üblicherweise ${\displaystyle d=1}$. Zur Bestimmung des Folgegliedes bestimmt man die Länge der Blöcke gleicher Ziffern in der Vorgängerzahl 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
7	eine Drei, eine Eins, zwei Zweien, zwei Einsen	13112221
…	usw.
70	…	Dezimaldarstellung hat 179.691.598 Stellen.

Conway-Folge für verschiedene Anfangswerte

d	Reihe	OEIS-Link
1	1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, …	Folge A005150 in OEIS
2	2, 12, 1112, 3112, 132112, 1113122112, 311311222112, …	Folge A006751 in OEIS
3	3, 13, 1113, 3113, 132113, 1113122113, 311311222113, …	Folge A006715 in OEIS
…
22	22, 22, 22, …	(Folge ist stationär)

Mathematische Eigenschaften

• Die Länge der Folge divergiert für alle Startwerte ${\displaystyle d}$ mit Ausnahme der 22 gegen ${\displaystyle \infty }$ und wächst sehr schnell. Die Dezimaldarstellung des 70. Folgengliedes für ${\displaystyle d=1}$ hat bereits 179.691.598 Stellen. Asymptotisch wächst die Länge der Folgenglieder mit der Geschwindigkeit ${\displaystyle \Theta (\lambda ^{n})}$. Hierbei bezeichnet ${\displaystyle \lambda \approx 1{,}303577\ldots }$ die so genannte Conway-Konstante.
• Sofern im Startwert nur die Ziffern 1, 2 und 3 enthalten sind und alle Folgen gleicher Ziffern höchstens drei Ziffern lang sind, bestehen auch alle weiteren Glieder der Conway-Folge nur aus den Ziffern 1, 2 und 3, wobei niemals die Ziffernfolge …333… vorkommt.

Weblinks

• Conway-Folge in der MathWorld: Look and Say Sequence (englisch)
• Conway-Folge in der On-Line Encyclopedia of Integer Sequences (englisch)
• John Conway über diese Folge (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.