Greedy algorithm for Egyptian fractions

In mathematics, an Egyptian fraction is a representation of a natural number as a sum of unit fractions, as e.g. 5/6 = 1/2 + 1/3. As the name indicates, these representations have been used as long ago as ancient Egypt, but the first published systematic method for constructing such expansions is described in the Liber Abaci (1202) of Leonardo of Pisa (Fibonacci), and rediscovered by Sylvester (1880). It is called a greedy algorithm because at each step the algorithm chooses greedily the largest possible unit fraction that can be used in any representation of the remaining fraction.

Algorithm and examples

In Fibonacci's algorithm, we expand the fraction x/y that we desire to represent, by repeatedly performing the replacement

${\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {-y{\bmod {x}}}{y\lceil y/x\rceil }}$

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

${\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.$

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

${\frac {3}{121}}={\frac {1}{41}}+{\frac {1}{2481}}+{\frac {1}{12308241}},$

while other methods lead to the much better expansion

${\frac {3}{121}}={\frac {1}{44}}+{\frac {1}{484}}.$

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

Sylvester's sequence and closest approximation

Sylvester's sequence 2, 3, 7, 43, 1807, ... can be viewed as generated by an infinite greedy expansion of this type for the number one, where at each step we choose the denominator $\lfloor y/x\rfloor +1$ instead of $\lceil y/x\rceil$. Truncating this sequence to k terms and forming the corresponding Egyptian fraction, e.g. (for k = 4)

${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}$

results in the closest possible underestimate of 1 by any k-term Egyptian fraction (Curtiss 1922; Soundararajan 2005). That is, for example, any Egyptian fraction for a number in the open interval (1805/1806,1) requires at least five terms. Curtiss (1922) describes an application of these closest-approximation results in lower-bounding the number of divisors of a perfect number, while Stong (1983) describes applications in group theory.

Integer sequences

The length, minimum denominator, and maximum denominator of the greedy expansion for all fractions with small numerators and denominators can be found in the On-Line Encyclopedia of Integer Sequences as sequences A050205, A050206, and A050210, respectively. In addition, the greedy expansion of any irrational number leads to an infinite increasing sequence of integers, and the OEIS contains expansions of several well known constants. Some additional entries in the OEIS, though not labeled as being produced by the greedy algorithm, appear to be of the same type.

References

• Curtiss, D. R. (1922). "On Kellogg's diophantine problem". American Mathematical Monthly. 29: 380–387.

• Soundararajan, K. (2005). "Approximating 1 from below using n Egyptian fractions". arXiv:math.CA/0502247. {{cite journal}}: Cite journal requires |journal= (help)

• Stong, R. E. (1983). "Pseudofree actions and the greedy algorithm". Mathematische Annalen. 265 (4): 501–512. doi:10.1007/BF01455950.

• Sylvester, J. J. (1880). "On a point in the theory of vulgar fractions". American Journal of Mathematics. 3 (4): 332–335.

• Wagon, S. (1991). Mathematica in Action. W. H. Freeman. pp. 271–­277. {{cite book}}: soft hyphen character in |pages= at position 5 (help)