Utilisateur:Zabar Djamel 12000419/Brouillon

En mathématiques, l'algorithme glouton pour les fractions égyptiennes est un algorithme glouton, d'abord décrit par Fibonacci, permettant de transformer des nombre rationnels en fraction égyptienne. Une fraction égyptienne est une représentation d'une fraction irréductible sous la forme d'une somme de fraction unitaires distinctes, telle que 5/6 = 1/2 + 1/3. Comme son nom l'indique, ces représentations ont été utilisées dès l'Égypte antique, mais la première méthode systématique publiée pour construire de telles expansions a été décrite en 1202 dans le Liber Abaci de Leonardo de Pise (Fibonacci). On l'appelle algorithme glouton car à chaque étape, l'algorithme choisit de manière avide la plus grande fraction unitaire possible qui peut être utilisée dans toute représentation de la fraction restante.

Fibonacci énumère en fait plusieurs méthodes différentes pour construire des représentations de fractions égyptiennes. Il inclut la méthode gloutonne en dernier recours pour les situations où plusieurs méthodes plus simples échouent. Voir fraction égyptienne pour une liste plus détaillée de ces méthodes. Comme le détaille Salzer (1948), la méthode gloutonne, ainsi que des extensions pour l'approximation de nombres irrationnels, ont été redécouvertes plusieurs fois par des mathématiciens modernes, en particulier par James Joseph Sylvester (1880) Une méthode d'expansion étroitement liée qui produit des approximations plus proches à chaque étape en permettant que certaines fractions unitaires de la somme soient négatives remonte à Lambert (1770).

L'expansion produite par cette méthode pour un nombre $x$ est appelée expansion égyptienne gloutonne, expansion de Sylvester, ou expansion Fibonacci–Sylvester de $x$. Cependant, le terme expansion Fibonacci fait généralement référence, non à cette méthode, mais à la représentation des entiers sous forme de sommes de nombres de Fibonacci.

Algorithme et exemples

L'algorithme de Fibonacci développe la fraction $x/y$ à représenter en effectuant de manière répétée 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 si nécessaire le deuxième terme de cette substitution). Par exemple : $${\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.$$ Dans cette expansion, le dénominateur 3 de la première fraction unitaire est le résultat de l'arrondi de 15/7 au plus proche entier supérieur, 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 le résultat de l'arrondi de 15/2 au plus proche entier supérieur, et la fraction restante 1/120 est ce qui reste de 7/15 après avoir soustrait à la fois 1/3 et 1/8.

Comme chaque étape de l'expansion réduit le numérateur de la fraction restante à développer, cette méthode se termine toujours par une expansion finie. Cependant, par rapport aux expansions égyptiennes anciennes ou aux méthodes plus modernes, cette méthode peut produire des expansions assez longues, avec de grands dénominateurs. Par exemple, cette méthode développe $${\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 à une bien meilleure expansion $${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.$$ Wagon (1991) suggère un exemple encore plus mal comporté, 31/311. La méthode gloutonne conduit à une expansion avec dix termes, le dernier ayant plus de 500 chiffres dans son dénominateur; cependant, 31/311 a une représentation non gloutonne beaucoup plus courte, 1/12 + 1/63 + 1/2799 + 1/8708.

Séquence de Sylvester et approximation la plus proche

La Suite de Sylvester 2, 3, 7, 43, 1807, ... ( A000058) peut être vue comme générée par une expansion gloutonne infinie de ce type pour le nombre 1, où à chaque étape nous choisissons le dénominateur ⌊ y/x ⌋ + 1 au lieu de ⌈ y/x ⌉. Tronquer cette séquence à k termes et former la fraction égyptienne correspondante, par exemple (pour k = 4) $${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}$$ donne la sous-estimation la plus proche possible de 1 par n'importe quelle fraction égyptienne à k termes. Autrement dit, par exemple, toute fraction égyptienne pour un nombre dans l'intervalle ouvert (1805/1806, 1) nécessite au moins cinq termes. Curtiss (1922) décrit une application de ces résultats d'approximation la plus proche dans la borne inférieure du nombre de diviseurs d'un nombre parfait, tandis que Stong (1983) décrit des applications en théorie des groupes.

Expansions de longueur maximale et conditions de congruence

Toute fraction x/y nécessite au plus x termes dans son expansion gloutonne. Mays (1987) examine les conditions sous lesquelles la méthode gloutonne produit une expansion de x/y avec exactement x termes; celles-ci peuvent être décrites en termes de conditions de congruence sur y.

Chaque fraction 1/y nécessite un terme dans son expansion gloutonne ; la fraction la plus simple de ce type est 1/1. Chaque fraction 2/y nécessite deux termes dans son expansion gloutonne si et seulement si y ≡ 1 (mod 2) ; la fraction la plus simple de ce type est 2/3. Une fraction 3/y nécessite trois termes dans son expansion gloutonne 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 de l'expansion gloutonne, $${\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{,{\frac {y(y+2)}{3}},}}$$, est en termes les plus simples. La fraction la plus simple 3/y avec une expansion de trois termes est 3/7. Une fraction 4/y nécessite quatre termes dans son expansion gloutonne si et seulement si y ≡ 1 ou 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 4/y avec une expansion de quatre termes est 4/17. La Conjecture d'Erdős-Straus affirme que toutes les fractions 4/y ont une expansion avec trois termes ou moins, mais lorsque y ≡ 1 ou 17 (mod 24), de telles expansions doivent être trouvées par des méthodes autres que l'algorithme glouton, avec le cas 17 (mod 24) étant couvert par la relation de congruence 2 (mod 3).