Sequenza di Farey

In matematica, la sequenza di Farey è una sequenza, per ogni numero naturale positivo $n$, definita come l'insieme di tutti i numeri razionali irriducibili espressi sotto forma di frazione con numeratore e denominatore compresi tra zero e $n$. Ad esempio

$F_{1} = \left \{ \frac{0}{1} \ ; \ \frac{1}{1} \right \}$

$F_{2} = \left \{ \frac{0}{1} \ ; \ \frac{1}{2} \ ; \ \frac{1}{1} \right \}$

$F_{3} = \left \{ \frac{0}{1} \ ; \ \frac{1}{3} \ ; \ \frac{1}{2} \ ; \ \frac{2}{3} \ ; \ \frac{1}{1}\right \}$

Per i numeratori, sequenza A006842 dell'OEIS, sequenza A006843 per i denominatori.

Proprietà

• La sequenza ha un numero dispari di termini, per ogni $n > 1$, e il termine centrale è sempre $\frac{1}{2}$.

• Dati tre termini della sequenza $\frac{p_1}{q_1} \ , \ \frac{p_2}{q_2} \ , \ \frac{p_3}{q_3} \,$ abbiamo che

$q \cdot p_1 - p \cdot q_1 = 1$

$\frac{p_1}{q_1} = \frac{(p + p_2)}{(q + q_2)} \,$

Di conseguenza, per calcolare i termini di una successione $F_{n+1}$ data la successione $F_{n}$ è sufficiente inserire la frazione mediana

$\frac{a+b}{c+d}$

tra i termini $\frac{a}{c}$ e $\frac{b}{d}$ e cosi via.

• Definito come $N(n) \,$ il numero di termini della sequenza di Farey $F_n \,$, abbiamo che

$N(n)= 1 + \sum_{k=1}^n \phi(k) \,$

Dove $\phi(k) \,$ è la Funzione phi di Eulero.

Voci correlate

• John Farey
• Frazione

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica