Egyptian Fractions and the Greedy Algorithm

Sums of unit fractions

A unit fraction is a fraction with 1 as its numerator, such as $\frac{1}{2}$1/2, $\frac{1}{3}$1/3 or $\frac{1}{12}$1/12. Scribes in ancient Egypt wrote fractions as sums of different unit fractions. In that notation, $\frac{7}{12}$7/12 is written $\frac{1}{2}+\frac{1}{12}$1/2 + 1/12.

The unit fractions in the sum must all be different. $\frac{7}{12}$7/12 is also $\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{1}{12}+\frac{1}{12}$1/12 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12 + 1/12, but that repeats $\frac{1}{12}$1/12, so it is not allowed. A sum of different unit fractions is called an Egyptian fraction.

7 twelfths are shaded in the top bar. A half is 6 twelfths, and 1 twelfth more makes 7: $\frac{7}{12}=\frac{1}{2}+\frac{1}{12}$7/12 = 1/2 + 1/12.

Take the biggest unit fraction that fits

The greedy method finds an Egyptian fraction for any fraction between 0 and 1. Take the biggest unit fraction that fits, meaning the biggest one that is not more than the fraction. Subtract it. Then do the same to what is left, written in lowest terms, and stop when what is left is a unit fraction.

To find the biggest unit fraction that fits inside $\frac{a}{b}$a/b, divide b by a and, if the answer is not a whole number, round it up. This works because $\frac{1}{n}$1/n fits exactly when $b\le a\times n$b ≤ a × n, which means n is at least $b/a$b / a, and the smallest such n gives the biggest unit fraction. For $\frac{7}{12}$7/12, 12 ÷ 7 = 1.7…, which rounds up to 2, so the biggest unit fraction that fits is $\frac{1}{2}$1/2. Subtract it: $\frac{7}{12}-\frac{1}{2}=\frac{7}{12}-\frac{6}{12}=\frac{1}{12}$7/12 − 1/2 = 7/12 − 6/12 = 1/12. That is a unit fraction, so the method stops: $\frac{7}{12}=\frac{1}{2}+\frac{1}{12}$7/12 = 1/2 + 1/12.

Now $\frac{5}{7}$5/7. 7 ÷ 5 = 1.4, which rounds up to 2, so take $\frac{1}{2}$1/2. $\frac{5}{7}-\frac{1}{2}=\frac{10}{14}-\frac{7}{14}=\frac{3}{14}$5/7 − 1/2 = 10/14 − 7/14 = 3/14. Next, 14 ÷ 3 = 4.6…, which rounds up to 5, so take $\frac{1}{5}$1/5. $\frac{3}{14}-\frac{1}{5}=\frac{15}{70}-\frac{14}{70}=\frac{1}{70}$3/14 − 1/5 = 15/70 − 14/70 = 1/70, a unit fraction. So $\frac{5}{7}=\frac{1}{2}+\frac{1}{5}+\frac{1}{70}$5/7 = 1/2 + 1/5 + 1/70.

The bar is one whole, and the line marks $\frac{5}{7}$5/7. Take one greedy step at a time: $\frac{1}{2}$1/2, then $\frac{1}{5}$1/5, then $\frac{1}{70}$1/70. The numerator of what is left goes 5, 3, 1. Choose $\frac{4}{13}$4/13 and its numerator goes 4, 3, 1.

Why the method always stops

In $\frac{5}{7}$5/7, the numerator of what was left went 5, then 3, then 1. It gets smaller at every step, for every fraction. Here is why.

Say what is left is $\frac{a}{b}$a/b, and the biggest unit fraction that fits is $\frac{1}{n}$1/n. The next unit fraction up, $\frac{1}{\left(n-1\right)}$1/(n − 1), did not fit, so it is more than $\frac{a}{b}$a/b, and b is more than a × (n − 1). Now subtract: $\frac{a}{b}-\frac{1}{n}=\frac{\left(\text{an}-b\right)}{\left(\text{bn}\right)}$a/b − 1/n = (an − b)/(bn). The new numerator is an − b = a − (b − a × (n − 1)). The bracket is at least 1, so the new numerator is less than a. It is not 0 either: that would make $\frac{a}{b}$a/b exactly $\frac{1}{n}$1/n, a unit fraction, and the method would already have stopped.

For $\frac{5}{7}$5/7, n = 2: the new numerator is 5 − (7 − 5 × 1) = 5 − 2 = 3, as found above. Canceling down afterward can only make the numerator smaller still.

A numerator is a whole number, and a whole number cannot get smaller forever. Starting from a, it reaches 1 after at most a − 1 steps. A numerator of 1 means that what is left is a unit fraction, and the method stops.

No unit fraction is used twice

What is left after taking $\frac{1}{n}$1/n is less than $\frac{1}{n}$1/n, so the next unit fraction taken is smaller than $\frac{1}{n}$1/n. The reason: $\frac{a}{b}$a/b is less than $\frac{1}{\left(n-1\right)}$1/(n − 1), and $\frac{1}{\left(n-1\right)}$1/(n − 1) is at most $\frac{2}{n}$2/n, because 2(n − 1) is at least n whenever n is 2 or more. So $\frac{a}{b}-\frac{1}{n}$a/b − 1/n is less than $\frac{2}{n}-\frac{1}{n}=\frac{1}{n}$2/n − 1/n = 1/n. Each unit fraction is smaller than the one before, so they are all different.

After $\frac{1}{2}$1/2, what is left of $\frac{5}{7}$5/7 is $\frac{3}{14}$3/14, less than $\frac{1}{2}$1/2. After $\frac{1}{5}$1/5, what is left is $\frac{1}{70}$1/70, less than $\frac{1}{5}$1/5.

Canceling down along the way

Take $\frac{4}{13}$4/13. 13 ÷ 4 = 3.25 rounds up to 4, and $\frac{4}{13}-\frac{1}{4}=\frac{\left(16-13\right)}{52}=\frac{3}{52}$4/13 − 1/4 = (16 − 13)/52 = 3/52. Next, 52 ÷ 3 = 17.3… rounds up to 18, and $\frac{3}{52}-\frac{1}{18}=\frac{\left(54-52\right)}{936}=\frac{2}{936}$3/52 − 1/18 = (54 − 52)/936 = 2/936, which cancels down to $\frac{1}{468}$1/468. So $\frac{4}{13}=\frac{1}{4}+\frac{1}{18}+\frac{1}{468}$4/13 = 1/4 + 1/18 + 1/468, and the numerators went 4, 3, 1.

Greedy is not always shortest

The greedy method always finishes, but it does not always find the shortest sum or the smallest denominators. For $\frac{5}{121}$5/121 it needs five unit fractions, and the third is already $\frac{1}{763}$1/763,309. A shorter answer exists: $\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}$5/121 = 1/33 + 1/121 + 1/363. Check it over the common denominator 363: $\frac{11}{363}+\frac{3}{363}+\frac{1}{363}=\frac{15}{363}=\frac{5}{121}$11/363 + 3/363 + 1/363 = 15/363 = 5/121.

The usual mistakes

Repeating a unit fraction. $\frac{5}{8}=\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}$5/8 = 1/8 + 1/8 + 1/8 + 1/8 + 1/8 is true, but it is not an Egyptian fraction. The greedy method gives $\frac{5}{8}=\frac{1}{2}+\frac{1}{8}$5/8 = 1/2 + 1/8.

Not taking the biggest unit fraction that fits. For $\frac{11}{12}$11/12, $\frac{1}{3}$1/3 fits, but so does $\frac{1}{2}$1/2, which is bigger. Greedy takes $\frac{1}{2}$1/2.

Taking a unit fraction that is too big. For $\frac{3}{10}$3/10, $\frac{1}{2}$1/2 is more than $\frac{3}{10}$3/10, so it does not fit. 10 ÷ 3 = 3.3… rounds up to 4, and $\frac{1}{4}$1/4 is the biggest that fits.