Suite de Farey - Définition

Histoire

L'histoire des 'séries de Farey' est très curieuse — Hardy & Wright (1979) Chapitre III

... une fois encore, l'homme dont le nom fut donné à la relation mathématique n'était pas celui qui l'a découverte. — Beiler (1964) Chapitre XVI

Les suites de Farey furent nommées en l'honneur du géologue britannique, Sir John Farey. Sa lettre à propos de ces suites fut publiée dans le Philosophical Magazine en 1816. Farey conjectura que chaque terme dans une telle suite est le médian de ses voisins — néanmoins, à ce que l'on connaît, il ne prouva pas cette propriété. La lettre de Farey fut lue par Cauchy, qui donna la preuve dans ses Exercices de mathématique, et attribua ce résultat à Farey. En fait, un autre mathématicien, C. Haros, publia des résultats similaires en 1802 qui ne fut pourtant certainement pas autant connu que Farey ou Cauchy. Ainsi, c'est un accident historique qui relie le nom de Farey à ces suites.

Un algorithme simple

De manière surprenante, un algorithme simple existe pour engendrer les termes dans un ordre, soit traditionnel (ascendant), soit non-traditionnel (descendant) :

       100   'Code UBASIC pour engendrer une Suite de Farey d'ordre N dans l'ordre traditionnel       110   N=7:NumTerms=1       120   A=0:B=1:C=1:D=N       140   print A;B       150   while (C       
Cet algorithme se déduit du fait que, si a / b et c / d sont deux termes successifs dans une suite de Farey alors les successeurs de c / d sont tous de la forme (kc − a) / (kd − b). Pour trouver le successeur à l'ordre n il faut trouver le plus grand k tel que 

    
    
 et celui-ci est fourni par la partie entière du quotient de n + b par d.
 
Pour engendrer la suite dans un ordre descendant (non-traditionnel) :
       120   A=1:B=1:C=N-1:D=N       150   while (A>0)      
       
Des recherches en force brute pour les solutions d'équations diophantiennes rationnelles peuvent souvent prendre l'avantage sur les suites de Farey (pour chercher seulement celles en formes réduites); la ligne 120 peut aussi être modifiée pour inclure deux termes adjacents quelconques afin d'engendrer seulement les termes plus grands (ou plus petits) qu'un terme donné.


Propriétés
 
 - Introduction - Exemples - Propriétés - Histoire - Un algorithme simple