# Kettenbrüche

1. Wir basteln einen Mondkalender
2. Wie kommt man auf „optimale Brüche“?

## 2. Wie kommt man auf „optimale Brüche“?

Bitte betrachten Sie die folgende Abbildung:
Wenn die Figur nur aus Quadraten besteht und die drei großen Quadrate die Seitenlänge 1 haben, wie breit ist dann die ganze Figur?

Die Antwort ist nicht schwer: Da die fünf kleinen Quadrate zusammen so breit sind wie ein großes, haben sie die Kantenlänge 1/5 und die ganze Figur also die Breite

\def\green{\bbox[#d0ffd0,2pt]} \def\gray{\bbox[#e0e0e0,2pt]} \bbox[border:1px #c0c0c0 solid,4pt]{ {\green 3 + \frac{1}{\gray 5}} } \: = \frac{16}5

Und wie breit ist die folgende Figur im Vergleich zu ihrer Höhe?
Die Figur besteht aus einem großen Quadrat und dem rechten Teil, der dem um 90° gedrehten ersten Beispiel entspricht, also das Seitenverhältnis 3 + 1/5 hat. Damit hat die ganze Figur das Seitenverhältnis

\def\blue{\bbox[#c0e0ff,2pt]} \def\green{\bbox[#d0ffd0,2pt]} \def\gray{\bbox[#e0e0e0,2pt]} \bbox[border:1px #c0c0c0 solid,4pt]{ \blue 1 + \frac{1}{\displaystyle \green 3 + \frac{1}{\gray 5}}} \: = 1 + \frac{1}{\frac{16}5} = 1 + \frac{5}{16} = \frac{21}{16}

Dieses Spiel lässt sich beliebig fortsetzen.
Hier ergibt sich mit den gleichen Überlegungen das Seitenverhältnis

\def\pink{\bbox[#ffe0e0,2pt]} \def\blue{\bbox[#c0e0ff,2pt]} \def\green{\bbox[#d0ffd0,2pt]} \def\gray{\bbox[#e0e0e0,2pt]} \bbox[border:1px #c0c0c0 solid,4pt]{ \pink 2 + \frac{1} {\displaystyle \blue 1 + \frac{1}{\displaystyle \green 3 + \frac{1}{\gray 5}} } } \: = 2 + \frac{1}{\frac{21}{16}} = 2 + \frac{16}{21} = \frac{58}{21}
Solche Brüche nennt man (reguläre) Kettenbrüche.

### Der umgekehrte Weg

Wir kehren jetzt das Spiel um und können damit beliebige rationale Zahlen als Kettenbrüche darstellen: Dazu zerlegen wir eine gegebene positive rationale Zahl x (z.B. 58/21) in ihren ganzzahligen Anteil und den Rest, der kleiner als 1 ist:

\def\green{\bbox[#d0ffd0,2pt]} \def\yellow{\bbox[#ffffa0,2pt]} \def\pink{\bbox[#ffe0e0,2pt]} x = \green{\lfloor x \rfloor} + \yellow{(x - \lfloor x \rfloor)} = \lfloor x \rfloor + \frac{1}{\pink{\frac{1}{x - \lfloor x \rfloor}}}
Der Kehrwert des Rests ist damit größer als 1. Wir können dieses Verfahren nun auf den Rest anwenden und das so oft wiederholen, bis kein Rest mehr übrig bleibt.

Was geschieht aber, wenn wir das Spiel mit einem irrationalen x durchführen? Da ja jeder endliche Kettenbruch eine rationale Zahl darstellt, kann die Kettenbruchentwicklung bei irrationalen Zahlen nicht abbrechen. Hört man trotzdem irgendwann auf und ignoriert den Rest, bekommt man offenbar einen Näherungswert.

Wir testen das mit unserer gerundeten Monatszahl 4,218656:

\def\green{\bbox[#d0ffd0,2pt]} \def\yellow{\bbox[#ffffa0,2pt]} \eqalign{ 4,218656 & = \green 4 + \yellow{0,218656} \approx 4 + \frac{1}{4.5733998} \cr & = \green 4 + \frac{1}{{\green 4 + \yellow{0.5733998}}} \approx 4 + \frac{1}{{4 + \frac{1}{1.7439838658}}} \cr & = \green 4 + {\frac{1}{\green 4 + {\frac{1}{\green 1 + \yellow{0.7439838658}}}}} \approx 4 + {\frac{1}{4 + {\frac{1}{1 + \frac{1}{1.3441151}}}}} \cr & = \ldots }

Lassen wir in jedem Schritt den Rest weg, bekommen wir folgende Näherungen:

\def\green{\bbox[#d0ffd0,2pt]} \eqalign{ & \green{[4]} & \longrightarrow & & & 4 \cr & \green{[4,4]} & \longrightarrow & 4 + \frac{1}{4} = \frac{17}{4} & = & 4,25 \cr & \green{[4,4,1]} & \longrightarrow & 4 + \frac{1}{4 + \frac{1}{1}} = \frac{21}5 & = & 4,2}

Die Listen vor den Pfeilen sind eine übliche Kurzdarstellung von Kettenbrüchen. Daraus lässt sich die rationale Zahl am einfachsten rekursiv ausrechnen, indem man zur ersten Zahl der Liste den Kehrwert des Kettenbruchs aus dem Listenrest addiert:

    # Umwandlung eines Kettenbruchs in eine Rationale Zahl
    # z.B. [3,2,4] ---> 3 + 1/(2 + 1/4)
    def rationalFromList(cf):
        if len(cf) == 0: return Rational(0)
        if len(cf) == 1: return Rational(cf[0])
        return cf[0] + Rational(1) / rationalFromList(cf[1:])

    rationalFromList([4,4,1])

Jetzt fehlt nur noch die Ermittlung der Liste (bis zu einer bestimmten Schrittzahl) aus einer gegebenen Zahl:

    # Annäherung einer reellen Zahl durch einen Kettenbruch
    def listFromNumber(x, steps):
        l = []
        for i in range(steps):
            i = floor(x)       # ganzzahliger Anteil
            l.append(i)
            if abs(x-i) < 0.00000001:
                break
            x = 1 / (x-i)      # weiter mit Kehrwert des Rests
        return l

    echteMondwochen = 29.53059 / 7
    listFromNumber(echteMondwochen, 5)

Nun wenden wir diese Funktionen an, um uns die ersten Näherungsbrüche für unsere Monatszahl zu erzeugen:

    print("Schritte | Näherungswert | Jahre bis 1 Tag Abweichung")
    for i in fromTo(1,7):
        naeherung = rationalFromList(listFromNumber(echteMondwochen, i))
        relativeAbweichung = naeherung/echteMondwochen - 1
        tageAbweichungProJahr = relativeAbweichung * 365.24
        jahreBisTagAbweichung = abs(1/tageAbweichungProJahr)
        print("{0:8} | {1:13} | {2}".format(i, naeherung, jahreBisTagAbweichung))

Im sechsten Schritt haben wir unser Getriebe wieder bekommen. Wenn Sie dies z.B. mit dem fünften Schritt vergleichen, sehen Sie, dass sich die Genauigkeit von 9 auf 122 Jahre verbessert hat. Trotzdem wird das Getriebe nicht komplizierter, im Gegenteil: Für 97/23 bräuchten wir Zahnräder mit 97 und 23 Zähnen, weil beide Zahlen Primzahlen sind. Dagegen lässt sich 135/32 in zwei einfachere Übersetzungen zerlegen:

\def\green{\bbox[#d0ffd0,2pt]} \def\pink{\bbox[#ffe0e0,2pt]} \frac{135}{32} = \frac{3^3\cdot 5}{2^5} = \pink{\frac 9 4} \cdot \frac{15}8 = \green{\frac{18}8} \cdot \frac{15}8

Zahnräder mit vier Zähnen sind mechanisch unmöglich, so dass wir wieder zur unserer Lösung (18/8) · (15/8) kommen.

### Die Klasse ContFrac

In mathGUIde gibt es die fertige Klasse `ContFrac`. Damit können wir die komplette Berechnung so durchführen:

    echteMondwochen = 29.53059 / 7
    print("Schritte | Näherungswert | Jahre bis 1 Tag Abweichung")
    for i in fromTo(1,7):
        cf = ContFrac(echteMondwochen, i)
        naeherung = cf.toRational()
        relativeAbweichung = naeherung/echteMondwochen - 1
        tageAbweichungProJahr = relativeAbweichung * 365.24
        jahreBisTagAbweichung = abs(1/tageAbweichungProJahr)
        print("{0:8} | {1:13} | {2}".format(i, naeherung, jahreBisTagAbweichung))