Stern-Brocot-Folge

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

${\displaystyle {\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.[6] Für große n erfordert diese Darstellung die Handhabung sehr großer Zahlen; beispielsweise lautet der Binomialkoeffizient ${\displaystyle {\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.[7][8]

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

Für die Glieder der Stern-Brocot-Folge gilt:[4]

• 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.[6]^: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, 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.

M. Stern[4] 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

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.[9]
• Die Summe der Kehrwerte der Produkte zweier aufeinander folgender Glieder in der Reihe ist eins.[9]
• Ü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 ${\displaystyle a,b,c}$ und direkt darunter ${\displaystyle d,e,f}$, dann gilt:

${\displaystyle 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:

${\displaystyle 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:

${\displaystyle {\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:

${\displaystyle {\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.

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.

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 ${\displaystyle {\begin{pmatrix}{\mathsf {n-j}}\\{\mathsf {j}}-1\end{pmatrix}}}$. Daraus kann eine explizite Formel zur #Berechnung der Folgenglieder abgeleitet werden.

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

${\displaystyle {\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 ${\displaystyle {\mathsf {k_{m}}}={\mathsf {k_{m}}}-1+{\tfrac {1}{1}}}$:

${\displaystyle {\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“[10] 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:[6]

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

und dem entspricht s₉ = 4.

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.[6]^:68[11]^:85[8]

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.

• 
  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.[10] 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.[12] 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.[11]

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.[11]^:85

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[6]^:69

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

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

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 ${\displaystyle {\tfrac {1}{0}}}$, siehe #Programmierung der Optimierung). Die Summenglieder sind die Medianten ${\displaystyle {\tfrac {m+m^{\prime }}{n+n^{\prime }}}}$ der #Stammglieder ${\displaystyle {\tfrac {m}{n}}}$ auf der linken und ${\displaystyle {\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.

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

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.

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