Farey-Reihe

aus Wikipedia, der freien Enzyklopädie

Die Farey-Reihe oder Farey-Folge F_N ist in der Zahlentheorie die Menge der ausgekürzten Brüche zwischen 0 und 1, deren jeweiliger Nenner den Index N nicht übersteigt. Benannt sind die Farey-Reihen nach dem britischen Geologen John Farey. Die einzelnen Brüche einer Farey-Reihe sind der Größe nach sortiert. Diese Brüche werden auch Farey-Brüche genannt.

Inhaltsverzeichnis

1 Beispiel
2 Konstruktion einer Farey-Reihe
- 2.1 Beispiel (Methode 1)
- 2.2 Beispiel (Methode 2)
3 Eigenschaften
4 Siehe auch
5 Literatur
6 Weblinks

[Bearbeiten] Beispiel

Die 6. Farey-Reihe lautet $\frac{0}{1} \ \frac{1}{6} \ \frac{1}{5} \ \frac{1}{4} \ \frac{1}{3} \ \frac{2}{5} \ \frac{1}{2} \ \frac{3}{5} \ \frac{2}{3} \ \frac{3}{4} \ \frac{4}{5} \ \frac{5}{6} \ \frac{1}{1}$

[Bearbeiten] Konstruktion einer Farey-Reihe

Es gibt wenigstens zwei Wege, eine Farey-Reihe zu konstruieren.

Bei der ersten Methode sammelt man zunächst alle notwendigen Brüche und sortiert sie anschließend. Für eine Farey-Reihe F_N werden folgende Brüche gebraucht: einmal die beiden Brüche $\frac{0}{1}$ und $\frac{1}{1}$ . Des Weiteren werden alle durchgekürzten Brüche gebraucht, deren Nenner zwischen 2 und N liegen und deren Zähler zwischen 1 und N-1 liegt. Wenn man alle möglichen Brüche zusammen hat, werden sie der Größe nach aufsteigend sortiert.

[Bearbeiten] Beispiel (Methode 1)

Die Brüche für F₈:

$\frac{0}{1} \ \ \frac{1}{1} \ \ \frac{1}{2} \ \ \frac{1}{3} \ \ \frac{2}{3} \ \ \frac{1}{4} \ \ \frac{3}{4} \ \ \frac{1}{5} \ \ \frac{2}{5} \ \ \frac{3}{5} \ \ \frac{4}{5} \ \ \frac{1}{6} \ \ \frac{5}{6} \ \ \frac{1}{7} \ \ \frac{2}{7} \ \ \frac{3}{7} \ \ \frac{4}{7} \ \ \frac{5}{7} \ \ \frac{6}{7} \ \ \frac{1}{8} \ \ \frac{3}{8} \ \ \frac{5}{8} \ \ \frac{7}{8}$

Der Größe nach sortiert ergibt sich:

$F_8 = \frac{0}{1} \ \ \frac{1}{8} \ \ \frac{1}{7} \ \ \frac{1}{6} \ \ \frac{1}{5} \ \ \frac{1}{4} \ \ \frac{2}{7} \ \ \frac{1}{3} \ \ \frac{3}{8} \ \ \frac{2}{5} \ \ \frac{3}{7} \ \ \frac{1}{2} \ \ \frac{4}{7} \ \ \frac{3}{5} \ \ \frac{5}{8} \ \ \frac{2}{3} \ \ \frac{5}{7} \ \ \frac{3}{4} \ \ \frac{4}{5} \ \ \frac{5}{6} \ \ \frac{6}{7} \ \ \frac{7}{8} \ \ \frac{1}{1}$

Die zweite Methode benutzt eine spezielle Form der Addition von Brüchen und die vorhergehende Farey-Reihe muss bekannt sein. Man ergänzt dabei die vorhergehende Farey-Reihe um Brüche, die man aus einer Operation jeweils nebeneinander liegender Brüche gewinnt, die aber eine Bedingung erfüllen müssen: die Summe der Nenner der beiden Brüche muss N ergeben. Die Operation sieht wie folgt aus: wenn die beiden, nebeneinander liegenden Brüche $\frac{a}{b}$ und $\frac{c}{d}$ sind, und die Summe der beiden Nenner b und d = N ist, dann ist der neue Bruch $\frac{a+c}{b+d}$ .

Für diese Operation hat sich die Bezeichnung Farey-Addition etabliert. Durch die gemachte Einschränkung $\left(b+d\right) \le N \$ gilt für jede Farey-Folge, dass sie Teilmenge der Peirce-Zahlen $\mathbb V_N \$ ist:

[Bearbeiten] Beispiel (Methode 2)

Berechnet werden soll F₇. $F_6 = \frac{0}{1} \ \frac{1}{6} \ \frac{1}{5} \ \frac{1}{4} \ \frac{1}{3} \ \frac{2}{5} \ \frac{1}{2} \ \frac{3}{5} \ \frac{2}{3} \ \frac{3}{4} \ \frac{4}{5} \ \frac{5}{6} \ \frac{1}{1}$

Nebeneinander liegende Brüche, deren Nenner als Summe gleich 7 ergeben, sind:

$\frac{0}{1} \ \frac{1}{6} \ \ ; \ \ \frac{1}{4} \ \frac{1}{3} \ \ ; \ \ \ \frac{2}{5} \ \frac{1}{2} \ \ ; \ \ \frac{1}{2} \ \frac{3}{5} \ \ ; \ \ \frac{2}{3} \ \frac{3}{4} \ \ ; \ \ \frac{5}{6} \ \frac{1}{1}$

$\frac{0+1}{1+6} = \frac{1}{7} \ \ ; \ \ \frac{1+1}{4+3} = \frac{2}{7} \ \ ; \ \ \ \frac{2+1}{5+2} = \frac{3}{7} \ \ ; \ \ \frac{1+3}{2+5} = \frac{4}{7} \ \ ; \ \ \frac{2+3}{3+4} = \frac{5}{7} \ \ ; \ \ \frac{5+1}{6+1} = \frac{6}{7}$

Richtig einsortiert ergibt sich:

$F_7 = \frac{0}{1} \ \frac{1}{7} \ \frac{1}{6} \ \frac{1}{5} \ \frac{1}{4} \ \frac{2}{7} \ \frac{1}{3} \ \frac{2}{5} \ \frac{3}{7} \ \frac{1}{2} \ \frac{4}{7} \ \frac{3}{5} \ \frac{2}{3} \ \frac{5}{7} \ \frac{3}{4} \ \frac{4}{5} \ \frac{5}{6} \ \frac{6}{7} \ \frac{1}{1}$

[Bearbeiten] Eigenschaften

Mächtigkeit: Die Mächtigkeit einer Farey-Reihe ist gleich der Mächtigkeit der Vorgängerreihe addiert mit dem Eulertotient von N: $|F_N| =|F_{N-1}| + \varphi(N)$

Bei zwei aufeinander folgenden Brüchen $\tfrac{a}{c}$ und $\tfrac{b}{d}$ ergeben die Produkte m=a·d und n=b·c zwei aufeinander folgende Zahlen. Man kann auch schreiben: $\begin{vmatrix} a & b \\ c & d \end{vmatrix} = (a\cdot d)-(b \cdot c) = -1$

Sind umgekehrt $\tfrac ac$ und $\tfrac bd$ zwei Brüche mit $0\le\tfrac ac < \tfrac bd\le1$ und $a d - b c = - 1$ , so handelt es sich um Nachbarn bis zur Farey-Folge $F c + d - 1$ , mit anderen Worten: Jeder dazwischen liegende Bruch $\tfrac pq$ hat einen Nenner $q \ge c+d$ . In der Tat müssen nämlich die Zähler der positiven Brüche $\tfrac pq - \tfrac ab = \tfrac{bp-aq}{qb}$ und $\tfrac cd-\tfrac pq = \tfrac{cq-dp}{dq}$ positive ganze Zahlen sein, also $bp-aq\ge 1$ und $cq-dp\ge1$ . Hieraus folgt $q=(bc-ad)\cdot q = b\cdot(cq-dp) + d\cdot(bp-aq) \ge b+d$ . Ebenso folgt $p = (bc-ad)\cdot p = c\cdot(bp-aq) + a\cdot(cq-dp)\ge c+a$ . Beide Ungleichungen werden scharf genau für die Farey-Summe $\tfrac pq=\tfrac{a+c}{b+d}$ .