Vor mehr als 50 Jahren gab der Student Lothar Collatz der Universität Hamburg die Beschreibung der Zahlenfolge 3a+1 an, die heute immer noch ungelöste Rätsel aufgibt.
Das Glied a1 ist eine beliebige natürliche Zahl. Die folgenden Glieder der Zahlenfolge werden definiert mit
| an+1 = an / 2 , falls an gerade an+1 = 3·an + 1 , falls an ungerade |
Beginnt man die Folge mit 3, ergibt sich damit (3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1 …) usw.
Wählt man ein beliebiges anderes Glied, so endet die Folge erneut periodisch auf 4, 2, 1. Verblüffend ist, dass dies bisher bei allen Testzahlen erfolgte; der Japaner Yoneda überprüfte alle Zahlen bis 1,2 Billionen. Ein Beweis der Periodizität gelang aber bisher nicht.
1996 wurde von Thwaites ein Preis von £ 1000 für die Lösung ausgesetzt. Der ungarische Mathematiker Erdos kommentiert das Problem mit:
„Die Mathematik ist noch nicht reif für solche Probleme.“
Wählen Sie dieses Unterprogramm, berechnet Ihnen das Programm für jede eingegebene natürliche Zahl die entstehende Zahlenfolge. Interessant ist z.B. die Zahlenfolge für den vordefinierten Ausgangswert von 31911. Erst nach 160 Iterationen wird die 1 erreicht.
Markieren Sie den Punkt verkürzte Folge, so werden die durch 3·an + 1 entstehenden geraden Glieder sofort durch 2 geteilt, d.h.
| an+1 = an / 2 , falls an gerade ist an+1 = (3 · an + 1) / 2 , falls an ungerade ist |
Damit wird die Folge bis zum Erreichen der 1 kürzer.
Collatz-2-Folge
Durch Roupam Ghosh wurde 2007 in „On the Collatz-Problem“ eine modifizierte Collatz-Folge definiert.
Erneut werden für eine Startzahl a1 die Glieder der ursprünglichen Zahlenfolge berechnet. Allerdings wird die Berechnung sofort abgebrochen, wenn eine Zahl auftritt, die in irgendeiner Collatz-Folge kleinerer Zahlen schon vorhanden war. Damit ergibt sich
| a1 | Folge |
| 1 | 1 |
| 2 | 2 (da die 1 schon auftrat) |
| 3 | 3, 10, 5, 16, 8, 4 (da die 2 schon auftrat) |
| 4 | – (da die 4 schon auftrat) |
| 5 | – (da die 5 schon auftrat …) |
| 7 | 7, 22, 11, 34, 17, 52, 26, 13, 40, 20 … |
| 9 | 9, 28, 14 (7) |
| 15 | 15, 46, 23, 70, 35, 106, 53, 160, 80 (40) |
Dabei wies Ghosh nach, dass es keinen Algorithmus für ungerade Startzahlen gibt, der entscheidet, wann eine Berechnung abgebrochen werden kann, ohne dass man die vorhergehenden Berechnungen durchgeführt hat. Die Fragestellung gehört wahrscheinlich zu den NP-Problemen.
Für gerade Startzahlen a1 ist das Problem trivial, da die zweite Zahl bei a1/2 schon vorhanden war.
In Lexikon von „Mathematik alpha“ kann diese Zahlenfolge berechnet werden.