egyptienne — Décomposition en fractions égyptiennes

Problème

Étant donné une fraction \(f\) (comprise entre 0 et 1), la décomposition en fractions égyptiennes revient à écrire cette fraction \(f\) comme somme de fractions de numérateur égal à 1, et de dénominateurs différents deux à deux.

Par exemple : \(\frac{3}{4}=\frac{1}{2}+\frac{1}{4}\), ou \(\frac{7}{22}=\frac{1}{4}+\frac{1}{5}+\frac{1}{660}\).

Propriétés

Deux questions qui se posent immédiatement sont :

  1. Toute fraction (comprise entre 0 et 1) peut elle être décomposée en fractions égyptiennes ?
  2. Si oui, cette décomposition est-elle unique ?

Les réponses sont oui et non (et une ébauche de démonstration est donnée en introduction de cet article) :

  1. toute fraction peut être décomposée en fractions égyptiennes ;
  2. pour chaque fraction, il existe une infinité de telles décompositions.

Algorithme

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def egyptienne(a, b):
    """Décompose ``a/b`` en fraction égyptienne.

    Renvoie la liste des dénominateurs de la décomposition.
    """
    (a, b) = irreductible(a, b)

    if a == 1:
        return [b]

    (n, r) = divmod(b, a)
    return [n + 1] + egyptienne(a * (a - r), b * (b - r + a))

L’algorithme mis en œuvre est un algorithme glouton : étant donné notre fraction \(f\), si elle n’est pas déjà égyptienne (lignes 8 et 9), on prend comme première fraction égyptienne la plus grosse fraction possible (inférieure à \(f\)), et on recommence sur la différence restante (ligne 12, en remarquant que si \(a = n b+r\), alors \(\frac{a}{b}-\frac{1}{n+1}=\frac{a (a-r)}{b (b - r + a)}\)).

Optimalité

Si l’on appelle optimale une décomposition qui minimise le nombre de termes de la décomposition, on remarque que l’algorithme n’est pas optimal. Par exemple, alors qu’il existe une décomposition en deux fractions de \(\frac{9}{20}\) (en effet, \(\frac{9}{20}=\frac{1}{4}+\frac{1}{5}\)), la décomposition donnée par l’algorithme glouton est \(\frac{9}{20}=\frac{1}{3}+\frac{1}{9}+\frac{1}{180}\)).

L’algorithme termine-t-il toujours ?

Existe-t-il une fraction pour laquelle l’algorithme s’exécute sans jamais s’arrêter ? La réponse est non, et une démonstration en est donnée ici.

Usage

Calculate egyptian fractions

usage: egyptienne [-h] [-v] A/B [A/B ...]

Positional Arguments

A/B Fractions to decompose, in the form “a/b” (where a and b are integers).

Named Arguments

-v, --version show program’s version number and exit