En mathématiques, l'algorithme glouton pour la décomposition en fractions égyptiennes est un algorithme glouton, décrit pour la première fois par Fibonacci, permettant d'exprimer un nombre rationnel positif comme somme de fractions égyptiennes (ou fractions unitaires). Une décomposition égyptienne est une représentation d'une fraction irréductible comme somme de fractions unitaires distinctes, comme par exemple 5/6 = 1/2 + 1/3.

Comme leur nom l'indique, ces représentations 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)^[1]. L'algorithme est dit « glouton » car à chaque étape, l'algorithme choisit la plus grande fraction unitaire possible qui peut être utilisée dans n'importe quelle représentation de la fraction restante.

Fibonacci répertorie en fait plusieurs méthodes différentes pour construire des représentations en fractions égyptiennes^[2]. 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^[3], premièrement par James Joseph Sylvester en 1880^[4]. Une méthode étroitement liée qui produit des approximations plus proches à chaque étape en permettant à certaines fractions unitaires de la somme d'être négatives remonte à Lambert en 1770^[5].

Le développement d'un nombre ${\displaystyle 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 ${\displaystyle x}$.

L'algorithme de Fibonacci développe la fraction ${\displaystyle x/y}$ en effectuant à plusieurs reprises la substitution :$${\displaystyle {\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: $${\displaystyle {\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−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 diminue strictement le numérateur de la fraction restante à développer, 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 $${\displaystyle {\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 :$${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$ Wagon (1991) suggère l'exemple encore plus maladroit 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.

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${\displaystyle \left\lfloor {\frac {y}{x}}\right\rfloor +1}$ au lieu de ${\displaystyle \left\lceil {\frac {y}{x}}\right\rceil +1}$. En tronquant cette suite à ${\displaystyle k}$ termes et en formant le développement égyptien correspondant, par exemple (pour ${\displaystyle k=4}$) :$${\displaystyle {\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 à ${\displaystyle k}$ termes^[6],[7]. C'est-à-dire, par exemple, que n'importe quel développement égyptien d'un nombre de l'intervalle ouvert ]1805/1806, 1[ 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^[6], tandis que Stong en 1983 décrit des applications en théorie des groupes^[8].

Toute fraction x/y nécessite au plus ${\displaystyle x}$ termes dans son développement glouton. Mays^[9] et Freitag & Phillips^[10] examinent les conditions dans lesquelles la méthode gloutonne produit un développement de x/y en exactement ${\displaystyle x}$ termes ; ceux-ci peuvent être décrits en termes de conditions de congruence 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, $${\displaystyle {\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$ est en 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 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 à ${\displaystyle x}$ termes et qui ont le plus petit dénominateur possible ${\displaystyle y}$ pour ${\displaystyle x}$ donné est :

${\displaystyle 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.

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^[11]. Certaines entrées supplémentaires de l'OEIS^[12], bien que non indiquées comme étant produites par l'algorithme glouton, semblent être du même type.

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 $${\displaystyle {\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},}$$ où ${\displaystyle d}$ est choisi, parmi toutes les valeurs possibles satisfaisant les contraintes, aussi petit que possible de telle sorte que ${\displaystyle xd>y}$ et tel que ${\displaystyle 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 d'Engel, dans lequel chaque dénominateur successif doit être un multiple du précédent, 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 ${\displaystyle x/y}$ avec ${\displaystyle y}$ impair, bien qu'il soit possible de trouver des développements impairs finis pour ces fractions par des méthodes non gloutonnes.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Greedy algorithm for Egyptian fractions » (voir la liste des auteurs).

• (en) D. R. Curtiss, « On Kellogg's diophantine problem », American Mathematical Monthly, vol. 29, n^o 10,‎ 1922 (DOI 10.2307/2299023) ;
• (de) J. H. Lambert, Beyträge zum Gebrauche der Mathematik und deren Anwendung, Berlin, 1770 ;
• (en) H. E. Salzer, « The approximation of numbers as sums of reciprocals », American Mathematical Monthly, vol. 54, n^o 3,‎ 1947 (DOI 10.2307/2305906) ;
• (en) Laurence Sigler, Fibonacci's Liber Abaci, Springer-Verlag, 2002 (ISBN 0-387-95419-8) ;
• (en) K. Soundararajan, Approximating 1 from below using n Egyptian fractions, 2005 (arXiv math.CA/0502247) ;
• (en) R. E. Stong, « Pseudofree actions and the greedy algorithm », Mathematische Annalen, vol. 265, n^o 4,‎ 1983 (DOI 10.1007/BF01455950) ;
• (en) J. J. Sylvester, « On a point in the theory of vulgar fractions », American Journal of Mathematics, vol. 3, n^o 4,‎ 1880 (DOI 10.2307/2369261).

• Arithmétique et théorie des nombres