Die Collatz-Vermutung

08. Februar 2026
869 Wörter

Zusammenfassung. Die Collatz-Vermutung besagt, dass die Iteration $n \mapsto n/2$ für gerade und $n \mapsto 3n + 1$ für ungerade $n$ von jeder positiven ganzen Zahl aus schließlich die 1 erreicht. Wir formulieren das Problem präzise, betrachten numerische Daten für $n \le 10^4$ , leiten aus einem Zufallsmodell die Größenordnung $\sigma_\infty(n) \approx 10{,}4 \ln n$ der Gesamtstoppzeit her und geben einen Überblick über die bekannten Teilergebnisse.

1. Das Problem

Die Collatz-Funktion $C : \mathbb{N} \to \mathbb{N}$ ist definiert durch

C(n) = \begin{cases} n/2, & n \text{ gerade}, \\ 3n + 1, & n \text{ ungerade}. \end{cases}

Die Gesamtstoppzeit $\sigma_\infty(n)$ ist die kleinste Zahl $k \ge 0$ mit $C^k(n) = 1$ , oder $\infty$ , falls es keine solche gibt. Erreicht die Folge die 1, läuft sie anschließend im Zyklus $1 \to 4 \to 2 \to 1$ .

Vermutung (Collatz, 1937). Für alle $n \ge 1$ ist $\sigma_\infty(n) < \infty$ .

Das Problem wird Lothar Collatz zugeschrieben und ist unter vielen Namen bekannt: $3n+1$ -Problem, Syracuse-, Kakutani-, Hasse- oder Ulam-Problem. Lagarias [1] gibt einen umfassenden Überblick. Eine Widerlegung müsste eine von zwei Formen annehmen: eine Folge, die unbeschränkt wächst, oder einen nichttrivialen Zyklus.

2. Numerische Befunde

Schon kleine Startwerte zeigen, wie unberechenbar die Folgen verlaufen. Mit $n = 27$ braucht die Folge 111 Schritte, um die 1 zu erreichen, und steigt zwischendurch bis auf 9232 an (Abbildung 1).

Liniendiagramm der Collatz-Folge mit Startwert 27 über 111 Schritte. Die Werte schwanken lange im Bereich unter 2000, steigen nach etwa 60 Schritten steil an, erreichen nach 77 Schritten das Maximum von 9232 und fallen dann rasch auf 1. — Abbildung 1: Die Collatz-Folge mit Startwert 27.

Abbildung 2 zeigt die Gesamtstoppzeiten aller $n \le 10^4$ . Der Rekord in diesem Bereich liegt bei $n = 6171$ mit 261 Schritten. Auffällig sind die Bänder: Benachbarte Zahlen laufen oft nach wenigen Schritten in dieselbe Folge ein und haben dann gleiche oder fast gleiche Stoppzeiten. Rechnergestützt ist die Vermutung inzwischen für alle $n < 2^{68} \approx 2{,}95 \cdot 10^{20}$ bestätigt [7].

Streudiagramm der Gesamtstoppzeiten für n von 1 bis 10.000. Die Punkte bilden waagerechte Bänder zwischen etwa 20 und 260 Schritten, mit der größten Dichte um 50 bis 150. Eine gestrichelte Kurve 10,43 mal ln n steigt flach von unten links bis etwa 96 bei n gleich 10.000 und verläuft mitten durch die Punktwolke. Der höchste Punkt bei n gleich 6171 mit 261 Schritten ist markiert. — Abbildung 2: Gesamtstoppzeiten für n ≤ 10.000 mit der heuristischen Kurve 10,43 · ln n aus Abschnitt 3.

3. Eine probabilistische Heuristik

Für die Analyse ist die beschleunigte Funktion $T(n) = n/2$ für gerade und $T(n) = (3n+1)/2$ für ungerade $n$ bequemer, da auf $3n+1$ stets ein Halbierungsschritt folgt. Terras [2] zeigte, dass die Paritätenfolge der ersten $k$ Schritte von $T$ nur von $n \bmod 2^k$ abhängt und dass jede der $2^k$ möglichen Paritätenfolgen genau einmal vorkommt, wenn $n$ ein volles Restsystem modulo $2^k$ durchläuft. In diesem Sinne verhalten sich die Paritäten wie unabhängige faire Münzwürfe.

Modelliert man sie als solche, so ist

\ln T^k(n) \approx \ln n + \sum_{i=1}^{k} X_i

mit unabhängigen $X_i$ , die jeweils mit Wahrscheinlichkeit $\tfrac12$ den Wert $\ln \tfrac32$ (ungerader Schritt) oder $\ln \tfrac12$ (gerader Schritt) annehmen. Das ist eine Irrfahrt mit dem negativen Drift

E[X_i] = \tfrac12 \ln \tfrac34 \approx -0{,}144.

Im Mittel schrumpft die Folge also pro Schritt um den Faktor $\sqrt{3/4}$ . Bis $\ln n$ abgebaut ist, vergehen ungefähr $\ln n / (\tfrac12 \ln \tfrac43)$ Schritte von $T$ . Da ein Schritt von $T$ im Mittel 1,5 Schritten von $C$ entspricht, erwartet man

\sigma_\infty(n) \approx \frac{3}{\ln(4/3)} \ln n \approx 10{,}43 \ln n.

Die Daten bestätigen das: Für $9000 \le n \le 10^4$ beträgt die mittlere Gesamtstoppzeit 96,1 Schritte, die Heuristik sagt bei $n = 9500$ den Wert 95,5 voraus. Ein Beweis ist das allerdings nicht. Die Heuristik beschreibt das typische Verhalten, kann aber einzelne Ausreißer – etwa eine divergente Folge – nicht ausschließen.

4. Was bewiesen ist

Fast alle Zahlen sinken. Terras [2] bewies 1976, dass die Menge der $n$ , deren Folge irgendwann unter $n$ fällt, natürliche Dichte 1 hat.
Viele Zahlen erreichen die 1. Krasikov und Lagarias [5] zeigten, dass für große $x$ mindestens $x^{0{,}84}$ der Zahlen $n \le x$ die 1 erreichen.
Fast alle Folgen werden fast beschränkt. Tao [6] bewies 2019: Für jede Funktion $f$ mit $f(n) \to \infty$ gilt $\min_k C^k(n) < f(n)$ für fast alle $n$ im Sinne der logarithmischen Dichte. Das ist das bislang stärkste Ergebnis in Richtung der Vermutung.
Zyklen müssten sehr lang sein. Eliahou [4] zeigte 1993, dass jeder nichttriviale Zyklus mindestens 17.087.915 Glieder hätte; mit den heutigen Verifikationsschranken ist die Schranke noch erheblich größer.
Verallgemeinerungen sind unentscheidbar. Conway [3] zeigte 1972, dass es für Funktionen derselben Bauart – stückweise linear abhängig vom Rest modulo $m$ – keinen allgemeinen Algorithmus gibt, der für eine solche Funktion und einen Startwert entscheidet, ob die Folge einen vorgegebenen Wert erreicht.

Conways Ergebnis besagt nicht, dass die Collatz-Vermutung selbst unentscheidbar ist. Es zeigt aber, dass Funktionen dieser Art beliebig komplexe Berechnungen ausführen können. Paul Erdős soll über das Problem gesagt haben: „Die Mathematik ist für solche Probleme noch nicht bereit.“

Literatur

J. C. Lagarias: The 3x + 1 Problem and Its Generalizations. American Mathematical Monthly 92 (1985), 3–23.
R. Terras: A Stopping Time Problem on the Positive Integers. Acta Arithmetica 30 (1976), 241–252.
J. H. Conway: Unpredictable Iterations. Proceedings of the 1972 Number Theory Conference, University of Colorado, Boulder (1972), 49–52.
S. Eliahou: The 3x + 1 Problem: New Lower Bounds on Nontrivial Cycle Lengths. Discrete Mathematics 118 (1993), 45–56.
I. Krasikov, J. C. Lagarias: Bounds for the 3x + 1 Problem Using Difference Inequalities. Acta Arithmetica 109 (2003), 237–258.
T. Tao: Almost All Orbits of the Collatz Map Attain Almost Bounded Values. Forum of Mathematics, Pi 10 (2022), e12.
D. Barina: Convergence Verification of the Collatz Problem. The Journal of Supercomputing 77 (2021), 2681–2688.