An Egyptian fraction is a finite sum of distinct unit fractions, such as
Beyond their historical use, Egyptian fractions have some practical advantages over other representations of fractional numbers. For instance, Egyptian fractions can help in dividing food or other objects into equal shares. For example, if one wants to divide 5 pizzas equally among 8 diners, the Egyptian fraction
Similarly, although one could divide 13 pizzas among 12 diners by giving each diner one pizza and splitting the remaining pizza into 12 parts (perhaps destroying it), one could note that
Egyptian fractions can provide a solution to rope-burning puzzles, in which a given duration is to be measured by igniting non-uniform ropes which burn out after a unit time. Any rational fraction of a unit of time can be measured by expanding the fraction into a sum of unit fractions and then, for each unit fraction , burning a rope so that it always has simultaneously lit points where it is burning. For this application, it is not necessary for the unit fractions to be distinct from each other. However, this solution may need an infinite number of re-lighting steps.
Egyptian fraction notation was developed in the Middle Kingdom of Egypt. Five early texts in which Egyptian fractions appear were the Egyptian Mathematical Leather Roll, the Moscow Mathematical Papyrus, the Reisner Papyrus, the Kahun Papyrus and the Akhmim Wooden Tablet. A later text, the Rhind Mathematical Papyrus, introduced improved ways of writing Egyptian fractions. The Rhind papyrus was written by Ahmes and dates from the Second Intermediate Period; it includes a table of Egyptian fraction expansions for rational numbers , as well as 84 word problems. Solutions to each problem were written out in scribal shorthand, with the final answers of all 84 problems being expressed in Egyptian fraction notation. Tables of expansions for similar to the one on the Rhind papyrus also appear on some of the other texts. However, as the Kahun Papyrus shows, vulgar fractions were also used by scribes within their calculations.
To write the unit fractions used in their Egyptian fraction notation, in hieroglyph script, the Egyptians placed the hieroglyph
(er, "[one] among" or possibly re, mouth) above a number to represent the reciprocal of that number. Similarly in hieratic script they drew a line over the letter representing the number. For example:
The Egyptians had special symbols for , , and that were used to reduce the size of numbers greater than when such numbers were converted to an Egyptian fraction series. The remaining number after subtracting one of these special fractions was written as a sum of distinct unit fractions according to the usual Egyptian fraction notation.
The Egyptians also used an alternative notation modified from the Old Kingdom to denote a special set of fractions of the form (for ) and sums of these numbers, which are necessarily dyadic rational numbers. These have been called "Horus-Eye fractions" after a theory (now discredited) that they were based on the parts of the Eye of Horus symbol. They were used in the Middle Kingdom in conjunction with the later notation for Egyptian fractions to subdivide a hekat, the primary ancient Egyptian volume measure for grain, bread, and other small quantities of volume, as described in the Akhmim Wooden Tablet. If any remainder was left after expressing a quantity in Eye of Horus fractions of a hekat, the remainder was written using the usual Egyptian fraction notation as multiples of a ro, a unit equal to of a hekat.
Modern historians of mathematics have studied the Rhind papyrus and other ancient sources in an attempt to discover the methods the Egyptians used in calculating with Egyptian fractions. In particular, study in this area has concentrated on understanding the tables of expansions for numbers of the form in the Rhind papyrus. Although these expansions can generally be described as algebraic identities, the methods used by the Egyptians may not correspond directly to these identities. Additionally, the expansions in the table do not match any single identity; rather, different identities match the expansions for prime and for composite denominators, and more than one identity fits the numbers of each type:
- For small odd prime denominators , the expansion
- For larger prime denominators, an expansion of the form
- For some composite denominators, factored as , the expansion for has the form of an expansion for with each denominator multiplied by . This method appears to have been used for many of the composite numbers in the Rhind papyrus, but there are exceptions, notably , , and .
- One can also expand
- The final (prime) expansion in the Rhind papyrus, , does not fit any of these forms, but instead uses an expansion
Egyptian fraction notation continued to be used in Greek times and into the Middle Ages, despite complaints as early as Ptolemy's Almagest about the clumsiness of the notation compared to alternatives such as the Babylonian base-60 notation. Related problems of decomposition into unit fractions were also studied in 9th-century India by Jain mathematician Mahāvīra. An important text of medieval European mathematics, the Liber Abaci (1202) of Leonardo of Pisa (more commonly known as Fibonacci), provides some insight into the uses of Egyptian fractions in the Middle Ages, and introduces topics that continue to be important in modern mathematical study of these series.
The primary subject of the Liber Abaci is calculations involving decimal and vulgar fraction notation, which eventually replaced Egyptian fractions. Fibonacci himself used a complex notation for fractions involving a combination of a mixed radix notation with sums of fractions. Many of the calculations throughout Fibonacci's book involve numbers represented as Egyptian fractions, and one section of this book provides a list of methods for conversion of vulgar fractions to Egyptian fractions. If the number is not already a unit fraction, the first method in this list is to attempt to split the numerator into a sum of divisors of the denominator; this is possible whenever the denominator is a practical number, and Liber Abaci includes tables of expansions of this type for the practical numbers 6, 8, 12, 20, 24, 60, and 100.
The next several methods involve algebraic identities such as
In the rare case that these other methods all fail, Fibonacci suggests a "greedy" algorithm for computing Egyptian fractions, in which one repeatedly chooses 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
Fibonacci suggests switching to another method after the first such expansion, but he also gives examples in which this greedy expansion was iterated until a complete Egyptian fraction expansion was constructed: 4/13 = 1/4 + 1/18 + 1/468 and 17/29 = 1/2 + 1/12 + 1/348.
Compared to ancient Egyptian expansions or to more modern methods, this method may produce expansions that are quite long, with large denominators, and Fibonacci himself noted the awkwardness of the expansions produced by this method. For instance, the greedy method expands
Sylvester's sequence 2, 3, 7, 43, 1807, ... can be viewed as generated by an infinite greedy expansion of this type for the number 1, where at each step we choose the denominator ⌊ y/x ⌋ + 1 instead of ⌈ y/x ⌉, and sometimes Fibonacci's greedy algorithm is attributed to James Joseph Sylvester.
After his description of the greedy algorithm, Fibonacci suggests yet another method, expanding a fraction a/b by searching for a number c having many divisors, with b/2 < c < b, replacing a/b by ac/bc, and expanding ac as a sum of divisors of bc, similar to the method proposed by Hultsch and Bruins to explain some of the expansions in the Rhind papyrus.
Modern number theoryEdit
Although Egyptian fractions are no longer used in most practical applications of mathematics, modern number theorists have continued to study many different problems related to them. These include 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.
- One of the earliest publications of Paul Erdős proved that it is not possible for a harmonic progression to form an Egyptian fraction representation of an integer. The reason is that, necessarily, at least one denominator of the progression will be divisible by a prime number that does not divide any other denominator. The latest publication of Erdős, nearly 20 years after his death, proves that every integer has a representation in which all denominators are products of three primes.
- The Erdős–Graham conjecture in combinatorial number theory states that, if the integers greater than 1 are partitioned into finitely many subsets, then one of the subsets has a finite subset of itself whose reciprocals sum to 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
- Znám's problem and primary pseudoperfect numbers are closely related to the existence of Egyptian fractions of the form
- 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
- Graham and Jewett proved that it is similarly possible to convert expansions with repeated denominators to (longer) Egyptian fractions, via the replacement
- Any fraction x/y has an Egyptian fraction representation in which the maximum denominator is bounded by
- 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
- 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.
- Engel expansion, sometimes called an Egyptian product, is a form of Egyptian fraction expansion in which each denominator is a multiple of the previous one:
- Anshel & Goldfeld (1991) study numbers that have multiple distinct Egyptian fraction representations with the same number of terms and the same product of denominators; for instance, one of the examples they supply is
- The number of different n-term Egyptian fraction representations of the number one is bounded above and below by double exponential functions of n.
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
- It is unknown whether an odd greedy expansion exists for every fraction with an odd denominator. If Fibonacci's greedy method is modified 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 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 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.
Guy (2004) describes these problems in more detail and lists numerous additional open problems.
- ^ Dick & Ogle (2018); , Koshaleva & Kreinovich (2021)
- ^ Winkler (2004).
- ^ Ritter (2002). See also Katz (2007) and Robson & Stedall (2009).
- ^ Hultsch (1895); Bruins (1957)
- ^ Gillings (1982); Gardner (2002)
- ^ Knorr (1982).
- ^ Eves (1953).
- ^ Struik (1967).
- ^ Kusuba (2004).
- ^ Sigler (2002), chapter II.7
- ^ Erdős (1932); Graham (2013)
- ^ Butler, Erdős & Graham (2015).
- ^ See Wagon (1999) and Beeckmans (1993)
- ^ Yokota (1988).
- ^ Vose (1985).
- ^ a b Erdős (1950).
- ^ Tenenbaum & Yokota (1990).
- ^ Konyagin (2014).
- ^ Breusch (1954); Stewart (1954)
- ^ Stewart (1992).
- Anshel, Michael M.; Goldfeld, Dorian (1991), "Partitions, Egyptian fractions, and free products of finite abelian groups", Proceedings of the American Mathematical Society, 111 (4): 889–899, doi:10.1090/S0002-9939-1991-1065083-1, MR 1065083
- Beeckmans, L. (1993), "The splitting algorithm for Egyptian fractions", Journal of Number Theory, 43 (2): 173–185, doi:10.1006/jnth.1993.1015, MR 1207497
- Botts, Truman (1967), "A chain reaction process in number theory", Mathematics Magazine, 40 (2): 55–65, doi:10.2307/2688508, JSTOR 2688508, MR 0209217
- Breusch, R. (1954), "A special case of Egyptian fractions, solution to advanced problem 4512", American Mathematical Monthly, 61: 200–201, doi:10.2307/2307234, JSTOR 2307234
- Bruins, Evert M. (1957), "Platon et la table égyptienne 2/n" [Plato and the Egyptian 2/n table], Janus (in French), 46: 253–263
- Butler, Steve; Erdős, Paul; Graham, Ron (2015), "Egyptian fractions with each denominator having three distinct prime divisors" (PDF), Integers, 15: Paper No. A51, 9, MR 3437526
- Dick, Lara K.; Ogle, Rebecca (September 2018), "Think like an Egyptian", Ohio Journal of School Mathematics, 80: 1–7
- Erdős, P. (1932), "Egy Kürschák-féle elemi számelméleti tétel általánosítása" [Generalization of an elementary number-theoretic theorem of Kürschák] (PDF), Mat. Fiz. Lapok (in Hungarian), 39: 17–24
- Erdős, Pál (1950), "Az egyenlet egész számú megoldásairól" [On a Diophantine equation] (PDF), Matematikai Lapok (in Hungarian), 1: 192–210, MR 0043117
- Eves, Howard (1953), An Introduction to the History of Mathematics, Holt, Reinhard, and Winston, ISBN 0-03-029558-0
- Gardner, Milo (2002), "The Egyptian Mathematical Leather Roll, attested short term and long term", in Gratton-Guinness, Ivor (ed.), History of the Mathematical Sciences, Hindustan Book Co, pp. 119–134, ISBN 81-85931-45-3
- Gillings, Richard J. (1982), Mathematics in the Time of the Pharaohs, Dover, p. 50, ISBN 978-0-486-24315-3
- Graham, R. L. (1964), "On finite sums of reciprocals of distinct nth powers" (PDF), Pacific Journal of Mathematics, 14 (1): 85–92, doi:10.2140/pjm.1964.14.85, MR 0159788, S2CID 2629869
- Graham, Ronald L. (2013), "Paul Erdős and Egyptian fractions" (PDF), Erdös centennial, Bolyai Soc. Math. Stud., vol. 25, János Bolyai Math. Soc., Budapest, pp. 289–309, doi:10.1007/978-3-642-39286-3_9, MR 3203600
- Guy, Richard K. (2004), "D11. Egyptian Fractions", Unsolved problems in number theory (3rd ed.), Springer-Verlag, pp. 252–262, ISBN 978-0-387-20860-2
- Hultsch, Friedrich (1895), "Die Elemente der ägyptischen Theilungsrechnung: Erste Anhandlung", Abhandlungen der philologisch-historischen Classe der Königlich-Sächsischen Gesellschaft der Wissenschaften, Sächsische Akademie der Wissenschaften zu Leipzig Philologisch-Historische Klasse (in German), Leipzig: S. Hirzel, 17 (1)
- Katz, Victor J., ed. (2007), The Mathematics of Egypt, Mesopotamia, China, India, and Islam: A Sourcebook, Princeton: Princeton University Press
- Knorr, Wilbur R. (1982), "Techniques of fractions in ancient Egypt and Greece", Historia Mathematica, 9 (2): 133–171, doi:10.1016/0315-0860(82)90001-5, MR 0662138
- Konyagin, S. V. (2014), "Double exponential lower bound for the number of representations of unity by Egyptian fractions", Mathematical Notes, 95 (1–2): 277–281, doi:10.1134/S0001434614010295, MR 3267215, S2CID 121871250
- Koshaleva, Olga; Kreinovich, Vladik (2021), "Egyptian fractions as approximators", Mathematical Structures and Modeling, 1 (57): 46–59
- Kusuba, Takanori (2004), "Indian rules for the decomposition of fractions", in Burnett, Charles; Hogendijk, Jan P.; Plofker, Kim; Yano, Michio (eds.), Studies in the History of the Exact Sciences in honour of David Pingree, Islamic Philosophy Theology and Science: Text and Studies, vol. 54, Leiden: Brill, pp. 497–516, MR 2054213
- Martin, G. (1999), "Dense Egyptian fractions", Transactions of the American Mathematical Society, 351 (9): 3641–3657, arXiv:math/9804045, doi:10.1090/S0002-9947-99-02327-2, MR 1608486, S2CID 2591861
- Ritter, Jim (2002), "Closing the Eye of Horus: the Rise and Fall of 'Horus-Eye Fractions'", in Steele, J.; Imhausen, A. (eds.), Under One Sky: Astronomy and Mathematics in the ancient Near East, Münster: Ugarit-Verlag, pp. 297–323
- Robson, E.; Stedall, J., eds. (2009), The Oxford Handbook of the History of Mathematics, Oxford: Oxford University Press
- Sigler, Laurence E. (trans.) (2002), Fibonacci's Liber Abaci, Springer-Verlag, ISBN 0-387-95419-8
- Stewart, B. M. (1954), "Sums of distinct divisors", American Journal of Mathematics, 76 (4): 779–785, doi:10.2307/2372651, JSTOR 2372651, MR 0064800
- Stewart, I. (1992), "The riddle of the vanishing camel", Scientific American, 266 (June): 122–124, Bibcode:1992SciAm.266f.122S, doi:10.1038/scientificamerican0692-122
- 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", Proceedings of the Physico-Mathematical Society of Japan, 3rd ser., 3 (6): 78–92, doi:10.11429/ppmsj1919.3.6_78
- Tenenbaum, G.; Yokota, H. (1990), "Length and denominators of Egyptian fractions", Journal of Number Theory, 35 (2): 150–156, doi:10.1016/0022-314X(90)90109-5, MR 1057319
- Vose, M. (1985), "Egyptian fractions", Bulletin of the London Mathematical Society, 17: 21, doi:10.1112/blms/17.1.21, MR 0766441
- Wagon, Stan (1999), Mathematica in Action, Springer, pp. 321–329, ISBN 0-387-98684-7
- Winkler, Peter (2004), "Uses of fuses", Mathematical Puzzles: A Connoisseur's Collection, A K Peters, pp. 2, 6, ISBN 1-56881-201-9</ref>
- Yokota, Hisashi (1988), "On a problem of Bleicher and Erdős", Journal of Number Theory, 30 (2): 198–207, doi:10.1016/0022-314X(88)90017-0, MR 0961916
- Brown, Kevin, Egyptian Unit Fractions.
- Eppstein, David, Egyptian Fractions.
- Knott, Ron, Egyptian fractions.
- Weisstein, Eric W., "Egyptian Fraction", MathWorld
- Giroux, André, Egyptian Fractions and Zeleny, Enrique, Algorithms for Egyptian Fractions, The Wolfram Demonstrations Project, based on programs by David Eppstein.