Collatz-Problem – einfach erklärt

Kernidee und Vermutung

Das Collatz-Problem, auch (3n+1)-Vermutung genannt, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde. Es gehört zur Zahlentheorie, hat aber auch Verbindungen zur Theorie dynamischer Systeme, zur Ergodentheorie und zur Berechenbarkeitstheorie in der Informatik. Es ist berühmt, weil es sehr leicht zu formulieren ist, aber bis heute weder bewiesen noch widerlegt wurde.

Man beginnt mit einer beliebigen natürlichen Zahl n > 0. Ist n gerade, nimmt man als nächste Zahl n/2. Ist n ungerade, nimmt man als nächste Zahl 3n + 1. Dieses Verfahren wird immer wieder auf die neu erhaltene Zahl angewendet. Die Collatz-Vermutung lautet: Jede so entstehende Zahlenfolge mündet irgendwann in den Zyklus 4, 2, 1, egal mit welcher positiven natürlichen Zahl man beginnt.

Ein Beispiel mit der Startzahl n = 19 ist: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, … Die Folge erreicht also 1 und wiederholt danach immer 4, 2, 1.

Mathematisch wird die Collatz-Funktion Col: N -> N definiert durch Col(n) = n/2, wenn n gerade ist, und Col(n) = 3n + 1, wenn n ungerade ist. Der Collatz-Orbit einer Zahl n ist die Folge n, Col(n), Col²(n), Col³(n), … Die Vermutung besagt: Zu jedem n in N existiert ein r in N, so dass Col^r(n) = 1. Gleichwertig kann man sagen: Das kleinste Element jedes Collatz-Orbits ist 1.

Warum das Problem schwierig ist

Für eine Collatz-Folge gibt es grundsätzlich drei Möglichkeiten: Sie endet im Zyklus (1,4,2), sie gerät in einen anderen Zyklus, oder sie wächst unbegrenzt. Die Collatz-Vermutung behauptet, dass für alle positiven Startzahlen nur die erste Möglichkeit eintritt. Bisher konnte aber weder ausgeschlossen werden, dass es einen anderen Zyklus gibt, noch dass eine Folge über alle Grenzen wächst. Es ist auch nicht bewiesen, dass es nur endlich viele Zyklen geben kann.

Oft verwendet man statt Col die verwandte Funktion T: N -> N mit T(n) = n/2 für gerade n und T(n) = (3n+1)/2 für ungerade n. Der Grund: Wenn n ungerade ist, ist 3n+1 immer gerade, so dass danach ohnehin eine Division durch 2 folgt. Die Funktion T fasst diese zwei Schritte zusammen. Der Zyklus (1,4,2) der Collatz-Funktion wird dadurch zum Zyklus (1,2).

Die Collatz-Vermutung ist äquivalent zu der Aussage, dass es für alle ganzen Zahlen n > 1 eine ganze Zahl k > 0 gibt, so dass T^k(n) < n. Riho Terras zeigte 1976, dass die asymptotische Dichte der Zahlen n > 1, für die dies gilt, existiert und gleich 1 ist. Das bedeutet grob: Für „fast alle“ Zahlen in diesem Sinn findet man irgendwann einen kleineren Wert, aber daraus folgt noch kein vollständiger Beweis.

Computerrechnungen haben die Vermutung für alle positiven ganzen Startzahlen bis 2^68, also ungefähr 2,95·10^20, bestätigt (Stand Juli 2020). Falls es bei der T-Iteration noch einen anderen Zyklus als (1,2) gibt, müsste dieser mindestens 10.439.860.591 Zahlen enthalten, davon mindestens 6.586.818.670 ungerade. Für unendlich viele n sind mindestens 6,143 log n Iterationen mit T nötig, um 1 zu erreichen. Stochastische Modelle sagen durchschnittlich (2 / log(4/3)) log n ≈ 6,952 log n Schritte voraus.

Graphen und grundlegende Eigenschaften

Ein Collatz-Graph ist ein gerichteter Graph zu einer Funktion f: N -> N. Die natürlichen Zahlen sind die Knoten, und zu jeder Zahl n gibt es eine gerichtete Kante von n nach f(n). Für die Nachfolgerfunktion s(n)=n+1 ist der Graph einfach 1 -> 2 -> 3 -> 4 -> … Bei der Collatz-Funktion C(n)=n/2 für gerade n und C(n)=3n+1 für ungerade n fand Collatz nur den „trivialen Kreis“ (1,4,2). In graphentheoretischer Formulierung lautet die Collatz-Vermutung: Der Collatz-Graph von C ist zusammenhängend.

Einige Eigenschaften der Folgen lassen sich durch elementare Rechnungen untersuchen, besonders wenn man nur ungerade Zahlen betrachtet. Ungerade Zahlen haben bei Division durch 4 entweder den Rest 1 oder den Rest 3. Zahlen der Form 4n+1 werden nach drei Anwendungen der Collatz-Funktion auf Zahlen der Form 3n+1 abgebildet; grafisch entspricht das insgesamt einem Sprung nach unten. Zahlen der Form 4n+3 werden nach zwei Anwendungen auf Zahlen der Form 6n+5 abgebildet; das ist zunächst ein Sprung nach oben. Nach zwei weiteren Iterationen werden sie auf Zahlen der Form 9n+8 abgebildet.

Diese Regeln helfen bei Computerprüfungen. Wenn man die Vermutung für alle natürlichen Zahlen bis zu einer Schranke M prüfen will, reicht es wegen der Eigenschaft von 4n+1-Zahlen, sich auf Zahlen der Form 4n+3 zu konzentrieren. Weitere Formeln mit Konstanten c(a,k) und d(a,k) beschreiben, wie T^k Zahlen der Form 2^k n + a abbildet: T^k(2^k n + a)=3^{c(a,k)}n+d(a,k). Die Beispiele zeigen unter anderem, dass es weder für den Maximalwert noch für die Länge von Collatz-Folgen eine obere Schranke gibt.

Eine besondere Rolle spielen Zweierpotenzen. Die Collatz-Vermutung entspricht auch der Aussage, dass jede Collatz-Folge nach endlich vielen Schritten ein Folgenelement erreicht, das eine Zweierpotenz mit endlichem Exponenten ist.

Syracuse-Funktion und Taos Teillösung

Die Syracuse-Funktion ist eine mit der Collatz-Funktion verwandte Abbildung auf den ungeraden Zahlen. Ist n ungerade, dann ist 3n+1 gerade. Man teilt 3n+1 so oft durch 2, bis wieder eine ungerade Zahl übrig bleibt. Formal gilt Syr(n) = (3n+1)/2^a = k, wobei 2^a die höchste Zweierpotenz ist, die 3n+1 teilt. Mit der 2-Bewertung ν₂, also der größten Zahl a mit 2^a | M, schreibt man Syr(n) = (3n+1)/2^{ν₂(3n+1)}. Beispiele sind Syr(3)=5, Syr(5)=1 und Syr(7)=11.

Die Syracuse-Funktion spielt eine zentrale Rolle in einer Teillösung von Terence Tao aus dem Jahr 2019. Tao bewies: Sei f: N+1 -> R eine Funktion mit lim_{N -> ∞} f(N)=+∞. Dann gilt Col_min^N(N) < f(N) für fast alle N in N+1. „Fast alle“ bezieht sich hier auf die logarithmische Dichte, eine schwächere Form als die asymptotische Dichte. Anschaulich bedeutet Taos Ergebnis, dass die Collatz-Folge für fast alle Startwerte irgendwann unter jede noch so langsam wachsende Schranke fällt, zum Beispiel unter log log log log n, sofern n groß genug betrachtet wird.

Aus Taos Satz folgt zum Beispiel, dass mindestens 99 Prozent der natürlichen Zahlen bis 10^24 bei der Collatzfolge einen Wert unter 200 erreichen. Das beweist die Collatz-Vermutung aber nicht vollständig, denn es bleibt möglich, dass eine sehr dünne Ausnahmemenge existiert, für die die Vermutung scheitert. Tao arbeitete mit probabilistischen Methoden und untersuchte statistisch das Langzeitverhalten vieler Anfangswerte unter der Collatztransformation.

Darstellung im Dualsystem

Im Dualsystem, also in der Schreibweise mit Bits 0 und 1, kann man gerade und ungerade Zahlen besonders einfach unterscheiden: Gerade Zahlen enden rechts mit 0, ungerade Zahlen mit 1. Auch Multiplikation und Division durch 2 sind einfach: Beim Multiplizieren mit 2 hängt man rechts eine 0 an; beim Dividieren durch 2 entfernt man rechts eine 0.

Die Collatz-Funktion kann im Dualsystem als abstrakte Maschine verstanden werden, die Bit-Zeichenketten in neue Bit-Zeichenketten umwandelt. Zuerst entfernt sie alle Nullen am Ende der Zeichenkette. Das entspricht den Divisionen durch 2, bis eine ungerade Zahl erreicht ist. Für eine ungerade Zahl n gelten dann drei Schritte: Rechts wird eine 1 angehängt, wodurch 2n+1 entsteht. Diese Zahl wird zur ursprünglichen Zahl addiert, also n + 2n + 1 = 3n + 1. Danach werden wieder alle Nullen am rechten Rand entfernt, also so oft durch 2 geteilt, bis erneut eine ungerade Zahl entsteht.

Beispiel: Startet man mit der dezimalen Zahl 7, also binär 111, erhält man den Orbit 111, 1111, 10110, 10111, 100010, 100011, 110100, 11011, 101000, 1011, 10000. Obwohl diese Darstellung einfache Regeln nutzt, wurde auch damit bisher kein Beweis der Collatz-Vermutung gefunden.

Verallgemeinerungen und Geschichte

Die genaue Entstehung der Collatz-Vermutung ist nicht vollständig dokumentiert. Collatz verbreitete das Problem vermutlich mündlich, unter anderem beim Internationalen Mathematikerkongress 1950 in Cambridge (Massachusetts). Auch Stanisław Ulam und Shizuo Kakutani erwähnten das Problem häufig. Als Collatz 1952 Professor in Hamburg wurde, erzählte er seinem Kollegen Helmut Hasse davon. Hasse verbreitete es während eines Forschungsaufenthalts an der Syracuse University, wodurch der Name Syracuse-Vermutung entstand.

1971 wurde das Problem in der gedruckten Version eines Vortrags von H. S. M. Coxeter vermutlich erstmals schriftlich veröffentlicht. 1972 machte Martin Gardner es in seiner Kolumne Mathematical Games im Scientific American bekannter. 1976 veröffentlichte Riho Terras erste wissenschaftliche Forschungsergebnisse direkt zum Collatz-Problem. 1985 erschien ein Überblicksartikel von Jeffrey Lagarias. Paul Erdős soll über das Problem gesagt haben: „Mathematics is not yet ready for such problems“ und „Hopeless. Absolutely hopeless.“

Verallgemeinerungen zeigen, dass ähnliche Probleme sehr verschiedenes Verhalten haben können. Erweitert man das Collatz-Problem auf alle ganzen Zahlen, gibt es außer dem Zyklus (1,4,2) mindestens vier weitere Zyklen: (0), (-1,-2), (-5,-14,-7,-20,-10) und (-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68,-34). Alle Startwerte n mit |n| < 10^8 enden in einem der bekannten Zyklen.

Beim analogen (5n+1)-Problem sagen stochastische Modelle voraus, dass fast alle Iterierten divergieren; Computersimulationen bestätigen dieses Verhalten. Es ist aber offen, auch nur für einen Orbit dieses Problems tatsächlich zu beweisen, dass er divergiert. John Conway zeigte 1972 außerdem, dass verallgemeinerte (3n+1)-Folgen universale Turingmaschinen simulieren können und dass ein bestimmtes zugehöriges Entscheidungsproblem unlösbar ist.