Egyptian Fraction Calculator

Convert any proper fraction to a sum of distinct unit fractions (1/n) using the greedy algorithm with step-by-step decomposition.

Enter Fraction

Egyptian Fraction Decomposition

Egyptian Fraction
1/2 + 1/5 + 1/70
sum of unit fractions
Original Fraction 5/7
Decimal Value 0.714286
Number of Unit Fractions 3
Verification Sum 0.714286

Greedy Algorithm Steps

5/7 = 1/2 + 1/5 + 1/70

What Are Egyptian Fractions?

An Egyptian fraction is a representation of a rational number as a sum of distinct unit fractions, where each unit fraction has the form 1/n for a positive integer n. Ancient Egyptians exclusively used this notation in their mathematical texts, most notably in the Rhind Mathematical Papyrus (c. 1650 BC). Every positive rational number can be expressed as a finite sum of distinct unit fractions.

For example, the fraction 3/4 can be written as 1/2 + 1/4, and 2/3 can be written as 1/2 + 1/6. The key constraint is that all unit fractions in the decomposition must be distinct (no repeats).

The Greedy Algorithm (Fibonacci-Sylvester)

Step 1: Find Largest Unit Fraction

Given a/b, find the smallest n such that 1/n is less than or equal to a/b. This means n = ceil(b/a).

n = ceil(b / a)

Step 2: Subtract

Compute the remainder: a/b - 1/n = (a*n - b) / (b*n).

remainder = a/b - 1/n

Step 3: Repeat

Apply the algorithm recursively to the remainder until the numerator becomes 0 or 1.

Repeat until remainder = 0

Termination

The algorithm always terminates because the numerator strictly decreases at each step (Fibonacci, 1202).

Each step: new_num < old_num

Example: 3/7

ceil(7/3)=3, so 1/3. Remainder: 3/7-1/3=2/21. ceil(21/2)=11, so 1/11. Remainder: 1/231.

3/7 = 1/3 + 1/11 + 1/231

Non-Uniqueness

Egyptian fraction representations are not unique. 2/3 = 1/2 + 1/6 = 1/3 + 1/4 + 1/12.

Multiple decompositions exist

History and Significance

The ancient Egyptians used unit fractions exclusively (with the sole exception of 2/3, which had its own hieroglyph). The Rhind Papyrus contains a table decomposing fractions of the form 2/n for all odd n from 3 to 101. Scholars believe this preference arose from practical considerations in dividing goods fairly among workers.

Mathematical Properties

  • Every positive rational number has an Egyptian fraction representation (proven by Fibonacci in 1202).
  • The greedy algorithm produces a finite representation but not always the shortest one.
  • The denominators in the greedy algorithm can grow very rapidly (exponentially in worst cases).
  • Finding the shortest Egyptian fraction representation is an NP-hard problem.
  • The Erdos-Straus conjecture states that 4/n can always be written as a sum of three unit fractions.

Alternative Algorithms

  • Greedy (Fibonacci-Sylvester): Always picks the largest possible unit fraction. Simple but may produce large denominators.
  • Odd Greedy: Restricts to odd denominators, conjectured to always terminate.
  • Binary Method: Uses the binary expansion of the fraction.
  • Continued Fraction Method: Derives Egyptian fractions from the continued fraction expansion.

Notable Examples

  • 2/3 = 1/2 + 1/6 (Rhind Papyrus standard form)
  • 4/13 = 1/4 + 1/18 + 1/468
  • 5/121 = 1/25 + 1/757 + 1/763,309 + 1/873,960,180,913 + ... (denominators grow rapidly)