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).
Read more about this topic: Greedy Algorithm For Egyptian Fractions
Famous quotes containing the words congruence and/or conditions:
“As for butterflies, I can hardly conceive
of one’s attending upon you; but to question
the congruence of the complement is vain, if it exists.”
—Marianne Moore (1887–1972)
“The Supreme Court would have pleased me more if they had concerned themselves about enforcing the compulsory education provisions for Negroes in the South as is done for white children. The next ten years would be better spent in appointing truant officers and looking after conditions in the homes from which the children come. Use to the limit what we already have.”
—Zora Neale Hurston (1891–1960)