Auf den ersten Blick scheint es lächerlich einfach. Und doch suchen Fachleute seit Jahrzehnten vergeblich nach einer Lösung. Bereits während des Kalten Kriegs sagte der Zahlentheoretiker Shizuo Kakutani: »Etwa einen Monat lang haben alle Mathematiker in Yale daran gearbeitet – ohne Ergebnis. Ein ähnliches Phänomen trat auf, als ich es an der University of Chicago erwähnte. Es wurde gescherzt, dass dieses Problem Teil einer Verschwörung sei, um die mathematische Forschung in den USA lahmzulegen.« Auch Paul Erdös, einer der erfolgreichsten Mathematiker des 20. Jahrhunderts, bemerkte: »Die Mathematik ist wahrscheinlich noch nicht bereit, solche Probleme zu lösen.«

Die Aussagen beziehen sich auf die Collatz-Vermutung. Dabei handelt es sich um eine dieser vermeintlich einfachen Aufgaben, in denen man sich gerne verliert. Aus diesem Grund warnen erfahrene Professoren ihre ehrgeizigen Studierenden häufig davor, sich mit der Collatz-Vermutung zu beschäftigen und ihre eigentliche Forschung aus dem Blick zu verlieren. Die Vermutung selbst lässt sich so einfach formulieren, dass selbst Grundschüler sie verstehen: Man nehme eine natürliche Zahl. Ist sie ungerade, multipliziert man sie mit drei und addiert eins hinzu; ist sie hingegen gerade, teilt man sie durch zwei. Mit dem Ergebnis x geht man ebenso vor: Falls x ungerade ist, rechnet man 3x + 1, sonst ^x⁄₂. Das wiederholt man so oft wie möglich – und landet der Vermutung zufolge am Ende immer bei der Zahl 1.

Zum Beispiel: Startet man mit 7, muss man 7 · 3 + 1 berechnen, was 22 ergibt. Da 22 eine gerade Zahl ist, muss man sie halbieren, wodurch 11 herauskommt. 11 mal 3 plus 1 ist 34, geteilt durch 2 ist 17, mal 3 plus 1 ist 52, geteilt durch 2 ist 26, geteilt durch 2 ist 13, mal 3 plus 1 ist 40, geteilt durch 2 ist 20, geteilt durch 2 ist 10, geteilt durch 2 ist 5, mal 3 plus 1 ist 16, geteilt durch 2 ist 8, geteilt durch 2 ist 4, geteilt durch 2 ist 2, geteilt durch 2 ist 1. Damit ist man nach 15 Schritten am Ende angelangt, bei der Zahl 1. Natürlich kann man mit 1 auch weiterrechnen, erhält dadurch 4, dann wieder 2 und 1: Die Rechenvorschrift führt also in eine Schleife, aus der man nicht mehr entkommen kann. Daher wird die 1 als Endpunkt der Prozedur gesehen.

Es macht richtig Spaß, die iterative Rechenvorschrift für verschiedene Zahlen durchzugehen und die entstehenden Zahlenfolgen zu betrachten. Startet man mit der Fünf, ergibt sich zum Beispiel: 5 → 16 → 8 → 4 → 2 → 1. Oder mit der Sechs: 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1. Oder 42: 42 → 21 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Egal mit welcher Zahl man startet, man landet offenbar immer bei der Eins. Zwar gibt es manche Zahlen, wie die 27, bei denen es recht lange dauert (27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → …) – doch bisher haben alle Ergebnisse am Ende zur 1 geführt (bei der Startzahl 27 muss man zugegebenermaßen geduldig sein, dort braucht es 111 Schritte). Ein Beweis, dass die Collatz-Vermutung wahr ist, steht allerdings noch aus.

Der Ursprung der Collatz-Vermutung ist nicht gesichert, weshalb die Hypothese unter vielen verschiedenen Name bekannt ist: Experten sprechen vom Syracuse-Problem, dem Ulam-Problem, der 3n + 1-Vermutung, vom Hasse-Algorithmus oder dem Kakutani-Problem. Der deutsche Mathematiker Lothar Collatz fing während seines Mathematikstudiums an, sich für iterative Funktionen zu interessieren, und untersuchte sie. Er veröffentlichte Anfang der 1930er Jahre auch Fachaufsätze dazu, doch die explizite Rechenvorschrift des nach ihm genannten Problems befand sich nicht darunter. In den 1950er und 60er Jahren gewann die Collatz-Vermutung schließlich an Berühmtheit, als Forscher wie Helmut Hasse und Shizuo Kakutani es sie verschiedenen Universitäten (darunter die Syracuse University in New York) verbreiteten.

Wie ein Sirenengesang zog die so einfach anmutende Vermutung die Fachleute in ihren Bann. Seit Jahrzehnten suchen sie nach einem Beweis dafür, dass man nach endlicher Wiederholung der Collatz-Prozedur bei eins landet. Grund für die Hartnäckigkeit ist nicht bloß die Einfachheit des Problems – tatsächlich hängt die Collatz-Vermutung mit anderen bedeutenden Fragen der Mathematik zusammen. Zum Beispiel tauchen solche iterativen Funktionen insbesondere bei dynamischen Systemen auf, also bei Modellen, die beispielsweise die Umlaufbahnen von Planeten beschreiben. Zudem hängt die Vermutung mit der riemannschen Vermutung zusammen, einem der ältesten zahlentheoretischen Probleme.

Die Empirie spricht für die Collatz-Vermutung

Im Jahr 2017 haben Forschende in einem kollaborativen Informatikprojekt die ersten 2⁶⁸ ≈ 3 · 10²⁰ Zahlen überprüft: Sie erfüllen alle als Startwerte die Collatz-Vermutung. Doch das heißt nicht, dass es nicht irgendwo einen Ausreißer gibt. Es könnte einen Startwert geben, der nach wiederholter Collatz-Prozedur immer größere Werte liefert, die schließlich irgendwann gegen unendlich ansteigen. Dieses Szenario erscheint allerdings unwahrscheinlich, wenn man das Problem statistisch untersucht.

Eine ungerade Zahl n wird nach dem ersten Schritt der Iteration auf 3n + 1 vergrößert, das Ergebnis ist aber zwangsläufig gerade und wird somit im darauf folgenden Schritt halbiert. In der Hälfte aller Fälle erhält man durch die Halbierung eine ungerade Zahl, diese muss man also wieder mit drei multiplizieren und eins hinzuaddieren, woraufhin man wieder ein gerades Ergebnis erhält. Falls das Ergebnis des zweiten Schritts aber wieder gerade war, muss man die neue Zahl in jedem vierten Fall zweimal hintereinander durch zwei teilen; in jedem achten Fall dreimal durch zwei teilen und so weiter. Um das langfristige Verhalten einer Zahlenfolge auszuwerten, hat der Mathematiker Jeffrey Lagarias 2018 daher aus diesen Überlegungen das geometrische Mittel gebildet und erhielt folgendes Ergebnis: (³⁄₂)^1/2 · (³⁄₄)^1/4 · (³⁄₈)^1/8 · … = ¾. Damit zeigt sich, dass die Folgenglieder bei jedem Schritt der iterativen Rechenvorschrift durchschnittlich um den Faktor ¾ schrumpfen. Damit ist es extrem unwahrscheinlich, dass es einen Startwert gibt, der durch die Prozedur bis ins Unendliche anwächst.

Es könnte aber einen Startwert geben, der in einer Schleife endet, die nicht 4 → 2 → 1 ist. Stattdessen könnte es eine andere Schleife mit größeren Zahlen geben, wodurch die 1 niemals erreicht wird. Solche »nichttrivialen« Schleifen findet man zum Beispiel, wenn man auch negative ganze Zahlen für die Collatz-Vermutung zulässt: In diesem Fall kann die iterative Rechenvorschrift nicht nur bei –2 → –1 → –2 → … enden, sondern auch bei –5 → –14 → –7 → –20 → –10 → –5 → … oder –17 → – 50 → … → –17 → … Beschränkt man sich auf natürliche Zahlen, sind bisher keine nichttrivialen Schleifen bekannt – was nicht heißt, dass es sie nicht gibt. Fachleute konnten jedoch inzwischen zeigen, dass eine solche Schleife im Collatz-Problem aus mindestens 186 Milliarden Zahlen bestehen müsste.

Selbst wenn das unwahrscheinlich klingt, muss es das nicht sein. In der Mathematik gibt es viele Beispiele, bei denen gewisse Gesetzmäßigkeiten erst sehr spät zusammenbrechen: So könnte man meinen, dass der Primzahlsatz die Anzahl der Primzahlen immer überschätzt – doch tatsächlich kehrt sich das nach etwa 10³¹⁶ Zahlen um. Ab dann unterschätzt der Primzahlsatz die tatsächliche Anzahl der Primzahlen. So könnte es auch mit der Collatz-Vermutung sein: Vielleicht gibt es tief verborgen im Zahlenstrahl eine riesige Zahl, die das bisher beobachtete Muster bricht.

Ein Beweis für fast alle Zahlen

Deshalb suchen Mathematikerinnen und Mathematiker seit Jahrzehnten nach einem stichhaltigen Beweis. Den größten Fortschritt markierte 2019 der Fields-Medaillist Terrence Tao von der University of California, als er bewies, dass fast alle Startwerte der natürlichen Zahlen irgendwann bei einem Wert nahe eins landen. »Fast alle« hat dabei eine präzise mathematische Bedeutung: Es bedeutet, dass, wenn man zufällig eine natürliche Zahl als Startwert auswählt, diese mit einer Wahrscheinlichkeit von 100 Prozent bei eins landet. (Das bedeutet aber nicht, dass das für alle gilt). »Das ist ungefähr so nahe, wie man der Collatz-Vermutung kommen kann, ohne sie tatsächlich zu lösen«, schrieb Terence Tao in einem Vortrag, den er im Jahr 2020 hielt.

Taos Methode lässt sich leider nicht auf alle Zahlen verallgemeinern, da sie auf statistischen Betrachtungen fußt. Auch alle anderen Ansätze führten bislang in eine Sackgasse. Vielleicht liegt das daran, dass die Collatz-Vermutung falsch ist. »Ich habe drei Jahre lang versucht, etwas zu beweisen. Und es ist mir nicht gelungen. Doch dann habe ich ein Gegenbeispiel gefunden«, sagte der Mathematiker Alex Kontorovich von der Rutgers University in New Jersey in einem Youtube-Video des Kanals »Veritasium«. »Vielleicht sollten wir auch beim Collatz-Problem mehr Energie auf die Suche nach Gegenbeispielen verwenden, als wir es derzeit tun.«

Vielleicht wird sich die Collatz-Vermutung in den kommenden Jahren als wahr oder falsch herausstellen. Es gibt aber noch eine dritte Möglichkeit: Eventuell gehört die Aufgabe zu der Art von Problemen, die sich mit unseren mathematischen Werkzeugen nicht beweisen lassen. Tatsächlich untersuchte der Mathematiker John Horton Conway im Jahr 1987 eine Verallgemeinerung der Collatz-Vermutung und fand heraus, dass die iterativen Funktionen Eigenschaften besitzen, die beweisbar unbeweisbar sind. Vielleicht gilt das für die Collatz-Vermutung ebenfalls: So einfach sie auch anmutet, könnte sie dazu verdammt sein, für immer ungelöst zu bleiben.

In die Kolumne hatte sich ein Fehler eingeschlichen. Fälschlicherweise wurde behauptet, dass 11·3 + 1 gleich 32 sei – dabei lautet das Ergebnis natürlich 34. Wir bitten, dies zu entschuldigen.