Greedy algorithm for Egyptian fractions

In mathematics, an Egyptian fraction is a representation of an irreducible fraction 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). 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.

Fibonacci actually lists several different methods for constructing Egyptian fraction representations (Sigler 2002, chapter II.7). He includes the greedy method as a last resort for situations when several simpler methods fail; see Egyptian fraction for a more detailed listing of these methods. As Salzer (1948) details, the greedy method, and extensions of it for the approximation of irrational numbers, have been rediscovered several times by modern mathematicians, earliest and most notably by Sylvester (1880); see for instance Cahen (1891) and Spiess (1907). A closely related expansion method that produces closer approximations at each step by allowing some unit fractions in the sum to be negative dates back to Lambert (1770).

The expansion produced by this method for a number "x" is called the "greedy Egyptian expansion", "Sylvester expansion", or "Fibonacci-Sylvester expansion" of "x". However, the term "Fibonacci expansion" usually refers, not to this method, but to representation of integers as sums of Fibonacci numbers.

Algorithm and examples

In Fibonacci's algorithm, we expand the fraction "x"/"y" that we desire to represent, by repeatedly performing the replacement:(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\{5\}\{121\}=frac\{1\}\{25\}+frac\{1\}\{757\}+frac\{1\}\{763309\}+frac\{1\}\{873960180913\}+frac\{1\}\{1527612795642093418846225\},$while other methods lead to the much better expansion:$frac\{5\}\{121\}=frac\{1\}\{33\}+frac\{1\}\{121\}+frac\{1\}\{363\}.$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\; floor+1$ instead of $lceil\; y/x\; ceil$. Truncating this sequence to "k" terms and forming the corresponding Egyptian fraction, e.g. (for "k" = 4):$frac12+frac13+frac17+frac1\{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.

Maximum-length expansions and congruence conditions

Any fraction "x"/"y" requires at most "x" terms in its greedy expansion. Mays (1987) and Freitag and Phillips (1999) examine the conditions under which "x"/"y" leads to an expansion with exactly "x" terms; these can be described in terms of congruence conditions on "y".

* Every fraction 1/"y" requires one term in its expansion; the simplest such fraction is 1/1.

* Every fraction 2/"y" for odd "y" > 1 requires two terms in its expansion; the simplest such fraction is 2/3.

* A fraction 3/"y" requires three terms in its expansion if and only if "y" ≡ 1 (mod 6), for then -"y" mod "x" = 2 and y(y+2)/3 is odd, so the fraction remaining after a single step of the greedy expansion,:::is in simplest terms. The simplest fraction 3/"y" with a three-term expansion is 3/7.

* A fraction 4/"y" requires four terms in its expansion if and only if "y" ≡ 1 or 17 (mod 24), for then the numerator -"y" mod "x" of the remaining fraction is 3 and the denominator is 1 (mod 6). The simplest fraction 4/"y" with a four-term expansion is 4/17. The Erdős–Straus conjecture states that all fractions 4/"y" have an expansion with three or fewer terms, but when "y" ≡ 1 or 17 (mod 24) such expansions must be found by methods other than the greedy algorithm.

More generally the sequence of the smallest denominators "y" leading to the longest expansion for each "x" is:1, 3, 7, 17, 31, 109, 253, 97, 271, ... OEIS|id=A048860.

Approximation of polynomial roots

Stratemeyer (1930) and Salzer (1947) describe a method of finding an accurate approximation for the roots of a polynomial, by applying the greedy algorithm to compute the greedy expansion of the root, at each step maintaining a polynomial the root of which is the remaining fraction to be expanded. For instance, suppose we want to find the greedy expansion of the golden ratio, one of the two solutions of the polynomial equation "P"₀("x") = "x"² - x - 1 = 0. Following Stratemeyer and Salzer, we perform the following sequence of steps:

#Since "P"₀("x") < 0 for "x" = 1, and "P"₀("x") > 0 for all "x" ≥ 2, there must be a root of "P"₀("x") between 1 and 2. That is, the first term of the greedy expansion of the golden ratio is 1/1. If "x"₁ is the remaining fraction after the first step of the greedy expansion, it satisfies the equation "P"₀("x"₁ + 1) = 0, which we can expand as "P"₁("x"₁) = "x"₁² + "x"₁ - 1 = 0.
#Since "P"₁("x") < 0 for "x" = 1/2, and "P"₁("x") > 0 for all "x" > 1, the root we are seeking lies between 1/2 and 1, and the next term in its greedy expansion is 1/2. If "x"₂ is the remaining fraction after this step of the greedy expansion, it satisfies the equation "P"₁("x"₂ + 1/2) = 0, which we can expand as "P"₂("x"₂) = 4"x"₂² + 8"x"₂ - 1 = 0.
#Since "P"₂("x") < 0 for "x" = 1/9, and "P"₂("x") > 0 for all "x" > 1/8, the next term in the greedy expansion is 1/9. If "x"₃ is the remaining fraction after this step of the greedy expansion, it satisfies the equation "P"₂("x"₃ + 1/9) = 0, which we can again expand as a polynomial equation with integer coefficients, "P"₃("x"₃) = 324"x"₃² + 720"x"₃ - 5 = 0.

Continuing this approximation process eventually produces the greedy expansion for the golden ratio,

:$varphi\; =\; frac11+frac12+frac19+frac1\{145\}+frac1\{37986\}+cdots$ OEIS|id=A117116.

Other 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 [http://www.research.att.com/~njas/sequences/A050205 A050205] , [http://www.research.att.com/~njas/sequences/A050206 A050206] , and [http://www.research.att.com/~njas/sequences/A050210 A050210] , respectively. In addition, the greedy expansion of any irrational number leads to an infinite increasing sequence of integers, and the OEIS contains [http://www.research.att.com/~njas/sequences/?q=greedy-Egyptian-fraction-expansion expansions of several well known constants] . Some [http://www.research.att.com/~njas/sequences/?q=Egyptian-fraction-for additional entries in the OEIS] , though not labeled as being produced by the greedy algorithm, appear to be of the same type.

Related expansions

In general, if one wants an Egyptian fraction expansion in which the denominators are constrained in some way, it is possible to define a greedy algorithm in which at each step one chooses the expansion:$frac\{x\}\{y\}=frac\{1\}\{d\}+frac\{xd-y\}\{yd\},$where "d" is chosen, among all possible values satisfying the constraints, as small as possible such that "xd" > "y" and such that "d" is distinct from all previously chosen denominators. For instance, the Engel expansion can be viewed as an algorithm of this type in which each successive denominator must be a multiple of the previous one. However, it may be difficult to determine whether an algorithm of this type can always succeed in finding a finite expansion. In particular, the odd greedy expansion of a fraction "x"/"y" is formed by a greedy algorithm of this type in which all denominators are constrained to be odd numbers; it is known that, whenever "y" is odd, there is a finite Egyptian fraction expansion in which all denominators are odd, but it is not known whether the odd greedy expansion is always finite.

References

* cite journal
author = Cahen, E.
title = Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues
journal = Nouvelles Annales des Mathématiques, Ser. 3
volume = 10
year = 1891
pages = 508–514

* cite journal
author = Curtiss, D. R.
title = On Kellogg's diophantine problem
journal = American Mathematical Monthly
volume = 29
year = 1922
pages = 380–387
doi = 10.2307/2299023

*cite conference
author = Freitag, H. T.; Phillips, G. M.
title = Sylvester's algorithm and Fibonacci numbers
booktitle = Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998)
pages = 155–163
publisher = Kluwer Acad. Publ.
location = Dordrecht
year = 1999
id = MathSciNet | id = 1737669

*cite book
author = Lambert, J. H.
authorlink = Johann Heinrich Lambert
title = Beyträge zum Gebrauche der Mathematik und deren Anwendung
location = Berlin
publisher = Zweyter Theil
year = 1770
pages = 99–104

*cite journal
author = Mays, Michael
title = A worst case of the Fibonacci-Sylvester expansion
journal = Journal of Combinatorial Mathematics and Combinatorial Computing
year = 1987
volume = 1
pages = 141–148
id = MathSciNet | id = 0888838

*cite journal
author = Salzer, H. E.
journal = American Mathematical Monthly
year = 1947
title = The approximation of numbers as sums of reciprocals
volume = 54
issue = 3
pages = 135–142
id = MathSciNet | id = 0020339
doi = 10.2307/2305906

*cite journal
author = Salzer, H. E.
journal = American Mathematical Monthly
year = 1948
title = Further remarks on the approximation of numbers as sums of reciprocals
volume = 55
issue = 6
pages = 350–356
id = MathSciNet | id = 0025512
doi = 10.2307/2304960

*cite book
title = Fibonacci's Liber Abaci
author = Sigler, Laurence E. (trans.)
publisher = Springer-Verlag
year = 2002
id = ISBN 0-387-95419-8

* cite journal
author = Soundararajan, K.
year = 2005
title = Approximating 1 from below using "n" Egyptian fractions
id = arxiv|archive = math.CA|id = 0502247

* cite journal
author = Spiess, O.
journal = Archiv der Mathematik und Physik, Ser. 3
year = 1907
title = Über eine Klasse unendlicher Reihen
volume = 12
pages = 124–134

* cite journal
author = Stong, R. E.
title = Pseudofree actions and the greedy algorithm
journal = Mathematische Annalen
volume = 265
issue = 4
year = 1983
pages = 501–512
doi = 10.1007/BF01455950
id = MathSciNet | id = 0721884

* cite journal
author = Stratemeyer, G.
title = Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl
journal = Mathematische Zeitschrift
volume = 31
year = 1930
pages = 767–768
doi = 10.1007/BF01246446

* cite journal
author = Sylvester, J. J.
authorlink = J. J. Sylvester
title = On a point in the theory of vulgar fractions
journal = American Journal of Mathematics
volume = 3
issue = 4
year = 1880
pages = 332–335
doi = 10.2307/2369261

* cite book
author = Wagon, S.
title = Mathematica in Action
publisher = W. H. Freeman
year = 1991
pages = 271–­277