Die Collatz-Vermutung, auch Collatz-Problem und (3n+1)-Vermutung genannt, ist ein mathematisches Spiel und bis heute (2017) ungelöstes Rätsel. Das Spiel handelt von Folgen ganzer Zahlen die man mit einer einfachen Regel erzeugen kann:
- Beginne mit irgendeiner natürlichen Zahl n>0.
- Ist n gerade, dann nimm als nächstes n2.
- Ist n ungerade, dann nimm als nächstes 3n+1.
Das kann man gut für verschiedene Startwerte n ausprobieren, aber warum nicht einen Tag damit verbringen einem Computer etwas beizubringen was man in ein paar Minuten per Hand machen kann (Douglas Adams)?
Wer ein paar Beispiele durchspielt wird feststellen, daß es lange und kurze Folgen gibt. Mal geht es nur bergab und die Zahlen werden immer kleiner (1024), manchmal geht es auf und ab (19, 27), und manchmal entstehen fantastisch lange Folgen (837799).
Hinweis: Die Berechnung der Folge endet hier bei der 1, obwohl die Regel eigentlich kein Abbruchkriterium enthält. Es ist offensichtlich, daß dort bei der 1 ein Zyklus 1→
Gibt es hier ein System?
Das weiß niemand so genau. Lothar Collatz wird die Vermutung zugeschrieben, daß alle Zahlen auf ihrer Reise durch die Collatz-Folge irgendwann bei der 1 bzw. im (einzigen) Zyklus ankommen, aber es gibt bis heute keinen Beweis dafür. Computer haben die Vermutung bis mindestens 2.361.183.346.958.000.000.001 geprüft und kein Gegenbeispiel gefunden, aber die Suche dauert an.
Im folgenden Experiment wird statt für eine einzelne Zahl die Collatz-Folge aufzustellen gleich für einen ganzen Bereich gerechnet. Wer die Beispiele oben aufmerksam betrachtet hat stellt fest, daß die Folgen einen Baum bilden: Von oben her gesehen wachsen sie zusammen und erreichen schließlich - falls Collatz recht hat - alle gemeinsam die Wurzel bei 1.
Weitere Detail zum Collatz-Problem hat Wikipedia.