Je ne comprends pas l'intérêt de ce problème : il y a une solution évidente qui est p/q= somme de 1 à p de 1/q non ?

Ah oui pardon

Je ne vais pas faire semblant d'ignorer les fractions égyptiennes.

Selon Wikipédia :

En effet, il est trivial d'exprimer toute fraction par une somme de fractions unitaires en se permettant de répéter les termes comme dans l'exemple :  [latex]\frac{2}{5} = \frac{1}{5} + \frac{1}{5}\,.[/latex]
Mais si l'on exige que tous les dénominateurs soient distincts, à l'instar des Égyptiens durant l'Antiquité, cette représentation est toujours possible grâce à l'identité : [latex]\frac{1}{a} = \frac{1}{(a+1)} + \frac{1}{a(a+1)}\,[/latex] que connaissait dès 1202 le grand mathématicien européen du Moyen Âge Leonardo Fibonacci.

Tout d'abord [latex]\frac{1}{a} = \frac{1}{a+1} + \frac{1}{a(a+1)}[/latex]
Du coup, une fraction unitaire peut se décomposer d'une infinité de manières différentes
[TeX]\frac{1}{a} = \frac{1}{a+1} + \frac{1}{a(a+1)}\\
\frac{1}{a} = \frac{1}{a+2} + \frac{1}{(a+1)(a+2)} + \frac{1}{a(a+1)}\\
\frac{1}{a} = \frac{1}{a+2} + \frac{1}{(a+1)(a+2)} + \frac{1}{a(a+1)+1} + \frac{1}{a(a+1)(a(a+1)+1)}
[/TeX]
etc...

Ensuite, [latex]\frac{a}{b} = \sum_{i=1}^a{\frac{1}{b}}[/latex]
Du coup, on peut remplacer chaque fraction [latex]\frac{1}{b}[/latex] par une somme de fractions unitaires du même type que celles vues plus haut.

Il faut quand même s'assurer que les différentes décompositions choisies pour les différents [latex]\frac{1}{b}[/latex] ne ramènent pas des termes identiques : en effet, les deux premières décompositions partagent par exemple un meme terme [latex]\frac{1}{a(a+1)}[/latex]. Pour cela, on va décomposer les [latex]\frac{1}{b}[/latex] un par un: si une décomposition n'est pas bonne, on applique la formule sur le terme qui nous embete, jusqu'à obtenir un terme correct, ce qui finira toujours par arriver vu que la formule nous donne des dénominateurs de plus en plus grand (et que tout ensemble non vide fini d'entiers admet nécessairement un plus grand élément)

Exemple: 5/4 = 1/4 + 1/4 + 1/4 + 1/4 + 1/4
On commence par 1/4 = 1/4

1/4 = 1/5 + 1/20
On continue donc avec 2/4 = 1/4 + 1/5 + 1/20

1/4 = 1/5 + 1/20 = 1/6 + 1/30 + 1/21 + 1/420
Donc 3/4 = 1/4 + 1/5 + 1/6 + 1/20 + 1/21 + 1/30 + 1/420

1/4 = 1/5 + 1/20 = 1/6 + 1/30 + 1/21 + 1/420
= 1/7 + 1/42 + 1/31 + 1/930 + 1/22 + 1/462 + 1/421 + 1/176820
Donc 4/4 = 1/4 + 1/5 + 1/6 + 1/7 + 1/20 + 1/21 + 1/22 + 1/30 + 1/31 + 1/42 + 1/420 + 1/421 + 1/462 + 1/930 + 1/176820

1/7 + 1/22 + 1/31 + 1/42 + 1/421 + 1/462 + 1/930 + 1/176820 =
1/8 + 1/56 + 1/23 + 1/506 + 1/32 + 1/992 + 1/43 + 1/1806 + 1/422 + 1/177662 + 1/463 + 1/213906 + 1/931 + 1/865830 + 1/176821 + 1/31265489220

Donc 5/4 = 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/20 + 1/21 + 1/22 + 1/23 + 1/30 + 1/31 + 1/32 + 1/42 + 1/43 + 1/56 + 1/420 + 1/421 + 1/422 + 1/462 + 1/463 + 1/506 + 1/930 + 1/931 + 1/992 + 1/1806 + 1/176820 + 1/176821 + 1/177662 + 1/213906 + 1/865830 + 1/31265489220

Voilà.

Bon ok c'est ma démo perso, elle vaut ce qu'elle vaut mais elle marche, par contre les résultats sont bien moins efficaces que d'autres algos comme celui de Fibonacci:
Exemple 5/4:
0<4/5<1 => 1/1
5/4-1/1 = 1/4, unitaire => 5/4 = 1/1 + 1/4

Exmple 7/9:
1<9/7<2 => 1/2
7/9-1/2 = 5/18, 3<18/5<4 => 1/4
5/18-1/4 = 1/36, unitaire => 7/9 = 1/2+1/4+1/36