Greedy Algorithm For Egyptian Fractions - Algorithm and Examples

Algorithm and Examples

Fibonacci's algorithm expands the fraction x/y to be represented, by repeatedly performing the replacement

(simplifying the second term in this replacement as necessary). For instance:

in this expansion, the denominator 3 of the first unit fraction is the result of rounding 15/7 up to the next larger integer, and the remaining fraction 2/15 is the result of simplifying (-15 mod 7)/(15×3) = 6/45. The denominator of the second unit fraction, 8, is the result of rounding 15/2 up to the next larger integer, and the remaining fraction 1/120 is what is left from 7/15 after subtracting both 1/3 and 1/8.

As each expansion step reduces the numerator of the remaining fraction to be expanded, this method always terminates with a finite expansion; however, compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators. For instance, this method expands

while other methods lead to the much better expansion

Wagon (1991) suggests an even more badly-behaved example, 31/311. The greedy method leads to an expansion with ten terms, the last of which has over 500 digits in its denominator; however, 31/311 has a much shorter non-greedy representation, 1/12 + 1/63 + 1/2799 + 1/8708.