Greedy Algorithm For Egyptian Fractions - Maximum-length Expansions and Congruence Conditions

Maximum-length Expansions and Congruence Conditions

Any fraction x/y requires at most x terms in its greedy expansion. Mays (1987) and Freitag & 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 fractions x/y that have x-term expansions and that have the smallest possible denominator y for each x is

(sequence A048860 in OEIS).