The Universe of Discourse

Egyptian Fractions
The Ahmes papyrus is one of the very oldest extant mathematical documents. It was written around 3800 years ago. As I mentioned recently, a large part of it is a table of the values of fractions of the form 2/n for odd integers n. The Egyptians, at least at that time, did not have a generalized fraction notation. They would write fractions of the form 1/n, and they could write sums of these. But convention dictated that they could not use the same unit fraction more than once. So to express 3/5 they would have needed to write something like 1/2 + 1/10, which from now on I will abbreviate as [2, 10]. (They also had a special notation for 2/3, but I will ignore that for a while.) Expressing arbitrary fractions in this form can be done, but it is non-trivial.

A simple algorithm for calculating this so-called "Egyptian fraction representation" is the greedy algorithm: To represent n/d, find the largest unit fraction 1/a that is less than n/d. Calculate a representation for n/d - 1/a, and append 1/a. This always works, but it doesn't always work well. For example, let's use the greedy algorithm to find a representation for 2/9. The largest unit fraction less than 2/9 is 1/5, and 2/9 - 1/5 = 1/45, so we get 2/9 = 1/5 + 1/45 = [5, 45]. But it also happens that 2/9 = [6, 18], which is much more convenient to calculate with because the numbers are smaller. Similarly, for 19/20 the greedy algorithm produces 19/20 = [2] + 9/20 = [2, 3] + 7/60 = [2, 3, 9, 180]. But even 7/60 can be more simply written than as [9, 180]; it's also [10, 60], [12, 30], and, best of all, [15, 20].

So similarly, for 3/7 this time, the greedy methods gives us 3/7 = 1/3 + 2/21, and that 2/21 can be expanded by the greedy method as [11, 231], so 3/7 = [3, 11, 231]. But even 2/21 has better expansions: it's also [12, 84], [14, 42], and, best of all, [15, 35], so 3/7 = [3, 15, 35]. But better than all of these is 3/7 = [4, 7, 28], which is optimal.

Anyway, while I was tinkering with all this, I got an answer to a question I had been wondering about for years, which is: why did Ahmes come up with a table of representations of fractions of the form 2/n, rather than the representations of all possible quotients? Was there a table somewhere else, now lost, of representations of fractions of the form 3/n?

The answer, I think, is "probably not"; here's why I think so.

Suppose you want 3/7. But 3/7 = 2/7 + 1/7. You look up 2/7 in the table and find that 2/7 = [4, 28]. So 3/7 = [4, 7, 28]. Done.

OK, suppose you want 4/7. You look up 2/7 in the table and find that 2/7 = [4, 28]. So 4/7 = [4, 4, 28, 28] = [2, 14]. Done.

Similarly, 5/7 = [2, 7, 14]. Done.

To calculate 6/7, you first calculate 3/7, which is [4, 7, 28]. Then you double 3/7, and get 6/7 = 1/2 + 2/7 + 1/14. Now you look up 2/7 in the table and get 2/7 = [4, 28], so 6/7 = [2, 4, 14, 28]. Whether this is optimal or not is open to argument. It's longer than [2, 3, 42], but on the other hand the denominators are smaller.

Anyway, the table of 2/n is all you need to produce Egyptian representations of arbitrary rational numbers. The algorithm in general is:

• To sum up two Egyptian fractions, just concatenate their representations. There may now be unit fractions that appear twice, which is illegal. If a pair of such fractions have an even denominator, they can be eliminated using the rule that 1/2n + 1/2n = 1/n. Otherwise, the denominator is odd, and you can look the numbers up in the 2/n table and replace the matched pair with the result from the table lookup. Repeat until no pairs remain.

• To double an Egyptian fraction, add it to itself as per the previous.

• To calculate a/b, when a = 2k, first calculate k/b and then double it as per the previous.

• To calculate a/b when a is odd, first calculate (a-1)/b as per the previous; then add 1/b.

• 19/20 = 18/20 + 1/20
• 19/20 = 9/10 + 1/20
  • 9/10 = 8/10 + 1/10
  • 9/10 = 4/5 + 1/10
    • 4/5 = 2/5 + 2/5
      • 2/5 = [3, 15] (from the table)
    • 4/5 = [3, 3, 15, 15]
    • 4/5 = 2/3 + 2/15
      • 2/3 = [2, 6] (from the table)
      • 2/15 = [12, 20] (from the table)
    • 4/5 = [2, 6, 12, 20]
  • 9/10 = [2, 6, 10, 12, 20]
• 19/20 = [2, 6, 10, 12, 20, 20]
• 19/20 = [2, 6, 10, 10, 12]
• 19/20 = [2, 5, 6, 12]

An alternative algorithm is to expand the numerator as a sum of powers of 2, which the Egyptians certainly knew how to do. For 19/20 this gives us 19/20 = 16/20 + 2/20 + 1/20 = 4/5 + [10, 20]. Now we need to figure out 4/5, which we do as above, getting 4/5 = [2, 6, 12, 20], or 4/5 = 2/3 + [12, 20] if we are Egyptian, or 4/5 = [2, 4, 20] if we are clever. Supposing we are neither, we have 19/20 = [2, 6, 12, 20, 10, 20] = [2, 6, 12, 10, 10] = [2, 6, 12, 5] as before.

(It is not clear to me, by the way, that either of these algorithms is guaranteed to terminate. I need to think about it some more.)

Getting the table of good-quality representations of 2/n is not trivial, and requires searching, number theory, and some trial and error. It's not at all clear that 2/105 = [90, 126].

Once you have the table of 2/n, however, you can grind out the answer to any division problem. This might be time-consuming, but it's nevertheless trivial. So Ahmes needed a table of 2/n, but once he had it, he didn't need any other tables.

[Other articles in category /math] permanent link