Stern-Brocot-Folge

Die Stern-Brocot-Folge (A002487 in OEIS), auch als „diatomische Folge von Stern und Brocot“ oder „Stern-Sequenz“ bekannt, ist eine Folge ganzer Zahlen, die unabhängig vom Mathematiker Gotthold Eisenstein und dem Uhrmacher Achille Brocot entdeckt und vom Mathematiker Moritz Stern genauer untersucht wurde.

Sie startet mit dem Zahlenpaar s₀ = 0 und s₁ = 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₁ und Unterteilung bei den Semikolons „;“) zur besseren Darstellung verschiedener Eigenschaften benutzt wird:

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	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 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 Übersetzungsverhältnis gefunden werden, was A. Brocot als erster erkannte, 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 Euler’schen φ-Funktion.
• Die Position eines Zahlenpaars (a,b) in der Stufentafel hängt mit der Kettenbruch­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.

Geschichte

Gotthold Eisenstein veröffentlichte im Februar 1850 eine Arbeit über eine Zahlenreihe,

„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.“

– G. 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;“ Eisenstein starb 1852 im Alter von nur 29 Jahren. Der Aufsatz von Brocot datiert auf das Jahr 1861.

Definition der Stern-Brocot-Folge

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₀, s₁, s₂,… ist durch das rekursive Bildungsgesetz

s2n	= sn
s2n+1	= sn + sn+1

mit den Anfangswerten

s₀ = 0    und    s₁ = 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. Dieses Gesetz ähnelt dem der Fibonacci-Folge.

Das Bildungsgesetz für die Glieder an ungeraden Stellen kann wegen s_2n = s_n umgeformt werden in

s_2n+1 = s_n + s_n+1 = s_2n + s_2(n+1) = s_2n + s_2n+2

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).

Die ersten 100 Glieder der Folge sind:

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19
sn	0	1	1	2	1	3	2	3	1	4	3	5	2	5	3	4	1	5	4	7
n	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39
sn	3	8	5	7	2	7	5	8	3	7	4	5	1	6	5	9	4	11	7	10
n	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59
sn	3	11	8	13	5	12	7	9	2	9	7	12	5	13	8	11	3	10	7	11
n	60	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79
sn	4	9	5	6	1	7	6	11	5	14	9	13	4	15	11	18	7	17	10	13
n	80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99
sn	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ürlicher Zahlen (m,n). Wenn diese nicht teilerfremd sind, dann enthalten alle Glieder der Folge deren 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.

Die Stern-Brocot-Folge wurde auch auf Polynome verallgemeinert.

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

${\mathsf {s_{n}}}=\sum _{\mathsf {2i+j=n-1}}\left({\begin{pmatrix}{\mathsf {i+j}}\\{\mathsf {i}}\end{pmatrix}}\mod 2\right)=\sum _{{\mathsf {j}}=1}^{\left[{\frac {\mathsf {n+1}}{2}}\right]}\left({\begin{pmatrix}{\mathsf {n-j}}\\{\mathsf {j}}-1\end{pmatrix}}\mod 2\right)$

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

Die folgenden Methoden basieren auf der mehrfachen Anwendung einer Berechnungsvorschrift:

• Nach dem Bildungsgesetz ist s_k = s_k/2, wenn k gerade, oder s_k = s_(k-1)/2 + s_(k+1)/2, wenn k ungerade ist. Durch fortgesetzte Anwendung dieser Formeln werden alle benötigten Folgenglieder und schließlich s_n berechnet. Beispielsweise ist

s₆ = s₃ = s₁ + s₂ = s₁ + s₁ = 2

Die Anzahl der zu berechnenden Glieder wächst mit dem Logarithmus von n.

• Aus der Formel für #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 Rest bei Division von a durch b ist (sodass a−r durch b teilbar und 0 ≤ r < b ist, [·] ist die Gaußklammer). Das Glied s_n ergibt sich aus n−1 maliger Anwendung der Formel auf s₀ und s₁.

• Für n > 1 besteht der Zusammenhang

s_n = k_n−1s_n−1 − s_n−2

Darin ist k_j die größte ungerade Zahl für die j durch 2^(k_j−1)/2 teilbar ist.

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:

• Keine zwei geraden Glieder stehen hinter einander.
• 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 = 1/(1+2[a/b]-a/b), wo die Gaußklammer [ · ] auf die nächste Ganzzahl abrundet.
• 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, das die Brüche s₀/s₁, s₁/s₂, s₂/s₃, s₃/s₄, s₄/s₅,… alle nicht negativen rationalen Zahlen ohne Zweifachnennungen durchlaufen, siehe auch #Abzählung der rationalen Zahlen und #Calkin-Wilf-Baum.

Eigenschaften der Stufentafel

M. Stern entwickelte seine Folge in Reihen, beginnend mit zwei 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 Summenglieder, und alle anderen 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. h. die Anzahl der zu n teilerfremden Zahlen, die kleiner oder gleich n sind.

Die Entwicklung (1,1) beginnt mit

p	p-te Reihe
0	1,	1
1	1,	2,	1
2	1,	3,	2,	3,	1
3	1,	4,	3,	5,	2,	5,	3,	4,	1
4	1,	5,	4,	7,	3,	8,	5,	7,	2,	7,	5,	8,	3,	7,	4,	5,	1
5	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
︙	︙	usw.																																᨞
	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	↓	…
Δ =	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^p+1.
• Die Summe der Glieder in der p-ten Reihe ist 3^p+1.
• Die Summe der Quotienten zweier aufeinander folgender Glieder in der Reihe ist (3·2^p−1)/2.
• Die Summe der Kehrwerte der Produkte zweier aufeinander folgender Glieder in der Reihe ist eins.
• Ü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 $a,b,c$ und direkt darunter $d,e,f$, dann gilt:

$a>{\frac {d}{2}},\quad ae-bd=1,\quad {\frac {a+c}{b}}={\frac {d+f}{e}}$

In der vierten Reihe steht beispielsweise 5,4,7 über 6,5,9 in der fünften Reihe, und es stimmt:

$5>{\frac {6}{2}}=3,\quad 5\cdot 5-4\cdot 6=1,\quad {\frac {5+7}{4}}={\frac {6+9}{5}}=3$

• 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:

${\begin{aligned}5=&1+4,\quad {\frac {1}{4}}=0+{\frac {1}{4}}=(0;4),\,&{\mathsf {p}}=&0+4=4\\5=&2+3,\quad {\frac {2}{3}}=0+{\frac {1}{1+{\frac {1}{2}}}}=(0;1,2),\,&{\mathsf {p}}=&0+1+2=3\\5=&3+2,\quad {\frac {3}{2}}=1+{\frac {1}{2}}=(1;2),\,&{\mathsf {p}}=&1+2=3\\5=&4+1,\quad {\frac {4}{1}}=4=(4;),\,&{\mathsf {p}}=&4\end{aligned}}$

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 = k₀+k₁+…+k_m−1, wenn a/b gleich ist zum einfachen Kettenbruch (k₀;k₁,…,k_m). Beispielsweise ist in der fünften Reihe, die mit 1,6,5,9,4,11 beginnt:

${\frac {1}{6}}=0+{\frac {1}{6}},\,{\frac {6}{5}}=1+{\frac {1}{5}},\,{\frac {5}{9}}=0+{\frac {1}{1+{\frac {1}{1+{\frac {1}{4}}}}}},\,{\frac {9}{5}}=1+{\frac {1}{1+{\frac {1}{4}}}},\,{\frac {4}{11}}=0+{\frac {1}{2+{\frac {1}{1+{\frac {1}{3}}}}}},\,\dots$

Die Summe der Teilnenner der Kettenbrüche ist hier in allen Fällen sechs, d. 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:

∃c:

ac ≡ 1 mod (a+b)

und

0 ≤ c < (a+b)/2

→

(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 = 15 ≡ 1 mod 14 und 3 < 14/2 = 7. Die Gruppe (9,5) andererseits liegt in der zweiten Hälfte, weil 9·11 ≡ (-5)·(-3) = 15 ≡ 1 mod 14 und 11 > 7.

Zähleigenschaften

Zusammenhang mit dem Pascal’schen Dreieck

Wenn man das 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.

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1
1	6	15	20	15	6	…
1	7	21	35	35	21	…
1	8	28	56	70	56	…
1	9	36	84	126	126	…

Die hervorgehobene Diagonale zeigt ein Beispiel. In der ersten Spalte geht man von Zeile n = 9 aus und betrachtet die übrigen Werte der Diagonalen: Die Anzahl der ungeraden Zahlen ist 4 und s₉ ist ebenfalls 4; Die Summe auf der Diagonalen ist 1+7+15+10+1 = 34 = f₉ 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 Binomialkoeffizienten ${\begin{pmatrix}{\mathsf {n-j}}\\{\mathsf {j}}-1\end{pmatrix}}$. 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_n. 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 = 1101₂, woraus sich die fünf alternierenden, mit Unterstreichung markierten Folgen

1101, 1101, 1101, 1101, 1101

bilden lassen und somit ist s₁₃ = 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₀;k₁,…,k_m) mit Teilnennern k_0,…,m dargestellt. Der Kettenbruch wird in eine Binärzahl übersetzt mit von links k_m Einsen, k_m-1 Nullen, wieder k_m-2 Einsen usw. Die Binärzahl entspricht der Stelle in der Stern-Brocot-Folge, an der a vor b steht.

Beispielsweise ist

${\begin{aligned}{\mathsf {k}}/1=&({\mathsf {k}};)\!\!\!\!\!\!\!\!&\rightarrow \;\;&{\mathsf {n}}=\underbrace {1\dots 1} _{\mathsf {k\;mal}}\,\!_{2}=2^{\mathsf {k}}-1\\{\mathsf {k}}/({\mathsf {k}}+1)=&0+{\frac {1}{1+{\frac {1}{\mathsf {k}}}}}=(0;1,{\mathsf {k}})\!\!\!\!\!\!\!\!&\rightarrow \;\;&{\mathsf {n}}=\underbrace {1\dots 1} _{\mathsf {k\;mal}}0_{2}=2^{{\mathsf {k}}+1}-2\end{aligned}}$

Wenn m ungerade ist, wird der letzte Teilnenner k_m ersetzt durch k_m−1 und eine Eins als Teilnenner hinzugefügt, entsprechend ${\mathsf {k_{m}}}={\mathsf {k_{m}}}-1+{\tfrac {1}{1}}$:

${\begin{aligned}1/{\mathsf {k}}=&0+{\frac {1}{\mathsf {k}}}=(0;{\mathsf {k}})=0+{\frac {1}{{\mathsf {k}}-1+{\frac {1}{1}}}}=(0;{\mathsf {k}}-1,1)\!\!\!\!\!\!\!\!&\rightarrow \;\;&{\mathsf {n}}=1\underbrace {0\dots 0} _{{\mathsf {k}}-1{\text{ mal}}}\,\!_{2}=2^{{\mathsf {k}}-1}\\(ab+1)/a=&b+{\frac {1}{a}}=b+{\frac {1}{a-1+{\frac {1}{1}}}}=(b;a-1,1)\!\!\!\!\!\!\!\!&\rightarrow \;\;&{\mathsf {n}}=1\underbrace {0\dots 0} _{a-1\;{\mathsf {mal}}}\underbrace {1\dots 1} _{b\;{\mathsf {mal}}}\,\!_{2}=2^{b}\left(2^{a-1}+1\right)-1\end{aligned}}$

Konkret steht in Übereinstimmung mit obigen Formeln das Paar (5,1) an der Stelle 31, (5,6) an der Stelle 62, (1,5) an der Stelle 16 und (13,4) = (4·3+1,4) an der Stelle 71.

In der „Hyperbinärdarstellung“ 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_n. Beispielsweise lässt sich acht auf vier Arten schreiben:

8 = 1000₂ = 200₂ = 120₂ = 112₂

und dem entspricht s₉ = 4.

Abzählung der rationalen Zahlen

Für Cantors erstes Diagonalargument wird eine Bijektion zwischen den Natürlichen Zahlen und den Rationalen Zahlen benötigt. Diese ergibt sich in einfacher Weise einerseits aus der eindeutig vergebenen Nummer n des Bruchs s_n/s_n+1. 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.

Binärer Baum von Stern und Brocot

Abb. 2: Binärer Baum von Stern und Brocot

Im binären Baum von Stern und Brocot aus Abb. 2 ist an jedem 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 eine Reihe der #Entwicklung (1,1).

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 s₁, eine Eins und dieselben Folgenglieder in umgekehrter Reihenfolge.

Zusammenhänge mit Brüchen

Calkin-Wilf-Baum

• 
  Abb. 4: Calkin-Wilf-Baum
• 
  Abb. 5: Calkin-Wilf-Spirale

Im Calkin-Wilf-Baum sind die Verhältnisse aufeinander folgender Glieder der Stern-Brocot-Folge in einer Baum­struktur angeordnet, siehe Abb. 4. Sie ist nach Neil Calting und Herbert Wilf benannt, die sie im Jahr 2000 untersucht haben. 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 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. Beispielsweise bekommt der Bruch 3/5 in der untersten Reihe die Binärzahl 1010₂ = 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₂, 101₂, 110₂ bzw. 111₂. Umkehrung der Binärdarstellungen liefert 001₂, 101₂, 011₂, 111₂ und sortiert 001₂, 011₂, 101₂ und 111₂, 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.

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 der Knoten zunimmt.

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

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

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

Stern-Brocot-Baum

Abb. 6: Stern-Brocot-Baum

Der Stern-Brocot-Baum ist eine Anordnung aller positiven rationalen Zahlen in Form eines binären Baumes. Er enthält die Brüche aus dem #Calkin-Wilf-Baum in jeder 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ändingen ${\tfrac {1}{0}}$, siehe #Programmierung der Optimierung). Die Summenglieder sind die Medianten ${\tfrac {m+m^{\prime }}{n+n^{\prime }}}$ der #Stammglieder ${\tfrac {m}{n}}$ auf der linken und ${\tfrac {m^{\prime }}{n^{\prime }}}$ 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 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

Rechtes Stammglied	1/0→	1/0➚	2/1→	2/1→	2/1➚	7/4➚	12/7
Summenglied	1,7>1/1➘	1,7<2/1➚	1,7>3/2➘	1,7>5/3➘	1,7<7/4➚	1,7<12/7➚	1,7=17/10
Linkes Stammglied	0/1➘	1/1→	1/1➘	3/2➘	5/3→	5/3→	5/3
Kleinster Abstand	7/10	3/10	1/5	1/30	1/30	1/70	0
Ende des Baums →

Innerhalb des Baumes aus Abb. 6 ist die beste Näherung 1,7 ≈ 5/3 = 1,6 in einem Abstand von 1/30 = 0,03. 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. h. mit zunehmender 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 approximate in folgendem 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.

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

Die generierte Liste ist endlich, wenn die gesuchte Zahl rational ist.

Die Python Funktion approximate gibt für eine positive reelle Zahl x den besten Näherungsbruch mit einem Nenner kleiner oder gleich n.

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

Weblinks

• Code-Beispiele zur Programmierung der Stern-Brocot-Folge auf Rosettacode.org

Siehe auch

• Farey-Folge
• Ford-Kreis