Naar de inhoud
OneKitly

The Greedy Method Always Finishes, But Not Always Well

Gepubliceerd op 27-10-2026 · 3 min leestijd · Dagelijkse calculators

Antonio Delgado

Antonio Delgado — Redacteur tradities en tijdverdrijf bij OneKitly

Symboliek · Kalenders

Getoetst aan 2 bronnen

Profiel bekijken →
Kort gezegd

Egyptian fractions write any fraction as a sum of distinct pieces each of the form one-over-something. The greedy recipe is to repeatedly subtract the largest such piece that still fits, and it is guaranteed to terminate: each step shrinks the numerator of what remains, so the process cannot run forever. What it does not guarantee is brevity. For 3/7 it produces 1/3 + 1/11 + 1/231, a fine three-term answer. For 5/121 it produces five terms ending in a denominator of 25 digits, while a moment's thought gives 1/33 + 1/121 + 1/363 — three terms, none longer than three digits. Terminating and being good are different properties.

Advertentie

Writing 5/121 as a sum of unit fractions takes three terms if you are clever and five if you are greedy — the fifth having a denominator 25 digits long.

Why anyone wrote fractions this way

Egyptian scribes had no notation for a general fraction: apart from a couple of special symbols, everything was written as a sum of unit parts. The Rhind papyrus, copied around 1550 BC from an older source, opens with a table giving such decompositions for every fraction of the form two-over-an-odd-number up to 101, and those entries are not the greedy ones — they were chosen for small denominators and for divisibility that made further arithmetic easy. Someone did the work in advance so that a scribe dividing bread among workers would not have to. That is a lookup table for a hard subproblem, written thirty-five centuries before the phrase existed.

Sharing loaves is the honest use

The classic puzzle asks how to divide five loaves among eight people so that everyone gets the same amount and no loaf is cut into eight slivers. The greedy answer, 5/8 = 1/2 + 1/8, says it plainly: cut four loaves in half and hand each person a half, then cut the last loaf into eight and hand each person a piece. Two cuts per loaf, everyone equal, no crumbs. The unit-fraction form is not a quaint notation here — it is the instruction sheet, and the number of terms is the number of different piece sizes you have to produce. That is why a decomposition with three small denominators beats one with five, whatever a computer thinks of the arithmetic.

Terms
What the greedy method returns
FractionDecompositionTerms
2/31/2 + 1/62
5/81/2 + 1/82
3/71/3 + 1/11 + 1/2313
4/131/4 + 1/18 + 1/4683
5/1211/25 + 1/757 + 1/763 309 + … (25 digits)5

Uitgewerkt met onze eigen calculator

Calculator Egyptische breuken

Gegeven

Teller
3
Noemer
4

Resultaat

Aantal termen
2

Deze cijfers komen uit de calculator hieronder, ze zijn niet met de hand ingetypt — ze worden opnieuw berekend telkens als de tool verandert.

Reken het door met je eigen cijfers →
Advertentie

Veelgestelde vragen

Why does the last denominator appear in scientific notation?
Because it has outgrown the range in which a browser counts exactly. Integers stay exact up to about sixteen digits; past that the value is stored as a floating-point approximation and displayed with an exponent. The 25-digit denominator in the 5/121 decomposition is therefore shown rounded, not because the mathematics is uncertain but because the display format has run out of room. Treat any term printed with an exponent as an order of magnitude rather than a figure to copy down — and take it as the signal that the greedy path has gone somewhere impractical.
Can every fraction be written this way?
Yes, and the greedy method is itself the proof. At each step the remainder's numerator strictly decreases while staying positive, so after finitely many steps it reaches zero and the process halts with a valid decomposition. What remains open is the opposite question — how few terms are always enough. A conjecture from 1948 says three terms suffice for every fraction of the form four-over-something, and it has been verified far beyond any practical range without being proved. So the existence question was settled by an algorithm anyone can run by hand, while the efficiency question has held out for three-quarters of a century.

Artikelen die je misschien interesseren

Alle gidsen →

Vergelijkbare tools

Bronnen

Een fout in dit artikel gezien?