Collatz-Problem

Das Collatz-Problem, auch als (3n+1)-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde. Es hat Verbindungen zur Zahlentheorie, zur Theorie dynamischer Systeme und Ergodentheorie und zur Berechenbarkeitstheorie in der Informatik.

Das Problem ist zwar einfach zu formulieren, aber notorisch schwierig. Jeffrey Lagarias, der als Experte für das Problem gilt, zitiert eine mündliche Mitteilung von Paul Erdős, der es als „absolut hoffnungslos“ bezeichnete.^[1]

Bei dem Problem geht es um Zahlenfolgen, die nach einem einfachen Bildungsgesetz konstruiert werden:

• Beginne mit einer beliebigen natürlichen Zahl n > 0 {\displaystyle n>0} .
• Ist n {\displaystyle n} gerade, so nimm als nächstes n / 2 {\displaystyle n/2} .
• Ist n {\displaystyle n} ungerade, so nimm als nächstes 3 n + 1 {\displaystyle 3n+1} .
• Wiederhole die Vorgehensweise mit der erhaltenen Zahl.

Zum Beispiel ergibt sich mit der Startzahl n = 19 {\displaystyle n=19} die Folge

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 tritt somit in einen Zyklus ein, in dem die Zahlen 4, 2, 1 ständig wiederholt werden.

Die Collatz-Vermutung lautet nun:

Die Zahlenfolge mündet immer in den Zyklus 4, 2, 1, egal, mit welcher positiven natürlichen Zahl man beginnt.

Diese Vermutung wurde bislang weder bewiesen noch widerlegt.

Bezeichne mit

• N := { 1 , 2 , 3 , … } {\displaystyle \mathbb {N} :=\{1,2,3,\dots \}} die natürlichen Zahlen ohne die Null.
• N 0 := { 0 , 1 , 2 , 3 , … } {\displaystyle \mathbb {N} _{0}:=\{0,1,2,3,\dots \}} die natürlichen Zahlen mit der Null.

Sei n ∈ N {\displaystyle n\in \mathbb {N} } und Col : N → N {\displaystyle \operatorname {Col} \colon \mathbb {N} \to \mathbb {N} } die Collatz-Funktion

Col ⁡ ( n ) = { n 2 wenn  n  gerade ist, 3 n + 1 wenn  n  ungerade ist. {\displaystyle \operatorname {Col} (n)={\begin{cases}{\frac {n}{2}}&{\text{wenn }}n{\text{ gerade ist,}}\\3n+1\quad &{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}

Definiere den Collatz-Orbit ∀ k ∈ N 0 {\displaystyle \forall k\in \mathbb {N} _{0}}

Col k ⁡ ( n ) = { n wenn  k = 0 , Col ⁡ ( Col k − 1 ⁡ ( n ) ) wenn  k > 1. {\displaystyle \operatorname {Col} ^{k}(n)={\begin{cases}n&{\text{wenn }}k=0,\\\operatorname {Col} (\operatorname {Col} ^{k-1}(n))\quad &{\text{wenn }}k>1.\end{cases}}}

Dann lautet die Vermutung:

Zu jedem n ∈ N {\displaystyle n\in \mathbb {N} } existiert ein r ∈ N {\displaystyle r\in \mathbb {N} } , so dass Col r ⁡ ( n ) = 1 {\displaystyle \operatorname {Col} ^{r}(n)=1} .

Für den Orbit Col N 0 ⁡ ( n ) = { n , Col ⁡ ( n ) , Col 2 ⁡ ( n ) , Col 3 ⁡ ( n ) , … } {\displaystyle \operatorname {Col} ^{\mathbb {N_{0}} }(n)=\{n,\operatorname {Col} (n),\operatorname {Col} ^{2}(n),\operatorname {Col} ^{3}(n),\dots \}} gilt somit Col 2 ⁡ ( n ) = Col ⁡ ( Col ⁡ ( n ) ) {\displaystyle \operatorname {Col} ^{2}(n)=\operatorname {Col} (\operatorname {Col} (n))} , Col 3 ⁡ ( n ) = Col ⁡ ( Col ⁡ ( Col ⁡ ( n ) ) ) {\displaystyle \operatorname {Col} ^{3}(n)=\operatorname {Col} (\operatorname {Col} (\operatorname {Col} (n)))} usw.

Um die Vermutung zu beweisen, muss man für jedes n {\displaystyle n} zeigen, dass ein solches r {\displaystyle r} existiert. Um die Vermutung zu widerlegen, muss man ein n {\displaystyle n} finden, für das ein solches r {\displaystyle r} nicht existiert.

Eine gleichwertige Aussage der Vermutung ist, dass das kleinste Element Col min N ⁡ ( n ) = inf r ∈ N Col r ⁡ ( n ) {\displaystyle \operatorname {Col} _{\text{min}}^{\mathbb {N} }(n)=\inf _{r\in \mathbb {N} }\operatorname {Col} ^{r}(n)} jedes Collatz-Orbits die Zahl 1 {\displaystyle 1} ist.

Wegen der simplen Formulierung der Problemstellung werden im Internet immer wieder angebliche Beweise veröffentlicht. Ein häufiger logischer Fehlschluss, der gemacht wird, besteht darin, das Problem lediglich neu zu formulieren, anstatt es tatsächlich zu beweisen.

Trotz zahlreicher Anstrengungen gehört diese Vermutung noch immer zu den ungelösten Problemen der Mathematik. Mehrfach wurden Preise für eine Lösung ausgelobt:

• 1970 bot H. S. M. Coxeter 50 Dollar für einen Beweis der Vermutung und 100 Dollar für ein Gegenbeispiel.^[3]
• 1982 versprach Bryan Thwaites in der Zeitung The Times 1000 Pfund für einen Beweis oder eine Widerlegung (Angebot 1996/1998 erneuert).^[4][5][6][7]
• Paul Erdős bot angeblich 500 Dollar für eine Lösung^[8] und sagte über das Collatz-Problem:^[1]

„Mathematics is not yet ready for such problems.“ („Die Mathematik ist für solche Probleme noch nicht bereit.“) und

„Hopeless. Absolutely hopeless.“ („Hoffnungslos. Absolut hoffnungslos.“)

Der Mathematiker Richard Guy warnte 1983 vor diesem und drei anderen auch heute noch ungelösten Problemen:^[9][10]

„Don’t try to solve these problems!“ („Versuche nicht, diese Probleme zu lösen!“)

Der Ursprung der Collatz-Vermutung liegt insofern etwas im Nebel, als aus der mutmaßlichen Entstehungszeit bisher keine schriftlichen Dokumente mit einer Beschreibung des Problems öffentlich zugänglich sind. Es wird berichtet, dass Collatz das Problem beim Internationalen Mathematikerkongress 1950 in Cambridge (Massachusetts) mündlich verbreitete.^[11] Stanisław Ulam und Shizuo Kakutani, die auf diesem Kongress zu Vorträgen eingeladen waren, stellten das Problem immer wieder in Gesprächen dar und werden deshalb in diesem Zusammenhang häufig genannt. Als Lothar Collatz 1952 seine Professur in Hamburg antrat, erzählte er seinem Hamburger Kollegen Helmut Hasse von der Vermutung. Dieser verbreitete das Problem während eines Forschungsaufenthalts an der Syracuse University, deshalb erhielt das Collatz-Problem auch den Namen Syracuse-Vermutung. Publikationen zur Entstehung und Verbreitung:

• 1971 wurde das Collatz-Problem in der gedruckten Version eines 1970 gehaltenen Vortrags von H. S. M. Coxeter zum vermutlich ersten Mal schriftlich veröffentlicht.^[3]
• 1972 erfuhr Martin Gardner von der Beschäftigung der akademischen Hacker am MIT mit dem (3n+1)-Problem^[12] und beschrieb es in seiner Kolumne Mathematical Games im Scientific American.^[13] Die Vermutung wurde durch diese und weitere Veröffentlichungen unter anderem von John Conway^[14] inner- und außerhalb von Fachkreisen weithin bekannt.
• 1976 veröffentlichte Riho Terras die ersten wissenschaftlichen Forschungsergebnisse direkt zum Collatz-Problem.^[15] Terras zeigte mit probabilistischen Methoden, dass

Col min N ⁡ ( n ) < n {\displaystyle \operatorname {Col} _{\text{min}}^{\mathbb {N} }(n)<n}

für fast alle (bezüglich der logarithmischen Dichte) n ∈ N {\displaystyle n\in \mathbb {N} } gilt.^[16]

• 1985 erschien in der Zeitschrift American Mathematical Monthly ein Überblicksartikel von Jeffrey Lagarias.^[8] Lagarias berichtet darin über Collatz’ Interesse an zahlentheoretischen Funktionen und Graphentheorie, und er zitiert einen Notizbucheintrag vom 1. Juli 1932, in dem Collatz die folgende Permutation der positiven ganzen Zahlen betrachtet:

g ( n ) = { 2 3 n wenn n ≡ 0 mod 3 , 4 3 n − 1 3 wenn n ≡ 1 mod 3 , 4 3 n + 1 3 wenn n ≡ 2 mod 3. {\displaystyle g(n)={\begin{cases}{\tfrac {2}{3}}n&{\text{wenn}}\quad n\equiv 0\mod 3,\\{\tfrac {4}{3}}n-{\tfrac {1}{3}}&{\text{wenn}}\quad n\equiv 1\mod 3,\\{\tfrac {4}{3}}n+{\tfrac {1}{3}}&{\text{wenn}}\quad n\equiv 2\mod 3.\end{cases}}}

Diese Permutation besitzt den Fixpunkt 1 und außerdem zumindest die Zyklen (2, 3), (4, 5, 7, 9, 6) und (44, 59, 79, 105, 70, 93, 62, 83, 111, 74, 99, 66). In dem zitierten Notizbucheintrag stellt Collatz die auch heute noch offene Frage, ob die mit 8 beginnende g-Trajektorie zyklisch wird oder gegen unendlich divergiert.^[8][11] Die ebenfalls weiterhin offene Frage, ob weitere Zyklen existieren, ist wie die (3n+1)-Vermutung eines der von Guy beschriebenen Probleme, die man nicht zu lösen versuchen solle.^[9][17]

• 1985 veröffentlichte Bryan Thwaites eine Mitteilung, er habe die Vermutung am 21. Juli 1952 um vier Uhr nachmittags als Aufgabe zur Unterhaltung seiner Schüler gestellt (er beanspruchte bereits 1982 die Entdeckung im Jahr 1952).^[5][18][7]
• 1986 ließ Lothar Collatz eine Darstellung seines Entdeckungswegs zur (3n+1)-Vermutung ins Chinesische übersetzen und in einem Journal der Pädagogischen Universität Qufu, Shandong, China, an der er einen Vortrag darüber gehalten hatte, veröffentlichen.^[19] Dies blieb die einzige Veröffentlichung von Collatz zu diesem Problem.

Nach Terras’ Publikation 1976 begann nach und nach eine rege wissenschaftliche Beschäftigung mit dem Collatz-Problem, die mittlerweile weit mehr als hundert Publikationen mit neuen Forschungsergebnissen umfasst. Im populärwissenschaftlichen Bereich entstanden neue Bezeichnungen:

• 1979 nannte Douglas R. Hofstadter in seinem Buch Gödel, Escher, Bach diejenigen Startzahlen, deren Collatz-Trajektorie im Zyklus (1,4,2) endet, wondrous numbers, wundersame Zahlen.^[20]
• 1984 nannte Brian Hayes die Zahlen von Collatz-Folgen in der Kolumne Computer recreations im Scientific American hailstone numbers, Hagelschlagzahlen.^[21]
• 1994 zeigte Ivan Korec, dass für die Anfangswerte S {\displaystyle S} fast überall für den Collatz-Algorithmus einen Wert unter S 0 , 7925 {\displaystyle S^{0,7925}} erreichen.^[22]
• 2019 zeigte Terence Tao, dass die Collatz-Vermutung für die natürlichen Zahlen fast zutrifft, siehe Abschnitt Collatz-Problem#Teillösung von Tao.^[23] Tao nützte dabei probabilistische Methoden und zeigte mittels der logarithmischen Dichte, dass das Infimum des Collatz-Orbits für die Elemente fast überall für jede divergierende Funktion beschränkt ist, egal wie langsam diese divergiert (zum Beispiel log ⁡ log ⁡ log ⁡ log ⁡ n {\displaystyle \log \log \log \log n} ).^[24]

Collatz’ Beschreibung seiner Motivation der (3n+1)-Vermutung ist sehr plausibel:^[25] Er assoziiert zunächst ganz allgemein zu einer beliebigen Funktion auf den natürlichen Zahlen mit Werten in den natürlichen Zahlen einen gerichteten Graphen, der von Lagarias im oben erwähnten Überblicksartikel Collatz-Graph genannt wird. Der Collatz-Graph einer zahlentheoretischen Funktion

f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} }

ist ein gerichteter Graph, bestehend aus der Menge der natürlichen Zahlen als Knotenmenge und zu jeder natürlichen Zahl n {\displaystyle n} einer gerichteten Kante von n {\displaystyle n} nach f ( n ) {\displaystyle f(n)} .

Die einfachste solche Funktion ist die Nachfolgerabbildung

s : N → N , s ( n ) = n + 1 , {\displaystyle s\colon \mathbb {N} \to \mathbb {N} ,\quad s(n)=n+1,}

deren Collatz-Graph aus einem unendlich langen Weg besteht:

1 → 2 → 3 → 4 → 5 → ⋯ {\displaystyle 1\to 2\to 3\to 4\to 5\to \dotsb }

Um mehr Beispiele zu haben, suchte er zunächst nach einer möglichst „einfachen“ zahlentheoretischen Funktion, deren Collatz-Graph einen Kreis enthält. Eine solche Funktion f {\displaystyle f} muss auf gewissen natürlichen Zahlen n {\displaystyle n} „aufsteigen“, also die Relation n < f ( n ) {\displaystyle n<f(n)} erfüllen, und auf anderen natürlichen Zahlen m {\displaystyle m} „absteigen“, also die Relation m > f ( m ) {\displaystyle m>f(m)} erfüllen. So stieß er zunächst auf die Funktion, die definiert ist durch

C 1 ( n ) := { n / 2 wenn  n  gerade ist, n + 1 wenn  n  ungerade ist. {\displaystyle C_{1}(n):={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\n+1\quad &{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}

Den Collatz-Graphen dieser Funktion kann man wie folgt beschreiben: Die Knoten sind, nach Definition, die positiven ganzen Zahlen. Ist der Knoten k {\displaystyle k} gerade, besitzt k {\displaystyle k} die beiden Vorgängerknoten k − 1 {\displaystyle k-1} und 2 k {\displaystyle 2k} , sonst nur 2 k {\displaystyle 2k} . Außerdem gilt

C 1 2 ( n ) = C 1 ( C 1 ( n ) ) = { n 4 wenn  n  durch 4 teilbar ist, n 2 + 1 wenn  n  durch 2, aber nicht durch 4 teilbar ist, n + 1 2 wenn  n  ungerade ist. {\displaystyle C_{1}^{2}(n)=C_{1}(C_{1}(n))={\begin{cases}{\frac {n}{4}}&{\text{wenn }}n{\text{ durch 4 teilbar ist,}}\\{\frac {n}{2}}+1&{\text{wenn }}n{\text{ durch 2, aber nicht durch 4 teilbar ist,}}\\{\frac {n+1}{2}}\quad &{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}

Daraus folgt

C 1 2 ( n ) < n  wenn  n > 2 , {\displaystyle C_{1}^{2}(n)<n\qquad {\text{ wenn }}n>2,}

und das hat zur Folge, dass der Collatz-Graph von C 1 {\displaystyle C_{1}} nur den Kreis ( 1 , 2 ) {\displaystyle (1,2)} besitzt und dass die C 1 {\displaystyle C_{1}} -Trajektorie zu jeder beliebigen Startzahl in diesen Kreis mündet.

Weil diese Argumentation ziemlich einfach ist, suchte Collatz weiter: Der Collatz-Graph der Funktion

C 2 ( n ) = { n / 2 wenn  n  gerade ist, 2 n + 1 wenn  n  ungerade ist, {\displaystyle C_{2}(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\2n+1\quad &{\text{wenn }}n{\text{ ungerade ist,}}\end{cases}}}

enthält keinen Kreis, da jede ungerade Zahl auf eine größere ungerade Zahl abgebildet wird, und die C 2 {\displaystyle C_{2}} -Trajektorien daher alle gegen unendlich divergieren.

Der nächste Versuch ist die Collatz-Funktion

C : N → N , C ( n ) = { n / 2 wenn  n  gerade ist, 3 n + 1 wenn  n  ungerade ist. {\displaystyle C\colon \mathbb {N} \to \mathbb {N} ,\quad C(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\3n+1&{\text{wenn }}n{\text{ ungerade ist.}}\end{cases}}}     (Folge A006370 in OEIS)

Zu dieser Funktion fand Collatz nur den „trivialen Kreis“ ( 1 , 4 , 2 ) {\displaystyle (1,4,2)} – er schrieb, er habe seine Ideen deshalb nicht veröffentlicht, weil er nicht beweisen konnte, dass der „triviale Kreis“ der einzige sei. Die Collatz-Vermutung ist in graphentheoretischer Formulierung die Vermutung, dass der Collatz-Graph von C {\displaystyle C} zusammenhängend ist.

Für eine C {\displaystyle C} -Trajektorie als Zahlenfolge kann man drei einander ausschließende Möglichkeiten unterscheiden:

• die Folge endet im (1,4,2)-Zyklus,
• die Folge gerät in einen anderen Zyklus,
• die Folge wächst über alle Grenzen.

Die Collatz-Vermutung besagt, dass nur die erste Möglichkeit für alle Folgen zutrifft. Eine Realisierung der zweiten und dritten Möglichkeit für eine bestimmte Folge konnte bisher nicht ausgeschlossen werden. Es konnte bisher auch nicht bewiesen werden, dass es nur endlich viele Zyklen geben kann.^[26]

Da 3 n + 1 {\displaystyle 3n+1} für ungerade n {\displaystyle n} stets gerade ist und somit die folgende Iteration immer die Division durch 2, wird statt der Collatz-Funktion C {\displaystyle C} meistens die etwas einfacher zu handhabende Funktion

T : N → N , T ( n ) = { n / 2 wenn  n  gerade ist, ( 3 n + 1 ) / 2 wenn  n  ungerade ist, {\displaystyle T\colon \mathbb {N} \to \mathbb {N} ,\quad T(n)={\begin{cases}n/2&{\text{wenn }}n{\text{ gerade ist,}}\\(3n+1)/2&{\text{wenn }}n{\text{ ungerade ist,}}\end{cases}}}     (Folge A014682 in OEIS)

verwendet, die also für ungerade n {\displaystyle n} zwei C {\displaystyle C} -Iterationen auf einmal macht und den der Vermutung zufolge stets erreichten Zyklus von (1,4,2) auf (1,2) reduziert. Die k {\displaystyle k} -fache Abbildung T k {\displaystyle T^{k}} bildet 2 k m {\displaystyle 2^{k}m} auf m {\displaystyle m} und 2 k m − 1 {\displaystyle 2^{k}m-1} auf 3 k m − 1 {\displaystyle 3^{k}m-1} ab, insbesondere gibt es für jeden beliebig großen Faktor Startwerte, die die wiederholte Abbildung mit C {\displaystyle C} oder T {\displaystyle T} um mindestens diesen Faktor vergrößert. Die Collatz-Vermutung ist äquivalent zu der Vermutung, dass für alle ganzen Zahlen n > 1 {\displaystyle n>1} eine ganze Zahl k > 0 {\displaystyle k>0} mit T k ( n ) < n {\displaystyle T^{k}(n)<n} existiert. Terras zeigte 1976, dass die asymptotische Dichte der ganzen Zahlen n > 1 {\displaystyle n>1} , für die das zutrifft, existiert und gleich 1 ist.^[15]

Berechnungen mit Computern ergaben:^[27]

• Alle positiven ganzen Zahlen bis 2⁶⁸ (ca. 2,95×10²⁰) als Startwerte bestätigen die Vermutung (Stand Juli 2020).^[28]
• Hat die T {\displaystyle T} -Iteration noch einen anderen Zyklus als (1,2), dann muss dieser aus mindestens 10.439.860.591 Zahlen bestehen, davon mindestens 6.586.818.670 ungerade.^[29]
• Für unendlich viele positive ganze Zahlen n {\displaystyle n} sind mindestens 6,143 log n Iterationen mit T {\displaystyle T} erforderlich, um 1 zu erreichen.^[30] Stochastische Modelle sagen voraus, dass durchschnittlich (2 / log(4/3)) log n ≈ 6,952 log n Schritte benötigt werden und dass für mindestens die Hälfte aller Zahlen mindestens so viele T {\displaystyle T} -Iterationen erforderlich sind.
• Für genügend große X {\displaystyle X} ist die Anzahl der positiven ganzen Zahlen kleiner oder gleich X {\displaystyle X} , die als Startwert die Vermutung bestätigen, mindestens X 0 , 84 {\displaystyle X^{0{,}84}} .^[31]

Terence Tao zeigte 2019, dass die Collatz-Vermutung für „fast alle“ natürlichen Zahlen „fast“ zutrifft (das heißt, man endet mit der Collatzfolge „nahe“ 1, wobei die Schranke für die Nähe vom Startwert N abhängt).^[23][24] Beispielsweise folgt aus Taos Satz, dass mindestens 99 Prozent der natürlichen Zahlen bis 10 24 {\displaystyle 10^{24}} , mit denen man die Collatzfolge startet, einen Endwert erreichen, der unter 200 liegt. Tao benutzte dabei Methoden, die er zuvor in der Theorie partieller Differentialgleichungen angewandt hatte, indem er statistisch eine Auswahl von Anfangswerten sampelte und dann das „Langzeitverhalten“ des Ensembles unter der Collatztransformation untersuchte.

Betrachtet man bei der Anwendung der Collatz-Funktion nur ungerade Zahlen, kann man mit elementaren Rechnungen einige grundlegende Eigenschaften dieser Abbildung zeigen.

Ungerade natürliche Zahlen haben bei einer Division durch 4 entweder den Rest 1 oder den Rest 3. Die ungeraden natürlichen Zahlen lassen sich so in zwei disjunkte Teilmengen aufteilen. Die eine Teilmenge der ungeraden Zahlen sind die Zahlen der Reihe 4n+1 mit n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} . Die andere Teilmenge sind die Zahlen der Reihe 4n+3 mit n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} . Wendet man nun auf die Zahlen der ersten Reihe die Collatz-Funktion an, erhält man die Zahlen der Reihe 12n+4. Da es sich bei diesen Zahlen immer um gerade Zahlen handelt, kann die Collatz-Funktion erneut angewendet werden. Die Zahlen der Reihe 12n+4 werden also auf die Zahlen der Reihe 6n+2 abgebildet und diese dann auf die Zahlen der Reihe 3n+1. Durch weitere Rechnungen in dieser Art lassen sich die folgenden allgemeinen Eigenschaften der Orbits zeigen:

• Die ungeraden Zahlen der Reihe 4n+1 mit n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} werden nach drei Anwendungen der Collatz-Funktion auf die Zahlen der Reihe 3n+1 abgebildet. Bei einer grafischen Darstellung der Folge ergibt sich hier also insgesamt ein Sprung nach unten.
• Die ungeraden Zahlen der Reihe 4n+3 mit n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} werden in den zwei folgenden Anwendungen der Collatz-Funktion auf die Zahlen der Reihe 6n+5 abgebildet. Bei einer grafischen Darstellung der Folge ergibt sich hier also insgesamt ein Sprung nach oben. Nach zwei weiteren Iterationen werden diese Zahlen dann auf die Zahlen der Reihe 9n+8 abgebildet. Die Zahlen der Reihe 9n+8 sind abwechselnd gerade und ungerade.
• Die Zahlen der Reihe 8n+3 mit n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} werden nach fünf Iterationen auf die Zahlen der Reihe 9n+4 abgebildet
• Aufgrund der ersten oben genannten Eigenschaft ist es bei einer Überprüfung der Collatz-Vermutung für alle natürlichen Zahlen unterhalb einer Schranke M {\displaystyle M} mit M ∈ N {\displaystyle M\in \mathbb {N} } hinreichend, sich auf die Zahlen der Reihe 4n+3, die kleiner oder gleich M {\displaystyle M} sind, zu beschränken.

Die genannten Regeln können dazu benutzt werden, um bei einer Überprüfung der Collatz-Vermutung für alle natürlichen Zahlen unterhalb einer gegebenen Schranke mit Hilfe von Computerprogrammen Rechenzeit einzusparen.

In ähnlicher Weise lässt sich auch die etwas allgemeinere Formel herleiten:

T k ( 2 k n + a ) = 3 c ( a , k ) n + d ( a , k ) {\displaystyle T^{k}(2^{k}n+a)=3^{c(a,k)}n+d(a,k)} .

Es gilt d ( a , k ) = T k ( a ) {\displaystyle d(a,k)=T^{k}(a)} . Die Konstante c ( a , k ) {\displaystyle c(a,k)} ist gleich der Anzahl aller ungeraden Zahlen, die sich bei den T {\displaystyle T} -Iterationen von a ergeben. Diese Anzahl hängt damit ebenfalls nur von den zwei Konstanten k {\displaystyle k} und a {\displaystyle a} ab. Für k = 2 {\displaystyle k=2} ergeben sich die folgenden Werte für die beiden Konstanten

c ( 0 … 3 , 2 ) = { 0 , 1 , 1 , 2 = k } d ( 0 … 3 , 2 ) = { 0 , 1 , 2 , 8 = 3 k − 1 } {\displaystyle {\begin{aligned}c(0\ldots 3,2)&=\{0,1,1,2=k\}\\d(0\ldots 3,2)&=\{0,1,2,8=3^{k}-1\}\end{aligned}}}

Für k = 5 {\displaystyle k=5} ergeben sich die folgenden Werte:

c ( 0 … 31 , 5 ) = { 0 , 3 , 2 , 2 , 2 , 2 , 2 , 4 , 1 , 4 , 1 , 3 , 2 , 2 , 3 , 4 , 1 , 2 , 3 , 3 , 1 , 1 , 3 , 3 , 2 , 3 , 2 , 4 , 3 , 3 , 4 , 5 = k } d ( 0 … 31 , 5 ) = { 0 , 2 , 1 , 1 , 2 , 2 , 2 , 20 , 1 , 26 , 1 , 10 , 4 , 4 , 13 , 40 , 2 , 5 , 17 , 17 , 2 , 2 , 20 , 20 , 8 , 22 , 8 , 71 , 26 , 26 , 80 , 242 = 3 k − 1 } {\displaystyle {\begin{aligned}c(0\ldots 31,5)&=\{0,3,2,2,2,2,2,4,1,4,1,3,2,2,3,4,1,2,3,3,1,1,3,3,2,3,2,4,3,3,4,5=k\}\\d(0\ldots 31,5)&=\{0,2,1,1,2,2,2,20,1,26,1,10,4,4,13,40,2,5,17,17,2,2,20,20,8,22,8,71,26,26,80,242=3^{k}-1\}\end{aligned}}}

Beispiele zu obiger Formel:

• Für 2 5 n + 1 {\displaystyle 2^{5}n+1} ergeben sich bei fünf T {\displaystyle T} -Iterationen immer drei ungerade Zahlen. Somit werden diese Zahlen auf die Zahlen 3 3 n + 2 {\displaystyle 3^{3}n+2} abgebildet.
• Für 2 2 n + 1 {\displaystyle 2^{2}n+1} ergibt sich bei zwei T {\displaystyle T} -Iterationen immer eine ungerade Zahl. Damit ergibt sich das bereits oben angegebene Ergebnis 3 n + 1 {\displaystyle 3n+1} .
• Für 2 k n − 1 {\displaystyle 2^{k}n-1} ergeben sich bei k {\displaystyle k} T {\displaystyle T} -Iterationen k {\displaystyle k} ungerade Zahlen. Das Ergebnis lautet dann 3 k n − 1 {\displaystyle 3^{k}n-1} .
• Für 2 k n + 1 {\displaystyle 2^{k}n+1} ergibt sich bei ungeradem k {\displaystyle k} nach k {\displaystyle k} T {\displaystyle T} -Iterationen 3 ( k + 1 ) / 2 n + 2 {\displaystyle 3^{(k+1)/2}n+2} .
• Für 2 k n + 1 {\displaystyle 2^{k}n+1} ergibt sich bei geradem k {\displaystyle k} nach k {\displaystyle k} T {\displaystyle T} -Iterationen 3 k / 2 n + 1 {\displaystyle 3^{k/2}n+1} .

Die letzten drei Beispiele zeigen, dass es weder für den Maximalwert noch für die Länge der Collatz-Folgen eine obere Schranke gibt.

Mit Hilfe der Konstanten c ( a , k ) {\displaystyle c(a,k)} und d ( a , k ) {\displaystyle d(a,k)} kann leicht gezeigt werden, dass für die Startwerte aus der Folge 4n+3 nach jeweils fünf T {\displaystyle T} -Iterationen und beliebiges n nur für a ∈ { 7 , 15 , 27 , 31 } {\displaystyle a\in \{7,15,27,31\}} die Folgenwerte größer sind als die Startwerte. Für alle anderen Startwerte aus der Folge 4n+3 wird nach fünf T {\displaystyle T} -Iterationen auf einen kleineren Wert abgebildet. Die letztgenannten Startwerte dürfen deshalb bei einer numerischen Überprüfung der Collatz-Vermutung weggelassen werden.

Die folgende Gleichung zeigt, dass es neben der Menge der Zweierpotenzen noch mindestens eine weitere unendlich große Teilmenge an Collatz-Folgen gibt, bei der jedes Element die Collatz-Vermutung erfüllt. Mit

b ( m , k ) := 2 3 ( m − 1 ) ( 2 k + 1 ) {\displaystyle b(m,k):=2^{3^{(m-1)}(2k+1)}}

m = 1 , 2 , 3 , 4 , 5 , … {\displaystyle m=1,2,3,4,5,\dots } und k = 0 , 1 , 2 , 3 , … {\displaystyle k=0,1,2,3,\dots } gilt

T m ( ( 2 3 ) m ( b ( m , k ) + 1 ) − 1 ) = b ( m , k ) {\displaystyle T^{m}\left(\left({\frac {2}{3}}\right)^{m}(b(m,k)+1)-1\right)=b(m,k)}

Die Ganzzahligkeit der Division lässt sich mit Hilfe der Partialsumme der geometrischen Reihe und vollständiger Induktion beweisen.^[32] Für m = 1 {\displaystyle m=1} bilden diese Startwerte gerade die Folge A002450 in OEIS ohne die 0 {\displaystyle 0} .

Die Collatz-Vermutung entspricht auch der Aussage, dass es bei jeder Collatz-Folge nach endlich vielen Iterationsschritten ein Folgenelement gibt, das als Zweierpotenz mit endlichem Exponenten darstellbar ist.

Die Syracuse-Funktion (benannt nach der Syracuse University in New York) ist eine mit der Collatz-Funktion verwandte Funktion. Sei n ∈ N {\displaystyle n\in \mathbb {N} } , falls n {\displaystyle n} eine ungerade Zahl ist, dann ist 3 n + 1 {\displaystyle 3n+1} gerade und besitzt eine Primfaktorzerlegung der Form

2 a p 1 e 1 ⋯ p s e s = 2 a k {\displaystyle 2^{a}p_{1}^{e_{1}}\cdots p_{s}^{e_{s}}=2^{a}k}

wobei a ∈ N {\displaystyle a\in \mathbb {N} } und k {\displaystyle k} die größte ungerade Zahl ist, welche 3 n + 1 {\displaystyle 3n+1} ohne Rest teilt. Sei 2 N + 1 := { 1 , 3 , 5 , … } {\displaystyle 2\mathbb {N} +1:=\{1,3,5,\dots \}} die Menge der ungeraden Zahlen, dann ist die Syracuse-Funktion Syr : 2 N + 1 → 2 N + 1 {\displaystyle \operatorname {Syr} :2\mathbb {N} +1\to 2\mathbb {N} +1} die Funktion

Syr ⁡ ( n ) := 3 n + 1 2 a = k . {\displaystyle \operatorname {Syr} (n):={\frac {3n+1}{2^{a}}}=k.}

Beispielsweise gilt Syr ⁡ ( 3 ) = 5 {\displaystyle \operatorname {Syr} (3)=5} , Syr ⁡ ( 5 ) = 1 {\displaystyle \operatorname {Syr} (5)=1} und Syr ⁡ ( 7 ) = 11 {\displaystyle \operatorname {Syr} (7)=11} .

Für eine Primzahl p {\displaystyle p} und M ∈ Z {\displaystyle M\in \mathbb {Z} } sei ν p ( M ) {\displaystyle \nu _{p}(M)} die p {\displaystyle p} -Bewertung, das heißt die größte Zahl a {\displaystyle a} , so dass p a ∣ M {\displaystyle p^{a}\mid M} , mit der Konvention ν p ( 0 ) = + ∞ {\displaystyle \nu _{p}(0)=+\infty } . Dann lässt sich Syr ⁡ ( n ) {\displaystyle \operatorname {Syr} (n)} auch wie folgt ausdrücken

Syr ⁡ ( n ) := 3 n + 1 2 ν 2 ( 3 n + 1 ) . {\displaystyle \operatorname {Syr} (n):={\frac {3n+1}{2^{\nu _{2}(3n+1)}}}.}

Analog zur Collatz-Funktion lässt sich nun auch der Syracuse-Orbit Syr N {\displaystyle \operatorname {Syr} ^{\mathbb {N} }} und sein Minimal-Element Syr min N {\displaystyle \operatorname {Syr} _{\text{min}}^{\mathbb {N} }} definieren.

Die Syracuse-Funktion spielt eine zentrale Rolle in Taos Beweis.

2019 bewies Tao den folgenden Satz:^[24]

Sei f : N + 1 → R {\displaystyle f:\mathbb {N} +1\to \mathbb {R} } eine Funktion mit lim N → ∞ f ( N ) = + ∞ {\displaystyle \lim \limits _{N\to \infty }f(N)=+\infty } . Dann gilt Col min N ⁡ ( N ) < f ( N ) {\displaystyle \operatorname {Col} _{\text{min}}^{\mathbb {N} }(N)<f(N)} für fast alle N ∈ N + 1 {\displaystyle N\in \mathbb {N} +1} .

Er benutzte die folgende Notation für die natürlichen Zahlen:

• mit der Null als N := { 0 , 1 , 2 , … } {\displaystyle \mathbb {N} :=\{0,1,2,\dots \}}
• ohne Null als N + 1 := { 1 , 2 , … } {\displaystyle \mathbb {N} +1:=\{1,2,\dots \}}
• an ungerader Stelle 2 N + 1 := { 1 , 3 , 5 , … } {\displaystyle 2\mathbb {N} +1:=\{1,3,5,\dots \}}

Die Bezeichnung fast alle bezeichnet eine Eigenschaft bezüglich der logarithmischen Dichte. Es ist eine schwächere Form als die asymptotische Dichte.

Logarithmische Dichte:

Sei R ⊂ N + 1 {\displaystyle R\subset \mathbb {N} +1} eine nicht leere endliche Teilmenge. Wir definieren die Zufallsvariable L o g ( R ) {\displaystyle \mathbf {Log} (R)} , welche Werte in R {\displaystyle R} annimmt und der logarithmischen Gleichverteilung folgt, das heißt, für alle A ⊂ N + 1 {\displaystyle A\subset \mathbb {N} +1} gilt

P ( L o g ( R ) ∈ A ) = ∑ N ∈ A ∩ R 1 N ∑ N ∈ R 1 N . {\displaystyle \mathbb {P} (\mathbf {Log} (R)\in A)={\frac {\sum _{N\in A\cap R}{\frac {1}{N}}}{\sum _{N\in R}{\frac {1}{N}}}}.}

Die logarithmische Dichte von A ⊂ N {\displaystyle A\subset \mathbb {N} } ist dann definiert als der Grenzwert

lim x → ∞ P ( L o g ( N + 1 ∩ [ 1 , x ] ) ∈ A ) , {\displaystyle \lim \limits _{x\to \infty }\mathbb {P} (\mathbf {Log} (\mathbb {N} +1\cap [1,x])\in A),}

sofern dieser existiert.

Die logarithmische Dichte von A {\displaystyle A} ist somit die Wahrscheinlichkeit, dass sich der Grenzwert der Zufallsvariable L o g ( N + 1 ∩ [ 1 , x ] ) {\displaystyle \mathbf {Log} (\mathbb {N} +1\cap [1,x])} in der Menge A {\displaystyle A} befindet.

Beispiele:

• Sei A := { 2 , 4 , 6 , 8 , 10 … } {\displaystyle A:=\{2,4,6,8,10\dots \}} und R x := N + 1 ∩ [ 1 , x ] {\displaystyle R_{x}:=\mathbb {N} +1\cap [1,x]} . Dann ist

lim x → ∞ P ( L o g ( R x ) ∈ A ) = lim x → ∞ ∑ N ∈ A ∩ R x 1 N ∑ N ∈ R x 1 N = ∑ N ∈ A 1 N ∑ N ∈ N + 1 1 N = 1 2 + 1 4 + 1 6 + 1 8 + 1 10 + ⋯ 1 + 1 2 + 1 3 + 1 4 + 1 5 + ⋯ = 1 2 {\displaystyle \lim \limits _{x\to \infty }\mathbb {P} (\mathbf {Log} (R_{x})\in A)=\lim \limits _{x\to \infty }{\frac {\sum _{N\in A\cap R_{x}}{\frac {1}{N}}}{\sum _{N\in R_{x}}{\frac {1}{N}}}}={\frac {\sum _{N\in A}{\frac {1}{N}}}{\sum _{N\in \mathbb {N} +1}{\frac {1}{N}}}}={\frac {{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{8}}+{\frac {1}{10}}+\cdots }{1+{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{5}}+\cdots }}={\frac {1}{2}}}

Fast alle:

Eine Eigenschaft P ( N ) {\displaystyle P(N)} gilt für fast alle N ∈ N + 1 {\displaystyle N\in \mathbb {N} +1} , falls

lim x → ∞ P ( P ( L o g ( N + 1 ∩ [ 1 , x ] ) ) ) = 1. {\displaystyle \lim \limits _{x\to \infty }\mathbb {P} (P(\mathbf {Log} (\mathbb {N} +1\cap [1,x])))=1.}

In Worten ausgedrückt P ( N ) {\displaystyle P(N)} gilt in einer Teilmenge N ⊂ N + 1 {\displaystyle N\subset \mathbb {N} +1} mit logarithmischer Dichte 1 {\displaystyle 1} .

Der Satz wird für Syr min N ⁡ ( N ) {\displaystyle \operatorname {Syr} _{\text{min}}^{\mathbb {N} }(N)} bewiesen und der Fall für Col min N {\displaystyle \operatorname {Col} _{\text{min}}^{\mathbb {N} }} folgt daraus, denn es gilt^[24]

Col min N ⁡ ( N ) = Syr min N ⁡ ( N / 2 ν 2 ( N ) ) {\displaystyle \operatorname {Col} _{\text{min}}^{\mathbb {N} }(N)=\operatorname {Syr} _{\text{min}}^{\mathbb {N} }(N/2^{\nu _{2}(N)})} .

Wir definieren:

• Für ein a ∈ N + 1 {\displaystyle a\in \mathbb {N} +1} und x ∈ R {\displaystyle x\in \mathbb {R} } die affine Abbildung

Aff a ⁡ ( x ) := 3 x + 1 2 a . {\displaystyle \operatorname {Aff} _{a}(x):={\tfrac {3x+1}{2^{a}}}.}

• Für ein n {\displaystyle n} -Tupel ( a 1 , … , a n ) ∈ ( N + 1 ) n {\displaystyle (a_{1},\dots ,a_{n})\in (\mathbb {N} +1)^{n}} die Komposition

Aff ( a 1 , … , a n ) ⁡ ( x ) := Aff a n ⁡ ( Aff a n − 1 ⁡ ( … ( Aff a 1 ⁡ ( x ) ) … ) ) {\displaystyle \operatorname {Aff} _{(a_{1},\dots ,a_{n})}(x):=\operatorname {Aff} _{a_{n}}(\operatorname {Aff} _{a_{n-1}}(\dots (\operatorname {Aff} _{a_{1}}(x))\dots ))} .

• Die n {\displaystyle n} -Syracuse-Bewertung a → ( n ) ( N ) ∈ ( N + 1 ) n {\displaystyle {\vec {a}}^{(n)}(N)\in (\mathbb {N} +1)^{n}} als

a → ( n ) ( N ) := ( ν 2 ( 3 N + 1 ) , ν 2 ( 3 Syr ⁡ ( N ) + 1 ) , … , ν 2 ( 3 Syr n − 1 ⁡ ( N ) + 1 ) ) . {\displaystyle {\vec {a}}^{(n)}(N):=\left(\nu _{2}(3N+1),\nu _{2}(3\operatorname {Syr} (N)+1),\dots ,\nu _{2}(3\operatorname {Syr} ^{n-1}(N)+1)\right).}

Daraus folgt Syr ⁡ ( N ) = Aff ν 2 ( 3 N + 1 ) ⁡ ( N ) {\displaystyle \operatorname {Syr} (N)=\operatorname {Aff} _{\nu _{2}(3N+1)}(N)} und Syr n ⁡ ( N ) = Aff a → ( n ) ( N ) ⁡ ( N ) {\displaystyle \operatorname {Syr} ^{n}(N)=\operatorname {Aff} _{{\vec {a}}^{(n)}(N)}(N)} .

Weiter definieren wir die geometrische Zufallsvariable Geom ⁡ ( μ ) {\displaystyle \operatorname {Geom} (\mu )} mit Erwartungswert μ > 1 {\displaystyle \mu >1} , so dass für alle a ∈ N + 1 {\displaystyle a\in \mathbb {N} +1} gilt

P ( Geom ⁡ ( μ ) = a ) = 1 μ ( μ − 1 μ ) a − 1 . {\displaystyle \mathbb {P} (\operatorname {Geom} (\mu )=a)={\frac {1}{\mu }}\left({\frac {\mu -1}{\mu }}\right)^{a-1}.}

Für ein zufälliges N ∈ 2 N + 1 {\displaystyle N\in 2\mathbb {N} +1} kann die Anzahl, wie oft 3 N + 1 {\displaystyle 3N+1} durch 2 {\displaystyle 2} geteilt werden kann, als geometrische Zufallsvariable mit Erwartungswert 2 {\displaystyle 2} interpretiert werden:

P ( Geom ⁡ ( 2 ) = a ) = 2 − a . {\displaystyle \mathbb {P} (\operatorname {Geom} (2)=a)=2^{-a}.}

Es lässt sich folgende Heuristik herleiten: Falls N {\displaystyle N} eine spezielle große, ungerade Zahl ist und n ≪ log ⁡ N {\displaystyle n\ll \log N} (bedeutet n {\displaystyle n} ist viel kleiner als log ⁡ N {\displaystyle \log N} ), dann verhält sich a → ( n ) ( N ) {\displaystyle {\vec {a}}^{(n)}(N)} wie die Zufallsvariable Geom ⁡ ( 2 ) n {\displaystyle \operatorname {Geom} (2)^{n}} . Genauer: Definiere die diskrete totale Variation zweier Zufallsvariablen auf einer diskreten Menge R {\displaystyle R} als

d T V ( X , Y ) := ∑ r ∈ R | P ( X = r ) − P ( Y = r ) | . {\displaystyle d_{TV}(X,Y):=\sum \limits _{r\in R}|\mathbb {P} (X=r)-\mathbb {P} (Y=r)|.}

Nun lässt sich eine obere Schranke für die totale Variation von a → ( n ) ( N ) {\displaystyle {\vec {a}}^{(n)}(N)} und Geom ⁡ ( 2 ) n {\displaystyle \operatorname {Geom} (2)^{n}} finden:

d T V ( a → ( n ) ( N ) , Geom ⁡ ( 2 ) n ) ≪ 2 − c 1 n , {\displaystyle d_{TV}\left({\vec {a}}^{(n)}(N),\operatorname {Geom} (2)^{n}\right)\ll 2^{-c_{1}n},}

wobei c 1 > 0 {\displaystyle c_{1}>0} eine Konstante bezeichnet. Da man nun sehr viel über die Verteilung von a → ( n ) ( N ) {\displaystyle {\vec {a}}^{(n)}(N)} weiß, lassen sich endliche Stoppzeiten für Syr N {\displaystyle \operatorname {Syr} ^{\mathbb {N} }} herleiten.

Im Dualsystem kann besonders einfach zwischen einer geraden und einer ungeraden natürlichen Zahl unterschieden werden, weil gerade Zahlen in diesem System ganz rechts immer mit einer Null und ungerade Zahlen ganz rechts immer mit einer 1 enden. Auch die Multiplikation einer natürlichen Zahl mit der Zahl 2 ist im Dualsystem sehr einfach durchzuführen. Es muss nur rechts eine Null an die Binärzahl hinzugefügt werden. Bei einer Division durch 2 muss entsprechend rechts eine Null entfernt werden.

Die Collatz-Funktion kann im Dualsystem als eine abstrakte Maschine verstanden werden, die eine Zeichenkette von Bits auf eine neue Zeichenkette von Bits abbildet. Diese Maschine entfernt zuerst alle Nullen am Ende der Zeichenkette. Dies entspricht den benötigten Divisionen durch die Zahl 2 bis eine ungerade Zahl vorliegt. Die Verarbeitung einer beliebigen ungeraden Zahl n {\displaystyle n} geschieht dann über die folgenden drei Regeln:

1. Füge rechts an die Binärzahl eine Eins an. Das ergibt 2n + 1.
2. Addiere die Zahl aus dem ersten Schritt zur ursprünglichen Zahl. Das ergibt dann n + 2n + 1 = 3n + 1.
3. Entferne alle Nullen am rechten Rand der neuen Zahl. Das entspricht so vielen Divisionen durch 2, bis das Resultat wieder eine ungerade Zahl ist.

Über die genannten Regeln kann somit ein gesamter Orbit im Dualsystem dargestellt werden.

Obwohl die schrittweise Verarbeitung der Zahlen im Dualsystem durch sehr einfache Regeln realisiert wird, wurde bisher auch in dieser Darstellung kein Beweis der Collatz-Vermutung gefunden.

Man startet mit der dezimalen 7 (binär 111). Der resultierende Collatz-Orbit lautet dann:

         111
        1111
       10110
      10111
     100010
    100011
    110100
   11011
  101000
 1011
10000

Für das auf alle ganzen Zahlen als Startwerte ausgeweitete Collatz-Problem gibt es außer dem (1,4,2)-Zyklus noch 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).

Die drei letzten Zyklen mit positiven statt negativen Vorzeichen entstehen auch mit der Definition C ( n ) = 3 n − 1 {\displaystyle C(n)=3n-1} statt C ( n ) = 3 n + 1 {\displaystyle C(n)=3n+1} für ungerade n {\displaystyle n} . Alle Startwerte n {\displaystyle n} mit | n | < 10 8 {\displaystyle |n|<10^{8}} enden in einem der bekannten Zyklen.^[33]

Marc Chamberland definierte eine stetige Funktion, welche die diskrete Collatz-Folge auf den Bereich der reellen Zahlen erweitert.^[34] Simon Letherman, Dierk Schleicher und Reg Wood betrachteten Funktionen im Bereich der komplexen Zahlen als Erweiterung.^[35] Allgemeine Vermutung: C ( n ) = 3 n + 3 x {\displaystyle C(n)=3n+3^{x}} für ungerade n {\displaystyle n} endet immer in ( 4 ⋅ 3 x , 2 ⋅ 3 x , 1 ⋅ 3 x ) {\displaystyle (4\cdot 3^{x},2\cdot 3^{x},1\cdot 3^{x})} und besitzt nur diesen einen Zyklus.

Betrachtet man das analoge (5n+1)-Problem, so liefern stochastische Modelle ein ganz anderes Verhalten: Fast alle Iterierten sollten divergieren, was durch Computersimulation bestätigt wird. Es ist aber ein offenes Problem zu beweisen, dass auch nur ein Orbit des (5n+1)-Problems tatsächlich divergiert.^[36]

John Conway betrachtete 1972^[14] verallgemeinerte (3n+1)-Folgen und zeigte, dass sie universale Turingmaschinen simulieren können (von ihm in der Programmiersprache FRACTRAN verallgemeinert). Außerdem zeigte er, dass ein bestimmtes Entscheidungsproblem unlösbar ist, das danach fragt, ob ein Eingangswert für die Iteration, der eine Potenz von 2 ist, zu einem iterierten Wert führt, der ebenfalls eine Potenz von 2 ist (das Collatz-Problem lässt sich auch so formulieren, dass für beliebige natürliche Zahlen als Input die Iterierte schließlich auf eine Potenz von 2 führt).

In ihrer 2020 veröffentlichten Arbeit analysierten Sultanow, Koch und Cox das Collatz-Problem aus graphentheoretischer Sicht.^[37] Sie betrachteten Zyklen für 3 n + 1 {\displaystyle 3n+1} und die verallgemeinerte Form k n + 1 {\displaystyle kn+1} , wobei k ∈ N > 0 {\displaystyle k\in \mathbb {N} _{>0}} . Das Dokument beinhaltet eine Liste bekannter Zyklen und leitet daraus Bedingungen für deren Auftreten in Collatz-Sequenzen ab.

• Jeffrey C. Lagarias: The 3x+1 problem and its generalizations, The American Mathematical Monthly 92, Januar 1985, S. 3–23 (englisch; 1986 mit dem Lester-R.-Ford-Preis ausgezeichnet; bei MathDL; beim CECM; Zentralblatt-Rezension)
• Günther J. Wirsching: The dynamical system generated by the 3n+1 function, Springer-Verlag, Berlin 1998, ISBN 3-540-63970-5 (englisch; revidierte Version der Habilitationsschrift von 1996; Zentralblatt-Rezension)
• Richard K. Guy: E16. The 3x+1 problem und E17. Permutation sequences in Unsolved problems in number theory (3. Auflage), Springer-Verlag, New York 2004, ISBN 0-387-20860-7, S. 330–336 und S. 336–337 (englisch; Zentralblatt-Rezension)
• Jeffrey C. Lagarias: The 3x+1 problem: An annotated bibliography (1963–1999) (sorted by author), arxiv:math/0309224 [math.NT], 2003–2011 (englisch)
• Jeffrey C. Lagarias: The 3x+1 problem: An annotated bibliography, II (2000–2009), arxiv:math/0608208 [math.NT], 2006–2012 (englisch)
• Jeffrey C. Lagarias (Hrsg.): The ultimate challenge: The 3x+1 problem, American Mathematical Society, Providence RI 2010, ISBN 978-0-8218-4940-8 (englisch; Zentralblatt-Rezension)
• Jeffrey C. Lagarias: The 3x+1 problem: An overview (PDF, 518 kB, Buchvorschau), S. 1–27 (englisch)

Wikibooks: Collatzfolgen und Schachbrett – Lern- und Lehrmaterialien

Commons: Collatz-Problem – Sammlung von Bildern, Videos und Audiodateien

• Eric W. Weisstein: Collatz Problem. In: MathWorld (englisch).
• On the 3x + 1 problem von Eric Roosendaal, ein Distributed-computing-Projekt, das sich mit dem Collatz-Problem beschäftigt (englisch)
• Das Collatz-Problem von Jürgen Dankert – Interaktives Skript zum (3n+1)- und (3n−1)-Problem zum Erzeugen von Folgen mit beliebig großen Startzahlen
• Terence Tao: The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3, 25. August 2011
• Paul J. Andaloro: The 3x+1 problem and directed graphs (PDF; 3,8 MB), Fibonacci Quarterly 40, 2002 (englisch), Archivlink abgerufen am 11. Januar 2025
• The Simplest Math Problem No One Can Solve – Veritasium auf YouTube (englisch)