Farey-Folge
Eine Farey-Folge (mathematisch unkorrekt auch Farey-Reihe oder einfach Farey-Brüche) ist in der Zahlentheorie eine geordnete Menge der vollständig gekürzten Brüche zwischen 0 und 1, deren jeweiliger Nenner den Index N nicht übersteigt. Benannt sind die Farey-Folgen nach dem britischen Geologen John Farey Sr., der diese Anordnung der Brüche 1816 vorschlug. Augustin Louis Cauchy griff das auf und benannte die Folgen nach Farey. Tatsächlich hatte aber ein Franzose namens Haros einige grundlegende Eigenschaften dieser Folge schon 1802 veröffentlicht, wovon aber erst später Notiz genommen wurde.

Formale Definition 

Eine Farey-Folge N-ter Ordnung  ist eine geordnete Menge von Brüchen  mit , ,  mit  Indexmenge und , so dass
  für alle  gilt.

Beispiele 

 
 
 
 

.

Die ersten 8 Folgen in einer strukturierten Darstellung:
 F1 = {0   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1}
 F2 = {0   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1/2   ·    ·    ·    ·    ·    ·    ·    ·    ·    ·   1}
 F3 = {0   ·    ·    ·    ·    ·    ·   1/3   ·    ·    ·   1/2   ·    ·    ·   2/3   ·    ·    ·    ·    ·    ·   1}
 F4 = {0   ·    ·    ·    ·   1/4   ·   1/3   ·    ·    ·   1/2   ·    ·    ·   2/3   ·   3/4   ·    ·    ·    ·   1}
 F5 = {0   ·    ·    ·   1/5  1/4   ·   1/3   ·   2/5   ·   1/2   ·   3/5   ·   2/3   ·   3/4  4/5   ·    ·    ·   1}
 F6 = {0   ·    ·   1/6  1/5  1/4   ·   1/3   ·   2/5   ·   1/2   ·   3/5   ·   2/3   ·   3/4  4/5  5/6   ·    ·   1}
 F7 = {0   ·   1/7  1/6  1/5  1/4  2/7  1/3   ·   2/5  3/7  1/2  4/7  3/5   ·   2/3  5/7  3/4  4/5  5/6  6/7   ·   1}
 F8 = {0  1/8  1/7  1/6  1/5  1/4  2/7  1/3  3/8  2/5  3/7  1/2  4/7  3/5  5/8  2/3  5/7  3/4  4/5  5/6  6/7  7/8  1}

Konstruktion 

Für gegebenes n>2 erhält man den Bruch  der Folge  aus den letzten beiden Brüchen derselben Folge:

Dabei bedeuten die unten eckigen Klammern ein Abrunden. Mit Integer-Arithmetik wird bei Division implizit abgerundet, so dass man beispielsweise in Java die Berechnung ohne explizites Abrunden programmieren kann:public class FareySequence {
	@FunctionalInterface
	public static interface BiIntConsumer {
		void accept(int p, int q);
	}
	public static void forEach(int n, BiIntConsumer consumer) {
		int p__ = 0; // p_{i-2} = p_1
		int q__ = 1; // q_{i-2} = q_1
		int p_ = 1; // p_{i-1} = p_2
		int q_ = n; // q_{i-1} = q_2
		consumer.accept(p__, q__);
		consumer.accept(p_, q_);
		while ((q_ != 1)) {
			int p = ((q__ + n) / q_) * p_ - p__; 
			int q = ((q__ + n) / q_) * q_ - q__;
			p__ = p_;
			p_ = p;
			q__ = q_;
			q_ = q;
			consumer.accept(p, q);
		}
	}

	// Beispiel Verwendung:
	public static void main(String[] args) {
		FareySequence.forEach(8,(p, q) -> System.out.print(p + "/" + q+", "));
		// Ausgabe: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1, 
	}
}

Eigenschaften 

Die Mächtigkeit einer Farey-Folge zum Index N ist gleich der Mächtigkeit der Vorgängerfolge zum Index N-1 addiert mit dem Wert der Eulerschen φ-Funktion für N:
.

Bei zwei aufeinander folgenden Brüchen  und  einer Farey-Folge ergeben die Produkte a·d und b·c zwei aufeinander folgende Zahlen. Man kann auch schreiben:
 .

Sind umgekehrt  und  zwei Brüche mit  und , so handelt es sich um Nachbarn bis zur Farey-Folge , mit anderen Worten: Jeder dazwischen liegende Bruch  hat einen Nenner . In der Tat müssen nämlich die Zähler der positiven Brüche  und  positive ganze Zahlen sein, also  und .

Hieraus folgt
 .

Ebenso folgt
 .
Beide Ungleichungen werden scharf genau für die Farey-Summe .

Farey-Folgen und Riemannvermutung 
Jérôme Franel bewies 1924 (ergänzt durch Edmund Landau), dass die Riemannvermutung zu einer Aussage über Farey-Reihen äquivalent ist.

Seien  die Elemente der n-ten Farey-Folge  und sei  der Abstand zwischen dem k-ten Term der n-ten Fareyfolge und dem k-ten Term der äquidistanten Punktreihe im Einheitsintervall mit derselben Anzahl von Termen wie die n-te Fareyfolge. Franel bewies dann die Äquivalenz der Riemannhypothese zu (verwendet werden die Landau-Symbole):

 

und Landau bemerkte, dass die Riemannhypothese dann auch zu

 

äquivalent ist.

Siehe auch 
 Farey-Graph
 Ford-Kreise
 Stern-Brocot-Baum

Literatur 
 John H. Conway, Richard K. Guy: The Book of Numbers. Copernicus Books, New York 1996, ISBN 0-387-97993-X.
 Leonard Eugene Dickson: Farey Series. In: History of the Theory of Numbers, Band 1 (Divisibility and Primality). Carnegie Institution, Washington 1919, S. 155–158.
 Jeffrey Lagarias, Charles Tresser: A walk along the branches of the extended Farey tree. In: IBM Journal of Research and Development, 39, 1995, Nr. 3, S. 283–294.
 Harald Scheid, Andreas Frommer: Zahlentheorie. 4. Auflage. Springer Spektrum, Heidelberg; [u. a.] 2006, ISBN 978-3-8274-1692-6.

Weblinks 
 
 Farey Series auf cut-the-knot
 Skript zu Fibonacci-Zahlen, Kettenbrüchen und Farey-Folgen (PDF; 1,22 MB)
 Horst Hischer: 4000 Jahre Mittelwertbildung (PDF; 4,23 MB)
 Farey-Reihen in der Encyclopedia of Mathematics (Springer)
 Bibliografie mit Beziehung zur riemannschen Vermutung

Einzelnachweise 

Zahlentheorie