Course contentsShow
← Computer Science
Lesson 895 of 2,87221. Greedy AlgorithmsFree lesson

Egyptian Fraction Representation

Represent a fraction as sum of unit fractions by repeatedly taking the largest possible unit fraction.

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:

  1. 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
  2. Now represent the remainder 1/3

    • 1/3 is already a unit fraction—done!

Result: 5/6 = 1/2 + 1/3

For 2/5:

  1. 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.