Egyptian Fraction Calculator (Greedy / Fibonacci–Sylvester)

What Are Egyptian Fractions?

An Egyptian fraction is a representation of a positive rational number as a finite sum of distinct unit fractions — fractions of the form 1/n where n is a positive integer. Ancient Egyptian scribes used this notation exclusively, as documented in the Rhind Mathematical Papyrus (circa 1650 BCE). For example, 3/4 was written as 1/2 + 1/4, and 2/5 as 1/3 + 1/15. The requirement that all denominators be distinct is the defining constraint separating Egyptian fractions from ordinary unit-fraction sums.

The Greedy Algorithm (Fibonacci–Sylvester Method)

The most systematic algorithm for computing Egyptian fraction expansions is the greedy algorithm, first described by Fibonacci in his 1202 treatise Liber Abaci and later formalized by James Joseph Sylvester in 1880. At each step the algorithm selects the largest possible unit fraction that does not exceed the remaining value, hence the name greedy. This approach is also called the Fibonacci–Sylvester algorithm in recognition of both contributors.

Core Formula

Given a proper fraction p/q where p and q are positive integers and p < q, the algorithm applies the following recurrence:

• Step 1 — Compute the ceiling: Let n = ⌈q/p⌉, the smallest positive integer such that 1/n ≤ p/q.
• Step 2 — Record the unit fraction: Append 1/n to the expansion list.
• Step 3 — Compute the remainder: The new fraction equals (p·n − q)/(q·n), derived directly from p/q − 1/n = (p·n − q)/(q·n).
• Step 4 — Iterate: Set p ← p·n − q and q ← q·n (after reducing by GCD), then return to Step 1 until the remainder equals zero.

Guaranteed Termination

The algorithm always terminates in a finite number of steps. When p does not divide q, the new numerator p·⌈q/p⌉ − q is strictly less than p, because ⌈q/p⌉ < q/p + 1 in that case, giving p·⌈q/p⌉ − q < p. Since the numerator is a positive integer that strictly decreases each iteration, it must eventually reach zero. When p divides q the remainder is zero immediately. This termination proof is detailed in Wolfram MathWorld: Egyptian Fraction.

Worked Example: Expanding 5/7

Apply the greedy algorithm to 5/7 step by step:

• Iteration 1: ⌈7/5⌉ = 2. Unit fraction: 1/2. Remainder: (5×2 − 7)/(7×2) = 3/14.
• Iteration 2: ⌈14/3⌉ = 5. Unit fraction: 1/5. Remainder: (3×5 − 14)/(14×5) = 1/70.
• Remainder zero — done. Result: 5/7 = 1/2 + 1/5 + 1/70.

Verification: 35/70 + 14/70 + 1/70 = 50/70 = 5/7. Correct.

The Fibonacci–Sylvester Sequence

Applying the greedy algorithm to the number 1 generates the Sylvester sequence: 2, 3, 7, 43, 1807, 3263443, ... Each term satisfies the recurrence a_{n+1} = a_n(a_n − 1) + 1, and the sum of reciprocals converges exactly to 1: 1/2 + 1/3 + 1/7 + 1/43 + 1/1807 + ··· = 1. The sequence grows doubly exponentially — each term is roughly the square of the previous — so only a handful of terms suffice to represent most fractions to high precision.

Key Variables

• p (Numerator): The top number of the input fraction. For a proper Egyptian fraction expansion p must be less than q. The algorithm's termination guarantee rests on p being a positive integer that strictly decreases each iteration.
• q (Denominator): The bottom number of the input fraction; must be a positive integer. Fractions with large or irregular denominators may produce expansions whose later unit-fraction denominators grow very large.
• ⌈q/p⌉ (Ceiling): The ceiling function rounds q/p up to the nearest integer and identifies the greedy unit fraction 1/⌈q/p⌉ — the largest unit fraction not exceeding the current remainder.

Applications and Open Problems

Egyptian fractions remain an active research area in number theory. The Erdős–Straus conjecture (1948) asserts that for every integer n ≥ 2 the fraction 4/n can be expressed as the sum of exactly three unit fractions; it has been verified computationally for all n up to 10^14 but remains unproven in general. Egyptian fraction decompositions also appear in fair division problems, where distinct shares of a resource must be allocated without repetition, and in combinatorial analysis of rational numbers. The OSU survey Egyptian fractions, Sylvester's sequence, and the Erdős–Straus conjecture provides an accessible yet rigorous treatment of these connections.

Limitations of the Greedy Algorithm

The greedy algorithm always produces a valid expansion but does not guarantee the shortest one or the one with the smallest denominators. For some fractions, other methods yield fewer terms. For instance, the greedy expansion of 4/17 produces denominators reaching into the millions, while a manual search finds 4/17 = 1/5 + 1/29 + 1/1233 with comparable length but different denominators. For applications where compact representations matter, exhaustive search or splitting algorithms may be preferable over the greedy approach.