Avec les développements égyptiens :
Exercices sur les fractions (collège)
Découvrir les algorithmes (lycée et plus)

En s'aidant d'un logiciel

Alain Barnier

Rappelons que les Égyptiens qui ne connaissaient que quelques fractions de numérateurs différents de 1, exprimaient ces dernières comme des sommes de fractions unitaires. D'où l'appellation de développements égyptiens.

En, bref

   Vous allez pouvoir faire calculer les élèves avec des fractions en leur faisant vérifier ou chercher des développements égyptiens d'ordre n d'une fraction P/Q ou de l'unité. En se limitant à des valeurs simples bien choisies, c'est possible dès le collège.

   Au lycée, vous pourrez aussi faire découvrir et appliquer l'algorithme qui permet de trouver toutes les solutions dans divers cas.

Que fait le logiciel

   Rappelons qu'un développement égyptien de l'unité ou d'une fraction est son écriture sous la forme d'une somme de fractions ayant toutes 1 pour numérateurs (fractions unitaires).

   Le logiciel permet de trouver et de compter tous les développements égyptiens de n d'éléments (d'ordre n) de l'unité ou de n'importe quelles fractions.

   Il permet aussi d'imposer des contraintes : parité, maximum, minimum...

   Il distingue deux cas, celui où toutes les fractions du développement sont différentes (Type 2) et celui où certaines peuvent être égales (Type 1).

   Une extension permet de déterminer les développements les plus courts possible pour une fraction donnée.

   On peut choisir d'afficher toutes les solutions d'un seul coup ou de proche en proche, ou seulement certaines d'entre elles à intervalles réguliers.

   Ce logiciel d'utilisation libre est téléchargeable à partir de sa page Web de présentation : Fractions égyptiennes.
http://alainb-sites.fr/programmes/

Ses limites

   Il permet de calculer avec des entiers de tailles quelconques, mais les limitations sont dues au temps de calcul pour les grandes valeurs.

Quelles élèves concernent-ils ?

   Dès le collège, la vérification de développements simples et même leur recherche est possible.

   Au lycée et au-dessus, la découverte et la pratique de l'algorithme permettant de trouver toutes les solutions dans différents cas, ainsi que sa programmation.

Quelques applications

Au collège

1. Vérifier que les sommes : 1/3 + 1/3 et 1/2 + 1/6, valent exactement 2/3 toutes les deux.
Que les sommes : 1/10 + 1/10 et 1/6 + 1/30, valent exactement 1/5 chacune.
Que les sommes : 1/5 + 1/5 et 1/3 + 1/15, valent exactement 2/5 chacune.
Que les sommes : 1/7 + 1/7 et 1/4 + 1/28, valent exactement 2/7 chacune.

2. Vérifier que les sommes : 1/4 + 1/4 + 1/6, 1/3 + 1/6 + 1/6, 1/3 + 1/4 +1/12 et 1/2 + 1/10 + 1/15 valent exactement 2/3 toutes les quatre.
Que les sommes : 1/4 + 1/4 + 1/8, 1/3 + 1/6 + 1/8 et 1/2 + 1/10 + 1/40 valent exactement 5/8 toutes les trois.

3. Vérifier que les sommes : 1/20 + 1/20 + 1/20 + 1/20, 1/18 + 1/18 + 1/18 + 1/30 et 1/15 + 1/15 + 1/20 + 1/60 valent exactement 1/5 chacune. De même pour la somme 1/10 + 1/11 + 1/111 + 1/12210 (*).
Vérifier que 1/20 = 1/40 + 1/40 et trouver 2 sommes simples de 5 fractions unitaires, qui valent exactement à 1/5 chacune.

4. En vous servant du logiciel vous pourrez vous exercer sur d'autres exemples de ce type.

(*) Pour les sommes comportant des fractions avec de grands nombres entiers on pourra, pour calculer exactement les numérateurs et les dénominateurs, se servir de la calculatrice.

Au lycée et plus

1. Approche du problème par le même genre d'exercice qu'au collège. Puis recherche de toutes les solutions dans des cas simples par les méthodes de résolution d'équations diophantiennes au programme ( ?!).

2. Démontrer que pour toute fraction P/Q, il existe une infinité de développements égyptiens possibles.

3. Recherche de toutes les solutions dans des cas simples ou un peu plus complexes par une méthode algorithmique, la somme P/Q et la valeur de n, étant fixées (voir ci-dessous des explications sur cette méthode).

4. Montrer que pour n donné, il ne peut exister qu'un nombre fini de développements égyptiens d'ordre n, tous égaux à la même fraction P/Q.

5. Écriture d'un programme mettant en oeuvre l'algorithme.

Quelques explications à donner ou suggérer aux élèves

   Soit n l'ordre des développements égyptiens que nous cherchons pour la fraction P/Q. Celle-ci pouvant être plus petite, égale ou plus grande que l'unité.

   Appelons, x₁ , x₂ , x₃ , ... , x_n, les dénominateurs des n fractions unitaires composant ces développements.

   Le problème revient donc à résoudre l'équation :

1/x₁ + 1/x₂ + 1/x₃ + ... + 1/x_n = P/Q

   x₁ , x₂ , x₃ , ... , x_n étant des nombres entiers positifs à déterminer et P/Q une fraction positive (pouvant être égal 1). C'est une équation diophantienne à n inconnues.

   Nous pouvons considérer comme une même solution tous les n–uplets (x₁ , x₂ , x+ , ... , x_n), qui ne diffèrent que par l'ordre de leurs termes.

   Quand on cherche des développements égyptiens, on peut tolérer que certaines valeurs des inconnues soient égales entre elles (type 1) ou imposer que toutes les inconnues soient différentes (type 2).

   On déterminera toutes les solutions en se limitant aux valeurs des inconnues telles que, pour le type 1 :
1/x₁ <= 1/x₂ <= 1/x₃ <= ... <= 1/x_n,

et pour le type2 :
1/x₁ < 1/x₂ < 1/x₃ < ... < 1/x_n.

   Dans le cas d'une recherche de type 1, si l'on autorise la valeur 1, la somme P/Q doit être inférieure ou égale à n, et si cette valeur 1 n'est pas autorisée, P/Q doit être inférieure ou égale à n/2.

   Pour une recherche de type 2, si l'on autorise la valeur 1, la somme P/Q doit être inférieure ou égale à :
1 + 1/2 + 1/3 + ... + 1/n, qui est la somme harmonique d'ordre n.

   Et si cette valeur 1 n'est pas autorisée, P/Q doit être inférieur ou égal à :
1/2 + 1/3 + ... + 1/n + 1/(n +1), qui est la somme harmonique d'ordre (n + 1) moins 1.

   Cela ne voudra pas dire pour autant que, même si la somme P/Q respecte ces conditions, un développement égyptien pour cette valeur de n, existe.

   Nous pouvons classer les solutions grâce à l'ordre dit lexicographique. Nous choisirons l'ordre décroissant. Une solution (y₁ , y₂ , y₃ , ... , y_n) sera inférieure à une solution (x₁ , x₂ , x₃ , ... , x_n), si :

· toutes les valeurs des y_i sont égales aux valeurs correspondantes des xi jusqu'à une certaine valeur de i strictement inférieur à n.

· pour la valeur immédiatement suivante, y_{(i + 1)} < x_{(i + 1)}.

Un algorithme pour ce problème

On va chercher toutes les solutions en testant toutes les valeurs possibles dans l'ordre lexicographique.

N, P/Q, le Type (1 ou 2) et un minimum m pour x1, sont fixés.

Max1 et Min1 étant respectivement un majorant et un minorant des valeurs possibles pour x1 :
On prendra, Max1 = Partie entière de [(Q×n)/P].
On prendra, Min1 = Partie entière de (Q/P) + 1. (*) Démonstration.

Posons, i = 1.

Si Min1 < m , posons Min1 = m.
Si Max1 < Min1 : FIN DE L'ALGORITHME
Sinon : BOUCLE 1 - Tant que i est non nul.

Nous avons attribué des valeurs à x₁, x₂, ... ,xi.

Ces i premiers termes de la somme sont donc supposés connus, les (n - i) termes suivants devront avoir pour somme :

P/Q - (1/x1 + 1/x2 + ... +1/xi) = p/q

Max(i + 1) et Min(i + 1) étant respectivement un majorant et un minorant des valeurs possibles pour x(i + 1) :

On prendra, Max(i + 1) = Partie entière de [(q×(n - i))/p].

On prendra, Min(i + 1) = Partie entière de [q/p] +1. (*) Démonstration

· Si Min(i + 1) < xi, pour le type 1, posons Min(i + 1) = xi.

· Si Min(i + 1) <= xi, pour le type 2, posons Min(i + 1) = xi + 1.

· Si Max(i + 1) >= Min(i + 1) et i < (n – 1) :

Posons x(i + 1) = Max(i + 1) et augmentons i d'une unité. 

· Sinon :

o Si (i = n – 1) et q/p est un entier :

Posons x(n) = q/p
On a une solution, affichons là et comptons là.

o BOUCLE 2 - Tant que i diminue et est différent de 0.

Si : x(i) > Min(i), posons x(i) = x(i) – 1
Sinon : i = i – 1

(*) Démonstration (pour Max1 et Min1 prendre i = 0) :

Si Max(i + 1) et Min(i + 1) sont respectivement un majorant et un minorant des valeurs possibles pour x(i + 1), pour le type 1 et pour le type 2, on a la relation :

1/Min(i + 1) < p/q <=( n - i)/Max(i + 1)

La première inégalité étant stricte tant que (i + 1) est différent de n.
Avec : p/q = P/Q – (1/x(i + 1) + 1/x(i + 2) + ...+ 1/xn).
Soit :Max(i + 1) <= (q×(n - i))/p,

On prendra, Max(i + 1) = Partie entière [ (q×(n - i))/p].
Et : q/p < Min(i + 1),
On prendra Min(i + 1) = Partie entière de [q/p] + 1, tant que i < (n-1).

En effet :

- Max(i + 1) doit toujours être supérieur ou égale à x(i +1). Toutes les inconnues suivantes sont supérieures ou égales à x(i + 1), leurs inverses seront inférieurs ou égaux à 1/x(i +1). Comme il y en a (n – i), leur somme qui vaut p/q doit être inférieure à n/x(i + 1), soit : p/q <= (n – i)/x(i + 1).

Comme on doit toujours avoir x(i +1) <= Max(i + 1) on doit avoir aussi  :

(n – i)/Max(i+1) <= (n – i)/x(i + 1).
En prenant Max(i + 1) tel que p/q = (n – i)/Max( i + 1) on aura une valeur possible de Max(i + 1).
Soit : Max(i + 1) = (q*(n – i))/p.
et choisira, Max(n – i) = Partie entière [ (q*(n – i))/p] .

- Min(i + 1) doit toujours être inférieur ou égal à x( i + 1).

1/Min(i + 1), est donc toujours supérieur ou égale à 1/x(i + 1).
p/q est supérieur à 1/x(i + 1) qui est un des termes positifs d'une somme valant p/q.
En choisissant Min(i + 1) tel que 1/Min(i + 1) = p/q, on aura une valeur possible pour Min(i + 1).

Soit : Min(i + 1) = q/p.
On prendra, Min(i + 1) = q/p arrondi à la valeur supérieure.
Remarquons si i est inférieur à n-1 on pourra prendre Min(i + 1) = Partie entière de [q/p] + 1.

Il y a des contraintes pour Max(i + 1) et Min(i + 1) :
Pour les équations du type 1 :
Max(i + 1) >= Min(i + 1) >= xi >= m ( Minimum choisi pour x1),
Pour les équations du type 2 :

Max(i + 1) >= Min(i + 1) > xi >= m.

Ci-dessous, cet algorithme traduit en langage Python. Le programme fonctionne, grâce à ce langage, pour des entiers de tailles quelconques. Il n'est pas aussi rapide, quand les nombres sont très grands, que les programmes principaux de cet article. Ceux-ci, écrits en C++ avec l'extension NT, sont plus complets.
http://alainb-sites.fr/programmes/

En téléchargements ici :

Le code python de ce programme : egyptiens.py et son exécutable : egyptiens.exe
http://alainb-sites.fr/programmes/egyptiens.py
http://alainb-sites.fr/programmes/egyptiens.exe

Le code : egyptiens2.py et son exécutable : egyptiens2.exe de ce programme amélioré.
http://alainb-sites.fr/programmes/egyptiens2.py
http://alainb-sites.fr/programmes/egyptiens2.exe

Le premier affiche systématiquement toutes les solutions. On peut contrôler cet affichage dans le second. Vous trouverez sur le site des versions de ces 2 programmes python utilisant le module Fraction et qui sont plus rapides quand les nombres sont grands.

calcul =1

while (calcul > 0) :

# Affichage d'explications :

print (" ")
print ("   DEVELOPPEMENTS  EGYPTIENS  d'Ordre n d'une fraction  P/Q")
print (" ")
print ("   P/Q = 1/x1 + 1/x2 + 1/x3 + ... + 1/xn ")
print (" ")
print ("   Avec pour le Type 1 : x1 <= x2 <= x3 <= ... <= xn")
print (" ")
print ("   Avec pour le Type 2 : x1 < x2 < x3 < ... < xn")
print (" ")

# Entree des donnees :

calcul = 0
n =int( input("   Ordre  n  (n>1) ? : "))
print (" ")
P = int(input("   P  ? : "))
print (" ")
Q = int(input("   Q  ? : "))

print (" ")
T = int(input("   Type  (1 ou 2)  ? : "))-1
print (" ")
m = int(input("   Minimum pour x1  ? : "))
if(m<1):
m=1
print (" ")

# Initialisation des variables :

sol = 0
Max = [0]
Min = [0]
x = [0]
for j in range (1 , n+2):
Max.append(0)
Min.append(0)
x.append(0)
i=1

# Valeurs de Max[1], Min[1] et valeur de depart pour x[1].

Max[1]=((Q*n)//P)
Min[1]= (Q//P)+1
if (Min[1]<m) :
Min[1]=m
if (Max[1]<Min[1]) :
i=0
else :
x[1]= Max[1]

# Boucle pour i >= 1

while (i!=0):

# Calcul de p et q et simplification de p/q      

p=0
q=1
for j in range(1, i+1):
p = p*x[j]+q
q = q*x[j]
p = P*q - p*Q
q = Q*q
p1=p
q1=q
while (p1 != q1) :
if (p1 > q1) :
p1 = p1 - q1
else:
q1 = q1 - p1
p =(p//p1)
q =(q//p1)

# valeurs de Max[i + 1] et Min[i +1]  :

Max[i+1]= (q*(n-i))//p
Min[i+1]= (q//p)+1
if (Min [i+1] <= x[i]):
Min[i+1]=x[i]+T

# Recherche des valeurs x[i] à tester et affichage des solutions.

if ((Max[i+1]>=Min[i+1])and(i<(n-1))):
x[i+1]=Max[i+1]
i=i+1
else :
if ((i==(n-1)) and ((q % p)==0)):
x[n]= (q // p)
if (x[n]>= x[n-1]+T):
sol= sol + 1
print(sol, end="  :  ")
for j in range (1, n+1):
print(x[j], end="  |  ")
print (" ")
s=1
while ((i!=0)and(s==1)):
s=0
if (x[i]> Min[i]):
x[i]= x[i] - 1
else :
i=i-1
s=1

# Effacement des variables liste en fin de calcul.

Max.clear()
Min.clear()
x.clear()

# Reprise d'un autre calcul ou fin.

print (" ")
calcul =int(input("   Nouveau calcul (1: oui, 0: Fin) ? : "))

if (calcul <=0):

exit()

Algorithme appliqué pour :

n = 3 et P/Q = 1/2
Type 2 1 :     4      6     12 2 :     4     5     20 3 :     3     10     15 4 :     3     9     18 5 :     3     8     24 6 :     3     7     42	Type 1 : 1 :     6     6     6 2 :     5     5     10 3 :     4     8     8 4      4     6     12 5 :     4     5     20 6 :     3     12     12 7 :     3     10     15 8 :     3     9     18 9 :     3     8     24 10 :     3     7     42
n = 4 et P/Q = 1
Type 2 : 1 :  2 4 6 12 2 : 2 4 5 20 3 : 2 3 10 15 4 : 2 3 9 18 5 : 2 3 8 24 6 : 2 3 7 42	Type 1 : 1 : 4 4 4 4 2 : 3 4 4 6 3 : 3 3 6 6 4 : 3 3 4 12 5 : 2 6 6 6 6 : 2 5 5 10 7 : 2 4 8 8 8 : 2 4 6 12 9 : 2 4 5 20 10 : 2 3 12 12 11 : 2 3 10 15 12 : 2 3 9 18 13 : 2 3 8 24 14 : 2 3 7 42

Renseignements pratiques

Ce logiciel peut être utilisé sur tout ordinateur 64 bits sous Windows. Il est gratuit et vous pouvez vous en servir librement.

Vous pouvez l'utiliser en projetant son écran de sortie avec un vidéoprojecteur. Ou alors le faire utiliser par les élèves, seuls ou par deux, derrière leur ordinateur en salle d'informatique. Ils peuvent aussi l'avoir aussi, chez eux, sur leur propre PC.

Il est téléchargeable à partir de la page Web suivante :

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

On y trouve aussi des liens vers des sites concernant le sujet et des exemples d'utilisation du logiciel.

Et également des liens vers les pages Web d'autres logiciels à usages pédagogiques que je propose.

(Pour le téléchargement, comme c'est un fichier «.exe », passez outre les recommandations de prudence de Windows).

La première fois que vous le lancerez (passez toujours outre les recommandations de prudence de Windows), il s'ouvrira dans une petite fenêtre avec, une dimension, des couleurs et une police qui ne vous conviendront peut-être pas. En cliquant droit dans la barre du haut de cette fenêtre, vous aurez accès à ses propriétés et pourrez les modifier à votre aise. Ces modifications resteront enregistrées pour les utilisations suivantes.

Les entrées sont sécurisées, et une faute de frappe ou une entrée incompatible ne plante pas le logiciel.

Il a été testé de nombreuses fois et ne semble pas avoir de bugs.

   L'interface du logiciel est simple et toutes les commandes (en nombre limité) sont expliquées ou rappelées en cours d'utilisation.

Il est écrit en C++ accompagné de son extension NTL qui permet de calculer avec des entiers de tailles quelconques.

Alain Barnier
Professeur de mathématiques retraité,
membre actif de l'APMEP
abarnier@wanadoo.fr

Cet article est sous licence Creative Commons Attribution 4.0 International. https://creativecommons.org/licenses/by/4.0/deed.fr

Association EPI
Avril 2024

Articles