Collatz-Problem

Das Collatz-Problem, auch als $(3n+1)$-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz definiert wurde.

Problemstellung

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

• Beginne mit irgendeiner natürlichen Zahl $n>0$.
• Ist $n$ gerade, so nimm als nächstes $n/2$,
• ist $n$ ungerade, so nimm als nächstes $3n+1$.

So erhält man z. B. für die Startzahl $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, ...

Anscheinend mündet jede Folge in den Zyklus 4, 2, 1 – egal welche Startzahl man probiert hat. Die Collatz-Vermutung lautet:

Jede so konstruierte Zahlenfolge endet im Zyklus 4, 2, 1, egal, mit welcher natürlichen Zahl man beginnt.

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 $ für einen Beweis der Vermutung und 100 $ für ein Gegenbeispiel.
• Bryan Thwaites hat 1996 1000 englische Pfund versprochen.
• Paul Erdős bot 500 Pfund für eine Lösung, sagte aber über das Collatz-Problem:

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

Ursprung und Geschichte

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.

Publizierte Quellen

• 1974: Ein Informatik-Lehrbuch enthält die erste schriftliche Publikation des Collatz-Problems.
• 1976: Riho Terras ist der Autor der ersten wissenschaftlichen Publikation mit Forschungsergebnissen zum Collatz-Problem.
• 1985: In der Zeitschrift American Mathematical Monthly erscheint ein Überblicksartikel von Jeffrey Lagarias. 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 ganzzahlige Funktion betrachtet:

$g(n):={\begin{cases}{\tfrac {2}{3}}n&{\mbox{wenn}}\quad n\equiv 0\mod 3,\\{\tfrac {4}{3}}n-{\tfrac {1}{3}}&{\mbox{wenn}}\quad n\equiv 1\mod 3,\\{\tfrac {4}{3}}n+{\tfrac {1}{3}}&{\mbox{wenn}}\quad n\equiv 2\mod 3.\end{cases}}$

Diese Funktion besitzt den Fixpunkt 1 und unter Iteration die Zykel (2,3) und (4,5,7,9,6). 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.

• 1985: Bryan Thwaites publiziert die Behauptung, er habe es am 21. Juli 1952 um vier Uhr nachmittags gefunden.
• 1986: Lothar Collatz lässt eine Darstellung seines Entdeckungswegs zur (3n+1)-Vermutung ins Chinesische übersetzen und im Journal einer Universität in China veröffentlichen.

Der Collatz-Graph einer Funktion

Orbits der ersten 30 natürlichen Zahlen (ohne 27) unter der Collatz-Funktion. Alle Orbits enden bei Eins.

Collatz’ Beschreibung seiner Motivation der (3n+1)-Vermutung ist sehr plausibel: 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:\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 einer gerichteten Kante von n nach f(n).

Die einfachste solche Funktion ist die Nachfolgerabbildung

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

deren Collatz-Graph aus einem unendlich langen Weg besteht:

$1\to 2\to 3\to 4\to 5\to \ldots .$

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$ muss auf gewissen natürlichen Zahlen n „aufsteigen“, also die Relation $n<f(n)$ erfüllen, und auf anderen natürlichen Zahlen m „absteigen“, also die Relation $m>f(m)$ erfüllen. So stieß er zunächst auf die Funktion

$f_{1}(n):={\begin{cases}n/2&{\mbox{wenn }}n{\mbox{ gerade ist,}}\\n+1\quad &{\mbox{wenn }}n{\mbox{ ungerade ist.}}\end{cases}}$

Den Collatz-Graph dieser Funktion kann man wie folgt beschreiben: Jeder Knoten k ist, nach Definition, eine natürliche Zahl. Falls k>1, besitzt k die beiden Vorgängerknoten k-1 und 2k, und der Knoten k=1 besitzt nur den Knoten 2 als Vorgänger. Außerdem gilt

$f_{1}^{2}(n)=f_{1}(f_{1}(n)):={\begin{cases}{\frac {n}{4}}&{\mbox{wenn }}n{\mbox{ durch 4 teilbar ist,}}\\{\frac {n}{2}}+1&{\mbox{wenn }}n{\mbox{ durch 2 aber nicht durch 4 teilbar ist,}}\\{\frac {n+1}{2}}\quad &{\mbox{wenn }}n{\mbox{ ungerade ist.}}\end{cases}}$

Daraus folgt

$f_{1}^{2}(n)<n\qquad {\mbox{ wenn }}n>2,$

und das hat zur Folge, dass der Collatz-Graph von $f_{1}$ nur den Kreis (1,2) besitzt, und dass die $f_{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

$f_{2}(n):={\begin{cases}n/2&{\mbox{wenn }}n{\mbox{ gerade ist,}}\\2n+1\quad &{\mbox{wenn }}n{\mbox{ ungerade ist,}}\end{cases}}$

enthält keinen Kreis, da jede ungerade Zahl auf eine größere ungerade Zahl abgebildet wird, und die $f_{2}$-Trajektorien daher alle gegen Unendlich divergieren.

Der nächste Versuch ist die Collatz-Funktion

$f:\mathbb {N} \to \mathbb {N} ,\quad f(n)={\begin{cases}n/2&{\mbox{wenn }}n{\mbox{ gerade ist,}}\\3n+1&{\mbox{wenn }}n{\mbox{ ungerade ist.}}\end{cases}}$

Zu dieser Funktion fand Collatz nur den „trivialen Kreis“ (1,4,2) – er schreibt, er habe seine Ideen deshalb nicht veröffentlicht, weil er nicht beweisen konnte, dass der „triviale Kreis“ der einzige sei.

Verbreitung des Collatz-Problems

Als Lothar Collatz 1952 seine Professur in Hamburg antrat, erzählte er seinem Hamburger Kollegen Helmut Hasse von diesem Problem. Dieser verbreitete das Problem während eines Forschungsaufenthalts an der Syracuse University, deshalb erhielt das Collatz-Problem auch den Namen Syracuse-Vermutung. Stanisław Marcin Ulam (Los Alamos) und Shizuo Kakutani (Yale) haben das Problem immer wieder in Gesprächen gestellt und werden deshalb in diesem Zusammenhang häufig genannt.

Nach Riho 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:

• Douglas R. Hofstadter nannte in seinem Buch Gödel, Escher, Bach diejenigen Startzahlen, deren Collatz-Trajektorie im Zykel (1,4,2) endet, wondrous numbers (wundersame Zahlen).
• Nach Clifford A. Pickover werden sie auch hailstone numbers (Hagelschlag-Zahlen) genannt.

Prinzipielles

Prinzipiell kann eine $f$-Trajektorie als Zahlenfolge eine der drei folgenden Eigenschaften haben:

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

Computer haben alle Zahlen bis $3\cdot 2^{61}$ (Stand 2008) durchprobiert; immer endet die Zahlenfolge mit 1, widerlegt also die Vermutung nicht.

Falls eine Folge in einen anderen Zyklus geraten könnte, müsste dieser aus mindestens 275.000 Zahlen bestehen, wie 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

Für das von den natürlichen Zahlen (positive) auf die ganzen Zahlen (Null und negative) ausgeweitete Collatz-Problem, wurden außer dem 1–4–2–1-Zyklus noch vier weitere Zyklen gefunden:

• 0, 0
• −1, −2, −1
• −5, −14, −7, −20, −10, −5 und
• −17, −50, −25, −74, −37, −110, −55, −164, −82, −41, −122, −61, −182, −91, −272, −136, −68, −34, −17.

Verallgemeinerungen des Problems

Audrey Terras gewinnt Teilerkenntnisse über Zyklen, indem sie als Anfangswert auch negative Zahlen zulässt (1976, 1979). Marc Chamberland definierte 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. Allgemeine Vermutung: $(3n+3^{x})$ endet immer in $4\cdot 3^{x},\;2\cdot 3^{x},\;1\cdot 3^{x},$ und besitzt nur diesen einen Zyklus.

Graphentheorie

Man untersucht den so genannten Collatz-Baum oder Collatz-Graphen. Dies ist ein Baum, dessen Knotenmenge die Menge der natürlichen Zahlen ist; der Knoten 1 ist die Wurzel des Baums. Jeder Knoten hat 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 ${\tfrac {2}{2}}=1$), 16 hat die Vorgänger 32 und 5 (denn $3\cdot 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 ${\tfrac {(n-1)}{3}}.$

Mit diesem Graphen beschäftigen sich unter anderem Paul J. Andaloro, Stefan Andrei, Manfred Kudlek und Raud Stefan Niculescu. Sie gewinnen unendliche Teilmengen der natürlichen Zahlen, für welche die Collatz-Folge bei 1 endet.

$(3n-1)$-Problem

Interessant ist, dass bei dem vergleichbaren $(3n-1)$-Problem je nach Startzahl $n\geq 1$ die Folge in einem der drei folgenden Zyklen endet:

• 2, 1
• 5, 14, 7, 20, 10
• 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34

Dies ist mit dem $3n+1$ Problem mit negativen Startzahlen vergleichbar (siehe oben).

Literatur

• Günther J. Wirsching: The Dynamical System Generated by the 3n+1 Function. Springer-Verlag, Berlin Heidelberg New York 1998, ISBN 3-540-63970-5. 

Weblinks

Wikibooks: Collatzfolgen und Schachbrett – Lern- und Lehrmaterialien

• On The 3x+1 Problem and its generalizations Ein Übersichtsartikel zum Collatz-Problem von Jeff Lagarias (englisch)
• On The 3x+1 Problem, ein Distributed-computing-Projekt, das sich mit dem Collatz-Problem beschäftigt (englisch)
• Collatz Conjecture, ein auf BOINC basierendes Projekt, das sich mit der Suche nach Gegenbeispielen beschäftigt
• Interaktives Skript zum (3n+1)- und (3n-1)-Problem ... zum Erzeugen von Folgen mit beliebig großen Startzahlen