Mathématiques et Informatique  

 

ÉQUATIONS DIOPHANTIENNES avec FRACTIONS UNITAIRES et FRACTIONS EGYPTIENNES

 

Logiciels permettant de résoudre certaines d’entre elles.

Suppléments :   Sommes Harmoniques   -   Nombres Premiers.

@@@@@@@

 

Table des matières :

 

 

Petite introduction pour les non matheux

 

 

 

 

 

 

bar_27.gif

 

 

Dans ce but, nous nous intéresserons tout particulièrement aux équations à n inconnues du type :

 

 

et plus généralement :

 

 

 

Pour lesquelles, x1, x2, x3, x4…, xn,  sont les inconnues qui doivent être des entiers positifs, et où P et Q sont aussi des nombres entiers positifs.

Tous les n-uplets (x1, x2, x3, x4…, xn) de valeurs entières positives des inconnues qui vérifient l'équation et qui ne différent que par l’ordre de leurs éléments sont considérés comme une seule et même solution.

 

   Nous distinguerons deux cas pour ces équations :

 

Le TYPE 1 pour lequel les valeurs des inconnues, x1, x2, x3, x4…, xn, d'une même solution peuvent, pour certaines, être égales entre elles.

 

Le TYPE 2 pour lequel les valeurs des inconnues x1, x2, x3, x4…, xn, d' une même solution doivent être toutes différentes.

 

On voit facilement que dans ces conditions la recherche des solutions d'une équation revient à trouver tous les n-uplets ordonnés tels que :

 

Pour le TYPE 1 :      (inégalités larges)

 

Pour le TYPE 2 :      (inégalités strictes)

 

   Ce premier programme permet un tri des solutions grâce l'introduction facultative d'une borne  M  majorant la valeur de la plus grande inconnue xn.

 

  Il permet également de n’afficher que les solutions dont toutes les inconnues sont,  soit PAIRES, soit IMPAIRES, soit de parités INDIFFERENTES.

 

Les solutions sont recherchées et affichées dans l'ordre dit  "alphabétique décroissant" :

-  Un n-uplet de valeurs des inconnues représentant une solution candidate est considéré comme un mot de n lettres. Les lettres étant remplacées par des nombres entiers et l'ordre alphabétique par la relation d'ordre sur les nombres. Cela permet donc de classer les solutions dans l'ordre dit "alphabétique décroissant". Le logiciel calcule les plus grandes valeurs possibles des inconnues en commençant par x1, teste la solution en arrivant à xn, puis determine la solution éventuelle immédiatement inférieure dans l'ordre alphabétique, la teste et ainsi de suite..., jusqu'à la dernière. Quand on étudie l'algorithme on voit que le nombre de possibilités à tester est toujours fini quoique pouvant être trés grand.

 

    On peut, facultativement, lancer la recherche en partant d'une séquence de valeurs des premières inconnues. Les solutions seront toutes inférieures ou égales à cette séquence de valeurs (au sens de l'ordre alphabétique décroissant).

   On peut également arréter la recherche à une séquence de valeurs des premières inconnues. Les solutions seront toutes supérieures ou égales à cette séquence de valeurs (au sens de l'ordre  alphabétique décroissant).

 

Ces deux dernières options sont pratiques, entre autres possibilités, pour ne rechercher que les solutions dont la première inconnue x1 a une valeur donnée ou est comprise entre deux valeurs données...  Il est aussi possible de partitionner l'affichage  des solutions ou le calcul de leur effectif total  quand celui-ci est trés grand. On peut lancer simultanément plusieurs instances du programme pour les calculs de ces partitions (afin de trouver plus rapidement le nombre de solutions pour n = 8 avec P/Q =1 par exemple).

 

Quand on démarre le programme, celui-ci demande successivement :

1.  Si l'on veut  lire une introduction : Oui [1] / Non [0].

2.   Le choix du type d'équation : TYPE 1 ou TYPE 2.

3.   Le nombre d'inconnues n, qui à partir de la version V9.5 peut-être quelconque.

4.   Les valeurs de P et Q. Pour une somme égale à 1, il suffit de rentrer P = Q (= 1).

5.  Si l'on veut sélectionner les solutions à afficher : Oui [1] / Non [0] .

6.  Dans le cas ou P/Q = 1, on peut choisir de faire afficher les nombres Bons (sommes des inconnues de chaque solution) ainsi que leur effectif et leur liste ordonnée en fin de calcul. Dans cette liste, chaque nombre Bon est suivi de son nombre d'occurences.

Seuls les nombres Bons des solutions affichées seront pris en compte. Ceci n'est possible que pour la version de base V9.54. S'il y a un grand nombre de solutions (n=7), il est préférable, dans les propriétés de la console d'affichage du logiciel au niveau de l'onglet "configuration", de fixer de grandes valeurs pour la mémoire tampon en largeur comme en hauteur. Sans cela, une partie de la liste des nombres Bons ne sera pas visible.

7.   Le nombre K de solutions (*) que l'on veut afficher en premier lieu ou autres options.

       Depuis la version V9.6 une erreur de saisie ne "plante" plus le programme mais cette saisie erronée est reproposée tant qu'une valeur correcte n'est pas entrée.

Les calculs débutent ensuite et le programme affiche la liste des solutions numérotées sous forme d’un tableau déroulant jusqu'à la K-ième. Il arrive souvent qu'elles soient trés nombreuses. Il vaut donc mieux pour les étudier se ménager des pauses. Quand le programme aura calculé les K premières solutions, il proposera de choisir une nouvelle valeur pour K afin d'afficher les suivantes.

Si l'on ne veut pas limiter le nombre de solutions affichées, il suffit de rentrer zéro (0). En rentrant  (- 1) on arrète le calcul. En rentrant (- K) avec K > 1, il n'y aura pas de limite mais les solutions ne seront affichées ainsi que leurs effectifs cumulés qu'à des  intervalles de longueurs  K.  Cette dernière possibilité est intéressante quand l'effectif complet est trés grand et qu'on veut le connaitre. Ne pas afficher les solutions abrège beaucoup le temps de calcul (Une grande valeur pour K est conseillée dans ce cas). Attention ! dans ce cas la liste des nombres Bons, s'ils sont utilisés, ne sera pas complète.

 

Pour 7 inconnues (Type 1) avec une somme de 1, la version de base met 9 mn pour afficher les solutions (~300 000) et 10 secondes pour les compter. La version ZZ qui n'est pas limité sur la taille des entiers, met respectivement 14 mn et 4 mn. Les deux versions donnent toutes les deux, dans ce cas, les bonnes réponses. La version ZZ ne permet pas d'afficher les nombres Bons.

Dans tous les cas, la dernière des solutions une fois atteinte et affichée, leur nombre le sera aussi ainsi qu'un rappel des données et des valeurs extrêmes prises par x1 et xn. Si P/Q = 1 et que l'option a été choisie, l'effectif et la liste ordonnée des nombres Bons seront également affichés.

 

Pour finir, le programme propose de faire un nouveau calcul. Il suffit de taper 1 après la question pour pouvoir recommencer depuis le début.

 

Vous verrez à l’usage que les calculs sont généralement extrêmement rapides pour des valeurs " courantes ". Cependant, dans certains cas, il y a des ralentissements et même des arrêts qui peuvent être longs avant la reprise de l’affichage des solutions. Cela est dû à « l'écartement » de certaines solutions et au grand nombre de tests des valeurs possibles entre ces solutions. C'est le cas quand plusieurs inconnues d'une même solution ont de grandes valeurs. Quand le nombre d'inconnues n grandit, le temps de calcul augmente également, il vaut mieux restreindre le champ des solutions.

 

Le même programme existe en deux versions, écrites toutes les deux en C++, 64 bits pour PC.

La différence, est que pour la première on ne peut pas calculer avec des entiers supérieurs ou égaux à 263-1, soit en interne dans les calculs, soit en entrée dans les données. Pour chaque solution possible testée, le programme calcule entre autre le produit des (n-1)  premières valeurs des inconnues avec la valeur de P. Ce produit peut excèder selon les cas la valeur limite.  Si l'on n'en tient pas compte, des erreurs se produisent et des solutions peuvent être oubliées ou fausses.

La deuxième version, dite ZZ (car il y a ces deux lettres dans le nom du fichier), permet de faire les calculs avec des entiers supérieurs à 263 -1. Pour celà, on utilise la bibliothèque NTL du C++ qui permet de manipuler des entiers de tailles quelconques. Cette extension désigne de tels entiers par le symbole ZZ.

Les opérations prennent plus de temps avec cette bibliothèque, mais la version les utilisant donnera les résultats exacts et complets.

 

Par défaut la console de sortie du logiciel est sur fond noir avec le texte en blanc. Vous pouvez modifier cette apparence par défaut  (taille de la fenêtre, couleur du fond, taille et couleur de la police, etc..) en cliquant droit sur la barre d’en tête de sa fenêtre et en choisissant « propriétés » dans le menu déroulant. Il faut redémarrer le programme pour constater les changements. Ceux-ci restent en mémoire pour ce programme.

(*)  Réflexions sur les nombres de solutions dans les différents cas quand la fraction P/Q varie.

Pour un développement égyptien (type 2) d'ordre n, la plus grande valeur qu'il puisse prendre est celle de la somme harmonique :

H (n) = 1/1 + 1/2 + 1/3 + ... + 1/n     (quand on autorise le nombre 1 comme valeur de la première inconnue).

Sinon elle est :

H (n +1) -1 = 1/2 + 1/3 + ... + 1/(n+1)   (quand on ne l'autorise pas).

Pour des valeurs supérieures il n'existe pas de développement égyptien.

Pour cette valeur précise il n'y en a qu'un, c'est la suite harmonique.

Pour des valeurs P/Q inférieures nous allons voir qu'on pourrait supposer que « statistiquement » le nombre de solutions a tendance à croître rapidement quand la fraction P/Q diminue.

En effet :

À chaque étape de la recherche des solutions:   Les k premières valeurs des inconnues : x1 , x2 , ... , xk , étant fixées. La somme des inverses de ces k premières valeurs étant la fraction  Nk/Dk = 1/x1 + 1/x2 + 1/x3 + ... + 1/xk .

Il faudra donc que l'on ait : 1/xk+1 + 1/xk+2 + ... + 1/xn = P/Q - Nk/Dk .

Comme :  xk+1 <=  xk+2  <= xk+3  <= ... <=  xn  (Inégalités larges ou strictes selon le type 1 ou 2) .

On  devra avoir  : (P/Q - Nk/Dk) > 1/xk+1 >  (P/Q - Nk/Dk) /(n - k) (inégalités strictes ou larges selon les cas)

La valeur maximum que peut prendre la (k+1)ème inconnue est :

maj(k+1) = Q*Dk*(n-k) / (P*Dk - Q*Nk) .

Et la valeur minimum qu'elle peut prendre est :

min(k+1) = Q*Dk / (P*Dk - Q*Nk) .

La plage de valeurs possibles à tester a donc pour longueur : maj(k+1) - min(k+1) = Dk*(n - k - 1) / ((P/Q)*Dk - Nk).

On voit que quand P/Q diminue le dénominateur de la fraction représentant la plage diminue également. Les autres paramètres étant fixes la valeur de la fraction augmente.

Donc le nombre de valeurs possibles à tester augmente. Cela à chaque étape des calculs.

Le nombre de solutions « possibles » à tester varie comme le produit des longueurs de ces plages de valeurs, il augmentera donc très rapidement quand P/Q diminue.

Cela ne veut pas dire d'une façon certaine que le nombre de solutions finales augmentera également. Mais on peut le supposer « statistiquement ».

On peut faire le même raisonnement pour des développements égyptiens de type 2 et de parités paires ou impaires.

On peut aussi faire le même raisonnement pour des développements égyptiens de type 1.

Dans ces derniers cas la valeur maximum d'un développement égyptien d'ordre n est n quand on autorise les inconnues à prendre la valeur 1 et elle est de n/2 quand on ne l'autorise pas.

 

On peut essayer de vérifier cette supposition « statistique » sur des exemples :

Pour n = 5 , la somme harmonique :  1/1 + 1/2 + 1/ 3 + 1/4 + 1/5  vaut  137/60.

S1 P/Q > 137/60 , quelques tests donnent bien 0 solution.

Si P/Q = 137/60 , une seule solution correspondant à la somme harmonique.

Puis pour des valeurs inférieures : ( 135/60 , 1) , (134/60 , 0) , (133/60 , 0 ) , (132/60 , 1) , (125/60 , 2 ) , (120/60 , 6 ) , (110/60 , 17 ) , ( 100/60 , 60 ) , ( 90/60, 71 ) , (80/60 , 274 )  ,  ( 75/60 , 591 ) , ( 70/60, 1607 ) , ( 65/60 , 8463 ) , (60/60 , 72 ) , ( 55/60 , 222 ) , (50/60 , 298 ) , (52/67 , 59 ) ,  (45/60 , 662) , ( 30/60 , 2293 ) , ( 42563/97624 , 59 ) , (20/60 , 15304) , (11/63 ,  28) , ( 10/60 , 190665) ...

 

Pour n = 6 , la somme harmonique vaut : 49/20

Si P/Q > 49/20 , quelque tests donnent bien 0 solution.

Si P/Q = 49/20 , une seule solution correspondant à la somme harmonique.

Pour des valeurs inférieures : (48/20 , 0) , (47/20 , 2) , (46/20 , 3) , (45/20, 4) , (44/20 , 9)  , (43/20, 13) , (40/20 , 72) , (35/20 , 662) , (30/20, 2294) , (563/397 , 1125) , (25/20, 47390) , (20/20 , 2320) , (951/491 , 1) , (15/20 , 49938) , (10/20 , 244817)  ...

 

Ces 2 exemples semblent montrer que la règle supposée est trés grossierement suivie, avec de nombreuses irrégularités,  et que d'autres facteurs interviennent pour influencer le nombre de solutions quand la valeur de P/Q diminue. Pour de petites valeurs de P/Q les tests semblent indiquer que les nombres de solutions deviennent trés grands.

 

 

 

Exemples d'utilisations

 

             Type 1 - 4 inconnues - P/Q = 1 - avec affichage des nombres bons :

 

 

             Type 2 - 4 inconnues - P/Q = 1 - avec affichage des nombres bons:

 

 

             Type 2 - 3 inconnues - P/Q = 4/7  :

 

 

             Type 1 - 3 inconnues - P/Q = 4/7 :

 

 

             Type 2 - 7 inconnues - P/Q = 1 - Affichage des solutions tous les 80 000 :

   

 

             Type 2 - 7 inconnues - P/Q = 1 - Affichage de quelques solutions :

 

 

             Type 1 - 4 inconnues - P/Q = 3/2 - Solutions paires :

 

 

             Type 1 - 4 inconnues - P/Q = 2/3 - Solutions impaires :

 

 

                 Type 2 - 4 inconnues - P/Q = 2/3 - Solutions paires :

 

 

             Type 2 - 4 inconnues - P/Q = 2/3 - Affichage de toutes les solutions en 4 étapes :

 

 

            Programme version ZZ -  Type 1 - 50 inconnues - P/Q = 1 - Affichage de quelques solutions selectionnées :

suite1

suite 2

suite et fin

 

Pour répondre à la deuxième question :

Quels sont les développements Egyptiens d'une fraction positive quelconque P/Q,  qui ont une taille minimale ? 

Nous utiliserons une extension du programme précèdent, dont voici les caractéristques :

 

Dans ces développements Egyptiens par défaut tous les dénominateurs doivent être différents (Type 2).

Si l'on veut permettre que des dénominateurs soient égaux il faut rentrer dans les options facultatives et choisir le Type 1.

Dans le cas d'une recherche par défaut, Quand  P/Q  >=  1  on peut choisir de ne pas avoir de dénominateurs égaux à 1.

Des options facultatives permettent d'imposer des contraintes pour la recherche :

Quand on ne veut pas utiliser une de ces  5 dernières options il suffit de rentrer zéro.

    Comme pour le programme principal depuis sa version V9.6, une erreur de saisie ne "plante" pas le programme mais cette saisie erronée est reproposée tant qu'une valeur correcte n'est pas entrée.

A tout moment du calcul, on doit avoir :  n/M  <=  P/Q  <=  n/N.

Si ces conditions ne sont pas respectées au début du calcul ou quand n varie, un message d'impossibilité s'affiche.

Quand le programme a trouvé la plus petite valeur de n pour laquelle des developpements Egyptiens existent compte tenu des contraintes, il affiche le premier de ces développements (avec l'ordre alphabetique décroissant).

On rentre alors dans le cas du programme initial permettant d'afficher tous les développements de longueur n d'une fraction P/Q. On peut donc afficher ou compter toutes les solutions pour cette valeur de n .

Attention ! Parfois les calculs peuvent être longs !  Par exemple, quand la taille du développement minimum dépasse 8, pour certaines valeurs de P/Q le programme doit tester un trés grand nombre de possibiltés, pour n = 8 d'abord, avant de chercher des développements d'ordre 9.

A cause des contraintes, il se peut aussi qu'il n'y ait aucune solution mais que le programme continue à chercher sans s'arréter. C'était le cas, par exemple, d'une fraction positive  irréductible P/Q  dont le dénominateur est paire, pour laquelle on cherchait des développements avec des denominateurs tous impairs.

Cette extension est égalemet écrite en C++ avec la librairie NTL qui permet de calculer avec n'importe quelles tailles d'entiers.

 

Exemples d'utilisations

             Pour  7/9  il faut 3 fractions au minimum (Type 2) :

 

 

             Pour  77/79  il en faut 6 :

.............       suite et fin (il y a 160 solutions dans ce cas) :

 

 

             Pour  732/733  il en faut 7 :

 

 

             Et il y a 2767 solutions dans ce cas :

 

 

             Pour 1 il en faut 10 si le plus petit dénominateur est 5 :

 

 

             Et il en faut 15 si ce plus petit dénominateur est 8 :

 

 

             Pour 1 il faut au minimum 4 fractions paires diférentes :

 

 

             Pour 1 il faut au minimum 9 fractions impaires (en excluant 1/1) :

 

 

             Pour 1 il existe des solutions avec 17 fractions impaires :

 

 

 

  < = >  

 

 

 Téléchargement d'un setup d'installation des programmes pour Windows :

Solution recommandée la plus pratique.

https://alainb-sites.fr/programmes/setup_Frac_Egypt.zip

 

 

  Vous pouvez aussi télécharger les fichers éxécutables isolément :

 

 Programmes permettant de trouver tous les développements de longueur n d'une fraction P/Q

 

Téléchargez une des deux versions V9.72 du logiciel à l'aide des liens suivants Windows et Linux) :

·       Version de base ne permettant pas de calculer avec des entiers supérieurs à 263 – 1 :

Lire les instructions ci-dessous pour pouvoir faire fonctionner ces programmes avec Linux.

·       Version ZZ permettant de calculer avec des entiers de tailles quelconques :

Lire les instructions ci-dessous pour pouvoir faire fonctionner ces programmes avec Linux.

Lire les instructions ci-dessous pour pouvoir faire fonctionner ces programmes avec Linux.

 

 

 

Procédure permettant de faire fonctionner les programmes téléchargés sous Linux :

 

 

 

 

 Code commenté des programmes au format RTF

 

 Version de base ne permettant pas de calculer avec des entiers supérieurs à 263 – 1 :

EQUATIONS_DIOPHANTIENNES_V9.72.PDF

 

 Version ZZ permettant de calculer avec des entiers de tailles quelconques :

EQUATIONS_DIOPHANTIENNES_ZZ_V9.72.PDF

 

      Extension permettant de trouver les développements Egyptiens de taille minimale :

  

 

 

 

A ce propos ...

 

Une équation diophantienne, en mathématiques, est une équation polynomiale à une ou plusieurs inconnues dont les solutions sont cherchées parmi les nombres entiers, éventuellement rationnels, les coefficients étant eux-mêmes également entiers.

 

La branche des mathématiques qui s'intéresse à la résolution de telles équations est l'arithmétique ou la théorie des nombres.

Si l'expression du problème posé est parfois simple, les méthodes de résolution peuvent devenir complexes. Gauss, au XIXe siècle, écrivait de la théorie des nombres que « son charme particulier vient de la simplicité des énoncés jointe à la difficulté des preuves ».

 

Certaines équations diophantiennes ont demandé pour leur résolution les efforts conjugués de nombreux mathématiciens sur plusieurs siècles.

Le dernier théorème de Fermat en est un exemple. Il est conjecturé par Pierre de Fermat et démontré, en 1994 par Andrew Wiles, après 357 ans d'efforts de la part de nombreux mathématiciens.

 

Certaines de ces équations, parmi les plus simples ont été et sont encore dans les programmes de mathématiques en terminales.

 

L'intérêt de la résolution de questions de cette nature réside rarement dans l'établissement d'un théorème fondamental ni dans l’utilité du résultat. La cryptologie fait cependant un grand usage du petit théorème de Fermat. Leur analyse amène le développement d'outils mathématiques puissants dont l'usage dépasse le cadre de l'arithmétique. Les formes quadratiques  en sont un exemple.

 

Ce type d'équation doit son nom à Diophante d'Alexandrie, mathématicien grec. Il a vécu entre le Ier siècle AV. J.-C. et le IVe siècle, peut-être au IIe siècle ou au IIIe siècle. Connu pour ses Arithmétiques, ouvrage dont une partie est aujourd'hui perdue, où il étudie certaines équations diophantiennes, il est parfois surnommé le « père de l'algèbre ».

 

En 1900, Hilbert proposa la résolubilité de tous les problèmes diophantiens comme le dixième de ses célèbres problèmes. En 1970, un nouveau résultat en logique mathématique connu sous le nom de théorème de Matiyasevich apporta une réponse négative. Ce théorème dit qu’en général les problèmes diophantiens ne sont pas solubles, au sens où l'on peut construire explicitement de tels problèmes pour lesquels l'existence d'une solution est indécidable.

 

 

Une fraction égyptienne ou unitaire, est une fraction de numérateur égal à un et de dénominateur entier strictement positif.

 

Un problème classique est d'écrire une fraction comme somme de fractions égyptiennes avec des dénominateurs tous différents, que l'on nomme développement en fractions égyptiennes ou plus simplement développement égyptien.

 

Tous les nombres rationnels positifs peuvent être écrits sous cette forme, ceci d'une infinité de façons différentes.

 

Des textes comme le papyrus Rhind et le papyrus de Moscou montrent que les anciens Égyptiens pouvaient effectuer les quatre opérations mathématiques de base (addition, soustraction, multiplication et division) et utilisaient les fractions.

La numération était décimale et basée sur des signes hiéroglyphiques pour chaque puissance de dix jusqu’à un million.

Mais leur système d’écriture ne pouvait écrire les fractions avec un numérateur supérieur à un, elles ont donc dû être écrites comme la somme de plusieurs fractions. Par exemple, 2/5 était écrit comme la somme de 1/3 et 1/15. Quelques fractions simples ont été toutefois écrites avec un glyphe spécial comme 2/3.

Le papyrus Rhind (vers environ -1650), qui est conservé au British Museum de Londres, est le plus important document nous informant des connaissances mathématiques des temps anciens. Il comporte quatre-vingt-quatre problèmes résolus d'arithmétique, de géométrie et d'arpentage. Mais, avant de prendre connaissance de ces problèmes, l'Égyptien devait avoir à sa disposition différentes tables lui permettant de décomposer directement les fractions non unitaires en fractions unitaires. Une de ces tables, la table dite « des fractions doubles » ou « de 2/n», se trouve en première position sur le papyrus de Rhind. Elle répertorie les fractions dont le numérateur est 2 et dont le dénominateur n varie de 3 à 101 (n impairs) et donne leur équivalent en somme de fractions unitaires.

Quelques exemples de décomposition en fractions unitaires de la table de 2 :

 

        2/5   → 1/3 + 1/15

        2/7   → 1/4 + 1/28

        2/9   → 1/6 + 1/18

        2/11 → 1/6 + 1/66

              

 

Les théoriciens des nombres modernes ont étudié de nombreux problèmes différents reliés aux fractions égyptiennes, incluant les problèmes de borne pour la longueur ou de dénominateur maximum. Également, la recherche de recouvrement ou de développements de certaines formes spéciales ou dans lesquels les dénominateurs sont tous d'un type particulier (premiers, paires, impaires, carrés,… ). Et aussi les problèmes de l'arrêt de divers algorithmes permettant d'obtenir des développements  égyptiens.

 

Obtenir un développement de P/Q en fraction égyptienne peut donc se faire grâce à plusieurs algorithmes, qui donneront des résultats différents mais néanmoins valides.

Citons en certains  :

 

·       Algorithme de Fibonacci-Sylvester (algorithme glouton)

·       Algorithme de Golomb

·       Algorithme d'Erdos et Bleiche

 

L'identité suivante est beaucoup utilisée :

 

 

Il est possible pour n'importe quelle fraction d'obtenir un développement égyptien aussi grand que l'on veut en utilisant l'identité précédente.

 

Algorithme glouton de Fibonacci pour trouver des fractions égyptiennes :

Cette méthode et sa preuve sont données par Fibonacci dans son livre Liber Abaci en 1202.

Nous voulons développer une fraction irréductible positive P/Q plus grande que 1, et pour laquelle P et Q sont plus grand que 1.

Ce procédé  consiste à déterminer  la plus grande fraction unitaire que l'on peut soustraire de P/Q (Son qualificatif de gourmand vient de là). Avec ce qui reste, on répète le processus.

On montre que cette suite de fractions unitaires diminue toujours, ne répète jamais une fraction et s’arrêtera toujours en aboutissant à une fraction unitaire.

Cette méthode ou algorithme, est qualifié de glouton ou gourmand ou goulu  dans le cas présent :  nous prenons (avec gourmandise) la plus grande fraction unitaire que nous pouvons de la fraction initiale P/Q, puis nous recommençons  avec le reste.

Voici un exemple : 521/1050

521/1050 est inférieur à 1/2 (puisque 521 < 1050/2), mais est plus grand que 1/3.

La plus grande fraction unitaire que nous pouvons retirer de 521/1050 est donc 1/3 :

521/1050 = 1/3  + R

Quel est le reste?

521/1050 - 1/3 = 171/1050 = 57/350

Nous répétons donc le processus sur 57/350

Cette fois la plus grande fraction unitaire inférieure à 57/350 est 1/7 et le reste est 1/50.

Finalement :

521/1050 = 1/3 + 57/350
521/1050  = 1/3+ 1/7 + 7/350
521/1050  = 1/3+ 1/7+ 1/50

 

En 1948, Paul Erdos et Ernst G. Straus ont conjecturé que pour tout entier n, la fraction  4/n  peut s'écrire comme somme de trois fractions égyptiennes.

De même, Waclaw Sierpinski a conjecturé, en 1956, que pour tout entier n, la fraction 5/n  peut s'écrire comme somme de trois fractions égyptiennes.

Aucune de ces deux conjectures n'est démontrée à ce jour, même s'il existe beaucoup de résultats assez forts concernant notamment la conjecture d'Erdos-Straus.

 

Voici quelques autres résultats que les mathématiciens ont prouvés :

 

Chaque fraction P/Q peut s’écrire sous la forme d’une somme de fractions unitaires... et ceci d’un nombre infini de façons !

 

Fractions égyptiennes les plus courtes :

 

Y a-t-il des fractions dont la longueur de fraction égyptienne la plus courte est 3 (ou 4 ou 5, …) ?

Par exemple :

 

Combien ya-t-il de fractions égyptiennes de longueur la plus courte pour P/Q  ?? !! ...

 

 

Fractions égyptiennes de longueur fixe (n) pour  P/Q  quelconque et pour 1 en particulier :

 

C’est le problème dont le programme présenté ici donne toutes les solutions dans différents cas.

 

Par exemple, combien y a-t-il de développements  égyptiens de longueur 3 pour la fraction  4/6 et quels sont-ils ?

- La réponse est 5 :  1/2 + 1/7 + 1/42  ;  1/2 + 1/8 + 1/24  ;  1/2 + 1/9 + 1/18  ;  1/2 + 1/10 + 1/15  ;  1/3 + 1/4 + 1/12 .

 

Et si l’oncherche les développements pour lesquels des fractions peuvent être égales.

- La réponse est 8,  il faut rajouter : 1/4 + 1/4 + 1/6  ;  1/3 + 1/6 +1/6  ;  1/2 + 1/12 + 1/12 .

 

L’algorithme utilisé donne toutes les solutions, toujours en nombre fini, quand elles existent, quelle que soit la fraction P/Q et la longueur du développement (n). On est limité cependant par les capacités des ordinateurs et le temps de calcul qui peut-être trés long.

 

Ce problème est bien celui de trouver toutes les solutions d'une équation diophantienne :

 

Dans le cas de notre exemple, cette équation est :

 

4/6 = 1/x +1/y + 1/z

 

Qui peut s’écrire sous forme polynomiale :

 

4xyz = 6xy + 6yz + 6xz

 

x , y,  z devant être des entiers strictements positifs.

Deux solutions qui ne diffèrent que par l’ordre des inconnues étant considérées comme identiques.

 

Quand la somme fait 1 (P = Q), les mathématiciens se sont intéressés aux nombres dits bons :

Nombre bon : La somme des inverses des termes d'une de ses partitions est égale à 1. Autrement dit, tout nombre bon est  la somme des dénominateurs de fractions unitaires qui ont 1 pour somme.

Différents types de nombres bons :

 

·         Simplement       S – Bon                Aucune contrainte sur les termes

·         Unique              U – Bon                Chaque terme est unique, jamais répété

·         Impair                I – Bon                 Les termes sont tous impairs

·         Premier             P – Bon                Les termes sont tous Premiers

 

 

Fractions égyptiennes de longueur minimale (n est inconnu) pour une fraction  P/Q  quelconque :

 

C'est la question à laquelle répond l'extension du programme précèdent,  présentée à la suite de celui-ci.

 

Par exemple quel est l'ordre minimal d'un développement égyptien pour la fraction  88888/89999 ? 

 - La réponse est 6 quand toutes les fractions doivent-être différentes et elle est de 6 également quand certaines fractions du développement peuvent-être égales.

 

Si l'on impose aux fractions d'être toutes paires et différentes :

 - la réponse est 7,

et si elles doivent-être toutes impaires :

- la réponse est 10.

 

Dans le cas ou elle doivent-être différentes, paires, avec un minimum de 6 pour le plus petit dénominateur :

 - il faut 18 fractions au minimum.

 

Dans tous les cas le logiciel donne la première solution (s'il y en a une compte tenu des contraintes imposées) et permet de lister ou compter toutes les autres.

D'autres cas de sélections des solutions sont prévus.

 

La aussi il n'y a pas de limite pour la fraction P/Q et les calculs internes. Le programme étant aussi écrit en C++ avec l'extension NTL  autorisant des calculs sans bornes sur la taille des nombres. On est cependant toujours limité par les capacités des ordinateurs et les temps de calcul qui peut-être trés longs.

 

 

 

 

 

@ @ @

 

  Liens sur le sujet  

(Beaucoup de ces liens renvoient à d'autres articles sur la question)