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 Modèle:Nobr.

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)Modèle:Sfn.

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 égyptiennesModèle:Sfn. 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 modernesModèle:Sfn, premièrement par James Joseph Sylvester en 1880Modèle:Sfn. 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 1770Modèle:Sfn.

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}{\lceil \frac{y}{x}\rceil }+\frac{(-y)modx}{y\lceil \frac{y}{x}\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 Modèle:Sfrac, et la fraction restante Modèle:Sfrac est le résultat de la simplification de Modèle:Sfrac = Modèle:Sfrac . Le dénominateur de la deuxième fraction unitaire, 8, est la partie entière supérieure de Modèle:Sfrac , et la fraction restanteModèle:Sfrac est ce qui reste de Modèle:Sfrac après avoir soustrait Modèle:Sfrac et Modèle:Sfrac .

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}{763309}+\frac{1}{873960180913}+\frac{1}{1527612795642093418846225},$$ 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 Modèle:Sfrac : la méthode gloutonne conduit à un développement à dix termes, dont le dernier a un dénominateur de plus de 500 chiffres, alors que Modèle:Sfrac possède une représentation non gloutonne beaucoup plus courte : Modèle:Nobr.

Suite de Sylvester et meilleure approximation

La suite de Sylvester 2, 3, 7, 43, 1807, ... ( Modèle:OEIS2C ) 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$\lfloor \frac{y}{x}\rfloor +1$ au lieu de $\lceil \frac{y}{x}\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$ termesModèle:SfnModèle:,Modèle:Sfn. C'est-à-dire, par exemple, que n'importe quel développement égyptien d'un nombre de l'intervalle ouvert $]1,\frac{1805}{1806}[$ 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 parfaitModèle:Sfn, et Stong décrit en 1983 des applications en théorie des groupesModèle:Sfn.

Développements de longueur maximale et conditions de congruence

Toute fraction Modèle:Sfrac 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 Modèle:Sfrac en exactement $x$ termes ; ceux-ci peuvent être décrits en termes de conditions de congruence portant sur y.

• Une fraction de type Modèle:Sfrac nécessite un terme dans son développement glouton ; la fraction la plus simple est Modèle:Sfrac .
• Une fraction de type Modèle:Sfrac nécessite deux termes dans son développement glouton si et seulement si Modèle:Nobr ; la fraction la plus simple est Modèle:Sfrac .
• Une fraction de type Modèle:Sfrac nécessite trois termes dans son développement glouton si et seulement si Modèle:Nobr, car alors Modèle:Nobr et Modèle:Sfrac est impair, donc la fraction restante après une seule étape du développement glouton, $$\frac{(-y)modx}{y\lceil \frac{y}{x}\rceil }=\frac{2}{\frac{y(y+2)}{3}}$$ est formée de termes plus simples. La fraction la plus simple de type Modèle:Sfrac ayant un développement à trois termes est Modèle:Sfrac .
• Une fraction de type Modèle:Sfrac nécessite quatre termes dans son développement gourmand si et seulement si Modèle:Nobr, car alors le numérateur Modèle:Nobr de la fraction restante est 3 et le dénominateur est congru à Modèle:Nobr . La fraction la plus simple de type Modèle:Sfrac avec un développement à quatre termes est Modèle:Sfrac . La conjecture d'Erdős-Straus énonce que toutes les fractions de type Modèle:Sfrac ont un développement avec trois termes ou moins, mais lorsque Modèle:Nobr de tels développements doivent être trouvés par des méthodes autres que l'algorithme glouton, le cas Modèle:Nobr étant couvert par la relation de congruence Modèle:Nobr .

Plus généralement la suite des fractions de type Modèle:Sfrac qui ont des développements gloutons à $x$ termes et qui ont le plus petit dénominateur possible $y$ pour $x$ donné est :

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 Modèle:OEIS2C, Modèle:OEIS2C et Modèle:OEIS2C, 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.

Bibliographie

• Modèle:Article ;
• Modèle:Ouvrage ;
• Modèle:Article ;
• Modèle:Ouvrage ;
• Modèle:Ouvrage ;
• Modèle:Article ;
• Modèle:Article.