Egyptian Fraction Representation
You'll learn how to express any fraction as a sum of distinct unit fractions using a greedy approach.
The Core Idea
An Egyptian fraction represents any fraction (like 5/6) as a sum of unit fractions—fractions with 1 in the numerator (like 1/2 + 1/3). Ancient Egyptians used this system exclusively.
The greedy algorithm approach works like this: repeatedly subtract the largest unit fraction that doesn't exceed your remaining fraction. "Largest" means the one with the smallest denominator (since 1/2 > 1/3 > 1/4...).
How It Works
Imagine you need to represent 5/6:
-
Find the largest unit fraction ≤ 5/6
- 1/1 is too big, but 1/2 works
- Subtract: 5/6 - 1/2 = 5/6 - 3/6 = 2/6 = 1/3
-
Now represent the remainder 1/3
- 1/3 is already a unit fraction—done!
Result: 5/6 = 1/2 + 1/3
For 2/5:
- Largest unit fraction ≤ 2/5 is 1/3
- Subtract: 2/5 - 1/3 = 6/15 - 5/15 = 1/15
Result: 2/5 = 1/3 + 1/15
The Algorithm Pattern
At each step, if you have fraction a/b:
- Find smallest integer d where 1/d ≤ a/b (equivalently, d ≤ b/a)
- This is your greedy choice: take ceiling(b/a)
- Subtract and repeat with the remainder
This mirrors the greedy choice property: pick the locally best option (biggest bite) each time.
Key Takeaway: The greedy Egyptian fraction algorithm decomposes any fraction into distinct unit fractions by repeatedly taking the largest possible unit fraction at each step—a classic greedy approach that always terminates but doesn't always produce the shortest representation.