Die Collatz-Vermutung

Such dir einen Startwert aus und verfolge, wohin die Regel ihn treibt. Wirf danach einen Blick auf das zweite Bild. Dort siehst du alle Startwerte bis zum Limit auf einmal.

Rechenbeispiel — Die Collatz-Vermutung

Gesamte Stoppzeit	111
Höchster erreichter Wert	9.232
Höchster Wert ÷ Startwert	341,93
Größter Abstand zum Nachbarn	101
Halbierungen pro Verdreifachung	1,7073
Die Bahn ohne die +1-Schritte	0,8341
Längste Bahn bis 10.000	261
Startwerte bis 10.000 mit Höchstwert 9.232	1.579

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Die 27 braucht 111 Schritte. Ihr Nachbar braucht zehn. 🖖

Setze 26 als Startwert ein. Die Bahn verläuft über 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Zehn Schritte, und der Wert steigt nie über 40.

Probiere es nun mit der 27. Sie braucht 111 Schritte und klettert auf 9.232, was dem 341,93-Fachen ihres Startwerts entspricht.

Nichts an der 27 kündigt das an. Sie sitzt zwischen der 26 und der 28, und die 28 ist bereits nach 18 Schritten am Ziel. Die Zeile Größter Abstand zum Nachbarn errechnet diesen Sprung als 101. Ziehe den Startwert weiter nach rechts, und du wirst sehen, dass die Punkte im unteren Feld niemals eine saubere Kurve formen.

Der extremste Sprung unterhalb von 10.000 beträgt 225. Sechs benachbarte Zahlenpaare schaffen ihn. Das erste Paar ist 6.170 und 6.171: Die eine Zahl benötigt 36 Schritte, die andere 261.

Drei Viertel pro Verdreifachung, und es stimmt immer wieder 🖖

Eine ungerade Zahl wird zu 3n + 1. Das Ergebnis ist gerade, also folgt zwingend eine Halbierung. Dieser neue Wert ist in der Hälfte der Fälle durch 4 teilbar und in einem Viertel der Fälle durch 8, weshalb im Durchschnitt zwei Halbierungen folgen. Eine Verdreifachung und zwei Halbierungen multiplizieren den Wert mit ¾.

Denkt man das bis zum Ende durch, sollte die Anzahl der nötigen Verdreifachungen, um n auf 1 zu bringen, ungefähr bei ln n ÷ ln(4/3) liegen. Das entspricht 3,4761 ln n.

Die Ergebnistabelle vergleicht dies mit jedem untersuchten Startwert. Bis 10.000 liegt die mittlere Anzahl der Verdreifachungen bei 28,21, und ¾ pro Verdreifachung sagt 28,54 voraus. Bis 1.000 sind es 19,67 gegen 20,57. Bis 100.000 dann 35,65 gegen 36,54.

Die gesamte Argumentation stützt sich auf die Worte im Durchschnitt. Die Halbierungen entlang einer Bahn sind keine unabhängigen Münzwürfe. Sie sind in dem Moment besiegelt, in dem du n wählst. Bisher hat niemand einen Weg gefunden, dies mathematisch auszudrücken und die Antwort trotzdem zu behalten. Paul Erdős wurde 1985 von Jeffrey Lagarias treffend zitiert: „Die Mathematik ist für solche Probleme noch nicht bereit.“

Mach aus der 3 eine 5 und dieselbe Regel fängt die 27 ewig ein 🖖

Klick auf 5n + 1 und setze den Start auf 13. Die Bahn verläuft über 13, 66, 33, 166, 83, 416, 208, 104, 52, 26 und ist dann wieder bei 13. Zehn Zahlen, und sie wird diese endlos durchlaufen, wenn du sie lässt. Hier muss nichts mehr vermutet werden. Du kannst diese Liste in einer Minute von Hand nachrechnen.

Auch die 27 ist gefangen, in einer anderen Schleife aus zehn Zahlen: 27, 136, 68, 34, 17, 86, 43, 216, 108, 54.

Die Heuristik verrät, warum das so ist. Eine Verdreifachung und zwei Halbierungen ergeben ¾. Eine Verfünffachung und zwei Halbierungen sind 5/4. Eine Regel, die im Durchschnitt mit 5/4 multipliziert, hat keinen Grund, wieder nach unten zu fallen. Lass 5n + 1 ausgewählt und betrachte das untere Feld, das sich fast komplett geleert hat. Von den ersten 10.000 Startwerten erreichen 256 die 1. Weitere 470 fallen in eine Schleife. Die übrigen 9.274 klettern über 2⁵³, wo die Arithmetik des Werkzeugs ungenau wird und es aufhört, ihnen zu folgen.

Ein Beweis der Collatz-Vermutung muss also zwingend den Unterschied zwischen 3 und 5 kennen. Bis 2025 wurde die Regel für jeden Startwert bis 2⁷¹ geprüft. Das sind etwa 2,36 × 10²¹ Stück, berechnet von David Bařina auf europäischen Supercomputern. Der nächste Wert ist noch immer offen.

Aufgabe vollständig gelöst

Warum die 27 ganze 41 Verdreifachungen braucht, wo die Mathematik doch zwölf vorhersagt 8 Schritte
Die ¾-Regel besagt, dass eine Bahn ungefähr ln n ÷ ln(4/3) Verdreifachungen brauchen sollte, um ans Ziel zu kommen. Für n = 27 liegt das zwischen elf und zwölf. Das Werkzeug zeigt 41. Finde heraus, woher die zusätzlichen neunundzwanzig kommen, und wende dann dieselbe Buchführung auf den größten Startwert an, der je geprüft wurde.

Öffne diese Aufgabe im Tool
1. Aus einem ungeraden n wird 3n + 1, was gerade ist, weshalb zwingend mindestens eine Halbierung folgt. Der Wert ist in der Hälfte der Fälle durch 4 teilbar, zu einem Viertel durch 8 und zu einem Achtel durch 16. Die erwartete Anzahl an Halbierungen ist die Summe von k·2^−k, was genau 2 ergibt. Eine Verdreifachung gefolgt von zwei Halbierungen entspricht einer Multiplikation mit ¾.
  
  $E [v_{2} (3 n + 1)] = k \geq 1 \sum k 2^{- k} = 2 ⟹ \frac{3}{2 ^{2}} = \frac{3}{4}$
2. Wenn jeder Schritt mit ¾ multipliziert, sollte die Bahn bei 1 ankommen, sobald (¾)^o das n aufgebraucht hat. Löst man das nach o auf, ergibt das ln 27 ÷ ln(4/3) = 11,46. Nennen wir es zwölf Verdreifachungen. Mit zwei Halbierungen pro Stück macht das insgesamt etwa fünfunddreißig Schritte.
  
  $(\frac{3}{4})^{o} = \frac{1}{n} ⟹ o = \frac{ln 27}{ln ( 4/3 )} = \frac{3 . 2958}{0 . 28768} = 11.46$
3. Lade nun die 27 in das Werkzeug. Die Gesamte Stoppzeit zeigt 111, und Halbierungen pro Verdreifachung zeigt die Aufteilung, aus der sie stammt: 41 Verdreifachungen und 70 Halbierungen. Die Vorhersage liegt hier um den Faktor 3,58 daneben. Die 27 ist also definitiv kein typischer Startwert.
  
  $o = 41, e = 70, t = o + e = 111, \frac{41}{11 . 46} = 3.58$
4. Nimm die +1-Schritte heraus und die Bahn wird zu purer Multiplikation: 41 Verdreifachungen und 70 Halbierungen, angewendet auf 27. Dieses Produkt lautet 0,8341, und das Werkzeug gibt es unter Die Bahn ohne die +1-Schritte aus. Es läge bei genau 1, wenn die +1-Schritte überhaupt nichts bewirken würden. Es landet unter 1, weil jede +1 den Halbierungen etwas extra zu entfernen gibt. Bei einer Zweierpotenz, bei der nie ein ungerader Schritt auftritt, ist der Wert exakt 1.
  
  $L = n \cdot \frac{3 ^{o}}{2 ^{e}} = 27 \cdot \frac{3 ^{41}}{2 ^{70}} = 0.8341 < 1, 2^{k} \cdot \frac{3 ^{0}}{2 ^{k}} = 1$
5. Stellen wir das um. Schreiben wir L für das Produkt, dann ist n·3^o ÷ 2^e = L. Ziehen wir den Logarithmus zur Basis 2, so ergibt sich e = o·log₂3 + log₂(n/L). Teilt man durch o, erhält man das vom Werkzeug angezeigte Verhältnis. Für 27 ist das 1,58496 + 0,12236 = 1,70732, was das Werkzeug auf 1,7073 rundet. Für eine Bahn, die die 1 erreicht, kann das Verhältnis niemals unter log₂3 = 1,5850 fallen. Diejenigen Startwerte, die am nächsten herankommen, verbrauchen für ihre Größe die meisten Verdreifachungen. Unterhalb von 100.000 kommt nichts näher heran als die 27.
  
  $\frac{e}{o} = lo g_{2} 3 + \frac{lo g _{2} ( n / L )}{o} = 1.58496 + \frac{lo g _{2} ( 27/0 . 8341 )}{41} = 1.58496 + 0.12236 = 1.70732$
6. Das ist das Wesen einer langen Bahn: Ihr gehen die Halbierungen aus. Hier siehst du die 27 und die drei Startwerte an der Spitze der drei Scan-Bereiche, mit der 26 als Kontrast daneben. Ein typischer Startwert liefert im Schnitt etwa zwei Halbierungen pro Verdreifachung. Jeder Rekordhalter hier bewegt sich zwischen 1,70 und 1,74. Die Bahn gibt ihre Verdreifachungen aus und bekommt die Divisionen nicht zurück.
  
  $n 2627871 6, 171 77, 031 t 10111178261350 o 2416596129 e 870113165221 e / o 4.0000 1.7073 1.7385 1.7188 1.7132$
7. Jeder Startwert bis 2⁷¹ wurde geprüft. Das sind ungefähr 2,36 × 10²¹ Stück, berechnet von David Bařina auf europäischen Supercomputern und 2025 veröffentlicht. Jeder einzelne kam am Ziel an. Wie lang sollte die Reise dort unten dauern? ln(2⁷¹) ist 49,213. Die Heuristik liefert also 171 Verdreifachungen und etwa 513 Schritte für eine typische Zahl dieser Größe.
  
  $n = 2^{71} \approx 2.36 \times 1 0^{21} : o \approx \frac{71 ln 2}{ln ( 4/3 )} = \frac{49 . 213}{0 . 28768} = 171, t \approx 3 o = 513$
8. Die Zahlen, die dieses Problem interessant machen, sind allerdings keine typischen. Verglichen mit der mittleren Gesamten Stoppzeit im jeweiligen Scan-Bereich (59,60, 84,98 und 107,54 Schritte) laufen die Rekordhalter 2,99, 3,07 und 3,25 mal so lang. Überträgt man den letzten Wert, dann wollen die langsamsten Startwerte in der Nähe von 2⁷¹ eher 1.700 Schritte als 500. Das Verhältnis klettert auch im größten Scan-Bereich des Werkzeugs noch weiter. Die 1.700 sind also eher eine Untergrenze als eine echte Schätzung. Jede Zahl in diesem Gedankengang ist lediglich die Extrapolation einer Heuristik. Es ist aber die einzige Art von Aussage, die überhaupt jemand über Zahlen dieser Größe hat.
  
  $\frac{178}{59 . 60} = 2.99, \frac{261}{84 . 98} = 3.07, \frac{350}{107 . 54} = 3.25 ⟹ 3.25 \cdot 513 \approx 1, 700$
Antwort

41 Verdreifachungen statt zwölf, weil die Bahn der 27 bei 1,7073 Halbierungen pro Verdreifachung läuft, wo eine typische bei etwa 2 liegt. Alles, was bleibt, um die 27 nach unten zu zwingen, ist die schmale Lücke zwischen 1,7073 und log₂3 = 1,5850. Deshalb dauert der Abstieg ganze 111 Schritte.

Nichts davon beweist irgendetwas. Die ¾ stammt daher, dass wir jedes 3n + 1 so behandeln, als würde eine Münze entscheiden, wie oft es durch zwei teilbar ist. Diese Münze ist Fiktion. Die Halbierungen entlang einer Bahn stehen fest, sobald du n auswählst. Jeder bisher geprüfte Wert ist ohnehin angekommen, alle 2,36 × 10²¹ davon. Terence Tao kam der Sache am nächsten und bewies, dass fast jeder Startwert letztlich unter f(n) fällt, für jedes f, das gegen unendlich wächst, ganz egal wie langsam. Dabei bedeutet fast jeder eine logarithmische Dichte von 1. Fast jeder bedeutet aber nicht jeder, und genau in dieser Lücke liegt das Problem weiterhin.

$\frac{e}{o} = lo g_{2} 3 + \frac{lo g _{2} ( n / L )}{o} o \to \infty lo g_{2} 3 = 1.5850$

Quellen (3)

The verification limit the page quotes, and where the 2.36 × 10²¹ comes from: David Bařina, "Improved verification limit for the convergence of the Collatz conjecture", The Journal of Supercomputing 81(1), 1–14, 2025. doi:10.1007/s11227-025-07337-0
The strongest partial result, which the answer quotes: Terence Tao, "Almost all orbits of the Collatz map attain almost bounded values", Forum of Mathematics, Pi 10, e12, 2022 (posted 2019). doi:10.1017/fmp.2022.8
Where the Erdős line comes from, and the standard survey of the problem: Jeffrey C. Lagarias, "The 3x + 1 problem and its generalizations", American Mathematical Monthly 92(1), 3–23, 1985.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.