Calkin–Wilf-Glied

Der Calkin–Wilf-Baum ist ein vollständiger Binärbaum, dessen Knoten genau die positiven rationalen Zahlen sind, jede einmal und in gekürzter Form. Liest man den Baum ebenenweise (oder indiziert man die Knoten in der natürlichen Binärheap-Reihenfolge, die dem Binärpfad einer positiven ganzen Zahl n entspricht), erhält man eine berühmte Aufzählung von Q+: die Calkin–Wilf-Folge. Index eins ist der Wurzelbruch eins zu eins; jeder spätere Index folgt einem eindeutigen Links-Rechts-Pfad, codiert durch die Binärziffern von n nach dem führenden Eins-Bit. Studierende der enumerativen Kombinatorik, der diskreten Mathematik und der rationalen Rekonstruktion brauchen ein schnelles Orakel, das Zähler und Nenner für einen beliebigen sicheren Index liefert, ohne den ganzen Baum aufzubauen. Diese Fähigkeit akzeptiert eine positive ganze Zahl n, folgt diesem Pfad mit wenigen ganzzahligen Additionen und liefert den gekürzten Bruch a/b zusammen mit einer Pfadzeichenkette und einer kurzen Formel.

Was die Calkin–Wilf-Aufzählung ist und wie der n-te Bruch definiert wird

Neil Calkin und Herbert Wilf popularisierten einen bemerkenswert einfachen Binärbaum positiver Rationalzahlen: die Wurzel ist eins zu eins; das linke Kind eines Bruchs a zu b ist a zu (a plus b); das rechte Kind ist (a plus b) zu b. Jede positive rationale Zahl erscheint genau einmal, bereits in gekürzter Form, sodass der Baum zugleich eine Aufzählung von Q+ und eine kanonische reduzierte Form jedes Werts ist.

Der natürliche 1-basierte Index n beschriftet Knoten nach ihrer Position in der vollständigen Binärheap-Ordnung: n gleich eins ist die Wurzel, n gleich zwei ist das linke Kind der Wurzel (ein Halb), n gleich drei ist das rechte Kind (zwei zu eins), n gleich vier ist das Enkelkind links-links (ein Drittel) und so weiter. Äquivalent schreiben Sie n binär, streichen das führende Eins-Bit, das stets die Wurzel markiert, und deuten jedes verbleibende Bit vom höchst- zum niederwertigsten als Zug: null bedeutet links, eins bedeutet rechts.

Nach diesen Zügen halten Sie den eindeutigen gekürzten Bruch a/b an diesem Knoten. Eine klassische Identität verknüpft diesen Gang mit der Sternschen diatomischen Folge s: der Calkin–Wilf-Bruch am Index n ist s(n) zu s(n plus eins). Dieser Endpunkt implementiert den direkten Baumgang statt einer separaten Stern-Tabelle, doch die Antworten stimmen für jedes positive n mit dieser Identität überein.

Weil jeder Schritt nur zwei positive ganze Zahlen addiert, ist der Algorithmus deterministisch, speicherschonend und frei von Gleitkomma-Rundung — ideal für Hausaufgaben-Orakel, LMS-Plugins und Forschungsnotebooks, die exakte Zähler und Nenner statt genäherter Dezimalzahlen brauchen.

Eingabevertrag, Antwortfelder und Fehlerverhalten

Werte unter eins — einschließlich null und jedes negativen Index — scheitern mit einer klaren Meldung, dass der Calkin–Wilf-Index mindestens eins sein muss; diese Validierungsfehler werden nicht berechnet. Bei Erfolg spiegelt der Körper n wider, liefert numerator und denominator als positive ganze Zahlen, fraction als Anzeigezeichenkette Zähler Schrägstrich Nenner, formula als kurze Wiederholung der Wurzel- und Kindregeln plus der Binärpfadregel und path als die Buchstaben L und R für die Züge nach der Wurzel (oder das Wort root, wenn n eins ist).

Beispiel: n gleich eins ergibt den Bruch eins Schrägstrich eins und path root. Beispiel: n gleich fünf hat die Binärzahl eins null eins, Pfadbits null dann eins, also links dann rechts von eins zu eins ergibt drei zu zwei, path LR. Beispiel: n gleich sieben hat path RR und Bruch drei zu eins.

Clients, die nur die rationale Zahl brauchen, können fraction oder das Integer-Paar lesen; Tutoren können path neben der Antwort zeigen, damit Lernende jeden Links- und Rechtsschritt prüfen. Die Implementierung ist reine Parse-Stufe A: kein Netz, keine Modell-Token, kein Dateisystem, und dasselbe Modul kann im kostenlosen Browserpfad und auf dem Edge-Worker ohne abweichende Ergebnisse laufen.

Wo der Calkin–Wilf-Term nützlich ist

Forschungsnotebooks, die hyperbinäre Darstellungen, Demos der Minkowski-Fragezeichenfunktion oder rationale Sampling-Strategien erkunden, brauchen oft ein schnelles exaktes Orakel für den n-ten Calkin–Wilf-Bruch bei konstruktionsbedingt gekürztem Ergebnis. Ingenieur- und Bildungswerkzeuge, die eindeutige positive Test-Rationalzahlen für eigenschaftsbasierte Tests erzeugen, können aufeinanderfolgende Glieder per Index abrufen, statt zufällige ungekürzte Paare zu erfinden, die später eine gcd-Bereinigung brauchen. Halten Sie Anfragen klein, dokumentieren Sie, dass n eine positive ganze Zahl ab eins ist, und behandeln Sie numerator, denominator und fraction als kanonische Antwortfelder für automatische Prüfungen.