Das Collatz-Problem

Vor 80 Jahren formulierte Lothar Collatz die folgende Fragestellung:

Startet man mit einer natürlichen Zahl n > 0, so kann man sie, wenn n gerade ist, halbieren und erhält eine neue Zahl n/2. Ist sie ungerade, so multipliziere man sie mit 3 und addiere 1; man erhält die Zahl 3n+1. Und mit dieser neu erhaltenen Zahl (n/2 bzw. 3n+1) fahre man genauso fort: Ist sie gerade, halbiert man sie; ist sie ungerade, wird sie mit 3 multipliziert und dann 1 addiert.

Vermutung (Collatz): Für jede Startzahl n gelangt diese Folge der nach dieser Vorschrift jeweils neu erzeugten Zahlen irgendwann in den trivialen Zyklus 1 --> 4 --> 2 --> 1 -->   ...

Siehe auch z.B. https://de.wikipedia.org/wiki/Collatz-Problem

Folien Vortrag zum Thema

vortrag-collatz-folien.pd...

Datum:
14.09.2017
Datei:
507 KB (PDF)
Download ReadSpeaker docReader

Im Rahmen meiner Forschungsarbeit habe ich mich mit dem Collatz-Problem auseinander gesetzt. Dabei standen Fragen der algorithmischen Zahlentheorie im Vordergrund.

Verteiltes Rechnen im Projekt 'Nontrivial Collatz Cycle'

Die Collatz-Vermutung (siehe rechte Spalte) ist bisher unbewiesen. Wäre sie falsch, dann müsste (mindestens) eine der beiden folgenden Aussagen eintreten:

  1. Es existiert eine Startzahl n, deren zugehörige Collatz-Folge der durch sie sukkzessiv erzeugten natürlichen Zahlen unbeschränkt wächst, d.h. immer größere Folgenglieder erzeugt; oder
  2. es existiert eine Startzahl n, deren zugehörige Collatz-Folge in einen vom trivialen Zyklus verschiedenen Zyklus übergeht und sich immer wieder wiederholt, ohne je die Zahl 1 zu erreichen.

Ziel des Projekts 'Nontrivial Collatz Cycle' war es deshalb nur ein Teilaspekt dieser Vermutung zu betrachten und folgenden, abgeschwächten (nun bewiesenen) Satz zu beweisen:

Satz: Jeder nicht-triviale Collatz-Zyklus besteht aus mehr als 17 Milliarden Folgengliedern.

(Bis dato war nur eine entsprechende Aussage mit etwas über einer Milliarde Folgengliedern bekannt.) Um diese Aussage zu beweisen, musste in dem Projekt für alle Startzahlen < 1020 nachgewiesen werden, dass ihre zugehörigen Collatz-Folgen in den trivialen Zyklus übergehen. Dies geschah auf optimierte Weise, sodass eine deutliche, auf algorithmischen Verbesserungen basierende Effizienz-Steigerung gegenüber ähnlichen Projekten in der Vergangenheit erreicht werden konnte.)

Während der Berechnung wurden automatisch auch neue Pfadrekorde, d.h. Startzahlen, in deren Collatz-Folgen größere Folgenglieder auftreten als für alle kleineren Startzahlen zuvor, siehe http://www.ericr.nl/wondrous/pathrecs.html , gefunden.

Gegenüber dem schon existierenden Projekt http://boinc.thesonntags.com/collatz/, dass sich einer ähnlichen Thematik widmet, existieren insbesondere deshalb Vorbehalte, da keine Berechnungen eines lückenlosen Bereichs von 1 bis zur kleinsten durch das Projekt betrachteten Startzahl von 271 gegeben sind. Auch nutzt es weniger effiziente Methoden (da das Ziel des Projekts ein leicht anderes war und so einige Optimierungen des 'Nontrivial Collatz Cycle' - Projekts nicht zum Einsatz kommen können).

Das Projekt hatte einen Arbeitsaufwand von ca. 35 CPU-Kern-Jahren (wovon die Hälfte auf Kontroll- und Validierungsrechnungen entfielen, damit man sicher gehen kann, dass nicht ein zufälliger Fehler das Ergebnis verfälscht hat), welcher durch im Schnitt 300 Kerne in den 40 Tagen von Mitte August bis Ende September 2017 durch Freiwillige auf der ganzen Welt geleistet wurde. Das Projekt wurde in Zusammenarbeit mit der Universität Flensburg durchgeführt.

Artikel in der Zeitschrift "Die Wurzel" Hefte 6 und 7/2018

wurzel-artikel-collatz.pd...

Datum:
26.07.2018
Datei:
499 KB (PDF)
Download ReadSpeaker docReader