- Egyptian fraction
An

**Egyptian fraction**is the sum of distinctunit fraction s, such as $frac\{1\}\{2\}+\; frac\{1\}\{3\}+\; frac\{1\}\{16\}$. That is, each fraction in the expression has anumerator equal to 1 and adenominator that is a positiveinteger , and all the denominators differ from each other. The sum of an expression of this type is a positiverational number "a"/"b"; for instance the Egyptian fraction above sums to 43/48. Every positive rational number can be represented by an Egyptian fraction. Sums of this type, and similar sums also including 2/3 and 3/4 assummand s, were used as a serious notation for rational numbers by the ancient Egyptians, and continued to be used by other civilizations into medieval times. In modern mathematical notation, Egyptian fractions have been superseded byvulgar fraction s anddecimal notation. However, Egyptian fractions continue to be an object of study in modernnumber theory andrecreational mathematics , as well as in modern historical studies of ancient mathematics.**Ancient Egypt**:"For more information on this subject, see

Egyptian numerals ,Eye of Horus , andEgyptian mathematics ."Egyptian fraction notation was developed in the

Middle Kingdom of Egypt , altering the Old Kingdom'sEye of Horus numeration system. Five early texts in which Egyptian fractions appear were theEgyptian Mathematical Leather Roll , theMoscow Mathematical Papyrus , theReisner Papyrus , theKahun Papyrus and theAkhmim Wooden Tablet . A later text, theRhind Mathematical Papyrus , introduced improved ways of writing Egyptian fractions. The Rhind papyrus was written byAhmes and dates from theSecond Intermediate Period ; it includes a table of Egyptian fraction expansions for rational numbers 2/"n", 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. 2/"n" tables similar to the one on the Rhind papyrus also appear on some of the other texts. However, as theKahun Papyrus shows,vulgar fraction s 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

D21

("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 1/2, 2/3, and 3/4 that were used to reduce the size of numbers greater than 1/2 when such numbers were converted to an Egyptian fraction series. The remaining number after subtracting one of these special fractions was written using the usual Egyptian fraction representations.

The Egyptians also used an alternative notation modified from the Old Kingdom and 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 "Horus-Eye fractions" 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, the subject of theAkhmim 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 regular Egyptian fraction notation as multiples of a "ro", a unit equal to 1/320 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 2/"n" in the Rhind papyrus. Although these expansions can generally be described as algebraic identities, they do not match any single identity; rather, different methods were used for prime and for composite denominators, and more than one method was used for numbers of each type:

* For small odd prime denominators "p", the expansion 2/"p" = 2/("p" + 1) + 2/"p"("p" + 1) was used.

* For larger prime denominators, an expansion of the form 2/"p" = 1/"A" + (2"A"-"p")/"Ap" was used, where "A" is a number with many divisors (such as a

practical number ) in the range "p"/2 < "A" < "p". The remaining term (2"A"-"p")/"Ap" was expanded by representing the number 2"A"-"p" as a sum of divisors of "A" and forming a fraction "d"/"Ap" for each such divisor "d" in this sum (Hultsch 1895, Bruins 1957). As an example, Ahmes' expansion 2/37 = 1/24 + 1/111 + 1/296 fits this pattern, with "A" = 24 and 2"A"-"p" = 11 = 3+8, since 3 and 8 are divisors of 24. There may be many different expansions of this type for a given "p"; however, as K. S. Brown observed, the expansion chosen by the Egyptians was often the one that caused the largest denominator to be as small as possible, among all expansions fitting this pattern.* For composite denominators, factored as "p"×"q", one can expand 2/"pq" using the identity 2/"pq" = 1/"aq" + 1/"apq", where "a" = ("p"+1)/2. For instance, applying this method for "pq" = 21 gives "p" = 3, "q" = 7, and "a" = (3+1)/2 = 2, producing the expansion 2/21 = 1/14 + 1/42 from the Rhind papyrus. Some authors have preferred to write this expansion as 2/"A" × "A"/"pq", where "A" = "p"+1 (Gardner, 2002); replacing the second term of this product by "p"/"pq" + 1/"pq", applying the distributive law to the product, and simplifying leads to an expression equivalent to the first expansion described here. This method appears to have been used for many of the composite numbers in the Rhind papyrus (Gillings 1982, Gardner 2002), but there are exceptions, notably 2/35, 2/91, and 2/95 (Knorr 1982).

* One can also expand 2/"pq" as 1/"pr" + 1/"qr", where "r" = ("p"+"q")/2. For instance, Ahmes expands 2/35 = 1/30 + 1/42, where "p" = 5, "q" = 7, and "r" = (5+7)/2 = 6. Later scribes used a more general form of this expansion, "n"/"pq" = 1/"pr" + 1/"qr", where "r" =("p" + "q")/"n", which works when "p" ≡ -"q" (mod "n") (Eves, 1953).

* For some other composite denominators, the expansion for 2/"pq" has the form of an expansion for 2/"q" with each denominator multiplied by "p". For instance, 95=5×19, and 2/19 = 1/12 + 1/76 + 1/114 (as can be found using the method for primes with "A" = 12), so 2/95 = 1/(5×12) + 1/(5×76) + 1/(5×114) = 1/60 + 1/380 + 1/570 (Eves, 1953). This expression can be simplified as 1/380 + 1/570 = 1/228 but the Rhind papyrus uses the unsimplified form.

* The final (prime) expansion in the Rhind papyrus, 2/101, does not fit any of these forms, but instead uses an expansion 2/"p" = 1/"p" + 1/2"p" + 1/3"p" + 1/6"p" that may be applied regardless of the value of "p". That is, 2/101 = 1/101 + 1/202 + 1/303 + 1/606. A related expansion was also used in the Egyptian Mathematical Leather Roll for several cases.

**Medieval mathematics**:"For more information on this subject, see

Liber Abaci andGreedy algorithm for Egyptian fractions ."Egyptian fraction notation continued to be used in Greek times and into the Middle Ages (Struik 1967), despite complaints as early as

Ptolemy 'sAlmagest about the clumsiness of the notation compared to alternatives such as the Babylonian base-60 notation. An important text of medieval mathematics, theLiber Abaci (1202) ofLeonardo of Pisa (more commonly known as Fibonacci), gives us 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 (Sigler 2002, chapter II.7) provides a list of method 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 apractical 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 $frac\{a\}\{ab-1\}=\; frac\{1\}\{b\}+\; frac\{1\}\{b(ab-1)\}.$ For instance, Fibonacci represents the fraction $frac\{8\}\{11\}$ by splitting the numerator into a sum of two numbers, each of which divides one plus the denominator: $frac\{8\}\{11\}=\; frac\{6\}\{11\}+\; frac\{2\}\{11\}.$ Fibonacci applies the algebraic identity above to each these two parts, producing the expansion$frac\{8\}\{11\}=\; frac\{1\}\{2\}+\; frac\{1\}\{22\}+\; frac\{1\}\{6\}+\; frac\{1\}\{66\}.$ Fibonacci describes similar methods for denominators that are two or three less than a number with many factors.

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

:$frac\{x\}\{y\}=frac\{1\}\{lceil\; y/x\; ceil\}+frac\{-y,mod,\; x\}\{ylceil\; y/x\; ceil\}.$

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: $frac\{4\}\{13\}=\; frac\{1\}\{4\}+\; frac\{1\}\{18\}+\; frac\{1\}\{468\}$ and $frac\{17\}\{29\}=\; frac\{1\}\{2\}+\; frac\{1\}\{12\}+\; frac\{1\}\{348\}.$

As later mathematicians showed, each greedy expansion reduces the numerator of the remaining fraction to be expanded, so 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, and Fibonacci himself noted the awkwardness of the expansions produced by this method. For instance, the greedy 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\; floor+1$ instead of $lceil\; y/x\; ceil$, and sometimes Fibonacci's greedy algorithm is attributed to 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 the ancient RMP 2/p expansions.

**Modern number theory**:"For more information on this subject, see

Erdős–Graham conjecture ,Znám's problem , andEngel expansion ."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 number s.*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\_\{nin\; S\}1/n\; =\; 1.$:The conjecture was proven in 2003 byErnest S. Croot, III .*

Znám's problem andprimary pseudoperfect number s are closely related to the existence of Egyptian fractions of the form::$sumfrac1\{x\_i\}\; +\; prodfrac1\{x\_i\}=1.$:For instance, the primary pseudoperfect number 1806 is the product of the prime numbers 2, 3, 7, and 43, and gives rise to the Egyptian fraction 1 = 1/2 + 1/3 + 1/7 + 1/43 + 1/1806.*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::$frac1k+frac1k=frac2\{k+1\}+frac2\{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::$frac1k+frac1k=frac1k+frac1\{k+1\}+frac1\{k(k+1)\}.$:This method can lead to long expansions with large denominators, such as::$frac45=frac15+frac16+frac17+frac18+frac1\{30\}+frac1\{31\}+frac1\{32\}+frac1\{42\}+frac1\{43\}+frac1\{56\}+frac1\{930\}+frac1\{931\}+frac1\{992\}+frac1\{1806\}+frac1\{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\{ylog^2\; y\}\{loglog\; 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 "n"th 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".

*

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:::$x=frac\{1\}\{a\_1\}+frac\{1\}\{a\_1a\_2\}+frac\{1\}\{a\_1a\_2a\_3\}+cdots.$:In addition, the sequence of multipliers "a_{i}" is required to be nondecreasing. Every rational number has a finite Engel expansion, whileirrational number s have an infinite Engel expansion.**Open problems**:"For more information on this subject, see

odd greedy expansion andErdő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::$frac4n=frac1x+frac1y+frac1z$:exist for every "n"? It is known to be true for all "n" < 10^{14}, and for all but a vanishingly small fraction of possible values of "n", but the general truth of the conjecture remains unknown.* It is unknown whether an

odd greedy expansion exists for every fraction with an odd denominator. 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 ofpolynomial time algorithms for these problems, or more generally thecomputational complexity of such problems, remains unknown.**References***cite journal

author = Beeckmans, L.

title = The splitting algorithm for Egyptian fractions

journal =Journal of Number Theory

volume = 43

year = 1993

pages = 173–185

id = MathSciNet | id = 1207497

doi = 10.1006/jnth.1993.1015*cite journal

author = Botts, Truman

title = A chain reaction process in number theory

journal =Mathematics Magazine

year = 1967

pages = 55–65

url = http://www.jstor.org/stable/2688508

id = MathSciNet | id = 0209217*cite journal

author = Breusch, R.

title = A special case of Egyptian fractions, solution to advanced problem 4512

journal =American Mathematical Monthly

volume = 61

year = 1954

pages = 200–201 |doi=*cite journal

author = Bruins, Evert M.

title = Platon et la table égyptienne 2/"n"

journal = Janus

volume = 46

year = 1957

pages = 253–263*cite book

author = Eves, Howard

authorlink = Howard Eves

title = An Introduction to the History of Mathematics

publisher = Holt, Reinhard, and Winston

year = 1953

id = ISBN 0-03-029558-0*cite conference

author = Gardner, Milo

title = The Egyptian Mathematical Leather Roll, attested short term and long term

pages = 119–134

booktitle = History of the Mathematical Sciences

editor = Ivor Gratton-Guiness (ed.)

publisher = Hindustan Book Co

year = 2002

id = ISBN 81-85931-45-3*cite book

last = Gillings, Richard J.

title = Mathematics in the Time of the Pharaohs

publisher = Dover

year = 1982

id = ISBN 0-486-24315-X*cite journal

author = Graham, R. L.

authorlink = Ronald Graham

title = On finite sums of reciprocals of distinct "n"th powers

journal =Pacific Journal of Mathematics

volume = 14

issue = 1

year = 1964

pages = 85–92

url = http://www.math.ucsd.edu/~sbutler/ron/64_07_reciprocals.pdf

id = MathSciNet | id = 0159788*cite book

author = Hultsch, Friedrich

authorlink = Friedrich Hultsch

title = Die Elemente der ägyptischen Theilungsrechnung

year = 1895

publisher = S. Hirzel

location = Leipzig*cite journal

author = Knorr, Wilbur R.

authorlink = Wilbur Knorr

title = Techniques of fractions in ancient Egypt and Greece

journal =Historia Mathematica

volume = 9

year = 1982

pages = 133–171

id = MathSciNet | id = 0662138

doi = 10.1016/0315-0860(82)90001-5*cite journal

author = Martin, G.

title = Dense Egyptian fractions

journal =Transactions of the American Mathematical Society

volume = 351

pages = 3641–3657

year = 1999

id = MathSciNet | id = 1608486

doi = 10.1090/S0002-9947-99-02327-2*cite book

author = Robins, Gay; Shute, Charles

title = The Rhind Mathematical Papyrus: An Ancient Egyptian Text

publisher = Dover

year = 1990

id = ISBN 0-486-26407-6*cite book

title = Fibonacci's Liber Abaci

author = Sigler, Laurence E. (trans.)

publisher = Springer-Verlag

year = 2002

id = ISBN 0-387-95419-8*cite journal

author = Stewart, B. M.

title = Sums of distinct divisors

journal =American Journal of Mathematics

volume = 76

year = 1954

pages = 779–785

id = MathSciNet | id = 0064800

doi = 10.2307/2372651*cite journal

author = Stewart, I.

authorlink = Ian Stewart (mathematician)

title = The riddle of the vanishing camel

journal =Scientific American

year = 1992

issue = June

pages = 122–124*cite book

author = Struik, Dirk J.

authorlink = Dirk Jan Struik

title = A Concise History of Mathematics

publisher = Dover

year = 1967

id = ISBN 0-486-60255-9

pages = 20–25*cite journal

author = Takenouchi, T.

title = On an indeterminate equation

journal =Proceedings of the Physico-Mathematical Society of Japan , 3rd ser.

volume = 3

year = 1921

pages = 78–92*cite journal

author = Tenenbaum, G.; Yokota, H.

title = Length and denominators of Egyptian fractions

journal =Journal of Number Theory

volume = 35

year = 1990

pages = 150–156

id = MathSciNet | id = 1057319

doi = 10.1016/0022-314X(90)90109-5*cite journal

author = Vose, M.

title = Egyptian fractions

journal = Bulletin of the London Mathematical Society

volume = 17

year = 1985

pages = 21

id = MathSciNet | id = 0766441

doi = 10.1112/blms/17.1.21*cite book

author = Wagon, S.

title = Mathematica in Action

publisher = W.H. Freeman

year = 1991

pages = 271–277**External links*** cite web

author = Brown, Kevin

title = Egyptian Unit Fractions

url = http://www.mathpages.com/home/kmath340/kmath340.htm

*cite web

author = Eppstein, David

authorlink = David Eppstein

title = Egyptian Fractions

url = http://www.ics.uci.edu/~eppstein/numth/egypt/*cite web

author = Gardner, Milo

authorlink = Gardner, Milo

title = Egyptian Fractions

url = http://planetmath.org/encyclopedia/EgyptianFraction2.html, http://emlr.blogspot.com, http://rmprectotable.blogspot.com, http://planetmath.org/encyclopedia/EgyptianMultiplicationAndDivision.html*cite web

author = Knott, R.

title = Egyptian fractions

url = http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html

*cite web

author = O'Connor, J. J.; Robertson, E. F.

title = Mathematics in Egyptian Papyri

year = 2000

url = http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Egyptian_papyri.html

*mathworld|urlname=EgyptianFraction|title=Egyptian Fraction

* [*http://demonstrations.wolfram.com/EgyptianFractions/ Egyptian Fractions*] by André Giroux and [*http://demonstrations.wolfram.com/AlgorithmsForEgyptianFractions/ Algorithms for Egyptian Fractions*] by Enrique Zeleny based on programs by David Eppstein,The Wolfram Demonstrations Project .

*Wikimedia Foundation.
2010.*