The Universe of Discourse | |||||||||||||||||||||||||||||||||||||||||||||
12 recent entries Archive:
Comments disabled |
Thu, 11 May 2006
Egyptian Fractions
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:
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 |
||||||||||||||||||||||||||||||||||||||||||||