suite de Farey

Prenez les dénominateurs de 1 à 5 et placez entre 0 et 1 toutes les fractions qui ne se simplifient plus. On obtient 0/1, puis 1/5, 1/4, 1/3, 2/5, jusqu’à 4/5. Une écriture comme 2/4 disparaît, car elle représente déjà 1/2.

La suite de Farey de rang 5 est précisément cette liste rangée. Le rang fixe la taille maximale des dénominateurs ; augmenter le rang conserve les anciennes fractions et insère de nouvelles valeurs à leur juste place.

Soit n un entier positif. Dans la convention de cette fiche, la suite de Farey de rang n, notée F_n, rassemble les fractions a/b telles que a est entier, 0 ≤ a/b < 1, avec un dénominateur b entier positif ne dépassant pas n. La fraction doit être irréductible : le plus grand commun diviseur de a et b vaut 1. Les valeurs sont rangées dans l’ordre croissant, donc chaque nombre rationnel admissible apparaît une seule fois.

Le nombre de termes est donné par l’indicatrice d’Euler φ, qui compte les entiers de 1 à k premiers avec k : $\mathrm{\mid }{F}_n\mathrm{\mid }={\sum }_{k=1}^n\phi (k)|F\_n|=\backslash sum\_\{k=1\}^\{n\}\backslash varphi(k)$. Cette formule correspond à l’intervalle semi-ouvert [0, 1[. Avec la convention courante qui inclut aussi 1/1, il faut ajouter un terme.

Si a/b précède immédiatement c/d dans F_n, alors $bc-ad=1bc-ad=1$. La portion située dans [p, p + 1[, où p est entier, s’obtient en ajoutant p à chaque terme de F_n.

La structure repose sur cinq éléments. Le rang n borne les dénominateurs. L’intervalle [0, 1[ fixe les valeurs retenues. Le numérateur entier a et le dénominateur entier positif b donnent une fraction a/b. L’irréductibilité, c’est-à-dire pgcd(a, b) = 1, élimine les écritures répétées. L’ordre croissant transforme enfin cet ensemble en une suite.

Le rang agit avant le tri : si b dépasse n, la fraction est exclue même si sa valeur est dans l’intervalle. L’irréductibilité agit avant le comptage : 2/4 ne s’ajoute pas à 1/2. Ces données suffisent à construire F_n, à compter ses termes avec φ et à tester la relation entre deux voisins.

Construisons F₅. Données : le rang est 5, l’intervalle est [0, 1[, les dénominateurs autorisés sont 1, 2, 3, 4 et 5, et chaque fraction doit être irréductible.

1. Pour chaque dénominateur, gardons les numérateurs premiers avec lui : 0/1 ; 1/2 ; 1/3 et 2/3 ; 1/4 et 3/4 ; 1/5, 2/5, 3/5 et 4/5.

2. Rangeons ces dix valeurs : 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5. Leur espacement n’est pas régulier, comme le montre leur placement exact sur l’intervalle.

3. Contrôlons le nombre de termes : $\phi (1)+\phi (2)+\phi (3)+\phi (4)+\phi (5)=1+1+2+2+4=10\backslash varphi(1)+\backslash varphi(2)+\backslash varphi(3)+\backslash varphi(4)+\backslash varphi(5)=1+1+2+2+4=10$.

4. Vérifions deux voisinages. Pour 1/3 et 2/5, 3 × 2 − 1 × 5 = 1. Pour 2/5 et 1/2, 5 × 1 − 2 × 2 = 1. Le comptage et ces déterminants confirment la construction.

Pour énumérer sans doublon les rationnels à dénominateur borné, on choisit un rang, on réduit les fractions puis on les ordonne. Une liste brute de toutes les écritures convient moins bien, car 1/2, 2/4 et 3/6 y désignent la même valeur.

Pour chercher des approximations rationnelles sous une borne de dénominateur, les voisins d’un réel dans F_n encadrent les candidats disponibles à ce rang. Si l’objectif est plutôt d’obtenir successivement d’excellentes approximations quand la borne augmente, les fractions continues offrent une organisation plus directe.

Pour passer du rang n au rang n + 1, il est inutile de trier à nouveau toutes les anciennes valeurs : elles gardent leur ordre et seules les fractions irréductibles de dénominateur n + 1 s’insèrent. Le nombre d’ajouts est exactement φ(n + 1).

Avec la liste de toutes les fractions de dénominateur au plus n. Une suite de Farey ne conserve que les écritures irréductibles. Au rang 4, 2/4 n’est donc pas un terme supplémentaire : il coïncide avec 1/2.

Avec l’arbre de Stern-Brocot. Cet arbre organise les rationnels positifs par générations et par médiantes. F_n est, elle, une liste ordonnée définie par une borne sur le dénominateur ; le rang 5 tranche immédiatement la différence.

Avec une fraction continue. Une fraction continue décrit un nombre au moyen de quotients successifs. Une suite de Farey rassemble au contraire tous les rationnels admissibles pour un rang donné ; elle n’est pas le développement d’un seul nombre.

Convention à l’extrémité droite. La source travaille sur [0, 1[, donc 1/1 est exclu et F₁ contient seulement 0/1. De nombreux ouvrages utilisent [0, 1] : leur comptage vaut alors $1+{\sum }_{k=1}^n\phi (k)1+\backslash sum\_\{k=1\}^\{n\}\backslash varphi(k)$. Il faut vérifier la convention avant de comparer deux listes.

Le déterminant 1 ne suffit pas à rang fixé. Deux fractions réduites a/b < c/d vérifiant bc − ad = 1 sont voisines dans F_n seulement si b + d > n. Ainsi, 0/1 et 1/1 vérifient le déterminant, mais 1/2 s’intercale dès le rang 2.

Une fraction hors borne reste absente. Entre 1/3 et 2/5 se trouve leur médiante 3/8, mais son dénominateur 8 dépasse 5. Elle n’appartient donc pas à F₅ ; elle apparaît au rang 8.

La translation conserve l’intervalle semi-ouvert. Ajouter l’entier p envoie [0, 1[ sur [p, p + 1[. Inclure aussi l’extrémité droite ferait compter l’entier p + 1 dans deux intervalles consécutifs.

La fiche Irréductible (fraction rationnelle) précise le critère qui élimine les écritures multiples d’un même quotient.

La fiche Fraction continue présente une autre organisation des rationnels, centrée sur l’approximation successive d’un nombre.

La fiche Rationnels replace les fractions réduites dans l’ensemble de nombres auquel elles appartiennent.