Formeln | Fraktale Welten

Eine einfache Frage

Die zahlentheoretische Frage, die zu diesem Fraktal führt, ist sehr einfach zu stellen: Man nehme eine beliebige natürliche Zahl größer 1 als Startwert und bilde daraus eine Folge, indem der jeweils nächste Wert folgendermaßen bestimmt wird: Ist die Zahl gerade, teil sie durch zwei; ist die Zahl ungerade, multiplizier sie mit 3 und addier 1.

Bei allen Startwerten, mit denen man das bislang ausprobiert hat (das waren sehr viele), wurde in dieser Folge irgendwann der Wert 1 erreicht (ab dort entsteht eine periodische Folge 1, 4, 2, 1, 4, 2, 1…). Die Frage, ob wirklich jeder Startwert zu 1 führt, oder ob es auch Startwerte gibt, die über alle Grenzen wachsen oder in eine andere Periode führen, ist ein zurzeit ungelöstes mathematisches Problem. Die bislang unbewiesene Collatz-Vermutung lautet, dass es solche Startwerte nicht gibt, dass also jeder Startwert dieser Folge nach einer endlichen Anzahl von Iterationen schließlich zu 1 führt.

Ein geradezu teuflisches Problem, weil es sich so einfach formulieren und verstehen lässt und doch sehr schwierig ist. Wer noch nie von diesem einfachen Problem gehört hat, sollte sich ruhig einmal den Computer nehmen, um sich selbst einen Eindruck zu verschaffen. Ein kleines Programm zur Untersuchung der Folge ist schnell geschrieben und wird in der Regel eher noch etwas unsauberer hingepfuscht sein als die folgende, in Python formulierte Version:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def collatz(n):
    n = long(n)
    s = [n]
    while n > 1:
        if n & 1 == 0:
            n /= 2
        else:
            n = 3 * n + 1
        s.append(n)
    return s

def print_collatz(n):
    print(", ".join([str(i) for i in collatz(n)]))

if __name__ == "__main__":
    import sys
    if len(sys.argv) == 1:
        print("Collatz-Problem")
        while True:
            print_collatz(raw_input("n = "))
    else:
        for n in sys.argv[1:]:
            print_collatz(n)

Mit einem solchen Programm kann man sich sehr leicht anschauen, wie sich die Folge für verschiedene Startwerte verhält. Manchmal kommt sie schnell zum Ziel, etwa für den Startwert 10:

10, 5, 16, 8, 4, 2, 1

Und manchmal gibt es ein Auf und Ab, das zunächst weit vom Ziel wegführt und den Gedanken gar nicht mehr absurd erscheinen lässt, diese Folge könnte auch über alle Grenzen wachsen, bis sie dann schließlich doch zum Ziel kommt, wie für den Startwert 27:

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Auch die Folgeglieder des Startwertes 73 geben einen guten Eindruck davon, dass sich hinter der trügerisch einfachen Formulierung der Iteration ein sehr komplexes Verhalten verbirgt:

73, 220, 110, 55, 166, 83, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1

Etwas Verallgemeinerung

Ich will hier gar nicht länger mit derartigem „Zahlensalat“ langweilen. Das Python-Programm kann jeder selbst ausführen, ein Python-Interpreter ist für jedes gängige Betriebssystem verfügbar. Eine Formulierung in anderen Programmiersprachen ist ebenfalls trivial. So kann sich jeder Mensch, der einen Computer zur Verfügung hat, selbst ein Bild machen. Wenn man es mit einem mathematischen Problem zu tun hat, das man jedem aufgeweckten Zehnjährigen, der die Grundrechenarten beherrscht, erklären kann, hat man es mit Zahlentheorie zu tun.

Für eine etwas ernsthaftere Untersuchung könnte es hilfreich sein, die zunächst nur für natürliche Zahlen definierte Iteration auf weitere Zahlbereiche zu verallgemeinern. Die Formulierung der Fallunterscheidung mit den Begriffen „gerade“ und „ungerade“ ist ja nur mit natürlichen und ganzen Zahlen sinnvoll, für eine erste Vereinfachung sollte sie durch einen anderen Ausdruck ersetzt werden. Hier bietet es sich in einem ersten Schritt an, Potenzen von -1 zu verwenden. Desweiteren ist es praktisch, die Iteration als eine Funktion zu betrachten, die einen Iterationswert der Collatz-Iteration auf den nächsten Wert abbildet. Das Ergebnis sieht so aus¹:

$f(z)=[1+(-1)^{z}]\frac{z}{4}+[1-(-1)^{z}]\frac{3z+1}{2}$

Damit ist die Iteration auf die Menge der rationalen Zahlen verallgemeinert². Wer diese Umformung verstehen will, mache sich einfach klar, dass sich [1+(-1)^z] für gerade z zu 0 vereinfacht, für ungerade z hingegen 2 wird.

Für eine Untersuchung mit dem Computer ist es jetzt aber noch störend, dass Potenzen einer negativen Zahl verwendet werden, die für negative Exponenten undefiniert sind. Hierfür gibt es jedoch einen recht eleganten Trick, mit dem diese Beschränkung umgangen werden kann. Denn so lange man ganze Zahlen betrachtet, gilt:

$(-1)^{z}=\cos(\pi z)\;\textrm{wenn}\; z\in\mathbb{Z}$

Das ermöglicht die Formulierung einer anderen Funktion, die ebenfalls für natürliche Zahlen den nächsten Wert der Collatz-Iteration liefert, aber für sämliche reellen und sogar sämtliche komplexen Werte definiert ist, nämlich:

$f(z)=(1+\cos(\pi z))\frac{z}{4}+(1-\cos(\pi z))\frac{3z+1}{2}$

Natürlich lässt sich der Ausdruck, der bei diesem Ansatz herauskommt, ein bisschen vereinfachen. Als stinkefauler Mensch (der gerade nicht sein sonst für solche Aufgaben benutztes Maxima zur Verfügung hat) habe ich dafür Wolfram Alpha verwendet und die folgende alternative Form erhalten:

$f(z)=\frac{1}{4}(7z-(5z+2)\cos(\pi z)+2)$

Obwohl diese Funktion sehr anders aussieht als die eingangs erwähnte Collatz-Iteration, ist sie durch recht einfache Umformungen aus dieser hervorgegangen und liefert für jede natürliche Zahl (ja, sogar für jede ganze Zahl) das jeweils nächste Folgeglied. Darüber hinaus ist sie auf der gesamten komplexen Ebene definiert.

Und das Fraktal?

Natürlich lässt sich diese Funktion bequem in einem Fraktalgenerator verwenden, um nach so viel abstrakter Betrachtung wieder ein paar „hübsche Bilder“ zu bekommen. Da bei der Iteration schon für relativ kleine Zahlen große Zwischenwerte auftreten können, muss der Fluchtradius sehr groß gemacht werden. Wenn dies beachtet wird (im folgenden Bild habe ich den Fluchtradius auf eine Million gesetzt und 100000 Iterationen untersucht), erhält man eine Karte des Iterationsverhaltens der komplexen Collatz-Iteration (zum Vergrößern das Vorschaubild klicken)…

…in der alle Startwerte schwarz gefärbt sind, die in einer zyklischen Folge enden. Der große „Gnubbel“ in der Mitte liegt im Bereich um 1. Längs der reellen Achse ist ein langer Ausläufer, auf dem sich für jede natürliche Zahl ein kleinerer schwarzer Bereich befindet, der anzeigt, dass die Zahl in der Iteration 4, 2, 1 endet. Bei dieser Verallgemeinerung gibt es jedoch auch weitere Werte, die nicht über alle Grenzen wachsen. Diese befinden sich teils auf der reellen Achse, sie ragen aber auch von den kleinen „Gnubbeln“ auf der reelen Achse ausgehend in den komplexen Wertebereich hinein. Dass es sich dabei wirklich um ein Fraktal unendlicher Filigranität in der Wiederkehr seiner Grundformen handelt, zeigt sich beim Hineinzoomen in eine der Inseln im komplexen Bereich:

Die Einfärbung in diesem Fraktalzoom ist übrigens experimentell und ich versprach mir von ihr, dass sie hilfreich wäre, um einen Eindruck in die Struktur des Fraktales zu gewinnen. Sie war nicht hilfreich.

Aber ist es nicht faszinierend, in welchen scheinbar fernliegenden Zusammenhängen ein Fraktal auftauchen kann.

Noch mehr Fraktale

Natürlich ist diese naheliegende Untersuchung auch von anderen gemacht worden. Nathaniel Johnston hat eine weitere Modifikation dieser Funktion vorgenommen, so dass der Punkt (1;0) zum Fixpunkt wird, statt in die Iteration 1, 4, 2, 1 zu führen:

$f(z)=\frac{z}{4}(1+\cos(\pi z))+\frac{3z+1}{16}(1-\cos(\pi z))(3-\sqrt{2}\cos((2z-1)\frac{\pi}{4}))$

Dabei entsteht ein anderes hochinteressantes und teilweise sehr ansprechendes Fraktal. Vielleicht werde ich in den nächsten Tagen einige Zooms rendern, aber hier gibt es jetzt erstmal zwei hübsche Bilder (beide mit experimentellen Einfärbungen).

¹Dies ist eine der Situationen, in denen ich wordpress.com wirklich dankbar dafür bin, dass ich hier LaTeX einbetten kann — denn dieser Audruck kann nicht in HTML gesetzt werden und die Browser beherrschen aus mir völlig unverständlichen Gründen immer noch kein MathML.

²Pedanten mögen einwenden, dass diese Funktion eine viel größere Definitionsmenge als die rationalen Zahlen haben kann. Sie haben damit recht. Aber das hier ist ein Blog über Fraktale, mehr nicht…

Fraktale Welten

Computer verwandeln Zahlen in Schönheit

Archiv der Kategorie: Formeln

Quetschglut

Tangensblüte

Zweite Blüte

Besucher

Collatz Zwei

Das Collatz-Fraktal

Bewerten:

Bewerten:

Bewerten:

Bewerten:

Bewerten:

Bewerten: