Farey Sequences – Ταξινόμηση των Ρητών στο [0, 1]

Οι Ακολουθίες Farey

Η ακολουθία Farey τάξης \(n\), \(F_n\), είναι η ακολουθία όλων των ανάγωγων ρητών αριθμών στο διάστημα \([0,1]\) με παρονομαστή μικρότερο ή ίσο με \(n\), γραμμένων σε αύξουσα σειρά. Περιλαμβάνουμε πάντα το \(0 = \dfrac{0}{1}\) και το \(1 = \dfrac{1}{1}\).

---

Παραδείγματα:

\(F_1:\quad \dfrac01,\ \dfrac11\)

\(F_2:\quad \dfrac01,\ \dfrac12,\ \dfrac11\)

\(F_3:\quad \dfrac01,\ \dfrac13,\ \dfrac12,\ \dfrac23,\ \dfrac11\)

\(F_4:\quad \dfrac01,\ \dfrac14,\ \dfrac13,\ \dfrac12,\ \dfrac23,\ \dfrac34,\ \dfrac11\)

\(F_5:\quad \dfrac01,\ \dfrac15,\ \dfrac14,\ \dfrac13,\ \dfrac25,\ \dfrac12,\ \dfrac35,\ \dfrac23,\ \dfrac34,\ \dfrac45,\ \dfrac11\)

\(F_6:\quad \dfrac01,\ \dfrac16,\ \dfrac15,\ \dfrac14,\ \dfrac13,\ \dfrac25,\ \dfrac12,\ \dfrac35,\ \dfrac23,\ \dfrac34,\ \dfrac45,\ \dfrac56,\ \dfrac11\)

\(F_7:\quad \dfrac01,\ \dfrac17,\ \dfrac16,\ \dfrac15,\ \dfrac14,\ \dfrac27,\ \dfrac13,\ \dfrac25,\ \dfrac37,\ \dfrac12,\ \dfrac47,\ \dfrac35,\ \dfrac23,\ \dfrac34,\ \dfrac45,\ \dfrac56,\ \dfrac67,\ \dfrac11\)

---

Βασικές Ιδιότητες

1. Γείτονες: Αν \(\dfrac{a}{b} < \dfrac{c}{d}\) είναι διαδοχικοί όροι στο \(F_n\), τότε \(bc - ad = 1\).
2. Mediant: Ο μέσος \(\dfrac{a+c}{\,b+d\,}\) βρίσκεται μεταξύ τους και ανήκει στο \(F_m\) για κάθε \(m \ge b+d\).
3. Μήκος: \[ |F_n| = 1 + \sum_{k=1}^n \varphi(k), \quad \varphi \text{ του Euler}. \] Ασύμπτωτα: \(|F_n| \sim \dfrac{3}{\pi^2}n^2\).
4. Εύρεση επόμενου όρου: Αν \(\dfrac{a}{b}\), \(\dfrac{c}{d}\) είναι διαδοχικοί, τότε \[ k = \left\lfloor \dfrac{n + b}{d} \right\rfloor, \quad \text{επόμενος} = \dfrac{kc-a}{kd-b}. \]

---

Ασκήσεις

1. Βρείτε το \(F_8\).
2. Δείξτε ότι αν \(\dfrac{a}{b}\) και \(\dfrac{c}{d}\) είναι γείτονες στο \(F_n\), τότε \(b+d>n\).
3. Υπολογίστε το πλήθος των όρων του \(F_{10}\).
4. Εντοπίστε όλα τα κλάσματα του \(F_9\) με παρονομαστή ίσο με 9.