Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

Das Collatz-Problem gehört zu den ungelösten Problemen der Mathematik. Es wird gelegentlich auch 3n+1-Problem, Syracuse-Vermutung (...), Kakutanis Problem (nach Shizuo Kakutani), Hasse-Algorithmus (nach Helmut Hasse), Thwaites-Vermutung (nach Bryan Thwaites) oder Ulams-Problem (nach Stanislaw Marcin Ulam) genannt. Allgemein gesagt, geht es darum, ob ein bestimmter rekursiver Algorithmus bei jeder Ausgangszahl gleich endet oder nicht.

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. Bryan Thwaites hat 1996 1000 englische Pfund versprochen. Paul Erdős sagte über das Collatz-Problem: „Mathematics is not yet ready for such problems.“ (Die Mathematik ist noch nicht bereit für solche Probleme.) Er bot 500 Pfund für eine Lösung.

Inhaltsverzeichnis 1 Die Problemstellung 2 Lösungsansätze 2.1 Collatz-Problem in den ganzen Zahlen 2.2 Verallgemeinerungen des Problems 2.3 Graphentheorie 3 Ergänzende Bemerkungen 3.1 Dualzahlen und Collatzfolgen 3.2 Dreiersystem und Collatzfolgen 3.3 Janus-Zahlen und Collatz-Folgen 4 Weblinks

Die Problemstellung

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

Parser-Fehler (die PNG-Konvertierung schlug fehl): {a_{n+1}} = T(n) = \left\{ \begin{matrix} \frac{1}{2}a_n & \mbox{für } a_n \mbox{ gerade}\\ 3a_n + 1 & \mbox{für } a_n \mbox{ ungerade} \end{matrix} \right.

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:

Parser-Fehler (die PNG-Konvertierung schlug fehl): {a_{n+1}} = T(n) = \left\{ \begin{matrix} \frac{1}{2}a_n & \mbox{für } a_n \mbox{ gerade}\\ \frac{3a_n + 1}{2} & \mbox{für } a_n \mbox{ ungerade} \end{matrix} \right.

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

Man hat mit unterschiedlichen Methoden versucht, das Problem zu lösen. Eine davon ist die systematische Suche nach Gegenbeispielen mit Computerunterstützung.

Collatz-Problem in den ganzen Zahlen

Wenn man das Collatz-Problem von den natürlichen Zahlen (positive) auf die ganzen Zahlen (0 und negative) ausweitet, bekommt man außer dem 1-4-2-1 Zyklus noch vier weitere Zyklen:

0,0

-1,-2,-1

-5,-14,-7,-20,-10,-5 und

-68,-34,-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68.

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). Jede Zahl n hat den Vorgänger 2n, und nur die Zahlen n kongruent 4 modulo 6 haben noch einen zweiten Vorgänger, nämlich (n-1)/3.

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 (n-1)/3 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.

Ergänzende Bemerkungen

Dualzahlen und Collatzfolgen

• Definition: Der Schritt x' = 3*x+1 soll M-Schritt („Multiplikation“) heißen.
• Definition: Der Schritt x' = x/2 soll D-Schritt („Division“) heißen.

Stellt man eine ungerade Zahl z als Dualzahl (z.B. z = 21 = 1*16 + 0*8 + 1*4 + 0*2 + 1 = I0I0I ) dar, so kann man an der Anzahl der endständigen „0I“-Gruppen erkennen, wie oft man mindestens nach dem nächsten M-Schritt durch „4“ teilen kann. In diesem Fall kann man also zweimal, d.h. mindestens durch „16“, teilen.

Dreiersystem und Collatzfolgen

Stellt man eine ungerade Zahl z im Dreiersystem (z.B. z = 21 = 2*9 + 1*3 + 0*1 = 210D ) dar, so bedeutet eine Multipliktion mit „3“ das Anhängen einer „0“. Eine Zahl ist dann durch „2“ teilbar, wenn die Quersumme (dezimal berechnet) in der Dreiersystem-Darstellung gerade ist.

Janus-Zahlen und Collatz-Folgen

(Janus: Römischer Gott mit zwei Gesichtern / Eigene Namensgebung)

Man kann Zahlen nicht nur in Stellenwertsystemen darstellen, sondern auch in anderen Schreibweisen (z.B. röm. Zahlen).

     Definition: Eine Janus-Zahl ist ein Produkt aus einer Zweier- und einer Dreier-Potenz,    
                       j= 2z * 3d mit z>=0 und d>=0.

Für das Collatz-Problem und die Darstellung der Zahlen in einer Folge bietet sich auch folgende Darstellung mit einer Summe von Janus-Zahlen an:

                       z = 21 = 2*9 + 1*3 = 16*1 + 4*1 + 1.

Wie man sieht, ist die Darstellung nicht eindeutig. Ein M-Schritt erhöht in jedem Summanden den Exponenten der Dreierpotenz um 1 und fügt der Summe eine „1“ als neuen Summanden hinzu.

                   M-Schritt:  z' = 3*z + 1 = 2*27 + 1*9 + 1.

Ein D-Schritt verringert in jedem Summanden den Exponenten der Zweierpotenz um 1. Entsteht in einem Summanden eine reine Dreierpotenz, so verhält sich die Folge anscheinend chaotisch. Durch schrittweise Auflösung der reinen Dreierpotenzen und eine Verringerung der Zahl der Summanden lässt sich dann etwas mehr Licht in das Chaos bringen.

Weblinks

• On The 3x+1 Problem, ein Distributed computing Projekt das sich mit dem Collatz-Problem beschäftigt (englisch)

• Dieser Link soll zu einer Art Beweis des Problems führen (englisch). [1]

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Collatz-Problem, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.