Greedy algorithm for Egyptian fractions

From Wikipedia, the free encyclopedia

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.

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.

1 Algorithm and examples
2 Sylvester's sequence and closest approximation
3 Maximum-length expansions and congruence conditions
4 Other integer sequences
5 See also
6 References

[edit] 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{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.

[edit] 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)

$\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.

[edit] 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,

$\frac{-y\bmod x}{y\lceil y/x\rceil} = \frac2{y(y+2)/3}$

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, ... (sequence A048860 in OEIS).

[edit] 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 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.

[edit] See also

[edit] References

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

Freitag, H. T.; Phillips, G. M. (1999). "Sylvester's algorithm and Fibonacci numbers". Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998), 155–163, Dordrecht: Kluwer Acad. Publ.. MR 1737669.

Mays, Michael (1987). "A worst case of the Fibonacci-Sylvester expansion". Journal of Combinatorial Mathematics and Combinatorial Computing 1: 141–148. MR 0888838.