Arbre de Stern-Brocot

l'arbre dit de Stern-Brocot a été découvert en 1858 (Über eine zahlentheoretische Funktion. Crelle's Journal 55:193-220) par le mathématicien allemand Moritz Stern (1807-1894) et de manière indépendante en 1861 (Calcul des rouages par approximation, nouvelle méthode. Revue Chronométrique 3:186-194) par l'horloger français Achille Brocot (1817-1878) [DMA].

L'arbre de Stern-Brocot représenté ci-contre contient toutes les fractions irréductibles strictement positives a/b et uniquement ces fractions. (Le numérateur a et se dénominateur b sont deux naturels premiers entre-eux).

Si tout en haut de l'arbre, on place la fraction 0/1 à l'extrême gauche et l'écriture 1/0 à droite, on explique plus aisément la manière de construire l'arbre de Stern-Brocot :

Chaque fraction est la médiante¹

 m      a + c                 a         c
---  = --------- médiante de --- et de ---
 n      b + d                 b         d

des deux fractions situées au-dessus de m/n, les plus proches horizontalement, a/b à gauche et c/d à droite.
(1) Edouard Lucas, à la p. 467 de son ouvrage "Théorie des nombres" de 1891, utilise la même définition et dit : « nous obtenons une fraction que nous appellerons la médiante des deux premières ». Quelques lignes plus loin : « Ainsi par ce procédé dit de médiation, dont on trouve de nombreux exemples dans les ouvrages d'Archimède et des géomètres de l'Inde, nous formons... ».
On obtient par exemple 3/5 à partir de 1/2 à gauche et 2/3 à droite en calculant le numérateur 3 = 1+2 et le dénominateur 5 = 2+3.

La moitié gauche de la liste ordonnée de toutes les fractions des k premiers niveaux confondus est une suite comme celle-ci : [Cliquer] (En prenant les fractions inverses dans, l'ordre inverse, on obtiendra l'autre moitié de la liste).

Le numérateur de la fraction médiante obtenue est la somme des numérateurs des deux fractions. Le dénominateur est la somme des dénominateurs.
Si a/b et c/d sont consécutives dans la liste de rang n, alors bc-ad=1 (égalité de Bézout).
On démontre aisément cette propriété par récurrence : de bc-ad=1 on déduit ab-ab + bc-ad=1, c.-à-d. b(a+c)-a(b+d)=1 au rang n+1 ...
Les fractions de l'arbre sont irréductibles. En effet les relations bc-ad=1 le prouvent pour a/b et pour c/d à la fois.
La médiante est comprise entre les deux fractions intervenant dans son calcul a/b < (a+c)/(b+d) < c/d. En effet bc-ad >0 entraîne b(a+c)-a(b+d)>0 et aussi (b+d)c-(a+c)d>0.

Suite de Stern-Brocot SB_k pour k =    

Les suites de Farey F_k s'obtiennent en ne conservant que les fractions de dénominateur inférieur ou égal à k comprises entre 0/1 et 1/1 comme dans ou encore
On obtient aussi la suite de Farey F_k en insérant les fractions de dénominateur k dans la suite F_k-1, comme médiantes de deux fractions de F_k-1.
On a donc encore la propriété bc-ad=1 pour a/b et c/d consécutives dans F_k.

Suite de Farey F_k pour k =    

En notant les mouvements L vers la gauche et R vers la droite (L=left, R=right) lorsqu'on parcourt l'arbre depuis sa racine 1/1 jusqu'à la fraction a/b, on obtient un mot utilisant les lettres l'alphabet binaire {L, R}.
Ce mot représente le rationnel a/b.
Le mot vide code le rationnel 1/1.

Par exemple 4/7 = LRLL = LRL². Le parcours passe par les fractions 1/1 la racine, 1/2, 2/3, 3/5 et 4/7.

Soit le réel x>0 correspondant au mot R^a₀ L^a₁ R^a₂ L^a₃ ...
(On commence toujours par R^a₀ et a₀ est éventuellement nul contrairement à a₁, a₂ ... qui sont strictement positifs).
Le réel x a pour développement en fraction continue [a₀ ; a₁, a₂, a₃ ... ] c'est-à-dire a₀+1/(a₁+1/(a₂+1/(a₃+ ...))).
Les réduites du développement de x sont obtenues dans le parcours de l'arbre de Stern-Brocot, elles encadrent x au plus près, alternativement inférieures et supérieures à x. Si, par exemple la fraction r_k< x est une réduite, la fraction suivante du parcours, ou même plusieurs fractions successives, sont supérieures à x, la plus petite de ce groupe est la prochaine réduite r_k+1 > x. On en déduit un algorithme de recherche des fractions continues bien plus efficace que celui qui calcule la partie entière et l'inverse de la partie décimale.

Par exemple la nombre exp(1) = e = 2,7182818... base des logarithmes népériens, se développe en R²L¹R²L¹R¹L⁴R¹L¹R⁶L¹R¹L⁸R¹L¹R¹⁰... et a pour fraction continue [ 2 ; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, ...] = 2+1/(1 +1/(2 +1/(1+1/(4+1/(1+1(6+...)))))), on devine la suite, Euler a démontré la propriété en partant de la fraction continue de th(1/2).
Les réduites de e sont 2/1, 3/1, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 299/110, 1264/465 etc. Repérez leurs positions parmi les fractions obtenues.
Plus généralement, le développement en fraction continue de e^l/m où l et m sont entiers strictement positifs, n'est connu que pour quelques valeurs particulières de l et de m (l/m irréductible et l=1 ou l=2).
L'algorithme développé en 1978 par L. Davison [DA] utilise une décomposition de matrices en produits des matrices L, R (qui correspondent exactement au parcours dans l'arbre de Stern-Brocot).
Une implémentation a été réalisée par Keith Matthews [KM] dans les langages bc et php (extension).

Lire tous les résultats dans l'espace ci-dessus [Back]

LRLRLRLR   L2RL2RL2RL2RL2RL2RL2RL2R   LRLR2LR3LR4LR5LR6

   

2/3   28245729/10391023 : exp(1) = e,   355/113 : Pi,   275807/195025 : racine carrée de 2  

   

2/3 (valeur approchée par un décimal 0,6...6 et non une valeur exacte, le mot obtenu a été limité volontairement aux 1000 premiers caractères !)  
exp(1) = e base des logarithmes népériens. e^2   e^-1   PI   PI^2   1/PI   racine(2)   1/racine(2)   racine(3)   racine(5)   racine(6)   racine(7)   racine(8)   racine(10)   ln(2)  

   

Avec le nombre d'or (racine(5)+1)/2 observez comment les numérateurs et dénominateurs vous donnent la suite de Fibonacci pour un parcours RLRLR... très simple de l'arbre.

Approximations successives par les fractions de l'arbre de Stern-Brocot d'un nombre donné. (Elles sont données dans les exemples des paragraphes ci-dessus).

L'exemple ci-dessus reprend le calcul approché de la racine carrée de 2 par Théon de Smyrne mais avec une petite modification : chaque fraction a/b est suivie par la fraction [2b/a] qui s'insére alors dans la suite originale, ceci pour permettre de retrouver toutes les fractions du chemin RLLRRLL... de l'arbre de Stern-Brocot.
On part de 1/1 et on effectue les calculs a/b, [2b/a], (a+2b)/(a+b), [2(a+b)/(a+2b)] ...