Einführung
Eine gute Zusammenfassung zum Collatz-Problem liefert die Wikipedia, aus der folgende Einführung stammt:
Das Collatz-Problem, auch als (3n+1)-Vermutung bezeichnet, ist ein ungelöstes mathematisches Problem, das 1937 von Lothar Collatz gestellt wurde.
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 `3 n + 1` .
- Wiederhole die Vorgehensweise mit der erhaltenen Zahl.
Für eine mit einer beliebigen natürlichen Zahl gestartete Zahlenfolge sind drei einander ausschließende Fälle denkbar:
- Fall 1: die Folge endet im (1,4,2)-Zyklus (sie kann dann bei erreichen von 1 abgebrochen werden),
- Fall 2: die Folge wächst über alle Grenzen,
- Fall 3: die Folge gerät in einen anderen Zyklus.
Die entstehende Zahlenfolge kann man im Collatz-Graphen darstellen (Beispiel siehe Wikipedia).
Die Collatz-Vermutung lautet:
Jede so konstruierte Zahlenfolge mündet in den Zyklus 4, 2, 1, egal, mit welcher natürlichen Zahl n > 0 man beginnt.
Da `3n + 1` für ungerade `n` stets gerade ist und somit die folgende Iteration immer die Division durch 2, wird statt der Collatz-Funktion `bb "C"` oft die etwas einfacher zu handhabende `bb "T"`-Funktion verwendet, die für ungerade `n` zwei `bb "C"`-Iterationen auf einmal macht und den der Vermutung zufolge stets erreichten Zyklus von (1,4,2) auf (1,2) reduziert:
Laut Eric Roosendaal wurde die Collatz-Vermutung mittels Durchprobierens für alle positiven ganzen Zahlen bis `2^68` (ca. 2,95×1020) als Startwerte bestätigt (Stand Juli 2020).
Lemma 1
Wenn die Collatz-Vermutung für alle ungeraden Zahlen richtig ist, ist sie es automatisch auch für alle geraden Zahlen.
Die Begründung ist trivial, denn zu Beginn der `bb "C"`-Folge wird jede Zahl so lange halbiert, bis sie ungerade ist.
Die Shift-Funktion `bb "S"` macht genau dies:
Es genügt also, die Richtigkeit der Collatz-Vermutung für alle ungeraden Zahlen zu beweisen. Wir rechnen daher mit Folgen, die nur ungerade Zahlen aufweisen.
Dafür verwenden wird die `bb "H"`-Funktion:
Hinweis: Falls man auch mit geraden Zahlen rechnen möchte, ist vor Beginn der Iteration mittels `bb "H"`-Funktion die Shift-Funktion anzuwenden.
`bb "C"`(19): 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
`bb "T"`(19): 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1
`bb "H"`(19): 19, 29, 11, 17, 13, 5, 1
Pfadlänge
Pfadlänge der `bb "C"`-Funktion: `bb "P"_C`(19) = 20
Pfadlänge der `bb "T"`-Funktion: `bb "P"_T`(19) = 14
Pfadlänge der `bb "H"`-Funktion: `bb "P"_H`(19) = 6
Es gilt:
`bb "P"_C(n)` ist gleich der Summe aller Schritte von `3n+1` und von `n/2` bis zum Erreichen von 1
`bb "P"_T(n)` ist gleich der Summe aller Schritte von `n/2` bis zum Erreichen von 1
`bb "P"_H(n)` ist gleich der Summe aller Schritte von `3n+1` bis zum Erreichen von 1
Damit gilt `bb "P"_H(n) + bb "P"_T(n) = bb "P"_C(n)`
`bb "P"_H(n) = 0` gilt für alle 2er-Potenzen, denn für diese ist nach Anwendung der Shift-Formel bereits die 1 erreicht, so dass keine Iterationen mit der `bb "H"`-Formel erforderlich sind.
Lemma 2
Ist die Collatz-Vermutung wahr, so gilt für alle `n in NN: bb "P"_H(n) < oo`
Ist die Collatz-Vermutung nicht wahr, so existieren `n`, für die gilt: `bb "P"_H(n) = oo`, denn für diese Zahlen erreicht der Pfad nie die Zahl 1.
In den nächsten Abschnitten wird ausschließlich mit den ungeraden Zahlen gearbeitet.