Collatz-Vermutung

Als Abbildung geschrieben lautet die Regel der Collatz-Vermutung

Ein Flug führt von $n$ über $f(n)$, $f(f(n))$ und so weiter und endet, sobald er 1 erreicht. Danach würde er nur noch die Runde 1 → 4 → 2 → 1 drehen. Die Vermutung besagt, dass jede positive ganze Zahl dort ankommt. Hier kannst du ganze Zahlen einzeln oder in einer Gruppe fliegen lassen, auch solche mit Hunderten von Stellen. Du kannst sie mit der groben Überlegung vergleichen, die die Vermutung so plausibel macht, und sehen, warum diese Überlegung kein Beweis ist.

Waagerecht steht die Schrittzahl, senkrecht der Wert, standardmäßig auf einer logarithmischen Achse. Direkt zeigt stattdessen das vertraute Hagelkornbild. Jede Zahl der Gruppe ist eine farbige Linie. Ein Abschnitt, den viele Zahlen durchlaufen, ist deshalb kräftiger gefärbt: auf dunklem Hintergrund heller, auf hellem dunkler. Die betrachtete Zahl ist hervorgehoben; ein roter Punkt zeigt, wo sie gerade ist. Flüge sind schwer vorherzusagen: 27 steigt bis 9 232 und braucht 111 Schritte bis zur 1, während 28 nur 18 braucht.

Warum glaubt man daran? Ein Schritt mit einer ungeraden Zahl liefert immer eine gerade Zahl. Fasse ihn daher mit der anschließenden Halbierung zu einem verkürzten Schritt zusammen. Nimm nun an, die Paritäten dieser Schritte verhielten sich wie unabhängige Würfe einer fairen Münze. In der Hälfte der Fälle wird $n$ ungefähr mit 3/2 multipliziert, in der anderen Hälfte mit 1/2. Im Mittel verändert ein verkürzter Schritt $\ln n$ also um

Die Zahlen sollten dann schrumpfen, typischerweise alle zwei verkürzten Schritte auf das 3/4-Fache. Auf der logarithmischen Achse ist diese Drift die gestrichelte Linie. Sie wird für eine Gruppe aus mindestens 100 Zahlen unter Gleiche Größenordnung gezeichnet. Sie berücksichtigt das Landen nicht: Zahlen, die 1 erreichen, bleiben am Boden. Daher sinkt die mittlere Höhe der Gruppe auf dieser Achse gegen Ende langsamer als die Linie.

Die Münzwürfe sind nur ein Modell für das durchschnittliche Verhalten der Zahlen. Die Vermutung betrifft aber jede positive ganze Zahl. Schon ein einziger Flug, der nie 1 erreicht, würde sie widerlegen.

Die negativen Zahlen zeigen, was die Überlegung übersieht. Dieselbe Regel hat dort Schleifen; drei sind bekannt, zum Beispiel −5 → −14 → −7 → −20 → −10 → −5. Das Münzmodell sagt auch dort ein Schrumpfen voraus. Doch eine vollständige Runde durch eine Schleife verändert $\log|n|$ um genau 0. Eine im Mittel abwärts gerichtete Drift kann eine Schleife nicht ausschließen, auch nicht unter den positiven Zahlen.

Koralle kehrt die Flüge um: Von 1 aus rückwärts gewachsen bilden die Wege einer Gruppe einen Baum. Jede Kante dreht sich gegenüber der vorherigen um $+\alpha$, wenn die neue Zahl gerade ist, und um $-\alpha \log_2 3$, wenn sie ungerade ist. α wird mit Biegung eingestellt. Rückwärts von 1 aus verdoppelt ein gerader Schritt die Zahl und erhöht ihren $\log_2$ um 1. Ein ungerader Schritt verringert ihn um etwas mehr als $\log_2 3$. Die Kante, die n erreicht, ist daher gegenüber der Senkrechten nach oben insgesamt um $\alpha \log_2 n$ gedreht, zuzüglich eines kleinen Betrags für jeden ungeraden Schritt. Ihre Drehung hält die Größe von n fest. Entlang eines Asts steigt und fällt die Richtung mit den Zahlen eines Flugs; jeder Ast ist also ein eingerollter Flug. Äste vereinigen sich dort, wo Flüge zusammentreffen. In dieser Darstellung besagt die Vermutung, dass der von 1 aus gewachsene Baum jede positive ganze Zahl enthält.

Das Problem wird gewöhnlich Lothar Collatz zugeschrieben, der in den 1930er-Jahren Fragen dieser Art stellte. Die Koralle folgt Edmund Harriss’ „Collatz seaweed“ (2016).