Computer Algebra Meets an Ancient Egyptian Problem

Yiu-Kwong Man
Department of Mathematics, Science, Social Science and Technology
The Hong Kong Institute of Education
10 Lo Ping Road, Tai Po
New Territories, Hong Kong, PRC

Abstract. The problem of decomposing a given rational number into a sum of distinct unit fractions (i.e. fractions with unit numerators) originated in Egypt. The ancient Egyptians might have known that 2/(2n+1) is equal to 1/(n+1) + 1/[(n+1)(2n+1)], where n is a natural number. Using this identity, one can rediscover most of the results found in the famous Rhind papyrus, which was written in Greek around 500 ~ 800 A.D. However, there is no evidence that the Egyptians might have known a general approach for decomposing fractions with numerators larger than two. The major breakthrough was made by Fibonacci in 1202, when he discovered a method for decomposing arbitrary fractions into sums of distinct unit fractions. His method is called the Greedy algorithm or the Fibonacci Algorithm nowadays. It is quite a simple approach, which uses division(s) only. In 1962, Golomb proposed another method for computing unit fraction expansions, based on the Bezout identity and the Euclidean algorithm. Although it is also simple to use, the maximal denominators obtained in the expansions could be terribly huge. In fact, this defect also exists in the Greedy algorithm. During the teaching of a course on history of mathematics and introduction of such an ancient problem in class in the past few years, we observed that the students found it both stimulating and interesting in learning various strategies in computing a unit fraction expansion for a given fraction, using Maple as a computational aids.

In this paper, we describe how to implement the original Greedy algorithm and the Golomb algorithm in Maple and the examples discussed in our history of mathematics class. In addition, we also discuss how to design and implement the improved version of the Greedy algorithm and the Golomb algorithm for computing unit fraction expansions, respectively. These improved algorithms have the advantage that the maximal denominators involved in the expansions will not exceed those computed by the original algorithms. Some new theoretical results obtained will also be included.