Randbemerkungen

Gespeichert von mk am Sa, 2.6.2018 - 12:23

Welche Collatz-Folgen interessieren uns eigentlich am meisten, von den Simplexfolgen einmal abgesehen? Wir werfen einen Blick auf Abb. 1. Sie zeigt das CD-Feld. Es sortiert alle natürlichen Zahlen größer als 0 derart, dass all jene mit gleichzahligen G- und U-Durchläufen an der gleichen Stelle liegen, also die gleichen (c, d)-Koordinaten haben. Der Abakus kann die Folgen direkt in das Feld schreiben, indem er sich die passenden Zahlen an den Positionen herauspickt und diese miteinander verbindet.

Unterer Rand
Abb. 1: Der untere Rand des CD-Feldes mit einigen Diagonal- und Horizontalband-Enden

Das Auffälligste am Bild ist der untere Rand der Schraffur, der aussieht wie eine Bruchkante. Die Enden der diagonalen Streifen markieren relativ längste Folgen. Relativ bedeutet, es gibt keine Folge mit dieser d-Koordinate des Startwertes, die länger ist als jene, die am Rand startet. Um Eindeutigkeit zu erzwingen, legen wir fest, dass nur der kleinste Startwert die Krone des Besten tragen darf, falls mehrere Folgen an derselben Stelle beginnen. Unter den Randpunkten gibt es wiederum welche, die besonders ausgezeichnet sind. Dort starten die dann relativ allerlängsten Folgen. Diese Positionen schließen ein Horizontal-Band nach links ab (zur Erinnerung: Die Bandnummer gibt die Anzahl der belegten Binärstellen der Zahlen in diesem Band an). Keine Diagonale oberhalb dieses Punktes reicht mehr in dieses H-Band hinein, denn alle Zahlen des Bandes liegen rechts vom Abschlusspunkt oder darauf.

Das hat Folgen

Als Konsequenz daraus lässt sich der folgende Satz formulieren: Es sei z eine Zahl mit Koordinaten (c, d) = (a, b) und ein H-Band-Abschluss des Bandes h. Dann gilt für alle Startwerte im Intervall [1, 2h]: Die zugehörigen Collatz-Folgen verlaufen innerhalb eines Vierecks, das die Koordinaten (0, 0), (a, min), (a, b) und (0, b) als Eckpunkte hat, wobei min die kleinste Diagonale sei, die verlängert, c noch oberhalb der x-Achse erreicht. Auch ohne den Terminierungsbeweis im Buch kann man also an der Struktur des CD-Feldes erkennen, dass man über einen kompletten Satz Collatz-Folgen mit beschränkter Länge und Maximalwert verfügt, wenn man nur einen einzigen (möglichst hohen) H-Band-Abschluss kennt. Warum sind diejenigen am Rand die längsten Folgen? Wir erinnern uns an die äquivalenten Folgen aus dem Hauptartikel (siehe die Abbildung dort). Diese verlaufen zunächst diagonal bis zur Spalte 0, bevor sie nach unten abbiegen. Man kann also unmittelbar sehen, dass die am Rand beginnenden Folgen die längsten sein müssen und immer länger werden, je höher der d-Wert wird. Die Tabelle in Abb. 2 listet einige Endpunkte auf.

Bestwerte (Stand 5-18)
Abb 2: Längste Folgen, sortiert nach H-Band
(Stand Juni 2018)

Vorsorglich der Hinweis, dass bei den Zahlen, mit denen wir und jetzt beschäftigen werden, der Abakus wohl passen muss (Ressourcen des Servers und Zahlenbereich der Websprachen sind leider limitiert). Wie kommt man also an diese Werte heran? Man könnte, wie im Buch beschrieben, versuchen nach und nach alle Diagonalen durchrechnen, sodass man ähnliches Bild wie oben erhält. Nach anfänglichen Enthusiasmus macht der Rechner aber schnell schlapp, der eine früher, der andere noch früher. Die Größe der Zahlen ist dabei nicht das Problem, sondern die gigantische Menge an Zahlen, die es zu berechnen gilt. Bis etwa H-Band 40 (kurz H40) hilft "Brute force". Man rechnet einfach alle Zahlen des Bandes durch und man kann sich sicher sein, dass man die Abschlusspositionen findet. Um in höhere Regionen vorzustoßen, benötigt man eine Strategie, um sich Rechenarbeit zu ersparen. Das geht allerdings auf Kosten der Genauigkeit. Die gefundenen Zahlen sind dann bestenfalls Näherungswerte, wenn auch gute. Diese lassen sich mit Geduld und Rechenkraft sicher noch toppen (bei mir hält sich beides in Grenzen).

Das gegenerische Lager

Man kann auch versuchen, die Collatz-Vermutung zu widerlegen. Dazu reicht es schließlich aus, nur ein einziges Gegenbeispiel zu finden. Dieser Aufgabe haben sich einige emsige Forscher verschrieben. Die dazu nötige Rechenkraft erhalten sie von einer Plattform namens BOINC. Sie ermöglicht es, freie Rechnerkapazitäten von Freiwilligen für wissenschaftliche Berechnungen zu bündeln. Das Open-source Projekt wird von der University of California, Berkeley betreut. Weitere Infos gibt es vom Verein Rechenkraft.net e.V., der sich ebenfalls in diesem Bereich engagiert. Eine Anwendung widmet sich der Collatz Conjecture. Das Ziel ist es, nach möglichst langen Collatz-Folgen zu suchen. Die Längsten landen in einer Bestenliste (März 2017). In dieser ist die Zahl 3179389980591125407167 mit 2760 Schritten (klassisch gerechnet) der derzeitige Spitzenreiter. Die Koordinaten lauten (c, d) = (1040, 680). Zur Umrechnung in Schritte verwende man 2c + d. Der Liste kann man entnehmen, dass gerade im H-Band 72 gerechnet wird (gerade heißt seit etwa 9 Jahren). Das Band erstreckt sich über [2(72 - 1), 272 - 1] = [2361183241434822606848, 4722366482869645213695]. Zufällig haben alle Zahlen 22 Dezimalstellen. Die Bestenliste ist jedoch nur bedingt aussagefähig, was daran liegt, dass das Projekt erst bei der Zahl 2361183346958000000001 gestartet wurde (als Nachfolgeprojekt eines früheren). Dadurch übersieht man leicht, dass auch kleinere Zahlen existieren, die es locker in die Spitzengruppe schaffen würden. Ordentliche Werte gibt es ab H-Band 70 und die Zahl 1763000105732245455975 (1043, 681) aus H71 übertrifft sogar den Spitzenreiter. Natürlich hat auch H72 ein linkes Ende. Der Startwert ist 2476422645088915427871 und liegt an der Position (1049, 685).

Die Lösung des Collatz-Problems erleichtert also das Auffinden besonders langer Folgen. Man ist nun nicht mehr darauf angewiesen, im Trüben zu fischen.