# Algorithme glouton pour la décomposition en fractions égyptiennes

En mathématiques, l'algorithme glouton pour la décomposition en fractions égyptiennes est un algorithme permettant de d'exprimer un nombre rationnel strictement positif comme somme de fractions égyptiennes (ou fractions unitaires) distinctes comme par exemple 5/6 = 1/2 + 1/3.
Comme leur nom l'indique, ces décompositions égyptiennes sont utilisées depuis l'époque de l'Égypte ancienne, mais la première méthode systématique publiée pour construire de tels développements a été décrite en 1202 dans le Liber abaci de Léonard de Pise (Fibonacci).
L'algorithme est dit « glouton » car à chaque étape, l'algorithme choisit la plus grande fraction unitaire possible inférieure au nombre considéré.
Fibonacci répertorie en fait plusieurs méthodes différentes pour construire des représentations en fractions égyptiennes. Il inclut la méthode gloutonne comme dernier recours pour les situations où plusieurs méthodes plus simples échouent ; voir à fraction égyptienne une liste plus détaillée de ces méthodes. La méthode gloutonne et ses extensions pour l'approximation des nombres irrationnels ont été redécouvertes plusieurs fois par les mathématiciens modernes, premièrement par James Joseph Sylvester en 1880. Une méthode étroitement liée produisant des approximations plus proches à chaque étape en permettant à certaines fractions unitaires de la somme d'être négatives remonte à Lambert en 1770.
Le développement d'un nombre $x$ produit par l'algorithme glouton est appelé le développement égyptien glouton, le développement de Sylvester ou le développement de Fibonacci-Sylvester de $x$.

## Algorithme et exemples

L'algorithme de Fibonacci développe la fraction irréductible $x/y$ en effectuant à plusieurs reprises la substitution :${\frac {x}{y}}={\frac {1}{\left\lceil {\frac {y}{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}$ (en simplifiant le deuxième terme si nécessaire). Par exemple: ${\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.$ Dans ce développement, le dénominateur 3 de la première fraction unitaire est la partie entière supérieure de 15/7, et la fraction restante 2/15 est le résultat de la simplification de −15 mod 7/15 × 3 = 6/45 . Le dénominateur de la deuxième fraction unitaire, 8, est la partie entière supérieure de 15/2 , et la fraction restante1/120 est ce qui reste de 7/15 après avoir soustrait 1/3 et 1/8 .
Comme à chaque étape du développement le numérateur de la fraction restante à développer diminue strictement, cette méthode aboutit toujours en un temps fini à ce que la dernière fraction soit unitaire ; cependant, comparée aux développements égyptiens antiques ou aux méthodes plus modernes, cette méthode peut produire des développements assez longs, avec de grands dénominateurs. Par exemple, cette méthode donne ${\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},$ alors que d’autres méthodes conduisent à un bien meilleur développement :${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.$ Wagon suggère l'exemple encore plus malheureux 31/311 : la méthode gloutonne conduit à un développement à dix termes, dont le dernier a un dénominateur de plus de 500 chiffres, alors que 31/311 possède une représentation non gloutonne beaucoup plus courte : 1/12 + 1/63 + 1/2799 + 1/8708.

## Suite de Sylvester et meilleure approximation

La suite de Sylvester 2, 3, 7, 43, 1807, ... (  A000058 ) peut être considérée comme générée par un développement glouton infini de ce type pour le nombre 1, où à chaque étape on choisit le dénominateur$\left\lfloor {\frac {y}{x}}\right\rfloor +1$ au lieu de $\left\lceil {\frac {y}{x}}\right\rceil +1$. En tronquant cette suite à $k$ termes et en formant le développement égyptien correspondant, par exemple (pour $k=4$) :${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}$ on obtient la valeur approchée par défaut la plus proche possible de 1 parmi les développements égyptien à $k$ termes$^,$. C'est-à-dire, par exemple, que n'importe quel développement égyptien d'un nombre de l'intervalle ouvert $\left]1,{\frac {1805}{1806}}\right[$ nécessite au moins cinq termes. En 1922, Curtiss décrit une application de ces résultats de meilleure approximation dans la recherche de la borne inférieure du nombre de diviseurs d'un nombre parfait, et Stong décrit en 1983 des applications en théorie des groupes.

## Développements de longueur maximale et conditions de congruence

Toute fraction x/y nécessite au plus $x$ termes dans son développement glouton. Mays et Freitag & Phillips examinent les conditions dans lesquelles la méthode gloutonne produit un développement de x/y en exactement $x$ termes ; ceux-ci peuvent être décrits en termes de conditions de congruence portant sur y.
* Une fraction de type 1/y nécessite un terme dans son développement glouton ; la fraction la plus simple est 1/1 .
* Une fraction de type 2/y nécessite deux termes dans son développement glouton si et seulement si y ≡ 1 (mod 2) ; la fraction la plus simple est 2/3 .
* Une fraction de type 3/y nécessite trois termes dans son développement glouton si et seulement si y ≡ 1 (mod 6), car alors −y mod x = 2 et y(y + 2)/3 est impair, donc la fraction restante après une seule étape du développement glouton, ${\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}$ est formée de termes plus simples. La fraction la plus simple de type 3/y ayant un développement à trois termes est 3/7 .
* Une fraction de type 4/y nécessite quatre termes dans son développement gourmand si et seulement si y ≡ 1 or 17 (mod 24), car alors le numérateur −y mod x de la fraction restante est 3 et le dénominateur est congru à 1 (mod 6) . La fraction la plus simple de type 4/y avec un développement à quatre termes est 4/17 . La conjecture d'Erdős-Straus énonce que toutes les fractions de type 4/y ont un développement avec trois termes ou moins, mais lorsque y ≡ 1 or 17 (mod 24) de tels développements doivent être trouvés par des méthodes autres que l'algorithme glouton, le cas 17 (mod 24) étant couvert par la relation de congruence 2 (mod 3) .
Plus généralement la suite des fractions de type x/y qui ont des développements gloutons à $x$ termes et qui ont le plus petit dénominateur possible $y$ pour $x$ donné est :
$1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots$ suite A048860 de l'OEIS.

## Autres suites d'entiers

La longueur, le dénominateur minimum et le dénominateur maximum du développement glouton pour les fractions avec de petits numérateurs et dénominateurs peuvent être trouvés dans l'Encyclopédie en ligne des suites d'entiers sous forme des suites  A050205,  A050206 et  A050210, respectivement. De plus, le développement glouton de tout nombre irrationnel conduit à une suite infinie croissante d'entiers, et l'OEIS donne les développements de plusieurs constantes connues. Certaines entrées supplémentaires de l'OEIS, bien que non indiquées comme étant produites par l'algorithme glouton, semblent être du même type.

## Développements proches

En général, si l'on veut un développement en fractions égyptiennes dans lequel les dénominateurs sont contraints d'une certaine manière, il est possible de définir un algorithme glouton dans lequel à chaque étape on choisit le développement ${\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},$ où $d$ est choisi, parmi toutes les valeurs possibles satisfaisant les contraintes, aussi petit que possible de telle sorte que $xd>y$ et tel que $d$ est distinct de tous les dénominateurs précédemment choisis. Parmi les exemples de méthodes définies de cette manière, on peut citer le développement en série de Engel, dans lequel les dénominateurs successifs sont des multiples des précédents, et le développement glouton impair, dans lequel tous les dénominateurs sont contraints d'être des nombres impairs.
Il peut cependant être difficile de déterminer si un algorithme de ce type peut toujours réussir à obtenir un développement fini. En particulier, on ne sait pas si le développement glouton impair donne un développement fini pour toutes les fractions $x/y$ avec $y$ impair, bien qu'il soit possible de trouver des développements impairs finis pour ces fractions par des méthodes non gloutonnes.