Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by 79.156.18.103 to version by David Eppstein. Report False Positive? Thanks, ClueBot NG. (4071618) (Bot) |
m →References: fix diacritic |
||
| (23 intermediate revisions by 15 users not shown) | |||
Line 1:
{{Short description|Finite sum of distinct unit fractions}}
[[File:
An '''Egyptian fraction''' is a finite sum of distinct [[unit fraction]]s, such as
That is, each [[
== Applications ==
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.<ref>{{harvtxt|Dick|Ogle|2018}}; {{harvtxt
means that each diner gets half a pizza plus another eighth of a pizza, for example by splitting 4 pizzas into 8 halves, and the remaining pizza into 8 eighths. Exercises in performing this sort of [[fair division]] of food are a standard classroom example in teaching students to work with unit fractions.{{sfnp|Wilson|Edgington|Nguyen|Pescosolido|2011}}
Egyptian fractions can provide a solution to [[rope-burning puzzle]]s, 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 <math>1/x</math>, burning a rope so that it always has <math>x</math> 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.{{sfnp|Winkler|2004}}
== Early history ==
{{further|Egyptian numerals|Egyptian mathematics}}
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 [[RMP 2/n table|table of Egyptian fraction expansions for rational numbers <math>\tfrac{2}{
=== Notation ===▼
To write the unit fractions used in their Egyptian fraction notation, in hieroglyph script, the Egyptians placed the [[Egyptian hieroglyphs|hieroglyph]]:▼
{| border=0 style="margin-left: 1.6em;
|}
▲===Notation===
▲To write the unit fractions used in their Egyptian fraction notation, in hieroglyph script, the Egyptians placed the [[Egyptian hieroglyphs|hieroglyph]]
▲<center><hiero>D21</hiero></center>
(''er'', "<nowiki>[one]</nowiki> among" or possibly ''re'', mouth) above a number to represent the [[Multiplicative inverse|reciprocal]] of that number. Similarly in hieratic script they drew a line over the letter representing the number. For example:
{|
|<hiero>D21:Z1*Z1*Z1</hiero>
| style="padding-right:1em;" |<math>= \frac{1}{3}</math>
Line 33 ⟶ 32:
|}
The Egyptians had special symbols for <math>\tfrac{
{| cellpadding="1em" style="margin-left: 1.6em;
|<hiero>Aa13</hiero>
| style="padding-right:1em;" |<math>= \frac{1}{2}</math>
Line 43 ⟶ 42:
|<math>= \frac{3}{4}</math>
|}
The Egyptians also used an alternative notation modified from the Old Kingdom to denote a special set of fractions of the form
They were used in the Middle Kingdom in conjunction with the later notation for Egyptian fractions to subdivide a [[hekat (volume unit)|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 <math>\tfrac{
=== Calculation methods ===
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 <math>\tfrac{
* For small odd prime denominators
* For some composite denominators, factored as <math>p\cdot q</math>, the expansion for <math>\tfrac{2}{pq}</math> has the form of an expansion for <math>\tfrac{2}{p}</math> with each denominator multiplied by <math>q</math>. This method appears to have been used for many of the composite numbers in the Rhind papyrus,<ref>{{harvtxt|Gillings|1982}}; {{harvtxt|Gardner|2002}}</ref> but there are exceptions, notably <math>\tfrac{2}{35}</math>, <math>\tfrac{2}{91}</math>, and <math>\tfrac{2}{95}</math>.{{sfnp|Knorr|1982}}
* One can also expand <math display=block>\frac{2}{pq}=\frac{1}{p(p+q)/2}+\frac{1}{q(p+q)/2}.</math> For instance, Ahmes expands <math>\tfrac{2}{35}=\tfrac{2}{5\cdot 7}=\tfrac{1}{30}+\tfrac{1}{42}</math>. Later scribes used a more general form of this expansion, <math display=block>\frac{n}{pq}=\frac{1}{p(p+q)/n}+\frac{1}{q(p+q)/n},</math> which works when <math>p+q</math> is a multiple of <math>n</math>.{{sfnp|Eves|1953}}
* The final (prime) expansion in the Rhind papyrus, <math>\tfrac{2}{101}</math>, does not fit any of these forms, but instead uses an expansion <math display=block>\frac{2}{p} = \frac{1}{p} + \frac{1}{2p} + \frac{1}{3p} + \frac{1}{6p}</math> that may be applied regardless of the value of <math>p</math>. That is, <math>\tfrac{2}{101} = \tfrac{1}{101} + \tfrac{1}{202} + \tfrac{1}{303} + \tfrac{1}{606}</math>. A related expansion was also used in the Egyptian Mathematical Leather Roll for several cases.
▲:was used, where ''A'' is a number with many divisors (such as a [[practical number]]) between {{sfrac|''p''|2}} and ''p''. The remaining term {{nowrap|{{sfrac|2''A'' − ''p''|''Ap''}}}} was expanded by representing the number {{nowrap|{{sfrac|2''A'' − ''p''|''Ap''}}}} as a sum of divisors of ''A'' and forming a fraction {{sfrac|''d''|''Ap''}} for each such divisor ''d'' in this sum.<ref>{{harvtxt|Hultsch|1895}}; {{harvtxt|Bruins|1957}}</ref> As an example, Ahmes' expansion {{nowrap|{{sfrac|1|24}} + {{sfrac|1|111}} + {{sfrac|1|296}}}} for {{sfrac|2|37}} fits this pattern with {{nowrap|1=''A'' = 24}} and {{nowrap|1={{sfrac|2''A'' − ''p''|''Ap''}} = 11 = 3 + 8}}, as {{nowrap|1={{sfrac|1|24}} + {{sfrac|1|111}} + {{sfrac|1|296}} = {{sfrac|1|24}} + {{sfrac|3|24 × 37}} + {{sfrac|8|24 × 37}}}}. 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.
== Later usage ==
{{further|Liber Abaci|Greedy algorithm for Egyptian fractions}}
Line 74 ⟶ 62:
The next several methods involve algebraic identities such as
For instance, Fibonacci represents the fraction {{sfrac|8|11}} by splitting the numerator into a sum of two numbers, each of which divides one plus the denominator: {{nowrap|1={{sfrac|8|11}} = {{sfrac|6|11}} + {{sfrac|2|11}}}}. Fibonacci applies the algebraic identity above to each these two parts, producing the expansion {{nowrap|1={{sfrac|8|11}} = {{sfrac|1|2}} + {{sfrac|1|22}} + {{sfrac|1|6}} + {{sfrac|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 Egyptian fractions|"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 {{sfrac|''x''|''y''}} by the expansion
▲:<math>\frac{x}{y}=\frac{1}{\,\left\lceil \frac{y}{x} \right\rceil\,}+\frac{(-y)\,\bmod\, x}{y\left\lceil \frac{y}{x}\right\rceil}</math>
where {{nowrap|⌈ ⌉}} represents the [[Floor and ceiling functions|ceiling function]]; since {{nowrap|(−''y'') mod ''x'' < ''x''}}, this method yields a finite expansion.
Line 86 ⟶ 72:
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
while other methods lead to the shorter expansion
[[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 {{nowrap|⌊ {{sfrac|''y''|''x''}} ⌋ + 1}} instead of {{nowrap|⌈ {{sfrac|''y''|''x''}} ⌉}}, and sometimes Fibonacci's greedy algorithm is attributed to [[James Joseph Sylvester]].
Line 94 ⟶ 80:
After his description of the greedy algorithm, Fibonacci suggests yet another method, expanding a fraction {{sfrac|''a''|''b''}} by searching for a number ''c'' having many divisors, with {{nowrap|{{sfrac|''b''|2}} < ''c'' < ''b''}}, replacing {{sfrac|''a''|''b''}} by {{sfrac|''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 theory ==
{{further|Erdős–Graham problem|Znám's problem|Engel expansion}}
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 number]]s.
*One of the earliest publications of [[Paul Erdős]] proved that it is not possible for a [[Harmonic progression (mathematics)|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.<ref>{{harvtxt|Erdős|1932}}; {{harvtxt|Graham|2013}}</ref> 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.{{sfnp|Butler|Erdős|Graham|2015}}
*The [[Erdős–Graham conjecture]] in [[Number theory|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 {{nowrap|''r'' > 0}}, and every ''r''-coloring of the integers greater than one, there is a finite monochromatic subset ''S'' of these integers such that <math display=block>\sum_{n\in S}\frac{1}{n} = 1.</math> The conjecture was proven in 2003 by [[Ernest S. Croot III]].
*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 <math display=block>\frac1k+\frac1k=\frac2{k+1}+\frac2{k(k+1)}</math> if ''k'' is odd, or simply by replacing {{nowrap|{{sfrac|1|''k''}} + {{sfrac|1|''k''}}}} by {{sfrac|2|''k''}} if ''k'' is even. This result was first proven by {{harvtxt|Takenouchi|1921}}.▼
*Graham and Jewett<ref>See {{harvtxt|Wagon|1999}} and {{harvtxt|Beeckmans|1993}}</ref> proved that it is similarly possible to convert expansions with repeated denominators to (longer) Egyptian fractions, via the replacement <math display=block>\frac1k+\frac1k=\frac1k+\frac1{k+1}+\frac1{k(k+1)}.</math> This method can lead to long expansions with large denominators, such as <math display=block>\frac45=\frac15+\frac16+\frac17+\frac18+\frac1{30}+\frac1{31}+\frac1{32}+\frac1{42}+\frac1{43}+\frac1{56}+▼
▲: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 {{nowrap|1=1 = {{sfrac|1|2}} + {{sfrac|1|3}} + {{sfrac|1|7}} + {{sfrac|1|43}} + {{sfrac|1|1806}}}}.
*{{harvtxt|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 <math display=block>\left[0,\frac{\pi^2}{6}-1\right)\cup\left[1,\frac{\pi^2}{6}\right).</math>▼
▲*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<ref>See {{harvtxt|Wagon|1999}} and {{harvtxt|Beeckmans|1993}}</ref> proved that it is similarly possible to convert expansions with repeated denominators to (longer) Egyptian fractions, via the replacement
▲:{{harvtxt|Botts|1967}} had originally used this replacement technique to show that any rational number has Egyptian fraction representations with arbitrarily large minimum denominators.
▲:terms.{{sfnp|Vose|1985}} The number of terms must sometimes be at least proportional to {{nowrap|log log ''y''}}; for instance this is true for the fractions in the sequence {{sfrac|1|2}}, {{sfrac|2|3}}, {{sfrac|6|7}}, {{sfrac|42|43}}, {{sfrac|1806|1807}}, ... whose denominators form [[Sylvester's sequence]]. It has been conjectured that {{nowrap|''O''(log log ''y'')}} terms are always enough.{{sfnp|Erdős|1950}} It is also possible to find representations in which both the maximum denominator and the number of terms are small.{{sfnp|Tenenbaum|Yokota|1990}}
▲*{{harvtxt|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
*{{harvtxt|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: <math display=block>x=\frac{1}{a_1}+\frac{1}{a_1a_2}+\frac{1}{a_1a_2a_3}+\cdots.</math> In addition, the sequence of multipliers ''a<sub>i</sub>'' is required to be nondecreasing. Every rational number has a finite Engel expansion, while [[irrational number]]s have an infinite Engel expansion.
▲:Unlike the ancient Egyptians, they allow denominators to be repeated in these expansions. They apply their results for this problem to the characterization of [[free product]]s of [[Abelian group]]s by a small number of numerical parameters: the rank of the [[commutator subgroup]], the number of terms in the free product, and the product of the orders of the factors.
*The number of different ''n''-term Egyptian fraction representations of the number one is bounded above and below by [[double exponential function]]s of ''n''.{{sfnp|Konyagin|2014}}
== Open problems ==
{{further|Odd greedy expansion|Erdős–Straus conjecture}}
Some notable problems remain unsolved with regard to Egyptian fractions, despite considerable effort by mathematicians.
* The [[Erdős–Straus conjecture]]{{sfnp|Erdős|1950}} concerns the length of the shortest expansion for a fraction of the form {{sfrac|4|''n''}}. Does an expansion <math display=block>\frac4n=\frac1x+\frac1y+\frac1z</math> exist for every ''n''? It is known to be true for all {{nowrap|''n'' < 10<sup>17</sup>}}, 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 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 {{sfrac|''x''|''y''}} have an odd denominator ''y'', and it is conjectured but not known that this is also a sufficient condition. It is known<ref>{{harvtxt|Breusch|1954}}; {{harvtxt|Stewart|1954}}</ref> that every {{sfrac|''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{{sfnp|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 [[Analysis of algorithms|computational complexity]] of such problems, remains unknown.
Line 143 ⟶ 108:
{{harvtxt|Guy|2004}} describes these problems in more detail and lists numerous additional open problems.
== See also ==
*[[List of sums of reciprocals]]
*[[17-animal inheritance puzzle]]
== Notes ==
{{Reflist|30em}}
== References ==
{{refbegin|30em}}
*{{citation
Line 172 ⟶ 138:
| volume = 43
| year = 1993
| issue = 2
}}
*{{citation
| doi = 10.2307/2688508
Line 191 ⟶ 158:
| volume = 61
| doi = 10.2307/2307234
| year = 1954| jstor = 2307234 }}
*{{citation
| last = Bruins | first = Evert M.
Line 265 ⟶ 232:
| volume = 14
| year = 1964
| doi=10.2140/pjm.1964.14.85| s2cid = 2629869 }}
*{{citation
| last = Graham | first = Ronald L. | authorlink = Ronald Graham
Line 274 ⟶ 241:
| publisher = János Bolyai Math. Soc., Budapest
| series = Bolyai Soc. Math. Stud.
| title =
| contribution-url = http://www.math.ucsd.edu/~ronspubs/13_03_Egyptian.pdf
| volume = 25
Line 311 ⟶ 278:
| last = Konyagin | first = S. V. | authorlink = Sergei Konyagin
| doi = 10.1134/S0001434614010295
| issue =
| journal = [[Mathematical Notes]]
| mr = 3267215
Line 317 ⟶ 284:
| title = Double exponential lower bound for the number of representations of unity by Egyptian fractions
| volume = 95
| year = 2014| s2cid = 121871250 }}
*{{citation
| last1 = Koshaleva | first1 = Olga
Line 353 ⟶ 320:
| year = 1999
| issue = 9| arxiv = math/9804045
| s2cid = 2591861
}}
*{{citation|last=Ritter|first=Jim|contribution=Closing the Eye of Horus: the Rise and Fall of 'Horus-Eye Fractions'|title=Under One Sky: Astronomy and Mathematics in the ancient Near East|editor1-first=J.|editor1-last=Steele|editor2-first=A.|editor2-last=Imhausen|editor2-link=Annette Imhausen|location=Münster|publisher=Ugarit-Verlag|year=2002|pages=297–323}}
Line 379 ⟶ 347:
| pages = 122–124
| title = The riddle of the vanishing camel
| year = 1992| volume = 266 | doi = 10.1038/scientificamerican0692-122 | bibcode = 1992SciAm.266f.122S }}
| year = 1992}}▼
*{{citation
| last = Struik | first = Dirk J. | author-link = Dirk Jan Struik
Line 425 ⟶ 393:
| title = Mathematica in Action
| year = 1999}}
*{{citation
| last1 = Wilson | first1 = P. Holt
| last2 = Edgington | first2 = Cynthia P.
| last3 = Nguyen | first3 = Kenny H.
| last4 = Pescosolido | first4 = Ryan C.
| last5 = Confrey | first5 = Jere
| date = November 2011
| doi = 10.5951/mathteacmiddscho.17.4.0230
| issue = 4
| journal = Mathematics Teaching in the Middle School
| jstor = 10.5951/mathteacmiddscho.17.4.0230
| pages = 230–236
| title = Fractions: how to fair share
*{{citation
| last = Winkler | first = Peter | author-link = Peter Winkler
Line 432 ⟶ 414:
| publisher = A K Peters
| title = Mathematical Puzzles: A Connoisseur's Collection
| year = 2004}}
*{{citation
| last = Yokota | first = Hisashi
Line 442 ⟶ 424:
| title = On a problem of Bleicher and Erdős
| volume = 30
| year = 1988
}}
{{refend}}
== External links ==
*{{citation
| last = Brown | first = Kevin
| |||