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.

` bb "C": NN rarr NN,     bb "C"(n)= {(n/2,if,n mod 2 -=0),(3n+1,if,n mod 2 -=1):} `
Die `bb "C"`-Funktion (originale Collatz-Funktion)

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:

` bb "T": NN rarr NN,     bb "T"(n)= {(n/2,if,n mod 2 -=0),((3n+1)/2,if,n mod 2 -=1):} `
Die `bb "T"`-Funktion ist eine Vereinfachung der `bb "C"`-Funktion

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:

`   bb "S"(n)= {(bb "S"(n/2),if,n mod 2 -=0),(n,if,n mod 2 -=1):} `
Die Shift-Funktion `bb "S"` halbiert eine Zahl solange, bis sie ungerade ist

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:

` bb "H": NN rarr NN,   n mod 2 -= 1,   bb "H"(n)=  bb "S"(3n+1) `
Die `bb "H"`-Funktion ist eine konsequentere Vereinfachung der `bb "C"`-Funktion unter Zuhilfenahme der `bb "S"`-Funktion

Hinweis: Falls man auch mit geraden Zahlen rechnen möchte, ist vor Beginn der Iteration mittels `bb "H"`-Funktion die Shift-Funktion anzuwenden.

Beispiel: Resultierenden Folgen am Beispiel der Zahl 19:

`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 

Es sei `bb "P"` die Pfadlänge, also die Anzahl der Iterationen bis zum erstmaligen Erreichen der Zahl 1.
Definition der Pfadlänge
Beispiel: Resultierenden Pfadlängen am Beispiel der Zahl 19:

  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.