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

Wie man mitrechnen kann

Der folgende Abschnitt bezog sich darauf, wie man sich an der Berechnung des (nun abgeschlossenen) Projekts beteiligen konnte:

Haben Sie ein Linux- oder Windows-64-Bit-Betriebssystem und x86- (etwa von AMD oder Intel) oder ARM-64-Bit-Prozessoren, dann können Sie sich am Verteilten-Rechnen-Projekt 'Nontrivial Collatz Cycle' aktiv beteiligen! (Eine Windows-Version folgt demnächst.) Dazu gehen Sie wie folgt vor:

  1. Herunterladen und installieren der BOINC-Infrastruktur (die die Kommunikation mit dem Projektserver übernimmt), siehe http://boinc.berkeley.edu/download.php.
  2. Den BOINC-Manager starten und dem Projekt yoyo@home beitreten. (Für Account-Erstellung eine e-Mail-Adresse und Passwort angeben.) Projekt-Webseite: http://www.rechenkraft.net/yoyo/.
  3. Auf eigene Account-Webseite für das Projekt yoyo@home anmelden (geht via BOINC-Manager oder auch über die Projekt-Webseite) und dort in den Preferences die yoyo@home preferences editieren und die Application Collatz auswählen.
  4. Fertig. Ab jetzt läuft alles automatisch. :)

Im Rahmen meiner Forschungsarbeit setze ich mich mit dem Collatz-Problem auseinander. Dabei stehen 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 und dessen Ergebnisse werden nach Abschluss des Projekts in einem wissenschaftlichen Artikel veröffentlicht. Ansprechpartner ist Dr. Christian Hercher.

Mathematischer Hintergrund (Kurzdarstellung)

Die Grundlage für die folgenden Überlegungen ist Shalom Eliahou. The 3x + 1 problem: new lower bounds on nontrivial cycle lengths. Discrete Mathematics, 118:45{56, 1993; auch online zu finden unter https://pdfs.semanticscholar.org/7477/6cf36405d70c2230613bf1416ac141013599.pdf . Nachfolgend wird die wesentliche Idee hier dargestellt. (Einen exakteren Zugang bietet z.B. folgende Masterarbeit: http://d-scholarship.pitt.edu/24817/1/Masters_-_Collatz.pdf )

Wir schauen uns folgende Heuristik an: Sind die betrachteten Zahlen groß, so wird eine gerade Zahl beim Übergang zur nächsten Zahl mit dem Faktor 1/2 multipliziert, eine ungerade dagegen mit "nur etwas mehr als 3". Lassen wir dieses "nur etwas mehr" unter den Tisch fallen und rechnen mit dem Faktor ca. 3. Dann besteht also eine Collatz-Folge aus einer Abfolge der Faktoren 1/2 und 3. Soll sich ein Zyklus schließen, dann muss demnach ein Produkt aus diesen Faktoren 1/2 und 3 etwa 1 ergeben (bzw. genau 1, wenn wir genau rechnen).

Sei p die Anzahl der Faktoren 1/2 (also der geraden Folgenglieder, die ja jeweils halbiert werden) und q der Faktoren 3 (also der ungeraden Folgenglieder, auf die ja jeweils eine solche Vergrößerung der Zahl erfolgt). Dann soll also (1/2)p * 3q ungefähr gleich 1 gelten. Logarithmieren und umstellen liefert dann die Bedingung p/q ungefähr gleich log(3)/log(2)=log2(3).

Arbeitet man genau, so erhält man die Abschätzung

log2(3) < p/q < log2(3+μ), wobei μ der (arithm.) Durchschnittswert der Reziproken 1/u aller ungeraden Folgenglieder u in diesem Zyklus ist. Kann man diesen Wert μ kleinhalten, so ist also der Bruch p/q durch sehr enge Grenzen beschränkt. Aus der Theorie der rationalen Approximation reeller Zahlen folgt dann, dass der Nenner q (und damit auch der Zähler p und somit die Gesamtzahl der Folgenglieder in dem betrachteten Zyklus p+q) dieses gemeinen Bruchs eine gewisse Schranke nicht unterschreiten kann. (Dies hat mit den Näherungsbrüchen von log2(3), die man aus der Kettenbruchentwicklung jener Zahl erhält, zu tun; siehe https://de.wikipedia.org/wiki/Kettenbruch#Beste_N.C3.A4herungen.)

Im Folgenden geht es also darum, den Wert μ = 1/q * summe_{u ungerades Folgenglied im Collatz-Zyklus} 1/u möglichst gut nach oben abzuschätzen.

Eine erste Feststellung ist, dass, wenn wir wissen, dass jede Startzahl kleiner oder gleich einer Schranke S in den trivialen Collatz-Zyklus mündet, alle Elemente eines nicht-trivialen Zykluses dies nicht tun und damit also > S sein müssen. Es folgt damit 1/u < 1/S für alle u und damit auch für μ als dem Durchschnitt dieser 1/u, dass auch μ < 1/S ist.

Mit diesem Ansatz arbeiten auch die Beweise zu den bisherigen Abschätzungen über die Mindestanzahl an Elementen eines nicht-trivialen Collatz-Zyklusses. Es bieten sich hierbei zwei mögliche Arten der Verbesserung dieser Herangehensweise an:

  • Man verbessert die Abschätzung für μ, sodass - mit dem Wissen, dass keine Zahl ≤ S Element des betrachteten nicht-trivialen Zyklusses ist - man einen Vorfaktor c(S) < 1 erhält, für die μ < c(S) * 1/S gilt.
  • Man testet weitere Startzahlen, erhöht die Schranke S, und verkleinert auf diese Weise den Wert für μ.

Beide Ansätze werden hier verfolgt, wobei signifikante Anstrengungen nach Wissen des Autors bisher nur in den zweitgenannten Punkt investiert wurden, während die strukturelle Verbesserung der Ungleichung durch Finden eines kleineren gültigen Wertes c(S) < 1 hier erstmals intensiver betrachtet wird.

Inhaltliche und Algorithmische Überlegungen

Verbesserung der Konstanten c in der Abschätzung  μ < c * 1/S

Möchte man die Abschätzung für μ verbessern, so fällt als erstes auf, dass alle ungeraden Elemente u des betrachteten yklusses naiv nur durch u > S abgeschätzt werden. Doch ist u z.B. von der Form u=4k+1, so lauten die nächsten Folgenglieder ja 12k+4, 6k+2 und 3k+1. Also ist insbesondere auch 3k+1 als Element des Zyklusses größer als S und damit u > 4/3 S... Analog kann man auch viele andere Restklassen modulo Zweierpotenzen betrachten.

Aber nicht nur die Betrachtung der Collatz-Nachfolger einer Zahl u lässt bessere Abschätzungen zu, wenn ein solcher Nachfolger kleiner ist als die betrachtete Zahl u. Auch die umgekehrte Richtung ist als fruchtbar zu betrachten: Genauso folgt nämlich auch, dass, wenn ein potentieller Collatz-Vorgänger v von u mit u< v existiert, dass dann für u eine deutlich bessere Abschätzung als u>S bekommt, denn es muss ja auch schon v>S gegolten haben, da ja auch die Collatz-Folge mit Startzahl v nicht in den trivialen, sondern den betrachteten nicht-trivialen Zyklus übergeht, was ja für alle Startzahlen <= S ausgeschlossen worden war.

Weiterhin weiß man, dass u > S ist. Betrachtet man gerade den Fall, dass u ≡ rest (mod 2a) ist, dann bedeutet dies, dass u mindestens so groß ist wie der kleinste Vertreter dieser Restklasse [rest] (mod 2a) . Das mag für kleine Werte von a keine signifkante Verbesserung sein. Ist aber a groß (z.B. >70) und rest < S, dann ist u mindestens rest+2a, was nun widerum viel größer als S ist, die Abschätzung also deutlich verbessert. Umgekehrt ist für Werte rest, die deutlich größer als S sind, natürlich auch u deutlich größer als S, sodass auch hier eine deutlich bessere Abschätzung als u>S gelingt.

Durch die Kombination dieser Methoden ist es bei Betrachtung der Restklassen modulo immer größerer Zweierpotenzen möglich, immer bessere Abschätzungen zu zeigen.

Um diese Untersuchungen durchzuführen, wurde ein Programm (in der Programmiersprache C, da das Laufzeitverhalten relevant ist) geschrieben, welches die notwendigen Berechnungen durchführt. Dabei werden rekursiv potnetiell alle Restklassen modulo einer großen Zweierpotenz (etwa 2200) betrachtet und für jede gezeigt, dass, wenn u in diese Restklasse fällt, dann 1/u bzw. der Durchschnitt der Reziproken der nächsten ungeraden Folgengliedern in dem Zyklus kleiner ist als c * 1/S, wobei c und S vorgegeben sind. Daber werden natürlich nicht alle diese Restklassen einzeln betrachtet, sondern werden zu großen Gruppen zusammengefasst. Beispielsweise reicht es in dem Teilbaum u=4k+1 für c > 3/4 aus, die oben genannte Überlegung anzustellen und damit u > 4/3S bzw. 1/u < 3/4 * 1/S nachzuweisen. Dies gilt dann auch für alle entsprechenden Restklassen modulo größerer Zweierpotenzen, die trotzdem kongruent 1 (mod 4) sind.

Damit ist ein deutlich geringerer Anstieg der benötigten Rechenzeit als die erwarteten 2n bei einer vollständigen, individuellen Betrachtung aller Restklassen modulo 2n verbunden. Leider steigt die benötigte Rechenzeit dennoch exponentiell an, sodass in realistischer Zeit nur begrenzte, aber deutlich spürbare Verbesserungen zu erzielen sind.

Nachgewiesen werden konnte eine Abschätzung μ < 0.4625 * 1/S für S=87*260 < 1,004*1021  ,sodass es genügt bis zu diesem Wert für alle kleineren Startzahlen nachzuweisen, dass ihre Collatz-Folgen in den trivialen Zyklus münden.

Verbesserung der Schranke S

Der Gedanke nach den Restklassen der Startzahlen modulo Zweierpotenzen zu unterscheiden ist auch bei der konkreten Betrachtung der Collatz-Folgen von Zahlen sehr gewinnbringend einsetzbar, und das gleich auf doppelte Weise:

Wie wir oben schon gesehen haben, geht jede Zahl der Form 4k+1 in zwei Schritten (wobei wir den automatischen Halbierungs-Schritt, der auf jeden Verdreifachungsschritt folgt, da bei ungeraden n der Wert 3n+1 ja auf jeden Fall gerade ist und damit also dann direkt halbiert wird, nicht mitzählen) in eine der Form 3k+1 über. Analog verhält es sich für die Zahlen der Form 4k+3. Die gehen in zwei Schritten in Zahlen der Form 9k+8 über. Das gleiche gilt für die Restklassen modulo größerer Zweierpotenzen: Betrachtet man die Zahlen modulo 2a, so kann man die nächsten a Schritte direkt zusammenfassen und mit vortabellierten Werten berechnen, denn sie hängen nur von der Kongruenz der Zahl modulo 2a ab. Diese Zusammenfassung mehrerer Einzelschritte zu einem Mehrfachschritt beschleunigt die Berechnung knapp um den Faktor a. (Dabei muss aber der Speicherplatzbedarf für die vorberechneten Werte in Betracht gezogen werden, denn der steigt natürlich auch exponentiell in a. Umgesetzt wurde im Projekt ein Wert von a=10, da insbesondere auch die dafür benötigten 32KB in den L1-Cache eines modernen Prozessors passen, sodass hier sehr schnell darauf zugegriffen werden kann.)

Andererseits wollen wir nur nachweisen, dass alle Startzahlen < S in den trivialen Zyklus übergehen. Dazu müssen wir nicht notwendigerweise die Folgen so weit berechnen, bis sie dort angelangt sind. Es reicht uns zu zeigen, dass eine Folge einen kleineren Wert m als die Startzahl erreicht. Denn haben wir für alle kleineren Startzahlen schon gezeigt, dass sie in den trivialen Zyklus übergehen, dann muss die gerade betrachtete Startzahl das nun auch tun, da ihre weitere Collatz-Folge nun mit der von m zusammenfällt. (Dabei ist die Reihenfolge, wann wir welche Startzahl betrachten, nicht relevant. Sind dann aber alle abgearbeitet worden, und ist für jede gezeigt, dass sie jeweils auf einen kleineren Wert führt, dann landen "induktiv" die Collatz-Folgen aller betrachteten Startzahlen < S irgendwann bei 1 und damit im trivialen Zyklus.)

Dies können wir nutzen: So müssen wir uns wegen 4k+1-->12k+4-->6k+2-->3k+1 < 4k+1 gar nicht mehr weiter um die Zahlen der Form 4k+1 kümmern. Analog können wir auch viele weitere Restklassen modulo größerer Zweierpotenzen ausschließen. Und analog oben hilft auch die "Rückwärtssuche" nach potentiellen Collatz-Vorgängern weiter. Auf diese Weise lässt sich etwa die Anzahl der zu betrachtenden Restklassen modulo 232  deutlich reduzieren: Von den insgesamt über 4 Milliarden solchen Restklassen müssen nur noch Startzahlen aus knapp 24 Millionen davon betrachtet werden; oder etwa 0,58%. (Der Ansatz, mit der Betrachtung und Berechnung der nächsten Collatz-Iterationen ganze Restklassen ausschließen zu können, wurde schon früher betrachet, etwa von Tomas Olivera e Silva, dessen Arbeiten in den Jahren bis 2008 den derzeitigen Status Quo darstellen. Die Idee der Rückwärtssuche dagegen ist neu und spart hier gegenüber den 42 Millionen von Olivera e Silva zu betrachtenden Resten etwa 1/3 an Rechenzeit, erhöht den Durchsatz also um den Faktor ca. 1,5.)

Datentypen

Relevant sind auch die in der Umsetzung verwendeten Datentypen: Moderne Prozessoren unterstützen Hardware-seitig 64-Bit-Operationen, d.h., solang alle Operanden und das Ergebnis kleiner sind als 264, ist alles gut und die Berechnungen können sehr schnell ausgeführt werden (wenige Prozessor-Takte). Bei größeren Zahlen dagegen gibt es leicht Probleme, da mit diesen Datentypen dann nur Berechnungen (jedenfalls für Additionen und Multiplikationen) modulo 264 ausgeführt werden: Ein exaktes Ergebnis liegt damit nicht mehr vor: Die führenden Bits werden einfach abgeschnitten. Zwar bietet der GNU C Compiler GCC den nativen Datentyp eines 128-Bit-Integers an. Dieser ist jedoch Software-implementiert (und die entsprechenden Instruktionen an den Prozessor, der keinen solchen Datentyp kennt, werden vom Compiler entsprechend der vorhandenen Prozessor-Architektur erzeugt) und damit deutlich langsamer. Zwar wird er im Programm, welches in dem 'Nontrivial Collatz Cycle'-Proejtk im Einsatz ist, herangezogen, aber sein Einsatz möglichst minimiert.

Um dennoch schnell zu Ergebnissen zu gelangen, werden in den Mehrfachschritten (s.o.) nicht die genannten Operationen mit den 128-Bit-Zahlen selbst durchgeführt, sondern einerseits nur mod 264, damit man die hinteren Bits kennt, die bestimmen, ob nun jeweils halbiert bzw. "verdreifacht" wird, und andererseits mit Gleitkomma-Zahlen, die Näherungen an die betrachteten Zahlen (genauer: an die Quotienten "aktuelles Folgenglied / Startzahl") enthalten. Mit letzteren kann man die absolute Größe der aktuellen Folgenglieder abschätzen. Wenn diese < 0.98 * die der Startzahl wird, kann man abbrechen, da dann sicher auch trotz eventueller Näherungsfehler in den hinteren Stellen der verwendeten double-Gleitkommawerten eine Zahl kleiner der Startzahl erreicht wurde.

Aktueller Stand und Ergebnisse

Es wurden die Startzahlen bis 87*260 > 1020 untersucht, und damit die bisher bekannte Schranke von 5*260 aus dem Jahr 2008 deutlich überboten. Dazu wurden die Restklassen modulo 232 vorgesiebt, sodass noch knapp 24 Millionen davon zu betrachten waren. Diese wurden durch das am 14. August gestartete und am 23. September beendete Projekt 'Nontrivial Collatz Cycle' zum Verteilten Rechnen verwaltet und an die einzelnen Hosts zur weiteren Berechnung verteilt.

Jede einzelne dieser Restklassen modulo 232 wurde dann weitergesiebt bis zur Tiefe 58. Für die dann noch zu betrachtenden Restklassen modulo 258 wurden alle darin liegenden Startzahlen < 87*260 erzeugt und für jede davon dann solang die nachfolgenden Collatz-Folgenglieder (je 10 Schritte durch den Mehrfachschritt auf einmal und beginnend mit der 58. Iteration, deren Wert man aus dem vorhergehenden Siebprozess schon kennt) berechnet, bis die Folge einen Wert kleiner der Startzahl erreichte. Dann konnte die Berechnung für diese Startzahl abgebrochen werden. (Abgebrochen wäre auch nach einer Anzahl von maximal 2000 Iterationsschritten, damit man nicht in eine Endlosschleife läuft, sollte eine Startzahl doch nicht in den trivialen Zyklus münden oder divergieren. Dies trat jedoch nie ein: Alle betrachteten Startzahlen landen bewiesenermaßen im trivialen Zyklus.)

Pro zu betrachtender, durch den Projekt-Server verwalteter, Restklasse modulo 232 mussten dabei einige hundert Millionen Startzahlen betrachtet werden, sodass für das gesamte Projekt in der Größenordnung  um 1018 Collatz-Folgen erzeugt wurden. Konkret wurden insgesamt etwa 25 * 1018 Rechenoperationen durchgeführt, was bedeutet, dass pro naiv einzeln zu betrachtender Startzahl im Schnitt jeweils nur etwa eine Viertel-Rechenoperation notwendig war. (Dies ist etwa um den Faktor 5 besser als beim letzten relevanten Projekt zu diesem Thema aus dem Jahr 2008/9.)

Dabei fielen auch die Maximalwerte, die die Collatz-Folgen erreichen, auf. Genauer: Es wurde ein Kandidat ausgegeben, wenn eine seiner Iterationen mindesten 2*1016 mal so groß ist wie die Startzahl. Dies sind potentielle Kandidaten für Pfadrekorde, wie sie Eric Roosendaal auf seiner Webseite http://www.ericr.nl/wondrous/ bzw. http://www.ericr.nl/wondrous/pathrecs.html auflistet. Durch dieses Projekt konnten insgesamt vier neue Pfad-Rekorde gefunden werden, wie man sie nun auch auf gerade genannter Übersichtsseite findet. (Eine detailiertere Übersicht über alle gefundenen Kandidaten findet man unter http://www.rechenkraft.net/yoyo/y_status_col.php .)