Jeder positive Bruch in gekürzter Form erscheint in diesem Baum exakt einmal. Die Regel, die ihn wachsen lässt, ist so klein, dass man sie auf einen Siegelstempel drucken könnte — und doch baut sie die gesamte Welt der rationalen Zahlen geordnet, einzigartig und vollständig. Zehn Kapitel führen durch seine Geometrie, seine Nachbarn und sein Echo im Euklidischen Algorithmus, im Fibonacci-Strom und in der fusc-Folge.
Zwischen zwei Brüchen a/b und c/d liegt der Mediant: nicht das arithmetische Mittel, sondern die Summe der Zähler über der Summe der Nenner.
a/b ⊕ c/d = (a+c) / (b+d)Trivial zu rechnen — und doch: wenn a/b und c/d Nachbarn im Stern-Brocot-Baum sind (also bc − ad = 1), ist ihr Mediant wieder gekürzt. Der Baum erzeugt nie einen Bruch, der gekürzt werden könnte.
Rechts: zwei editierbare Brüche, ihr Mediant rot. Probiere 1/1 ⊕ 1/0 = 2/1, oder 22/7 ⊕ 333/106.Der Stern-Brocot-Baum enthält jeden gekürzten positiven Bruch — und keinen zweimal. Gib einen Bruch ein: der Pfad von der Wurzel zu ihm ist eindeutig. Eine Folge aus L's und R's. Die Länge des Pfads wächst mit der Kürze des Bruchs — und ist genau die Summe der Teilbrüche seiner Kettenbruchentwicklung.
q = [a0; a1, a2, …] ↔ Ra0La1Ra2…Probiere bekannte Brüche: 22/7 (π-Näherung), 355/113 (bessere), 3/5, 7/4. Der Pfad unten zeigt, wie du dich dorthin bewegst.
Stern-Brocot erzeugt jede Generation per Mediant aus Nachbarn. Calkin-Wilf nimmt jeden Knoten p/q und gibt ihm die Kinder p/(p+q) links und (p+q)/q rechts. Unterschiedliche Regel — gleiche Menge: jeder positive gekürzte Bruch erscheint auch hier genau einmal.
Calkin-Wilf-Kinder von p/q: p/(p+q) und (p+q)/qDie Folge a(n), genannt fusc oder Stern's diatomische Reihe, ist rekursiv definiert:
a(0)=0, a(1)=1Und hier der Witz: die n-te Rationale im Calkin-Wilf-Baum ist einfach a(n) / a(n+1). Die Folge ist also ein Linearverkehr durch den Baum — ohne Baum.
Der Plot rechts zeigt die ersten 256 Werte. Die Zacken liegen exakt an Fibonacci-Indizes — dort wird die Folge extrem. An Potenzen von 2 kehrt sie immer zu 1 zurück.
Hovere Punkte im Plot um den Wert zu sehen. Die Tabelle darunter listet 1..16 explizit.Nimm einen Pfad, der im Zickzack geht — L R L R L R … — und lies die Brüche an jedem Knoten. Du bekommst Fibonacci-Verhältnisse:
1/1 → 1/2 → 2/3 → 3/5 → 5/8 → 8/13 → 13/21 → 21/34 → …Die Zähler sind F(n), die Nenner F(n+1). Ihr Verhältnis nähert sich dem Goldenen Schnitt φ = 1/(1+1/(1+1/(1+…))) — der Kettenbruch besteht nur aus Einsen, und das entspricht genau einem Pfad aus lauter Alternierungen.
Die Kettenbruchentwicklung eines Bruchs ist der Euklidische Algorithmus in Verkleidung. Für 355/113:
355 = 3 · 113 + 16Die Quotienten 3, 7, 16 sind die Koeffizienten der Kettenbruchentwicklung [3; 7, 16] — und exakt die Längen der aufeinanderfolgenden L/R-Blöcke im Stern-Brocot-Pfad zu 355/113. Drei Schritte rechts, sieben links, sechzehn rechts.
Fn listet alle gekürzten Brüche p/q mit 0 ≤ p/q ≤ 1 und q ≤ n, sortiert nach Grösse. Zwischen zwei konsekutiven Farey-Brüchen a/b und c/d gilt immer bc − ad = 1. Ihre Mediant taucht in Fb+d zum ersten Mal auf — und steht genau zwischen ihnen.
Eine hyperbinäre Darstellung einer Zahl n ist eine Summe von Zweierpotenzen (20, 21, 22, …), bei der jede Potenz höchstens zweimal vorkommen darf — also 0, 1 oder 2 mal.
9 = 8 + 1 = 4 + 4 + 1 = 4 + 2 + 2 + 1Drei Darstellungen. Und tatsächlich: a(10) = 3. Die Folge zählt also etwas Konkretes, Kombinatorisches. Das ist keine willkürliche Rekursion — sie zählt Bausätze.
Rechts: alle hyperbinären Darstellungen für deine Wahl von n. Die Anzahl steht oben als a(n+1).Ist x = p/q der aktuelle Bruch, dann ist der nächste:
next(x) = 1 / ( 2·⌊x⌋ + 1 − x )Das ist Newmans Formel. Sie iteriert durch die gesamte Calkin-Wilf-Folge — 1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, … — ohne Baum, ohne Rekursion. Nur Floor-Funktion, Subtraktion, Kehrwert.
Damit wird die gesamte Menge der positiven Rationalen zu einer Bahn eines dynamischen Systems — Startwert 1, Iterationsregel oben. Jede positive gekürzte Rationale erscheint genau einmal, in exakt der Reihenfolge, in der Calkin-Wilf den Baum zeilenweise liest.
Rechts: die ersten N Iterationen per Button. Beobachte, wie der Zeiger durch die Rationalen "springt" — ohne je zu wiederholen.