Algorithme glouton pour la décomposition en fractions égyptiennes

L'algorithme de Fibonacci développe la fraction irréductible ${\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 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 $${\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 suggère l'exemple encore plus malheureux 31/311^[6] : 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^[7],[8]. C'est-à-dire, par exemple, que n'importe quel développement égyptien d'un nombre de l'intervalle ouvert ${\displaystyle \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^[7], et Stong décrit en 1983 des applications en théorie des groupes^[9].

Toute fraction x/y nécessite au plus ${\displaystyle x}$ termes dans son développement glouton. Mays^[10] et Freitag & Phillips^[11] 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 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, $${\displaystyle {\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 à ${\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^[12]. Certaines entrées supplémentaires de l'OEIS^[13], bien que non indiquées comme étant produites par l'algorithme glouton, semblent être du même type.