Quelltext der Seite Stern-Brocot-Folge

Die '''Stern-Brocot-Folge''' (A002487 in OEIS<ref>[http://oeis.org/search?q=A002487 A002487] ist die Bezeichnung der Zahlenfolge in der ''On-Line Encyclopedia of Integer Sequences''</ref>), auch als „diatomische Folge von Stern und Brocot“ oder „Stern-Sequenz“ bekannt, ist eine Folge ganzer Zahlen, die unabhängig vom Mathematiker [[Gotthold Eisenstein]]<ref name="eisenstein">{{Literatur
 |Autor=G. Eisenstein
 |Hrsg=[[American Mathematical Society]]
 |Titel=Mathematische Werke
 |Band=1
 |Verlag=AMS Chelsea Publishing Series
 |Datum=1989
 |ISBN=0-8284-1280-4
 |Seiten=710–711
 |Online={{Google Buch
 |BuchID=bXacGQjSYKwC
 |Seite=711}}}}<br />{{Literatur
 |Autor=G. Eisenstein
 |Hrsg=[[Preußische Akademie der Wissenschaften]]
 |Titel=Bericht über die zur Bekanntmachung geeigneten Verhandlungen der Königl. Preuss. Akademie der Wissenschaften zu Berlin
 |Datum=1850
 |Seiten=41–42
 |Kommentar=PDF-Seite 48/49
 |Online=[https://www.forgottenbooks.com/fr/download/BerichtUberdiezurBekanntmachungGeeignetenVerhandlungenderKoniglPreussAkademieder_11042176.pdf forgottenbooks.com]
 |Format=PDF
 |KBytes=}}</ref> und dem [[Liste bedeutender Uhrmacher (chronologisch)#1801–1850|Uhrmacher Achille Brocot]]<ref name="brocot">{{Literatur
 |Autor=A. Brocot
 |Titel=Berechnung von Zahnrädern durch Annäherung, neue Methode
 |Sammelwerk=Revue Chronométrique
 |Band=3
 |Datum=1861
 |Seiten=186–194
 |Sprache=fr
 |Originaltitel=Calcul des rouages par approximation, nouvelle méthode
 |Online=[https://www.eyrolles.com/BTP/Livre/calcul-des-rouages-par-approximation-nouvelle-methode-par-achille-brocot--9782016164440/ eyrolles.com]}}</ref>
entdeckt und vom Mathematiker [[Moritz Stern]]<ref name="stern">{{Literatur
 |Autor=[[Moritz Stern|M. Stern]]
 |Titel=Ueber eine zahlentheoretische Funktion
 |Sammelwerk=[[Journal für die reine und angewandte Mathematik]]
 |Band=55
 |Nummer=28
 |Datum=1858
 |Seiten=193–220
 |Online=[http://www.digizeitschriften.de/resolveppn/GDZPPN002150301 digizeitschriften.de]}}</ref> genauer untersucht wurde.

Sie startet mit dem Zahlenpaar s<sub>0</sub>&nbsp;=&nbsp;0 und s<sub>1</sub>&nbsp;=&nbsp;1. Zusätzliche Glieder der Folge ergeben sich, indem fortgesetzt die bisherige Folge kopiert und in der Kopie zwischen je zwei Glieder deren Summe eingefügt wird. Die ersten 33 Glieder der Folge sind

: 0; 1; 1, 2; 1, 3, 2, 3; 1, 4, 3, 5, 2, 5, 3, 4; 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5; 1 …

wobei auch die folgende Stufentafel (Beginn der Folge mit s<sub>1</sub> und Unterteilung bei den Semikolons „;“) zur besseren Darstellung verschiedener Eigenschaften benutzt wird:
{{Anker|Stufentafel}}
{| style="text-align: right; font-family: monospace; line-height: 1em; width: 600px;"
|-
|style="width:5%;"| 1
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|style="width:5%;"|
|-
| 1
| 2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|-
| 1
| 3
| 2
| 3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|-
| 1
| 4
| 3
| 5
| 2
| 5
| 3
| 4
|
|
|
|
|
|
|
|
|
|
|
|
|-
| 1
| 5
| 4
| 7
| 3
| 8
| 5
| 7
| 2
| 7
| 5
| 8
| 3
| 7
| 4
| 5
|
|
|
|
|-
| 1
| 6
| 5
| 9
| 4
| 11
| 7
| 10
| 3
| 11
| 8
| 13
| 5
| 12
| 7
| 9
| 2
| 9
| 7
| …
|-
| 1
| 7
| 6
| 11
| 5
| 14
| 9
| 13
| 4
| 15
| 11
| 18
| 7
| 17
| 10
| 13
| 3
| 14
| 11
| …
|-
| 1
| 8
| 7
| 13
| 6
| 17
| 11
| 16
| 5
| 19
| 14
| 23
| 9
| 22
| 13
| 17
| 4
| 19
| 15
| …
|-
| 1
| 9
| 8
| 15
| 7
| 20
| 13
| 19
| 6
| 23
| 17
| 28
| 11
| 27
| 16
| 21
| 5
| 24
| 19
| …
|}

siehe [[#Eigenschaften der Stufentafel]]. Die Stern-Brocot-Folge weist einige bemerkenswerte mathematische Besonderheiten auf:
* Aufeinander folgende Zahlen der Folge sind einander [[Teilerfremdheit|teilerfremd]] und jedes mögliche Paar positiver, teilerfremder, ganzer Zahlen kommt genau einmal vor; das erlaubt mit ihr die Menge der rationalen Zahlen abzuzählen, siehe [[#Abzählung der rationalen Zahlen]].
* Die Folge zählt ungerade Glieder im Pascal’schen Dreieck, Wege in Graphen oder Darstellungsweisen von Hyperbinärzahlen, siehe [[#Zähleigenschaften]].
* Mit der Folge kann die am besten passende Zahnradpaarung für ein bestimmtes [[Übersetzung (Technik)#Mechanik|Übersetzungsverhältnis]] gefunden werden, was A. Brocot als erster erkannte,<ref>Die Anwendung wird beispielsweise beschrieben in: {{Internetquelle
 |autor=David Austin
 |url=http://www.ams.org/samplings/feature-column/fcarc-stern-brocot
 |titel=Trees, Teeth, and Time: The mathematics of clock making
 |hrsg=[[American Mathematical Society]]
 |datum=2018-11-12
 |sprache=en
 |abruf=2015-05-15}}</ref> siehe [[#Stern-Brocot-Baum]].
* Die größten Glieder in jeder Zeile der Stufentafel bilden die [[Fibonacci-Folge]].
* Das Vorkommen einer Zahl in der Stufentafel ergibt sich aus der [[Eulersche φ-Funktion|Euler’schen φ-Funktion]].
* Die Position eines Zahlenpaars (a,b) in der Stufentafel hängt mit der [[Kettenbruch]]&shy;entwicklung des Bruchs a/b zusammen.

Diese und andere Eigenschaften sowie ihr relativ geringer Bekanntheitsgrad haben [[Jean-Paul Delahaye]] veranlasst, die Folge „die verkannte Schwester der Fibonacci-Folge“ zu nennen.<ref name="delahaye">{{Literatur
 |Autor=[[Jean-Paul Delahaye]]
 |Titel=Die verkannte Schwester der Fibonacci-Folge
 |Sammelwerk=[[Spektrum der Wissenschaft]]
 |Datum=2015-05
 |Seiten=64–69
 |Online=[http://www.spektrum.de/artikel/1338241 spektrum.de]}}</ref>

== Geschichte ==
[[Gotthold Eisenstein]] veröffentlichte im Februar 1850 eine Arbeit über eine Zahlenreihe,
{{Zitat
 |Text=welche aus zwei gegebenen Zahlen m und n ohne gemeinschaftlichen Theiler auf die Art entspringt, daß man fortgesetzt zwischen je zwei bereits erhaltene Zahlen ihre Summe schreibt.
 |Autor=G. Eisenstein
 |ref=<ref name="eisenstein" />}}

Er konnte einige der [[#Eigenschaften der Stufentafel]] angeben und regte M. Stern schon im Januar 1850 dazu an, die Reihe auch zu untersuchen. Stern entsprach 1858 mit seiner Arbeit, wie er schrieb, „leider zu spät, dem Wunsche meines unvergeßlichen Freundes;“<ref name="stern" />{{rp|193}} Eisenstein starb 1852 im Alter von nur 29 Jahren. Der Aufsatz von Brocot datiert auf das Jahr 1861.<ref name="brocot" />

== Definition der Stern-Brocot-Folge ==
[[Datei:Suite Diatomique Stern graphe.png|mini|Abb. 1: Glieder der Folge aufgetragen über ihre Stelle in der Folge zeigen fraktale Strukturen. Die tiefsten Einschnitte liegen bei Zweierpotenzen.]]

Die Stern-Brocot-Folge s<sub>0</sub>,  s<sub>1</sub>, s<sub>2</sub>,… ist durch das [[Rekursion|rekursive]] Bildungsgesetz

{|
|s<sub>2n</sub>||= s<sub>n</sub>
|-
| s<sub>2n+1</sub>||= s<sub>n</sub> + s<sub>n+1</sub>
|}

mit den Anfangswerten
: s<sub>0</sub> = 0 &nbsp;&nbsp;&nbsp;und&nbsp;&nbsp;&nbsp; s<sub>1</sub> = 1

definiert. Das bedeutet in Worten:
* Die Folge beginnt mit null und eins.
* Glieder mit einer geraden Nummer sind gleich dem Glied mit der halben Nummer und
* Glieder mit einer ungeraden Nummer sind gleich der Summe der Glieder mit der halben Nummer ihres Vorgängers und Nachfolgers. Anders ausgedrückt zerlegt man die ungerade Nummer in zwei Teile, die so eng benachbart sind wie überhaupt möglich: eine Zahl und die daran anschließende Zahl. Das Folgenglied ist dann die Summe der Glieder mit diesen Teilnummern.<ref name="delahaye" />{{rp|64}} Dieses Gesetz ähnelt dem der [[Fibonacci-Folge]].

Das Bildungsgesetz für die Glieder an ungeraden Stellen kann wegen s<sub>2n</sub>&nbsp;=&nbsp;s<sub>n</sub> umgeformt werden in

: s<sub>2n+1</sub> = s<sub>n</sub> + s<sub>n+1</sub> = s<sub>2n</sub> + s<sub>2(n+1)</sub> = s<sub>2n</sub> + s<sub>2n+2</sub>

{{Anker|Entwicklung}}
Das entspricht dem eingangs angegebenen Rezept, aus dem Zahlenpaar (0,1) zusätzliche Glieder zu generieren, indem fortgesetzt die bisherige Folge kopiert und in der Kopie zwischen je zwei Glieder deren Summe eingefügt wird; M. Stern nannte das die ''Entwicklung'' (0,1).<ref name="stern" />{{rp|194}}

Die ersten 100 Glieder der Folge sind:{{Anker|s0-s99}}

{| class="wikitable" style="text-align:right;"
!n
|0||1||2||3||4||5||6||7||8||9||10||11||12||13||14||15||16||17||18||19
|-
!s<sub>n</sub>
|0||1||1||2||1||3||2||3||1||4||3||5||2||5||3||4||1||5||4||7
|- class="hintergrundfarbe2"
|colspan="21" style="border-left: 1px solid #ffffff;border-right: 1px solid #ffffff;"|
|-
!n
|20||21||22||23||24||25||26||27||28||29||30||31||32||33||34||35||36||37||38||39
|-
!s<sub>n</sub>
|3||8||5||7||2||7||5||8||3||7||4||5||1||6||5||9||4||11||7||10
|- class="hintergrundfarbe2"
|colspan="21" style="border-left: 1px solid #ffffff;border-right: 1px solid #ffffff;"|
|-
!n
|40||41||42||43||44||45||46||47||48||49||50||51||52||53||54||55||56||57||58||59
|-
!s<sub>n</sub>
|3||11||8||13||5||12||7||9||2||9||7||12||5||13||8||11||3||10||7||11
|- class="hintergrundfarbe2"
|colspan="21" style="border-left: 1px solid #ffffff;border-right: 1px solid #ffffff;"|
|-
!n
|60||61||62||63||64||65||66||67||68||69||70||71||72||73||74||75||76||77||78||79
|-
!s<sub>n</sub>
|4||9||5||6||1||7||6||11||5||14||9||13||4||15||11||18||7||17||10||13
|- class="hintergrundfarbe2"
|colspan="21" style="border-left: 1px solid #ffffff;border-right: 1px solid #ffffff;"|
|-
!n
|80||81||82||83||84||85||86||87||88||89||90||91||92||93||94||95||96||97||98||99
|-
!s<sub>n</sub>
|3||14||11||19||8||21||13||18||5||17||12||19||7||16||9||11||2||11||9||16
|}

Eisenstein und M. Stern betrachteten auch die Entwicklung zweier beliebiger [[Natürliche Zahl|natürlicher Zahlen]] (m,n). Wenn diese nicht teilerfremd sind, dann enthalten alle Glieder der Folge deren [[Größter gemeinsamer Teiler|größten gemeinsamen Teiler]] k. Werden alle Glieder der Folge durch k geteilt, entsteht eine Folge mit teilerfremdem m und n, und nur diese brauchen untersucht zu werden. Die Entwicklung mit teilerfremdem m und n ist als Bruchstück in der Entwicklung (0,1) enthalten, denn in dieser kommen alle möglichen Paare teilerfremder Zahlen vor. Allerdings treten in diesen Bruchstücken nicht mehr alle positiven Zahlen auf, sondern nur solche, die als Summe ganzzahliger Vielfache von m und n darstellbar sind.<ref name="stern" />{{rp|210}}

Die Stern-Brocot-Folge wurde auch auf [[Polynom]]e verallgemeinert.<ref name="delahaye" />{{rp|69}}

== Quantitative Eigenschaften ==
=== Berechnung der Folgenglieder ===
Neben dem Bildungsgesetz aus der [[#Definition der Stern-Brocot-Folge]] gibt es weitere bemerkenswerte Methoden zur Berechnung von Folgengliedern. Der [[#Zusammenhang mit dem Pascal’schen Dreieck]] führt auf das explizite Bildungsgesetz
:<math>\mathsf{s_n}
=\sum_\mathsf{2i+j=n-1}\left(
\begin{pmatrix}\mathsf{i+j}\\\mathsf i\end{pmatrix}\mod2\right)
=\sum_{\mathsf j=1}^{\left[\frac{\mathsf{n+1}}2\right]}
\left(\begin{pmatrix}\mathsf{n-j}\\\mathsf j-1\end{pmatrix}\mod2\right)
</math>

worin die [[Gaußklammer]] [·] auf die nächste Ganzzahl abrundet und „mod 2“ den [[Division mit Rest|Rest bei der Division]] durch zwei gibt, also eins bei ungeraden Zahlen und null bei geraden.<ref name="delahaye" /> Für große n erfordert diese Darstellung die Handhabung sehr großer Zahlen; beispielsweise lautet der [[Binomialkoeffizient]] <math>\begin{pmatrix}60\\30\end{pmatrix}=114.449.595.062.769.120</math>.

Die folgenden Methoden basieren auf der mehrfachen Anwendung einer Berechnungsvorschrift:
* Nach dem Bildungsgesetz ist s<sub>k</sub>&nbsp;=&nbsp;s<sub>k/2</sub>, wenn k gerade, oder s<sub>k</sub>&nbsp;=&nbsp;s<sub>(k-1)/2</sub>&nbsp;+&nbsp;s<sub>(k+1)/2</sub>, wenn k ungerade ist. Durch fortgesetzte Anwendung dieser Formeln werden alle benötigten Folgenglieder und schließlich s<sub>n</sub> berechnet. Beispielsweise ist
:: [[#s0-s99|s<sub>6</sub>]] = s<sub>3</sub> = s<sub>1</sub> + s<sub>2</sub> = s<sub>1</sub> + s<sub>1</sub> = 2
: Die Anzahl der zu berechnenden Glieder wächst mit dem [[Logarithmus]] von n.
* Aus der Formel für [[#Der nächste Bruch|#den nächsten Bruch]] leitet sich für das auf a, b folgende Glied
:: c = a + b − 2r
: ab, wo r = a − [a/b]·b der [[Division mit Rest|Rest bei Division]] von a durch b ist (sodass a−r durch b teilbar und 0&nbsp;≤&nbsp;r&nbsp;<&nbsp;b ist, [·] ist die Gaußklammer). Das Glied s<sub>n</sub> ergibt sich aus n−1 maliger Anwendung der Formel auf s<sub>0</sub> und s<sub>1</sub>.
* Für n > 1 besteht der Zusammenhang
:: s<sub>n</sub> = k<sub>n−1</sub>s<sub>n−1</sub> − s<sub>n−2</sub>
: Darin ist k<sub>j</sub> die größte ungerade Zahl für die j durch 2<sup>(k<sub>j</sub>−1)/2</sup> teilbar ist.<ref>[http://oeis.org/search?q=A037227 A037227] in [[On-Line Encyclopedia of Integer Sequences|OEIS]]</ref><ref name="glasby">{{Literatur |Autor=Stephen P. Glasby |Hrsg=[[Mathematical Association of America]] |Titel=Aufzählung der rationalen Zahlen von links nach rechts |Sammelwerk=[[American Mathematical Monthly]] |Band=118 |Nummer=9 |Datum=2011 |Seiten=830–835 |Sprache=en |Originaltitel=Enumerating the rationals from left to right |arXiv=1011.2823 |DOI=10.4169/amer.math.monthly.118.09.830}}</ref>

Weitere Formeln können aus den [[#Zähleigenschaften]] der Stern-Brocot-Folge abgeleitet werden.

=== Eigenschaften der Folge ===

Für die Glieder der Stern-Brocot-Folge gilt:<ref name="stern" />
* Keine zwei geraden Glieder stehen hintereinander.
* Bei drei aufeinander folgenden Gliedern ist nicht nur die mittlere von ihnen ungerade; es sind aber auch nicht alle drei ungerade.
* Die Summe der beiden Nachbarn eines Gliedes ist durch selbiges teilbar.
* Das auf a,b folgende Paar b,c ergibt sich aus b/c&nbsp;=&nbsp;1/(1+2[a/b]-a/b), wo die [[Gaußklammer]] [&nbsp;·&nbsp;] auf die nächste Ganzzahl abrundet.<ref name="delahaye" />{{rp|69}}
* Zwei aufeinander folgende Glieder sind teilerfremd.
* Die Folge enthält jede Natürliche Zahl und alle möglichen Paare einander teilerfremder Zahlen.
* Ein bestimmtes Zahlenpaar kommt nur genau einmal in der Folge vor.

Die letzten drei Aussagen bedeuten, dass die Brüche s<sub>0</sub>/s<sub>1</sub>,  s<sub>1</sub>/s<sub>2</sub>, s<sub>2</sub>/s<sub>3</sub>, s<sub>3</sub>/s<sub>4</sub>, s<sub>4</sub>/s<sub>5</sub>,… alle nicht negativen [[Rationale Zahl|rationalen Zahlen]] ''ohne Zweifachnennungen'' durchlaufen, siehe auch [[#Abzählung der rationalen Zahlen]] und [[#Calkin-Wilf-Baum]].

=== Eigenschaften der Stufentafel ===

M. Stern<ref name="stern" /> entwickelte seine Folge in Reihen, beginnend mit zwei [[Natürliche Zahl|natürlichen Zahlen]] (m,n), indem er fortgesetzt die Reihe kopierte und in der Kopie zwischen je zwei aufeinanderfolgende Zahlen die Summe derselben einfügte. Dies nannte er ''Entwicklung'' (m,n). Die Stern-Brocot-Folge ist die Entwicklung (0,1) und die [[#Stufentafel]] entsteht aus der Entwicklung (1,1); die erste Hälfte jeder ihrer Reihen ergibt sich aus der Entwicklung (1,2), die Eisenstein untersuchte. M. Stern definierte:
* Die Reihe (m,n), die entwickelt wird, ist die nullte Reihe,
* Jede Zahl einer Reihe ist ein ''Glied'' der Reihe und eine ''Gruppe'' ist eine Anzahl aufeinander folgender Glieder.
* Glieder, die aus der Summe ihrer Nachbarn entstanden, heißen {{Anker|Summenglieder}}''Summenglieder'', und alle anderen {{Anker|Stammglieder}}''Stammglieder''. Die Summenglieder stehen an geraden Stellen und die Stammglieder an ungeraden Stellen jeder Reihe außer der nullten.
* φ(n) ist die [[Eulersche φ-Funktion]], d.&nbsp;h. die Anzahl der zu n teilerfremden Zahlen, die kleiner oder gleich n sind.

Die Entwicklung (1,1) beginnt mit

{| style="text-align:center;border-collapse:collapse;"
|style="border-right: 1px solid #000000; border-bottom: 1px solid #000000"|p
|colspan="33" style="text-align:left;border-bottom: 1px solid #000000"|&nbsp;p-te Reihe
|-
|style="border-right: 1px solid #000000"|0
|&nbsp;1,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|1
|&nbsp;1,||2,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|2
|&nbsp;1,||3,||2,||3,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|3
|&nbsp;1,||4,||3,||5,||2,||5,||3,||4,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|4
|&nbsp;1,||5,||4,||7,||3,||8,||5,||7,||2,||7,||5,||8,||3,||7,||4,||5,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|5
|&nbsp;1,||6,||5,||9,||4,||11,||7,||10,||3,||11,||8,||13,||5,||12,||7,||9,
|2,||9,||7,||12,||5,||13,||8,||11,||3,||10,||7,||11,||4,||9,||5,||6,||1&nbsp;
|-
|style="border-right: 1px solid #000000"|︙
|︙||colspan="32" style="text-align:center;"|usw.||᨞
|- style="color:blue"
|
|&nbsp;↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓
|↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||↓||…
|- style="color:blue"
|Δ =
|&nbsp;0||1||1||2||1||3||2||3||1||4||3||5||2||5||3
|4||1||5||4||7||3||8||5||7||2||7||5||8||3||7||4||5||1||…
|}

Entfernt man in jeder Reihe die endständige Eins, entstehen die Zeilen der eingangs angegebenen [[#Stufentafel]]. Die folgenden Eigenschaften der Reihen trug M. Stern zusammen, wenn nicht anders angegeben:
* Die Anzahl der Glieder in der p-ten Reihe ist 2<sup>p</sup>+1.
* Die Summe der Glieder in der p-ten Reihe ist 3<sup>p</sup>+1.
* Die Summe der Quotienten zweier aufeinander folgender Glieder in der Reihe ist (3·2<sup>p</sup>−1)/2.<ref name="grimm">{{Literatur
 |Autor=J. Grimm
 |Hrsg=[[INRIA]]
 |Titel=Fibonacci-Zahlen und der Stern-Brocot-Baum in Coq
 |TitelErg=Research Report RR-8654
 |Datum=2014
 |Seiten=1–76
 |Sprache=en
 |Originaltitel=Fibonacci numbers and the Stern-Brocot tree in Coq
 |Online=https://www.researchgate.net/publication/280790424
 |Abruf=2022-01-17
 |arXiv=1011.2823v1}}</ref>
* Die Summe der Kehrwerte der Produkte zweier aufeinander folgender Glieder in der Reihe ist eins.<ref name="grimm" />
* Übereinander stehende Glieder erzeugen eine [[Arithmetische Folge]] und die Differenzen in den Folgen ergeben ihrerseits die Stern-Brocot-Folge, vermerkt in der untersten, blau geschriebenen Zeile obiger Tabelle.
* Jede Reihe ist ein [[Palindrom]], dessen Mitte bei Reihen ungerader Länge eine Zwei ist.
* Steht in einer Zeile die Gruppe <math>a,b,c</math> und direkt darunter <math>d,e,f</math>, dann gilt:
::<math>a>\frac d2,\quad ae-bd=1,\quad\frac{a+c}b=\frac{d+f}e</math>
: In der vierten Reihe steht beispielsweise 5,4,7 über 6,5,9 in der fünften Reihe, und es stimmt:
::<math>5>\frac 62=3,\quad 5\cdot 5-4\cdot 6=1,\quad\frac{5+7}4=\frac{6+9}5=3</math>
* Jede Zahl n kommt sooft als Summenglied vor, wie es kleinere Zahlen gibt, die zu ihr teilerfremd sind; diese Anzahl ist φ(n). Eine [[Primzahl]] π kommt π−1-mal als Summenglied vor. In Zeile n−1 kommt n zum letzten Mal als Summenglied vor. Ab der n-ten Zeile kommt n in jeder Zeile φ(n) mal als Stammglied vor.
* Die Zahl n kommt in Zeile p sooft vor, wie die Zerlegung von n in zwei teilerfremde a, b gelingt, sodass die Summe der Teilnenner des zu a/b gleichen Kettenbruchs nicht größer als p ist. Beispielsweise lässt sich die Zahl fünf viermal in einander teilerfremde Zahlen zerlegen:
::<math>\begin{align}
5=&1+4,\quad\frac14=0+\frac14=(0;4),\,&\mathsf p=&0+4=4
\\
5=&2+3,\quad\frac23=0+\frac1{1+\frac12}=(0;1,2),\,&\mathsf p=&0+1+2=3
\\
5=&3+2,\quad\frac32=1+\frac12=(1;2),\,&\mathsf p=&1+2=3
\\
5=&4+1,\quad\frac41=4=(4;),\,&\mathsf p=&4
\end{align}</math>
: Entsprechend kommt fünf vor der dritten Reihe keinmal, in der dritten Reihe zweimal und in allen darauf folgenden Reihen viermal vor.
* Die Gruppe (a,b) steht in der Zeile p&nbsp;=&nbsp;k<sub>0</sub>+k<sub>1</sub>+…+k<sub>m</sub>−1, wenn a/b gleich ist zum einfachen Kettenbruch  (k<sub>0</sub>;k<sub>1</sub>,…,k<sub>m</sub>). Beispielsweise ist in der fünften Reihe, die mit 1,6,5,9,4,11 beginnt:
::<math>\frac16=0+\frac16,\,\frac65=1+\frac15,\,\frac59=0+\frac1{1+\frac1{1+\frac14}},\,\frac95=1+\frac1{1+\frac14},\,\frac4{11}=0+\frac1{2+\frac1{1+\frac13}},\,\dots</math>
: Die Summe der Teilnenner der Kettenbrüche ist hier in allen Fällen sechs, d.&nbsp;h. eins mehr als die Zeilennummer fünf, so wie es sein muss.
* Die Gruppe (a,b) kommt in der ersten Hälfte einer Reihe vor, wenn die kleinste positive Zahl c, die mit a multipliziert den Rest 1 bei Division durch a+b ergibt, kleiner als (a+b)/2 ist:
:: {|
|style="vertical-align: top;"|∃c:
|style="text-align: center;vertical-align: top;"|&nbsp;ac&nbsp;≡&nbsp;1&nbsp;[[Division mit Rest#Modulo|mod]]&nbsp;(a+b)
|style="width: 4em;text-align: center;vertical-align: top;"|und
|style="text-align: center;vertical-align: top;"|0&nbsp;≤&nbsp;c&nbsp;<&nbsp;(a+b)/2
|style="width: 4em;text-align: center;vertical-align: top;"|→
|style="text-align: left;vertical-align: top;"|(a,b) kommt in der ersten Hälfte einer Reihe vor.
|}
: So steht die Gruppe (5,9) in der ersten Hälfte der fünften Reihe, weil 5·3&nbsp;=&nbsp;15&nbsp;≡&nbsp;1&nbsp;mod&nbsp;14 und 3&nbsp;<&nbsp;14/2&nbsp;=&nbsp;7. Die Gruppe (9,5) andererseits liegt in der zweiten Hälfte, weil 9·11&nbsp;≡&nbsp;(-5)·(-3)&nbsp;=&nbsp;15&nbsp;≡&nbsp;1&nbsp;mod&nbsp;14 und 11&nbsp;>&nbsp;7.

== Zähleigenschaften ==
=== Zusammenhang mit dem  Pascal’schen Dreieck ===
Wenn man das [[Pascalsches Dreieck|Pascal’sche Dreieck]] als Stufentafel anordnet (siehe folgende Tabelle), so bildet die Anzahl der ungeraden Zahlen in den aufsteigenden Diagonalen, von denen eine gelb markiert ist, die Stern-Brocot-Folge. Die [[Fibonacci-Folge]] findet sich hier ebenfalls, und zwar in der Summe der Zahlen.

{| style="text-align: right; font-family: monospace; line-height: 1em; width: 250px;"
|-
|style="width:14%;"| 1
|style="width:14%;"|
|style="width:14%;"|
|style="width:14%;"|
|style="width:14%;"|
|style="width:14%;"|
|style="width:14%;"|
|-
| 1
| 1
|
|
|
|
|
|-
| 1
| 2
| 1
|
|
|
|
|-
| 1
| 3
| 3
| 1
|
|
|
|-
| 1
| 4
| 6
| 4
! class="hintergrundfarbe3"| 1
|
|
|-
| 1
| 5
| 10
! class="hintergrundfarbe3"| 10
| 5
| 1

|-
| 1
| 6
! class="hintergrundfarbe3"| 15
| 20
| 15
| 6
| …
|-
| 1
! class="hintergrundfarbe3"| 7
| 21
| 35
| 35
| 21
| …
|-
! class="hintergrundfarbe3"| 1
| 8
| 28
| 56
| 70
| 56
| …
|-
| 1
| 9
| 36
| 84
|&nbsp;126
|&nbsp;126
| …
|}

Die hervorgehobene Diagonale zeigt ein Beispiel. In der ersten Spalte geht man von Zeile n&nbsp;=&nbsp;9 aus und betrachtet die übrigen Werte der Diagonalen: Die Anzahl der ungeraden Zahlen ist 4 und s<sub>9</sub> ist ebenfalls 4; Die Summe auf der Diagonalen ist 1+7+15+10+1&nbsp;=&nbsp;34&nbsp;=&nbsp;f<sub>9</sub> in der Fibonacci-Folge.

Auf der n-ten Diagonale steht die Zahl der Spalte j in Zeile n+1−j und hat den Wert des [[Binomialkoeffizient]]en <math>\begin{pmatrix}\mathsf{n-j}\\\mathsf j-1\end{pmatrix}</math>. Daraus kann eine explizite Formel zur [[#Berechnung der Folgenglieder]] abgeleitet werden.

=== Zusammenhang mit der Binärdarstellung von Zahlen ===
Die Stern-Brocot-Folge weist folgende bemerkenswerten Beziehungen zur Binärdarstellung von Zahlen auf.

Die Anzahl der alternierenden Folgen aus Einsen und Nullen, die aus der [[Binärdarstellung]] von n gebildet werden können, ist gleich s<sub>n</sub>. Gezählt werden Folgen, die mit einer Eins beginnen und enden und in denen keine zwei Nullen und keine zwei Einsen hintereinander stehen. Eine einzelne Eins zählt hier auch als alternierende Folge. Beispielsweise ist 13&nbsp;=&nbsp;1101<sub>2</sub>, woraus sich die fünf alternierenden, mit Unterstreichung markierten Folgen
: {{Unterstrich|1}}101, 1{{Unterstrich|1}}01, 110{{Unterstrich|1}}, {{Unterstrich|1}}1{{Unterstrich|01}}, 1{{Unterstrich|101}}

bilden lassen und somit ist [[#s0-s99|s<sub>13</sub>]]&nbsp;=&nbsp;5.

Die Stelle, an der zwei teilerfremde Zahlen a, b in der Stern-Brocot-Folge hintereinander stehen, kann wie folgt bestimmt werden. Dazu wird der Bruch a/b als [[Kettenbruch]] (k<sub>0</sub>;k<sub>1</sub>,…,k<sub>m</sub>) mit Teilnennern k<sub>0,…,m</sub> dargestellt. Der Kettenbruch wird in eine Binärzahl übersetzt mit von links k<sub>m</sub> Einsen, k<sub>m-1</sub> Nullen, wieder k<sub>m-2</sub> Einsen usw. Die Binärzahl entspricht der Stelle in der Stern-Brocot-Folge, an der a vor b steht.

Beispielsweise ist
:<math>\begin{align}
\mathsf{k}/1=&(\mathsf{k};)
\!\!\!\!\!\!\!\!&\rightarrow\;\;&
\mathsf{n}=\underbrace{1\dots1}_{\mathsf{k\;mal}}\,\!_2=2^\mathsf{k}-1
\\
\mathsf{k}/(\mathsf{k}+1)=&0+\frac1{1+\frac1{\mathsf{k}}}=(0;1,\mathsf{k})
\!\!\!\!\!\!\!\!&\rightarrow\;\;&
\mathsf{n}=\underbrace{1\dots1}_{\mathsf{k\;mal}}0_2=2^{\mathsf{k}+1}-2
\end{align}</math>

Wenn m ungerade ist, wird der letzte Teilnenner k<sub>m</sub> ersetzt durch k<sub>m</sub>−1 und eine Eins als Teilnenner hinzugefügt, entsprechend <math>\mathsf{k_m}=\mathsf{k_m}-1+\tfrac11</math>:
:<math>\begin{align}
1/\mathsf{k}=&0+\frac1{\mathsf{k}}=(0;\mathsf{k})
=0+\frac1{\mathsf{k}-1+\frac11}=(0;\mathsf{k}-1,1)
\!\!\!\!\!\!\!\!&\rightarrow\;\;&
\mathsf{n}=1\underbrace{0\dots0}_{\mathsf{k}-1\text{ mal}}\,\!_2
=2^{\mathsf{k}-1}
\\
(ab+1)/a=&b+\frac1a=b+\frac1{a-1+\frac11}=(b;a-1,1)
\!\!\!\!\!\!\!\!&\rightarrow\;\;&
\mathsf{n}=1\underbrace{0\dots0}_{a-1\;\mathsf{mal}}
\underbrace{1\dots1}_{b\;\mathsf{mal}}\,\!_2=2^b\left(2^{a-1}+1\right)-1
\end{align}</math>

Konkret steht in Übereinstimmung mit obigen Formeln das Paar (5,1) an der [[#s0-s99|Stelle 31]], (5,6) an der Stelle 62, (1,5) an der Stelle 16 und (13,4)&nbsp;=&nbsp;(4·3+1,4) an der Stelle 71.

In der „Hyperbinärdarstellung“<ref name="wilf">{{Literatur |Autor=Neil Calkin, [[Herbert Wilf]] |Hrsg=[[Mathematical Association of America]] |Titel=Nachzählen der rationalen Zahlen |Sammelwerk=[[The American Mathematical Monthly]] |Band=107 |Nummer=4 |Datum=2000 |Seiten=360–363 |Sprache=en |Originaltitel=Recounting the rationals |Online=[http://www.math.upenn.edu/%7Ewilf/website/recounting.pdf recounting.pdf] |Abruf=2022-01-12 |DOI=10.1080/00029890.2000.12005205}}</ref> einer Zahl n+1 sind neben den Ziffern Null und Eins noch die Zwei zur Darstellung der Zahl erlaubt, was mehrere Arten ihrer Schreibung gestattet; deren Anzahl ist s<sub>n</sub>. Beispielsweise lässt sich acht auf vier Arten schreiben:<ref name="delahaye" />

: 8 = 1000<sub>2</sub> = 200<sub>2</sub> = 120<sub>2</sub> = 112<sub>2</sub>

und dem entspricht [[#s0-s99|s<sub>9</sub>]] = 4.

=== Abzählung der rationalen Zahlen ===

Für [[Cantors erstes Diagonalargument]] wird eine [[Bijektion]] zwischen den [[Natürliche Zahl|Natürlichen Zahlen]] und den [[Rationale Zahl|Rationalen Zahlen]] benötigt. Diese ergibt sich in einfacher Weise einerseits aus der eindeutig vergebenen Nummer n des Bruchs s<sub>n</sub>/s<sub>n+1</sub>. Weil jedes Zahlenpaar nur genau einmal in der Folge auftritt, liefert die im [[#Zusammenhang mit der Binärdarstellung von Zahlen]] geschilderte [[Kettenbruchmethode]] für einen Bruch a/b dessen Nummer.<ref name="delahaye" />{{rp|68}}<ref name="poeppe" />{{rp|85}}<ref name="glasby" />

=== Binärer Baum von Stern und Brocot ===
[[Datei:BinaryTreeOfSternAndBrocot.svg|mini|400px|Abb. 2: Binärer Baum von Stern und Brocot]]
Im binären Baum von Stern und Brocot aus Abb. 2 ist an jedem [[Knoten (Graphentheorie)|Knoten]] die Anzahl der Wege notiert, die von den beiden obersten, rot geschriebenen Einsen abwärts, den Pfeilen folgend, zum Knoten führen.
Im binären Baum steht in den Knoten gleicher [[Tiefe (Graphentheorie)|Tiefe]] eine Reihe der [[#Entwicklung]] (1,1).
{{Absatz}}

[[Datei:TernaryTreeOfSternAndBrocot.svg|mini|400px|Abb. 3]]

Im Baum in Abb. 3 ist an jedem Knotenpunkt die Anzahl der Wege notiert, die von der obersten Eins abwärts, den Pfeilen folgend, zum Knoten führen. In diesem Baum stehen in den Knoten gleicher Tiefe bis zur Mitte die ersten Folgenglieder der Stern-Brocot-Folge ab [[#s0-s99|s<sub>1</sub>]], eine Eins und dieselben Folgenglieder in umgekehrter Reihenfolge.
{{Absatz}}

== Zusammenhänge mit Brüchen ==

=== Calkin-Wilf-Baum ===
<gallery widths="250" heights="250">
CalkinWilf.svg|Abb. 4: Calkin-Wilf-Baum
Calkin-Wilf spiral.svg|Abb. 5: Calkin-Wilf-Spirale
</gallery>

Im Calkin-Wilf-Baum sind die Verhältnisse aufeinander folgender Glieder der Stern-Brocot-Folge in einer [[Baum (Graphentheorie)|Baum]]&shy;struktur angeordnet, siehe Abb. 4. Sie ist nach Neil Calting und [[Herbert Wilf]] benannt, die sie im Jahr 2000 untersucht haben.<ref name="wilf" /> Indem die Brüche im Baum zeilenweise gelesen werden, haben sie die Eigenschaften:
* Der Nenner eines Bruchs ist der Zähler des folgenden; b(n)/b(n+1) wird gefolgt von b(n+1)/b(n+2).
* Die b(n), angefangen mit n=0, sind die Anzahl der Möglichkeiten n als Summen von Zweierpotenzen zu schreiben, von denen jede maximal doppelt gezählt wird (Hyperbinärzahlen, siehe auch [[#Zusammenhang mit der Binärdarstellung von Zahlen]]).
* b(n) und b(n+1) sind einander teilerfremd.
* Jede rationale Zahl erscheint nur genau einmal im Baum.

Der Baum konstruiert sich wie folgt:

* 1/1 ist die [[Wurzel (Graphentheorie)|Wurzel des Baumes]] (im Bild oben).
* Der Verzweigungspunkt mit dem Bruch i/j hat zwei Äste; der linke führt zum Verzweigungspunkt i/(i+j) und der rechte zu (i+j)/j.

Hier steht in den Zählern und Nennern eine Zeile der [[#Stufentafel]] jeweils in richtiger und umgekehrter Reihenfolge. Indem die Zeilen des Baums nacheinander und von links nach rechts gelesen werden, reihen sich die Brüche in gekürzter Form und ohne Doppeltzählungen – der Spirale in Abb. 5 folgend – aneinander. Die Stelle des Bruchs in dieser Aufzählung entspricht der [[Binärzahl]], die entsteht, wenn die im Baum in Abb. 4 rot geschriebenen Nullen und Einsen von der Spitze 0/1 bis zum Bruch aneinander gehängt werden.<ref>{{Literatur
 |Autor=M. Niqui
 |Titel=Exakte Arithmetik auf dem Stern–Brocot–Baum
 |Sammelwerk=Journal of Discrete Algorithms
 |Band=5
 |Nummer=2
 |Verlag=Elsevier
 |Datum=2007
 |Seiten=356-379
 |Sprache=en
 |Originaltitel=Exact arithmetic on the Stern–Brocot tree
 |DOI=10.1016/j.jda.2005.03.007}}</ref> Beispielsweise bekommt der Bruch 3/5 in der untersten Reihe die Binärzahl 1010<sub>2</sub>&nbsp;=&nbsp;10 zugeordnet, was seiner Position in der Abzählung entspricht. Umgekehrt ist die Binärdarstellung der Zahl n auch eine Wegbeschreibung zum n-ten Glied der Abzählungskette. Dazu geht man vom Ursprung bei 0/1 zur nächsten Verzweigung und nimmt bei einer Eins in der nächsten Ziffer der Binärdarstellung den rechten Ast und bei einer Null den linken. Das zehnte Glied wird beispielsweise durch abwechselnde Wahl des rechten, linken, rechten und wieder linken Asts erreicht (beim Ausgangspunkt 0/1 gibt es nur den rechten Ast.)

Werden die Brüche in jeder Zeile nach ihrer Größe geordnet, entsteht der [[#Stern-Brocot-Baum]]. Diese Reihenfolge kann auch mit der oben definierten Binärdarstellung hergestellt werden, indem diese umgekehrt und nach dieser umgekehrten Binärdarstellung sortiert wird. In der dritten Zeile stehen beispielsweise 1/3, 3/2, 2/3 und 3/1 an den Stellen 100<sub>2</sub>, 101<sub>2</sub>, 110<sub>2</sub> bzw. 111<sub>2</sub>. Umkehrung der Binärdarstellungen liefert 001<sub>2</sub>, 101<sub>2</sub>, 011<sub>2</sub>, 111<sub>2</sub> und sortiert 001<sub>2</sub>, 011<sub>2</sub>, 101<sub>2</sub> und 111<sub>2</sub>, was den Brüchen 1/3, 2/3, 3/2, und 3/1 entspricht. Das funktioniert auch zeilenübergreifend, wenn die Binärdarstellungen vor dem Sortieren mit führenden Nullen auf gleiche Länge gebracht werden.<ref name="poeppe">{{Literatur
 |Autor=Christoph Pöppe
 |Titel=Rationale Zahlen zählen
 |Sammelwerk=[[Spektrum der Wissenschaft]]
 |Datum=2021-05
 |Seiten=82–86
 |Online=[http://spektrum.de/artikel/1848328 spektrum.de]}}</ref>

Der Grund für diese Eigenschaften ist darin zu suchen, dass die Differenz zwischen benachbarten Brüchen (i+j)/j und i/(i+j) mit der [[Tiefe (Graphentheorie)|Tiefe]] der [[Knoten (Graphentheorie)|Knoten]] zunimmt.<ref name="poeppe" />{{rp|85}}

=== Der nächste Bruch ===
Zur Berechnung des nächsten Bruchs im [[#Calkin-Wilf-Baum]] gibt es eine einfache Formel. Ist a/b der vorgelegte Bruch, dann lautet der nächste Bruch<ref name="delahaye" />{{rp|69}}

: b/c = 1/(1 + 2[a/b] − a/b)

wo die [[Gaußklammer]] [ · ] auf die nächste Ganzzahl abrundet.

=== Stern-Brocot-Baum ===
[[Datei:SternBrocotTree.svg|mini|400px|Abb. 6: Stern-Brocot-Baum]]
Der Stern-Brocot-Baum ist eine Anordnung aller positiven [[Rationale Zahl|rationalen Zahlen]] in Form eines [[Binärer Baum|binären Baumes]]. Er enthält die Brüche aus dem [[#Calkin-Wilf-Baum]] in jeder [[Tiefe (Graphentheorie)|Tiefe]] nach der Größe sortiert und eignet sich so zur Bestimmung von Näherungsbrüchen für reelle Zahlen.

Der Baum entsteht durch Verbindung der [[#Summenglieder]], die an den geraden Stellen in jeder Zeile stehen, von einer Zeile zur nächsten, und nur die ihnen entsprechenden Brüche werden als solche ausgewertet (nicht so die randständigen <math>\tfrac10</math>, siehe [[#Programmierung der Optimierung]]).
Die Summenglieder sind die [[Mediante (Mathematik)|Medianten]] <math>\tfrac{m+m^\prime}{n+n^\prime}</math>  der [[#Stammglieder]] <math>\tfrac{m}{n}</math> auf der linken und <math>\tfrac{m^\prime}{n^\prime}</math> der rechten Seite (an den ungeraden Stellen jeder Zeile, ein Stammglied ist der direkte Vorfahre, das andere ein weiter oben stehender). In jeder Zeile des Baums stehen die ersten Glieder der Stern-Brocot-Folge in der richtigen Reihenfolge in den Zählern der Brüche und in den Nennern in umgekehrter Reihenfolge. Da der größte Bruch in jeder Zeile linear mit der Zeilennummer wächst, die Anzahl der Glieder jedoch mit der Potenz von zwei, nähern sich die Brüche mit zunehmender Tiefe immer weiter an.

==== Optimale rationale Näherung für eine reelle Zahl ====
Brocot suchte zu einer bestimmten [[Reelle Zahl|reellen Zahl]] x den besten Näherungsbruch p/q in dem Sinn, dass jede [[rationale Zahl]] s/t, die näher als p/q an x liegt, einen größeren Nenner hat: t>q. Die Zahl x markiert man im Baum als senkrechte Linie und setzt den Baum mit Hilfe der beiden links und rechts der Linie nächstgelegenen Stammglieder und des von ihnen eingeschlossenen Summenglieds/Medianten fort, bis eine zufriedenstellende Annäherung erreicht ist.

Für die Zahl 1,7 = 17/10 führt das Vorgehen zu

{| class="wikitable" style="text-align:center;"
! style="text-align:right;"|Rechtes Stammglied
|1/0→
|1/0<sup>➚</sup>
|2/1→
|2/1→
|style="border-right: 2px solid #000000"|2/1<sup>➚</sup>
|7/4<sup>➚</sup>
|12/7
|-
! style="text-align:right;"|Summenglied
|1,7>1/1<sub>➘</sub>
|1,7<2/1<sup>➚</sup>
|1,7>3/2<sub>➘</sub>
|1,7>5/3<sub>➘</sub>
|style="border-right: 2px solid #000000"|1,7<7/4<sup>➚</sup>
|1,7<12/7<sup>➚</sup>
|1,7=17/10
|-
! style="text-align:right;"|Linkes Stammglied
|0/1<sub>➘</sub>
|1/1→
|1/1<sub>➘</sub>
|3/2<sub>➘</sub>
|style="border-right: 2px solid #000000"|5/3→
|5/3→
|5/3
|- class="hintergrundfarbe2"
|colspan="6" style="border-left: 1px solid #ffffff;border-right: 2px solid #000000;"|
|colspan="2" style="border-right: 1px solid #ffffff;"|
|-
! style="text-align:right;"|Kleinster Abstand
|7/10||3/10||1/5||1/30||style="border-right: 2px solid #000000"|1/30||1/70||0
|- class="hintergrundfarbe2"
|colspan="6" style="text-align:right; border-left: 1px solid #ffffff; border-bottom: 1px solid #ffffff; border-right: 2px solid #000000"|Ende des Baums →
|colspan="2" style="text-align:right; border-bottom: 1px solid #ffffff; border-right: 1px solid #ffffff"|
|}

Innerhalb des Baumes aus Abb. 6 ist die beste Näherung 1,7&nbsp;≈&nbsp;5/3&nbsp;=&nbsp;1,{{Oberstrich|6}} in einem Abstand von 1/30&nbsp;=&nbsp;0,0{{Oberstrich|3}}. Sie ist beste Näherungen in dem Sinn, dass jede rationale Zahl, die näher als 1/30 an x liegt, einen größeren Nenner hat, wie zum Beispiel 12/7 im Abstand 1/70. Offenbar nimmt der Abstand von links nach rechts, d.&nbsp;h. mit zunehmender [[Tiefe (Graphentheorie)|Tiefe]], monoton ab. Das Summenglied wird in jeder Spalte mit dem Medianten des rechten und linken Stammglieds verglichen, und dieser Mediant ersetzt das, von x aus gesehen, auf der Seite des Medianten liegende Stammglied, was durch Pfeile angedeutet ist.

==== Programmierung der Optimierung ====
Obige Suche lässt sich problemlos in ein [[Computerprogramm]] umsetzen, wofür zwei Beispiele angegeben werden.

Die Funktion <code>approximate</code> in folgendem [[Haskell (Programmiersprache)|Haskell]]-Programm generiert die Liste aller besten Näherungen für eine positive reelle Zahl, die als Funktion gegeben ist, welche für jede rationale Zahl angibt, ob sie größer, kleiner oder gleich der gesuchten ist.

<syntaxhighlight lang="Haskell">
type Ratio = (Integer, Integer)

type Interval = (Ratio, Ratio)

mediant :: Interval -> Ratio
mediant ((m, n), (m', n')) = (m+m', n+n')

approximate :: (Ratio -> Ordering) -> [Ratio]
approximate c = h ((0,1),(1,0)) where
    h interval@(lo, hi) = mid : case c mid of
        LT -> h (mid, hi)
        GT -> h (lo, mid)
        EQ -> []
        where mid = mediant interval

</syntaxhighlight>
Die generierte Liste ist endlich, wenn die gesuchte Zahl rational ist.

Die [[Python (Programmiersprache)|Python]] Funktion <code>approximate</code> gibt für eine positive reelle Zahl x den besten Näherungsbruch mit einem Nenner kleiner oder gleich n.
<syntaxhighlight lang="Python">
def approximate( x=1., n=1000000 ):
    """approximate( x=1., n=1000000 )
    Gibt den besten Naeherungsbruch fuer x mit Nenner <= n"""
    from fractions import Fraction
    ( l, m, r ) = [ [0,1], [1,1], [1,0] ] # Stammglieder mit Mediant
    f = 3*[ -1 ]                          # optimale l, m und r
    while f.count( -1 ) > 0:
        a = m
        m = [ l[0] + r[0], l[1] + r[1] ]  # Mediant von l und r
        if f[1] < 0 and m[1] > n:         # maximaler Nenner ueberschritten
            f[1] = Fraction( *a )         # speichern des optimalen m
        if m[0] < x*m[1]:                 # l0/l1 < m0/m1 < x < r0/r1
            if f[0] < 0 and m[1] > n:     # maximaler Nenner ueberschritten
                f[0] = Fraction( *l )     # speichern des optimalen l
            l = m
        elif m[0] > x*m[1]:               # l0/l1 < x < m0/m1 < r0/r1
            if f[2] < 0 and m[1] > n:     # maximaler Nenner ueberschritten
                f[2] = Fraction( *r )     # speichern des optimalen r
            r = m
        else: # m0/m1 == x
            if f[1] < 0:                  # m noch nicht gespeichert
                f[1] = Fraction( *m )     # speichern des optimalen m
            break
    return sorted( [ (abs(y - x), y) for y in f ] )[0][1] # optimales f
</syntaxhighlight>

== Weblinks ==
{{Commonscat|Calkin–Wilf tree and sequence|Stern-Brocot-Folge}}
* Code-Beispiele zur Programmierung der [http://rosettacode.org/wiki/Stern-Brocot_sequence Stern-Brocot-Folge] auf Rosettacode.org

== Siehe auch ==
* [[Farey-Folge]]
* [[Ford-Kreis]]

== Einzelnachweise ==
<references />

[[Kategorie:Folge ganzer Zahlen]]
[[Kategorie:Zahlentheorie]]