Sie sind hier: Collatz-Problem für Dummies» Einführung

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 .
  • Ist gerade, so nimm als nächstes .
  • Ist ungerade, so nimm als nächstes .
  • 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.

Die -Funktion (originale Collatz-Funktion)

Da für ungerade stets gerade ist und somit die folgende Iteration immer die Division durch 2, wird statt der Collatz-Funktion  oft die etwas einfacher zu handhabende  -Funktion verwendet, die für ungerade zwei -Iterationen auf einmal macht und den der Vermutung zufolge stets erreichten Zyklus von (1,4,2) auf (1,2) reduziert:

Die -Funktion ist eine Vereinfachung der -Funktion

Laut Eric Roosendaal wurde die Collatz-Vermutung mittels Durchprobierens für alle positiven ganzen Zahlen bis (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 -Folge wird jede Zahl so lange halbiert, bis sie ungerade ist.
Die Shift-Funktion  macht genau dies:

Die Shift-Funktion  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 -Funktion:

Die -Funktion ist eine konsequentere Vereinfachung der -Funktion unter Zuhilfenahme der -Funktion

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

Beispiel: Resultierenden Folgen am Beispiel der Zahl 19:

(19): 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

(19): 19, 29, 44, 22, 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1

(19): 19, 29, 11, 17, 13, 5, 1

 

Pfadlänge 

Es sei  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 -Funktion:   (19) = 20 

  Pfadlänge der -Funktion:   (19) = 14

  Pfadlänge der -Funktion:   (19) = 6

Es gilt:

ist gleich der Summe aller Schritte von und von bis zum Erreichen von 1

ist gleich der Summe aller Schritte von bis zum Erreichen von 1

ist gleich der Summe aller Schritte von bis zum Erreichen von 1

Damit gilt 


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 -Formel erforderlich sind.

Lemma 2

Ist die Collatz-Vermutung wahr, so gilt für alle

Ist die Collatz-Vermutung nicht wahr, so existieren , für die gilt: , 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.