Egyptian Fractions and the Greedy Algorithm - Numberphile

Numberphile

Egyptian Hieroglyphic Number System

Ancient Egyptians used base 10 system with hieroglyphic symbols
Number symbols by powers of 10:
- 1: single stroke
- 2: two single strokes combined
- 10: cattle hobble (used to slow cattle)
- 100: coil of rope
- 1,000: water lily
- 10,000: bent finger
- 100,000: tadpole
- 1,000,000: Heh (personification of eternity/infinity)
Million also meant eternal/infinite amount (similar to "1,001 Arabian Nights" meaning infinity)
Numbers written by combining symbols (e.g., 23 = two tens + three ones)

Used mouth symbol over number to represent fractions
Only created unit fractions (1/n format)
Three exceptions to unit fraction rule:
- 2/3: special symbol
- 3/4: special symbol
- 1/2: different representation
All other fractions expressed as 1/n where n is denominator

Examples demonstrated:
- 5/6 = 1/2 + 1/3
- 15/36 = 1/3 + 1/12 (after simplification: 1/3 leaves 3/36 = 1/12)
All denominators in Egyptian fraction representation must be different

Systematic method to convert any fraction p/q to Egyptian fraction form
Process:
- Find largest 1/n such that 1/n < p/q
- n = ceiling(q/p) (smallest integer above q/p)
- Subtract 1/n from p/q to get new fraction p₁/q₁
- Key property: p₁ < p (numerator decreases each step)
- Repeat until numerator equals 1
Algorithm guarantees termination since:
- Positive integers can't decrease infinitely
- Eventually hits numerator = 1
- All denominators different by construction

Modified approach: n = q/p + 1
Example with fraction 1:
- 1 = 1/2 + 1/3 + 1/7 + 1/43 + ...
Special property: truncating at any point gives Egyptian fraction closest to 1 for that number of terms
- 1/2: closest single-term Egyptian fraction to 1
- 1/2 + 1/3: closest two-term Egyptian fraction to 1
- 1/2 + 1/3 + 1/7: closest three-term Egyptian fraction to 1

Try for free