Sternsche diatomische / Stern–Brocot-Folge

Sterns diatomische Folge ist eine klassische ganzzahlige Folge, eng verknüpft mit dem Stern–Brocot-Baum positiver Rationalzahlen. Sie wird durch zwei Startwerte und eine Teilungsregel nach der Parität des Index definiert: s von null ist null, s von eins ist eins; wenn der Index gerade und gleich zwei k ist, gleicht das Glied s von k; wenn er ungerade und gleich zwei k plus eins ist, gleicht das Glied s von k plus s von k plus eins. Die resultierende Liste beginnt null, eins, eins, zwei, eins, drei, zwei, drei, eins, vier, drei, fünf, zwei, fünf, drei, vier und setzt sich mit der bemerkenswerten Eigenschaft fort, dass aufeinanderfolgende Glieder stets teilerfremd sind.

So entsteht die Folge

Die Folge beginnt mit zwei Startwerten: s(0) ist 0 und s(1) ist 1. Jedes weitere Glied hängt nur davon ab, ob der Index gerade oder ungerade ist. Bei einem geraden Index übernehmen Sie einfach den Wert beim halben Index. Bei einem ungeraden Index addieren Sie die beiden Glieder um die Hälfte herum, also s(k) und s(k + 1). So entstehen die ersten Glieder 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4. Weil der Index bei jedem Schritt etwa halbiert wird, braucht selbst ein großer Index nur wenige Schritte, und da nur ganze Zahlen addiert werden, entsteht kein Rundungsfehler.

Was die Folge besonders macht

Zwei benachbarte Glieder sind immer teilerfremd. Liest man die Quotienten aufeinanderfolgender Glieder, erscheint jede positive rationale Zahl genau einmal, bereits gekürzt. Diese Aufzählung entspricht dem Stern-Brocot-Baum, Ebene für Ebene gelesen. Im Unterricht zeigt die Folge, wie zwei einfache Regeln alle Brüche ordnen, und beim Training für Programmierwettbewerbe dient sie als zuverlässige Kontrolle eigener Lösungen. Beachten Sie, dass die Zählung bei s(0) beginnt und negative Indizes nicht erlaubt sind.

Was Sterns diatomische Folge ist und wie die gerade/ungerade Rekursion funktioniert

Beginnen Sie mit den Keimen s von null gleich null und s von eins gleich eins. Für jeden späteren Index hängt die Regel nur von der Parität ab. Ist n gerade, schreiben Sie n gleich zwei k und setzen s von n gleich s von k — derselbe Wert erscheint bei halb so großem Index.

Ist n ungerade, schreiben Sie n gleich zwei k plus eins und setzen s von n gleich s von k plus s von k plus eins. Einige Schritte abrollen liefert null, eins, eins, zwei, eins, drei, zwei, drei, eins, vier, drei, fünf, zwei, fünf, drei, vier, eins, fünf, vier, sieben, drei und so weiter.

Benachbarte Paare sind stets teilerfremd, jede positive rationale Zahl erscheint genau einmal als aufeinanderfolgendes Verhältnis s von m über s von m plus eins beim Durchlaufen der Folge, und diese Aufzählung ist genau der Stern–Brocot-Baum, der in der Breite abgeflacht ist. Dieselbe Rekursion heißt je nach Darstellung manchmal Calkin–Wilf- oder Stern–Brocot-Folge; dieses Werkzeug nutzt die standardmäßige diatomische Form mit s von null gleich null. Weil jeder Schritt exakte Ganzzahladdition oder reines Index-Halbieren ist, gibt es keinen Rundungsfehler und keine Abhängigkeit von Wanduhrzeit oder Zufallskeimen.

Wenn Sie nur ein einzelnes Glied brauchen, senden Sie den Index n; die Antwort echoiert n, den Stern-Wert, eine kurze Formelzeichenkette für die geraden und ungeraden Fälle und die vollständige Beschreibung der Rekursionskeime, damit Bewerter und Studierende von Hand oder auf Papier nachrechnen können.

Praktische Tipps, Grenzen und verwandte Suchen

Beim Benoten prüfen Sie sowohl das Feld stern als auch die Formelzeichenkette, damit eine falsche Rekursion oder eine Fibonacci-Verwechslung leicht zu diagnostizieren ist. Geschwisterseiten in diesem Kit decken andere Folgen- und Figurierten-Absichten wie Padovan-Zahlen, Dreieckszahlen, Polygonalzahlen und Summen arithmetischer Reihen ab; diese Seite ist speziell für Personen, die nach einem Stern–Brocot-Folgenrechner, sternschen diatomischen Zahlen oder dem n-ten Glied von Sterns Folge suchen.

Behandeln Sie die ganze Zahl nicht allein als Blackbox — koppeln Sie sie beim Unterrichten mit den dokumentierten geraden und ungeraden Regeln, damit alternative OEIS-Offsets nicht mit der hier verwendeten Konvention s von null gleich null verwechselt werden. Decken Sie n bei einer Milliarde, damit jede Anfrage beschränkt bleibt; brauchen Sie größere Indizes, wechseln Sie zu Big-Integer-Werkzeugen außerhalb dieses kostenlosen Parse-Pfads.