suite de Stern-Brocot

Partons de 0 et 1, puis regardons les premiers termes : 0, 1, 1, 2, 1, 3, 2, 3, 1. À chaque indice pair positif, la suite recopie un terme déjà rencontré. À chaque indice impair supérieur à 1, elle additionne deux termes voisins d'une étape précédente.

Cette alternance entre copie et somme produit une suite très organisée à partir de deux seules valeurs initiales. La parité de l'indice indique immédiatement laquelle des deux règles employer.

La suite diatomique de Stern, aussi appelée suite de Stern-Brocot, est une suite d'entiers naturels notée a. Son terme d'indice 0 vaut 0 et son terme d'indice 1 vaut 1. Pour tout entier n strictement positif, les deux règles de récurrence sont :

La première égalité traite les indices pairs : diviser l'indice par 2 ramène à une valeur antérieure. La seconde traite les indices impairs supérieurs à 1 : les deux indices n et n + 1 sont voisins, et leurs valeurs sont additionnées. Les premières valeurs sont a(0) = 0, a(1) = 1, a(2) = 1, a(3) = 2, a(4) = 1, a(5) = 3, a(6) = 2 et a(7) = 3. Introduite par Moritz Stern en 1858, cette suite est liée à l'arbre de Stern-Brocot, aux fractions continues et à l'arithmétique des nombres rationnels.

La structure repose sur quatre éléments. Les deux conditions initiales, a(0) = 0 et a(1) = 1, amorcent la suite. L'indice entier naturel indique le terme demandé. Sa parité choisit ensuite la branche de la récurrence : une branche de copie pour un indice pair, une branche de somme pour un indice impair supérieur à 1.

Les deux branches réduisent le calcul à des indices plus petits. Dans la branche paire, 2n dépend seulement de n. Dans la branche impaire, 2n + 1 dépend des deux voisins n et n + 1. Les conditions initiales arrêtent ces descentes. Ces données suffisent à déterminer chaque terme de manière unique ; la façon de disposer ou de colorer les valeurs ne fait pas partie de la définition.

Calculons le terme d'indice 13. Le schéma de dépendance rend visibles les copies et les sommes nécessaires, jusqu'aux valeurs déjà connues.

Données.
Indice demandé : 13.
Conditions initiales : a(0) = 0 et a(1) = 1.
Règle paire : a(2n) = a(n).
Règle impaire : a(2n + 1) = a(n) + a(n + 1), pour n > 0.

Étape 1. Comme 13 = 2 × 6 + 1, l'indice est impair. La règle de somme donne a(13) = a(6) + a(7).

Étape 2. Comme 6 = 2 × 3, la règle de copie donne a(6) = a(3). Puis 3 = 2 × 1 + 1, donc a(3) = a(1) + a(2) = 1 + 1 = 2.

Étape 3. Comme 7 = 2 × 3 + 1, a(7) = a(3) + a(4). Or a(3) = 2 et a(4) = a(2) = a(1) = 1, donc a(7) = 3.

Résultat et contrôle. On obtient a(13) = 2 + 3 = 5. En construisant directement les termes de a(0) à a(13), on trouve 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5 : la dernière valeur confirme le calcul.

Pour calculer un terme isolé, on traite directement a(0) et a(1), qui sont les cas initiaux. Pour tout autre terme, on examine la parité de son indice. Un indice pair positif est immédiatement divisé par 2. Un indice impair supérieur à 1 ouvre deux calculs voisins, dont les résultats sont additionnés. Cette descente est préférable à la construction de toute la liste lorsque seul un terme est demandé.

Pour produire une tranche complète de la suite, on pose d'abord les cas initiaux, puis on avance par indices croissants. Au moment de calculer a(2n), le terme a(n) est déjà disponible. Pour calculer a(2n + 1), les termes a(n) et a(n + 1) sont déjà disponibles. Cette méthode évite de recommencer les mêmes sous-calculs.

Pour étudier les rationnels associés, la suite intervient par les rapports de deux termes consécutifs. On conserve alors le couple a(n), a(n + 1), plutôt qu'un terme seul, car l'information utile porte sur les deux voisins.

Suite de Stern-Brocot et arbre de Stern-Brocot. La suite est une liste d'entiers indexée par n, tandis que l'arbre organise des nombres rationnels en branches. Le terme a(13) = 5 appartient à la suite ; une fraction placée entre deux fractions parentes relève de l'arbre.

Suite et fraction continue. Une fraction continue est une représentation emboîtée d'un nombre, pas une suite définie par les deux règles pair-impair de Stern. Les deux sujets sont liés, mais la présence de quotients emboîtés signale une fraction continue, tandis qu'un calcul comme a(6) = a(3) signale la suite.

L'indice 0 est un cas initial, pas un passage par la règle paire. Écrire n = 0 dans a(2n) = a(n) ne calcule rien : on obtient a(0) = a(0). Il faut partir de la condition a(0) = 0.

L'indice 1 est lui aussi initial. La règle impaire donnée pour n > 0 commence à l'indice 3. La valeur a(1) = 1 doit donc être fournie avant toute récurrence.

Une valeur répétée n'a pas une position unique. Le nombre 1 apparaît notamment aux indices 1, 2, 4 et 8. Retrouver une valeur ne suffit donc pas à retrouver son indice ; il faut conserver l'indice avec le terme.

La somme ne porte pas sur les termes précédents dans la liste. Pour l'indice 13, on additionne a(6) et a(7), non a(11) et a(12). Le bon réflexe consiste à écrire 13 sous la forme 2n + 1 avant de choisir les deux termes.

Fraction continue — Pour étudier la représentation arithmétique qui éclaire le lien entre la suite et les nombres rationnels.

Les fractions continues, — Pour prolonger la relation annoncée dans la définition par un article consacré à cette écriture des nombres.