Egyptian fraction

An Egyptian fraction is the sum of distinct unit fractions, such as ${\frac {1}{2}}+{\frac {1}{3}}$. That is, each fraction in the sum has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from each other. It can be shown that every positive rational number, a/b, can be written in the form of an Egyptian fraction. This type of sum was used as a serious notation for fractions by the ancient Egyptians, continuing into medieval times. In modern mathematical notation, Egyptian fractions have been replaced by vulgar fractions and decimal notation. However, Egyptian fractions continue to be an object of study in modern number theory and recreational mathematics, as well as in modern historical studies of ancient mathematics.

In this article we summarize what is known about Egyptian fractions both ancient and modern. For details of the subjects discussed here, see the linked articles.

Ancient Egypt

For more information on this subject, see Egyptian numerals and Egyptian mathematics.

One of the first known uses of Egyptian fractions comes from the Rhind Mathematical Papyrus. Three older texts are the Egyptian Mathematical Leather Roll, the Moscow Mathematical Text, and the Akhmim Wooden Tablet. The Rhind papyrus was written by Ahmes and other Egyptian scribes and dates from the Second Intermediate Period. It includes a table of Egyptian fraction expansions for 101 fractions of the form 2/n as well as 84 Egyptian fraction based math problems and solutions. The Egyptians left few formal description of the methods they used to obtain the solutions on this papyrus, so what little we know about ancient methods for calculating with Egyptian fractions is based on extrapolation from the patterns observed in one papyrus, and finding a related method in another papyrus.

The Egyptians placed the hieroglyph

(er, "[one] among" or possibly re, mouth) above a number to represent a unit fraction. For example:

$={\frac {1}{3}}$

$={\frac {1}{10}}$

They also had special symbols for 1/2, 2/3, and 3/4:

$={\frac {1}{2}}$

$={\frac {2}{3}}$

$={\frac {3}{4}}$

The Egyptians used an alternative notation based on the parts of the Eye of Horus to denote a special set of fractions of the form 1/2^k (for k = 1, 2, ..., 6), that is, dyadic rational numbers. These fractions were used to divide a hekat, the primary ancient Egyptian volume measure for grain. They were also used for such grain products as bread and beer. If any remainder was left after using Eye of Horus fractions of a hekat to express a quantity, the remainder was written using the regular Egyptian fraction notation as multiples of a ro, a unit equal to 1/320 of a hekat.

The problems in the Rhind papyrus used a symbol for an unknown quantity much as in modern-day algebra. A typical problem from the RMP is:

Problem 24: A quantity and its ¹/₇ added together become 19. What is the quantity?

The answer listed for this problem is

16 + 1/2 + 1/8.

Using modern notation for algebra and fractions the solution can be obtained by the sequence of steps x + 1/7x = 19; (8/7)x = 19; x = 133/8; and x = 16 + 5/8, which equals 16 + 1/2 + 1/8; the Egyptians likely performed a similar sequence of steps in their own notation.

Medieval mathematics

For more information on this subject, see Greedy algorithm for Egyptian fractions and Engel expansion.

Egyptian fraction notation continued to be used into Greek times and even the middle ages (Struik 1967) despite complaints as early as Ptolemy's Almagest about the clumsiness of this notation compared to alternatives such as the Babylonian base-60 notation.

The Liber Abaci (1202) of Leonardo of Pisa (Fibonacci) contains several section on mathematics related to Egyptian fractions. Best known of these is a greedy algorithm for computing Egyptian fractions, by repeatedly choosing the unit fraction with the smallest denominator that is no larger than the remaining fraction to be expanded: that is, in more modern notation, we replace a fraction x//y by the expansion

${\frac {x}{y}}={\frac {1}{\lceil y/x\rceil }}+{\frac {-y\,{\bmod {\,}}x}{y\lceil y/x\rceil }}.$

As each such expansion reduces the numerator of the remaining fraction to be expanded, this method always terminates with a finite expansion; however, compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators. For instance, this method expands

${\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763309}}+{\frac {1}{873960180913}}+{\frac {1}{1527612795642093418846225}},$

while other methods lead to the much better expansion

${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.$

Sylvester's sequence 2, 3, 7, 43, 1807, ... can be viewed as generated by an infinite greedy expansion of this type for the number one, where at each step we choose the denominator $\lfloor y/x\rfloor +1$ instead of $\lceil y/x\rceil$, and sometimes Fibonacci's greedy algorithm is attributed to Sylvester.

In the Liber Abaci, Fibonacci also wrote about an ascending form of a continued fraction,

$x={\frac {\displaystyle 1+{\frac {\displaystyle 1+{\frac {\displaystyle 1+\cdots }{\displaystyle a_{3}}}}{\displaystyle a_{2}}}}{\displaystyle a_{1}}},$

which can be rewritten as a kind of Egyptian fraction, sometimes called an Egyptian product:

$x={\frac {1}{a_{1}}}+{\frac {1}{a_{1}a_{2}}}+{\frac {1}{a_{1}a_{2}a_{3}}}+\cdots .$

An expansion of this form in which the integers a_i are nondecreasing is called an Engel expansion. Every rational number has a finite Engel expansion, while irrational numbers have an infinite Engel expansion.

Modern number theory

For more information on this subject, see Erdős–Graham conjecture and Znám's problem.

Modern number theorists have studied many different problems related to Egyptian fractions, including problems of bounding the length or maximum denominator in Egyptian fraction representations, finding expansions of certain special forms or in which the denominators are all of some special type, the termination of various methods for Egyptian fraction expansion, and showing that expansions exist for any sufficiently dense set of sufficiently smooth numbers.

• The Erdős–Graham conjecture in combinatorial number theory states that, if the unit fractions are partitioned into finitely many subsets, then one of the subsets can be used to form an Egyptian fraction representation of one. That is, for every r > 0, and every r-coloring of the integers greater than one, there is a finite monochromatic subset S of these integers such that

$\sum _{n\in S}1/n=1.$

The conjecture was proven in 2003 by Ernest S. Croot, III.

• Znám's problem is closely related to the existence of Egyptian fractions of the form

$\sum {\frac {1}{x_{i}}}+\prod {\frac {1}{x_{i}}}=1.$

• Egyptian fractions are normally defined as requiring all denominators to be distinct, but this requirement can be relaxed to allow repeated denominators. However, this relaxed form of Egyptian fractions does not allow for any number to be represented using fewer fractions, as any expansion with repeated fractions can be converted to an Egyptian fraction of equal or smaller length by repeated application of the replacement

${\frac {1}{k}}+{\frac {1}{k}}={\frac {2}{k+1}}+{\frac {2}{k(k+1)}}$

if k is odd, or simply by replacing 1/k+1/k by 2/k if k is even. This result was first proven by Takenouchi (1921).

• Graham and Jewett (Wagon 1991) and Beeckmans (1993) proved that it is similarly possible to convert expansions with repeated denominators to (longer) Egyptian fractions, via the replacement

${\frac {1}{k}}+{\frac {1}{k}}={\frac {1}{k}}+{\frac {1}{k+1}}+{\frac {1}{k(k+1)}}.$

This method can lead to long expansions with large denominators, such as

${\frac {4}{5}}={\frac {1}{5}}+{\frac {1}{6}}+{\frac {1}{7}}+{\frac {1}{8}}+{\frac {1}{30}}+{\frac {1}{31}}+{\frac {1}{32}}+{\frac {1}{42}}+{\frac {1}{43}}+{\frac {1}{56}}+{\frac {1}{930}}+{\frac {1}{931}}+{\frac {1}{992}}+{\frac {1}{1806}}+{\frac {1}{865830}}.$

Botts (1967) had originally used this replacement technique to show that any rational number has Egyptian fraction representations with arbitrarily large minimum denominators.

• Any fraction x/y has an Egyptian fraction representation in which the maximum denominator is bounded by

$O({\frac {y\log y}{\log \log y}})$

(Tenenbaum and Yokota 1990) and a representation with at most

$O({\sqrt {\log y}})$

terms (Vose 1985).

• Graham (1964) characterized the numbers that can be represented by Egyptian fractions in which all denominators are nth powers. In particular, a rational number q can be represented as an Egyptian fraction with square denominators if and only if q lies in one of the two half-open intervals

$[0,{\frac {\pi ^{2}}{6}}-1)\cup [1,{\frac {\pi ^{2}}{6}}).$

• Martin (1999) showed that any rational number has very dense expansions, using a constant fraction of the denominators up to N for any sufficiently large N.

Open problems

For more information on this subject, see Odd greedy Egyptian fractions and Erdős–Straus conjecture.

Some notable problems remain unsolved with regard to Egyptian fractions, despite considerable effort by mathematicians.

• The Erdős–Straus conjecture concerns the length of the shortest expansion for a fraction of the form 4/n. Does an expansion

${\frac {4}{n}}={\frac {1}{x}}+{\frac {1}{y}}+{\frac {1}{z}}$

exist for every n? It is known to be true for all n < 10¹⁴, and for all but a vanishingly small fraction of possible values of n, but the general truth of the conjecture remains unknown.

• The existence of odd greedy Egyptian fractions for all fractions with odd denominators. If we modify Fibonacci's greedy method so that it always chooses the smallest possible odd denominator, under what conditions does this modified algorithm produce a finite expansion? An obvious necessary condition is that the starting fraction x/y have an odd denominator y, and it is conjectured but not known that this is also a sufficient condition. It is known (Breusch 1954; Stewart 1954) that every x/y with odd y has an expansion into distinct odd unit fractions, constructed using a different method than the greedy algorithm.

• It is possible to use brute-force search algorithms to find the Egyptian fraction representation of a given number with the fewest possible terms (Stewart 1992) or minimizing the largest denominator; however, such algorithms can be quite inefficient. The existence of polynomial time algorithms for these problems, or more generally the computational complexity of such problems, remains unknown.

Bibliography

• Beeckmans, L. (1993). "The splitting algorithm for Egyptian fractions". Journal of Number Theory. 43: 173–­185. {{cite journal}}: soft hyphen character in |pages= at position 5 (help)

• Botts, Truman (1967). "A chain reaction process in number theory". Mathematics Magazine: 55–65.

• Breusch, R. (1954). "A special case of Egyptian fractions, solution to advanced problem 4512". American Mathematical Monthly. 61: 200–­201. {{cite journal}}: soft hyphen character in |pages= at position 5 (help)

• Gillings, Richard J. (1982). Mathematics in the Time of the Pharaohs. Dover. ISBN 0-486-24315-X.

• Graham, R. L. (1964). "On finite sums of reciprocals of distinct nth powers". Pacific Journal of Mathematics. 14 (1): 85–92.

• Martin, G. (1999). "Dense Egyptian fractions". Transactions of the American Mathematical Society. 351: 3641–3657.

• Menninger, Karl W. (1969). Number Words and Number Symbols: A Cultural History of Numbers. MIT Press. ISBN 0-262-13040-8.

• Stewart, B. M. (1954). "Sums of distinct divisors". American Journal of Mathematics. 76: 779–­785. {{cite journal}}: soft hyphen character in |pages= at position 5 (help)

• Stewart, I. (1992). "The riddle of the vanishing camel". Scientific American (June): 122–­124. {{cite journal}}: soft hyphen character in |pages= at position 5 (help)

• Struik, Dirk J. (1967). A Concise History of Mathematics. Dover. pp. 20–25. ISBN 0-486-60255-9.

• Takenouchi, T. (1921). "On an indeterminate equation". Proc. Physico-Mathematical Soc. of Japan, 3rd ser. 3: 78–92.

• Tenenbaum, G.; Yokota, H. (1990). "Length and denominators of Egyptian fractions". Journal of Number Theory. 35: 150–­156. {{cite journal}}: soft hyphen character in |pages= at position 5 (help)CS1 maint: multiple names: authors list (link)

• Vose, M. (1985). "Egyptian fractions". Bulletin of the London Mathematical Society. 17: 21.

• Wagon, S. (1991). Mathematica in Action. W.H. Freeman. pp. 271–­277. {{cite book}}: soft hyphen character in |pages= at position 5 (help)

External links

• Eppstein, David. "Egyptian Fractions".

• Knott, R. "Egyptian fractions".

• O'Connor, J. J.; Robertson, E. F. (2000). "Mathematics in Egyptian Papyri".{{cite web}}: CS1 maint: multiple names: authors list (link)

• Weisstein, Eric W. "Egyptian Fraction". MathWorld–A Wolfram Web Resource.