Nimm eine ganze Zahl. Halbiere sie, wenn sie gerade ist. Andernfalls verdreifache sie und addiere eins. Wiederhole, bis du bei 1 bist — und du wirst, so sagt man, immer ankommen.
Zwei Zeilen Code. Keine Ausnahmen. Und doch: nach fast neunzig Jahren kein Beweis.
Die Collatz-Vermutung beschreibt die simpelste Operation, die man auf einer natürlichen Zahl ausführen kann. Von n ausgehend folgt man einer von zwei Regeln — je nachdem, ob n gerade oder ungerade ist. Die Folge, die dabei entsteht, heißt Hagelkorn-Folge, weil sie wie ein Hagelkorn in einer Wolke auf- und abtrudelt, bevor sie den Boden berührt.
Der „Boden“ ist 1. Von dort fällt die Folge in den Zyklus 1 → 4 → 2 → 1. Die Vermutung besagt: jede positive ganze Zahl erreicht diesen Zyklus. Geprüft wurde das bislang für alle n bis ungefähr 268 — ein astronomisch großer Bereich, aber eben nicht alle.
Gib eine Saat ein. Das Instrument zeichnet die Flugbahn als Kurve — X-Achse sind die Schritte, Y-Achse ist der Wert (logarithmisch skaliert, damit auch die höchsten Gipfel ins Bild passen). Ungerade Schritte sind rot, gerade blau.
Übereinandergelegt zeigen die Hagelbahnen eine Art Wolkendecke: tief fliegende Kurzlebige, dazwischen vereinzelte Hochfliegende, die weit oben durchs Bild jagen, bevor sie stürzen. Die kleinsten Saaten können die wildesten Flüge auslösen — 27 erreicht einen Gipfel von 9232, obwohl es selbst nur zweistellig ist.
Die Haltezeit (auch Stopping Time) ist die Anzahl der Schritte, bis eine Saat bei 1 landet. Sie wächst nicht monoton mit n — sie flattert, in chaotischen Sprüngen. Hier die Verteilung für die ersten 1000 Saaten.
Eine Zahl ist ein Rekord-Setter, wenn ihre Haltezeit länger ist als die aller kleineren Saaten vor ihr. Die folgenden sind berühmt genug, um im OEIS als Folge A006877 zu stehen.
Die Mathematik ist noch nicht reif für solche Probleme.— Paul Erdős · über Collatz
Keine andere offene Frage der Zahlentheorie ist so zugänglich und so unbeugsam zugleich. Die Collatz-Vermutung ist in fast jeder Ecke der Welt unabhängig wiederentdeckt worden — und sie hat fast so viele Namen wie Länder, die sie kennen.
Der deutsche Mathematiker notiert das Problem als Student. Er veröffentlicht es nie förmlich — es kursiert jahrzehntelang als Folklore, getragen durch Vorlesungen und Briefe. Erst in den 1950ern bekommt es einen ersten schriftlichen Auftritt.
Der japanische Mathematiker Shizuo Kakutani erzählt es an der Yale und in Princeton. Erdős hört zu, notiert es, bietet 500 Dollar für einen Beweis. Es wird ruhig. Die Summe ist nie ausgezahlt worden.
An der Syracuse University greift H. Hasse das Problem auf — der Ort gibt dem Problem einen seiner Namen. Gleichzeitig kursieren Begriffe wie Hagelkorn-Folge, Ulam-Vermutung, Kakutani-Problem.
Terence Tao zeigt: fast alle Saaten landen unter jeder beliebig tiefen Schwelle. Kein Beweis der Vermutung, aber der bislang tiefste Schritt dahin. Vollzogen wird ihr Ausgang durch probabilistische Methoden — jedes einzelne n bleibt offen.
Verteilte Rechenprojekte haben alle Saaten bis ~2,95·1020 durchgeprüft. Alle erreichen 1. Die höchsten Gipfel stammen von Saaten, die ihrerseits winzig sind — ein Hinweis auf die Dynamik, die hinter der simplen Regel steckt.
Varianten mit 3n+3, 3n+5 oder 5n+1 verhalten sich anders: manche haben kurze Zyklen, manche divergieren. Die Collatz-Vermutung ist kein Naturgesetz — sie ist eine Aussage über einen sehr spezifischen dynamischen Feinabgleich.