Das Collatz-Problem gehört zu den ungelösten Problemen der Mathematik. Es wird gelegentlich auch 3n+1-Problem, Syracuse-Vermutung, Kakutanis Problem, Hasse-Algorithmus, Thwaites Vermutung oder Ulams Problem (nach Stanislaw Marcin Ulam) genannt.

Das Problem lautet:

Man beginne mit einer beliebigen natürlichen Zahl a₀ und bilde damit die rekursive Zahlenfolge

Die Folge endet, wenn sie den Wert 1 erreicht.

Alternativ reicht es auch, dass die Folge einen Wert der Form 2ⁿ erreicht, da alle Zahlen der Form 2ⁿ bei 1 enden.

Vermutung: Für jede natürliche Zahl a₀ erreicht die Folge nach endlich vielen Schritten den Wert 1.

Diese Vermutung konnte bisher weder bewiesen noch widerlegt werden.

Beispiel: Sei a₀ = 5. Dann erhält man die Folge 5,16,8,4,2,1. Für a₀ = 7 lautet die Folge 7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1.

Da auf jede ungerade Zahl n = 2k+1 eine gerade Zahl folgt ( 3n+1 = 3*(2k+1) +1 = 6k + 4 ist gerade) betrachtet man oft auch das äquivalente Problem:

Das Problem wurde 1937 von Lothar Collatz veröffentlicht. Seitdem haben sich viele Mathematiker mit dem Problem beschäftigt. Mehrfach wurden Preise für eine Lösung ausgelobt. 1970 bot H.S.M. Coxeter 50$ für einen Beweis der Vermutung und 100$ für ein Gegenbeispiel. B. Thwaites hat 1996 1000 englische Pfund versprochen.

Prinzipiell kann die Zahlenfolge eine der 3 folgenden Eigenschaften haben:

• die Folge endet bei 1.
• die Folge wächst über alle Grenzen.
• die Folge gerät in einen Zyklus.

Computer haben alle Zahlen bis 3 * 2⁵³ (Stand 1999) durchprobiert; immer endet die Zahlenfolge mit 1, bestätigt also die Vermutung.

Falls die Folge in einen Zyklus gerät, dann besteht dieser aus mindestens 275.000 Zahlen, wie J.C. Lagarias 1985 zeigte.

Lösungsansätze

Das Problem kann als gelöst betrachtet werden. Die Collatz-Vermutung kann nicht bewiesen werden. Es wären unendlich viele Schritte notwendig, wie von Feinstein gezeigt:

" The Collatz 3n+1 Conjecture is Unprovable Subject: General Mathematics, 11B37, 37A45, 39B12, 11Y35, 11M06 Authors: Feinstein, Craig Alan; ... "

Die Zusammenhänge für die nicht Beweisbarkeit werden von Doron Shadmi ebenfalls aufgezeigt:

"A proof that 3n+1 cannot be proved within ZF"

"An axiom of some mathematical system cannot be proved within its own system, therefore Collatz sequences are true but cannot be proved within ZF axiomatic system (and this result is equivalent to Godel's incompleteness theorem)."

"As each transfer is at least n to n+1 we can conclude that Collatz sequences iterations are equivalent to the ZF axiom of infinity iterations."

"General: any iteration that is based on root or exponent value 2, is equivalent to the ZF axiom of infinity iteration." Doron Shadmi

Man hat mit unterschiedlichen Methoden versucht, das Problem zu lösen.

Collatz-Problem in den ganzen Zahlen

Wenn man das Collatz-Problem von den natürlichen Zahlen auf die ganzen Zahlen ausweitet, dann bekommt man außer dem 1-4-2-1 Zyklus noch die drei Zyklen 0-0; (-1)-(-2)-(-1) und (-5)-(-14)-(-7)-(-20)-(-10)-(-5)

Verallgemeinerungen des Problems

R.Terras gewinnt Teilerkenntnisse über Zyklen, indem er als Anfangswert auch negative Zahlen zulässt (1976,1979).
Marc Chamberland und Grinnell College definieren eine stetige Funktion, welche die diskrete Collatz-Folge auf den Bereich der reellen Zahlen erweitert.
Simon Letherman, Dierk Schleicher und Reg Wood betrachten Funktionen im Bereich der komplexen Zahlen als Erweiterung.

Graphentheorie

Man untersucht den so genannten Collatz-Baum oder Collatz-Graphen. Dies ist ein Graph, dessen Wurzelknoten mit 1 beginnt. Zu jedem Knoten gibt es einen oder zwei Vorgänger, nämlich die Zahlen, von denen aus durch Anwendung der Iterationsvorschrift der Knoten erreicht wird. 1 hat den Vorgänger 2 (denn 2/2 = 1), 16 hat die Vorgänger 32 und 5 (denn 3*5+1 = 16).
Mit diesem Graphen beschäftigen sich u.a. Paul J. Andaloro, Stefan Andrei, Manfred Kudlek, Raud Stefan Niculescu. Sie gewinnen unendliche Teilmengen der natürlichen Zahlen, für welche die Collatz-Folge bei 1 endet.

Alle durch 3 teilbaren Zahlen n haben keine anderen Vorgänger als diejenigen der Form 2n, da ein Vorgänger der Form 3n+1 zu einer Zahl führen würde, die nicht durch 3 teilbar ist, was zu einem Widerspruch führt. So sind die Graphen:

2n*3-... ...-192-96-48-24-12-6-3

sowie alle anderen Graphen die aus Gliedern der Form aⁿ*3 bestehen, unverzweigt.