Farey-Reihe

Farey-Reihe
1. Definition. Fur jede naturliche Zahl n > 1 definieren wir die Farey-Reihe FARn .
Die Farey-Reihe FARn ist die Menge der gek
urzten Br
uche zwischen 0 und 1, deren
jeweiliger Nenner den Index n nicht u
bersteigt. Die einzelnen Br
uche einer Farey-Reihe
sind der Große nach sortiert.
Beispiel: Die Bruche fur FAR6 :
0 1 1 1 2 1 3 1 2 3 4 1 5
, , , , , , , , , , , , .
1 1 2 3 3 4 4 5 5 5 5 6 6
Der Große nach sortiert ergibt sich:
FAR6 :
0 1 1 1 1 2 1 3 2 3 4 5 1
, , , , , , , , , , , , .
1 6 5 4 3 5 2 5 3 4 5 6 1
Das Sortieren nimmt sehr viel Zeit. Deshalb benutzt man die folgende Methode, mit
der man schnell FARn aus FARn−1 bilden kann. F
ur jeden der zwei Br
uche ab è dc , die
in der Reihe FARn−1 nebeneinander liegen und die Bedingung b + d = n erf
ullen, bilden
a
c
wir einen neuen Bruch a+c
.
Diesen
Bruch
stellen
wir
zwischen
und
ein.
b+d
b
d
Beispiel: Bilden wir FAR7 aus FAR6 :
0 1 1 1 1 2 1 3 2 3 4 5 1
, , , , , , , , , , , , .
1 6 5 4 3 5 2 5 3 4 5 6 1
V
V
V V
V
V
1
7
Also:
2
7
3
7
4
7
5
7
6
7
0 1 1 1 1 2 1 2 3 1 4 3 2 5 3 4 5 6 1
, , , , , , , , , , , , , , , , , , .
1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 1
FAR7 :
Aufgabe 1. Berechnen Sie FAR8 .
Aufgabe 2. Fur jeden der zwei aufeinander folgenden Bruche ab , dc in der Farey-Reihe
FARn gilt die Formel ad − bc = −1. Beweisen Sie das per Induktion.
Aufgabe 3∗ . Begrunden Sie die zweite Methode, mit der man FARn aus FARn−1
bilden kann.
Aufgabe 4. Beweisen Sie, daß die Machtigkeit der Farey-Reihe FARn gleich der
Machtigkeit der Vorgangerreihe ist addiert mit der Euler'schen Funktion von n:
|FARn | = |FARn−1 | + ϕ(n).
Aufgabe 5∗ . Beweisen Sie mit Hilfe der Farey-Reihe den folgenden Satz:
Satz. Sei n > 1 eine naturliche Zahl. Dann jede reale Zahl α in der folgenden Form
dargetellt sein kann:
α=
P
θ
+
,
Q Qn
wobei 0 < Q 6 n, (P, Q) = 1, |θ| < 1
1
ist.

Download Report