Egyptian Fraction

Egyptian Fraction asks you to write any proper fraction as a sum of distinct unit fractions — fractions whose numerator is 1, like 1/3 or 1/11. The ancient Egyptians wrote every fraction this way, and a simple greedy rule always works.

The slow way first

You might try to search for a set of denominators that add up exactly to n/d — testing combinations of 1/2, 1/3, 1/4, ... until one set works. That search blows up fast: there are exponentially many subsets to try, and no obvious way to prune them.

The question to ask: what is the single largest unit fraction I can subtract right now without going negative? If I always take the biggest legal piece, the remainder shrinks every step — and it turns out it shrinks fast enough to terminate.

The idea: take the biggest unit fraction that fits

For n/d, the largest unit fraction 1/x that is not larger than n/d uses x = ceil(d / n). Subtract it. The new fraction is:

n/d - 1/x = (n*x - d) / (d*x)

so we update n to n*x - d and d to d*x, then repeat. Each step the new numerator n*x - d is strictly smaller than the old n, so n keeps dropping and eventually hits 0 — at which point we are done.

Because we always grab the largest legal piece, the denominators come out strictly increasing, so the unit fractions are automatically distinct.

Walk through it

Step through the animation starting from 3/7. We pick 1/3 (since ceil(7/3) = 3), leaving 2/21. Then 1/11 (since ceil(21/2) = 11), leaving 1/231. That last fraction already has numerator 1, so it is itself a unit fraction. The result list [1/3, 1/11, 1/231] builds up underneath.

Pseudocode

result = empty list
while n is not 0:
    x = ceil(d / n)          # smallest x so 1/x <= n/d
    append x to result
    n = n*x - d              # numerator of the remainder
    d = d*x                  # denominator of the remainder
return result                # denominators of the unit fractions

The Python solution

def egyptian_fraction(n, d):
    result = []
    while n != 0:
        x = -(-d // n)          # ceil(d / n)
        result.append(x)
        n = n * x - d
        d = d * x
    return result

• result collects the denominators x of each unit fraction 1/x.
• The loop runs until the numerator n becomes 0 — that is when nothing is left to express.
• -(-d // n) is the integer ceiling of d / n (Python floor-divides toward negative infinity, so negating twice rounds up).
• n = n * x - d and d = d * x together replace n/d with the remainder (n*x - d) / (d*x).
• When n reaches a numerator of 1, x = d and the subtraction sends n to 0, ending the loop.

Complexity

The greedy method produces a representation in just a handful of terms for typical inputs, and the numerator strictly decreases each step, so the loop is guaranteed to end. The space is whatever it takes to hold the output list.

When this pattern shows up

Practice