Collatz-Problem

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 (Stanislaw Marcin Ulam) genannt.

Das Problem lautet:

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

${a_{n+1}}=T(n)=\left\{{\begin{matrix}{\frac {1}{2}}a_{n}&{\mbox{für }}a_{n}gerade\\3a_{n}+1&{\mbox{für }}a_{n}ungerade\end{matrix}}\right.$

Die Folge endet, wenn sie den Wert 1 erreicht.

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:

${a_{n+1}}=T(n)=\left\{{\begin{matrix}{\frac {1}{2}}a_{n}&{\mbox{für }}a_{n}gerade\\{\frac {3a_{n}+1}{2}}&{\mbox{für }}a_{n}ungerade\end{matrix}}\right.$

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.

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

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 sogenannten 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.