suite de Farey
ANALYSE
Du nom d’un géologue anglais qui les a découvertes en 1816.
Une suite de Farey de rang n est la suite des fractions irréductibles a/b rangées par ordre croissant, pour lesquelles on a ≤ b≤ n.
Il suffit que a/b appartienne à [0 , 1[ car la partie de la suite compris entre p et p+1 se déduit de celle comprise entre 0 et 1 en ajoutant p à cette dernière.
Exemple ; pour n = 5, on a entre 0 et 1 les fractions 0/1 ; 1/5 ; 1/4; 1/3 ; 2/5 ; 1/2 ; 3/5 ; 2/3 ; 3/4 ; 4/5.
Le nombre d’éléments de la suite de rang n est Σk=1k=n φ(k) où φ est la fonction indicatrice d’Euler (ou indicateur d’Euler).
Propriété :
a/b et a’/b’ étant deux fractions consécutives de la suite de Farey de rang n, ab’-ba’ = 1 ou -1