Das Collatz-Problem (3k+1)-Problem

Manchmal führen schon ganz einfache Fragestellungen zu kniffligen Problemen. Das folgende ist ein bis heute ungelöstes mathematisches Problem:Zur Erzeugung einer Zahlenfolge denken wir uns eine beliebige, natürliche Zahl k aus. Ausgehend von dieser Zahl bilden wir die Zahlenfolge nach folgendem Muster:

Ist die Zahl gerade, so wird diese halbiert, andernfalls mit drei multipliziert und eins dazu addiert

Aufgrund des Bildungsgesetzes der Folge ist klar, daß das Problem als (3k+1)-Problem bekannt ist. Für viele Jahre war dies ein ungelöstes Problem erst kürzlich konnte gezeigt werden, daß egal mit welcher Zahl man startet, man jedesmal bei der Zahl Eins landet. Für die Startzahl Sieben zum Beispiel erhält man die folgende Zahlenfolge:

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Für die Ausgangszahl Sieben benötigt es also 17 Iterationen bis man bei der Zahl 1 landet.
Für andere Zahlen dauert es zum Teil wesentlich länger, hier rechts ist die Folge der Zahlen mit der Startzahl 27 gezeigt. Es braucht hier 112 Iterationen bis die Zahl Eins erreicht wird.
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Man kann nun die Frage stellen, wie lange es dauert, d.h. wieviele Schritte nötig sind eine gegebene Zahl mit dieser Berechnungsvorschrift auf die 1 zurückzuführen. Stellt man die Anzahl der Schritte für ein ganzen Intervall von Zahlen graphisch dar, erhält man beispielsweise die nebenstehende Grafik

Stacks Image 91

Interessant dabei ist die Ausbildung von „Bändern“. Diese „Bandbildung“ heißt ja nichts Anderes, als daß bestimmte Folgenlängen häufiger auftreten als andere. Als nächstes tragen wir die Länge einer Collatz-Folge gegen die entsprechende Häufigkeit des jeweiligen Auftretens der Folgenlänge auf. Das Ergebnis ist dann wie folgt:

Stacks Image 92
Als Download gibt es hier das entsprechende Mathematica-Notebook und die entsprechende Datei als PDF-Dokument:
  • Mathematica Notebook
  • PDF-Dokument
RapidWeaver Icon

Made in RapidWeaver