Greedy algorithm for Egyptian fractions

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

${\displaystyle {\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:

${\displaystyle {\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

${\displaystyle {\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

${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$

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.

Sylvester's sequence 2, 3, 7, 43, 1807, ... (OEIS: A000058) 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 ${\displaystyle \lfloor y/x\rfloor +1}$ instead of ${\displaystyle \lceil y/x\rceil }$. Truncating this sequence to k terms and forming the corresponding Egyptian fraction, e.g. (for k = 4)

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

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

• Every fraction 1/y requires one term in its greedy expansion; the simplest such fraction is 1/1.
• Every fraction 2/y requires two terms in its greedy expansion if and only if y ≡ 1 (mod 2); the simplest such fraction is 2/3.
• A fraction 3/y requires three terms in its greedy 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,

${\displaystyle {\frac {(-y){\bmod {x}}}{y\lceil y/x\rceil }}={\frac {2}{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 greedy 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, with the 17 (mod 24) case being covered by the congruence relationship 2 (mod 3).

More generally the sequence of fractions x/y that have x-term greedy expansions and that have the smallest possible denominator y for each x is

${\displaystyle 1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots }$ (sequence A048860 in the OEIS).

Stratemeyer (1930) and Salzer (1947) describe a method of finding an accurate approximation for the roots of a polynomial based on the greedy method. Their algorithm computes the greedy expansion of a root; at each step in this expansion it maintains an auxiliary polynomial that has as its root the remaining fraction to be expanded. Consider as an example applying this method to find the greedy expansion of the golden ratio, one of the two solutions of the polynomial equation P₀(x) = x² - x - 1 = 0. The algorithm of Stratemeyer and Salzer performs the following sequence of steps:

1. 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 can be expanded as P₁(x₁) = x₁² + x₁ - 1 = 0.
2. Since P₁(x) < 0 for x = 1/2, and P₁(x) > 0 for all x > 1, the root of P₁ lies between 1/2 and 1, and the first term in its greedy expansion (the second term in the greedy expansion for the golden ratio) 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 can be expanded as P₂(x₂) = 4x₂² + 8x₂ - 1 = 0.
3. 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 can again be expanded as a polynomial equation with integer coefficients, P₃(x₃) = 324x₃² + 720x₃ - 5 = 0.

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

${\displaystyle \varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$ (sequence A117116 in the OEIS).

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 OEIS: A050205, OEIS: A050206, and OEIS: 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.

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

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