algorithme de Fibonacci-Sylvester

algorithme glouton de Fibonacci-Sylvester

ARITHMETIQUE
CALCUL

Fibonacci donne sans démonstration, en 1202, dans son ouvrage Liber Abaci un algorithme permettant d’écrire tout nombre rationnel positif (toute fraction d’entiers positifs) sous forme d’une somme de fractions de numérateur 1 et dénominateur entier positif ( fractions égyptiennes ) : «Soustraire à la fraction donnée la plus grande fraction égyptienne possible, répéter l’opération avec la nouvelle fraction, et ainsi de suite jusqu’à ce que l’opération donne une fraction égyptienne. ». On obtient ainsi une décomposition en un nombre fini de fractions unitaires.
Cette méthode a été démontrée par James Sylvester en 1880.
On l’appelle « algorithme glouton de Fibonacci-Sylvester ».

En liaison avec les fractions égyptiennes , Sylvester a donné son nom à la suite de Sylvester, qu’il a étudiée dans les années 1880. La suite de Sylvester est un suite de nombres entiers tels que chaque terme est le produit des termes précédents plus 1.
si = s i-1 * (s i-1 – 1) +1, avec s0 = 2.
Les termes successifs sont : 2, 3, 7, 43, .
Les termes croissent selon une fonction exponentielle double.
La série des inverses converge vers 1. La série est donc une représentation de 1 sous forme de fraction égyptienne infinie.

De plus, on a une représentation de 1 par fraction égyptienne lorsqu’on tronque la série à n’importe quel terme et qu’on soustraie 1 du dernier dénominateur.
Exemples : 1 = 1/2 + 1/3 + 1/6 ; 1 = 1/2 + 1/3 + 1/7 +1/42