algorithme de Fibonacci-Sylvester

Prenons 5/7. Parmi les fractions de numérateur 1 qui ne dépassent pas 5/7, la plus grande est 1/2. Après l'avoir retirée, il reste 3/14. La méthode recommence sur ce reste : elle choisit 1/5, puis atteint 1/70.

L'algorithme de Fibonacci-Sylvester avance donc par choix gloutons : à chaque tour, il prend la plus grosse part unitaire autorisée, sans anticiper les tours suivants. Pour un rationnel positif, le procédé finit et fournit une somme de fractions unitaires.

Une fraction unitaire est une fraction de la forme 1/n, où le dénominateur n est un entier strictement positif. L'algorithme glouton de Fibonacci-Sylvester décompose un rationnel positif en une somme finie de telles fractions. Pour une fraction propre a/b, avec a et b entiers strictement positifs et a inférieur à b, il choisit le plus petit entier n tel que 1/n ne dépasse pas a/b.

Cet entier est le plafond du quotient b/a. Le choix et le nouveau reste s'écrivent :

Si a divise b, la fraction de départ est déjà unitaire et le procédé s'arrête. Sinon, le numérateur positif an − b du reste est strictement inférieur à a. Cette décroissance entière garantit l'arrêt après un nombre fini d'étapes. Pour un rationnel supérieur ou égal à 1, la règle retire d'abord 1/1 autant de fois que nécessaire, puis traite la partie propre. Dans le cas propre, les dénominateurs obtenus sont strictement croissants.

Soit a/b un rationnel strictement positif écrit avec des entiers a et b strictement positifs. À chaque étape, on prend n égal au plafond de b/a, on inscrit la fraction unitaire 1/n, puis on remplace a/b par le reste a/b − 1/n réduit en fraction.

Le reste est toujours positif ou nul. S'il est nul, la décomposition est terminée ; sinon, la même règle s'applique au nouveau rationnel. Pour une fraction propre, le numérateur du reste diminue strictement, donc l'arrêt a lieu en un nombre fini d'étapes.

La donnée doit être un nombre rationnel strictement positif. Une écriture a/b avec a et b entiers positifs suffit ; réduire la fraction avant de commencer simplifie les calculs, sans changer les fractions unitaires choisies. À chaque tour, le dénominateur n est déterminé sans ambiguïté par le plafond de b/a.

Le cas a = 1 est le point d'arrêt : a/b est déjà une fraction unitaire. Le cas a = 0 ne demande aucune décomposition non vide, et les nombres négatifs sortent du domaine annoncé ; on peut traiter séparément leur valeur absolue puis remettre le signe. Pour un irrationnel positif, les soustractions peuvent se poursuivre, mais la preuve d'arrêt par décroissance d'un numérateur entier ne s'applique plus : ce n'est pas une décomposition finie garantie par cet algorithme.

Décomposons 5/7. Le schéma synthétise les deux soustractions successives et permet de suivre le reste exact jusqu'à la dernière fraction unitaire.

Données.
Fraction de départ : 5/7.
Numérateur : a = 5.
Dénominateur : b = 7.

Étape 1. Le plafond de 7/5 vaut 2. La plus grande fraction unitaire qui ne dépasse pas 5/7 est donc 1/2. Le reste vaut :

Étape 2. Le plafond de 14/3 vaut 5. On retire 1/5 au reste 3/14 :

Étape 3. Le reste 1/70 est unitaire : l'algorithme s'arrête. Le résultat est $\frac{5}{7}=\frac{1}{2}+\frac{1}{5}+\frac{1}{70}\backslash frac\{5\}\{7\}=\backslash frac\{1\}\{2\}+\backslash frac\{1\}\{5\}+\backslash frac\{1\}\{70\}$.

Contrôle. Avec le dénominateur commun 70, les trois termes donnent 35/70 + 14/70 + 1/70 = 50/70 = 5/7.

Pour construire une décomposition égyptienne à la main, on calcule le plafond du quotient dénominateur/numérateur, puis on soustrait la fraction unitaire obtenue. Sur 5/7, ce geste donne successivement les dénominateurs 2, 5 et 70.

Dans un programme, il vaut mieux conserver des entiers et réduire chaque reste par le plus grand commun diviseur. Les calculs restent alors exacts ; des nombres décimaux introduiraient des erreurs d'arrondi et rendraient le test d'arrêt fragile.

Pour additionner rapidement des fractions déjà données, un dénominateur commun est souvent plus direct. L'algorithme glouton est préférable lorsque l'objectif est précisément d'obtenir une somme de fractions unitaires, pas nécessairement celle qui comporte le moins de termes.

Fraction égyptienne et algorithme glouton. Une fraction égyptienne est une représentation en fractions unitaires ; l'algorithme de Fibonacci-Sylvester est une procédure particulière pour en produire une. La somme 5/7 = 1/2 + 1/5 + 1/70 est à la fois le résultat et la représentation, tandis que les choix successifs constituent l'algorithme.

Algorithme de Fibonacci-Sylvester et suite de Sylvester. Le premier part d'un rationnel strictement positif et choisit un dénominateur par plafond. La seconde commence par 2 et chaque terme est le produit des précédents augmenté de 1 : 2, 3, 7, 43, 1807, … Elle fournit des identités particulières pour 1, mais elle n'est pas la liste des dénominateurs obtenus pour toute fraction.

Choix glouton et décomposition minimale. « Glouton » signifie choisir à chaque étape la plus grande fraction unitaire admissible. Cela ne signifie pas minimiser globalement le nombre de termes ou les dénominateurs ; ces deux objectifs peuvent demander une autre recherche.

Entiers et rationnels supérieurs à 1. La règle autorise alors 1/1 et peut le répéter. Si l'on réserve l'expression « fraction égyptienne » aux fractions propres avec des dénominateurs distincts, on sépare d'abord la partie entière et on applique l'algorithme à la partie fractionnaire.

Croissance des dénominateurs. L'arrêt est garanti, mais les dénominateurs peuvent devenir très grands. Dans l'exemple 5/7, ils passent déjà de 2 à 5 puis à 70. Il faut donc employer des entiers exacts de taille suffisante plutôt que conclure à un échec lorsque les valeurs gonflent.

Troncature de la série de Sylvester. Dans l'identité liée à 2, 3, 7, 43, …, on remplace le dernier dénominateur retenu s_n par s_n − 1. On ne soustrait pas 1 à toute la somme : 2, 3, 7 donnent ainsi 1/2 + 1/3 + 1/6 = 1.

La fraction égyptienne replace l'algorithme dans l'étude plus générale des représentations d'un rationnel comme somme de fractions unitaires.

La suite de Sylvester révèle une identité télescopique : chaque inverse 1/s_n est la différence entre deux fractions successives liées aux produits des termes. Cette structure explique à la fois la convergence de la série des inverses vers 1 et les décompositions finies obtenues en remplaçant le dernier dénominateur par s_n − 1.