HTTP/1.1 200 OK
Date: Tue, 14 Feb 2012 23:06:00 GMT
Server: Apache/2.2.3 (CentOS)
Accept-Ranges: bytes
Connection: close
Content-Type: text/html; charset=UTF-8
Set-Cookie: Coyote-2-80c30153=80c3018f:0; path=/

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>Egyptian Fractions</title>
</head>
<body>

<h1>Egyptian Fractions</h1>

<hr>
<p>Nowadays, we usually write non-integer numbers either as
fractions (2/7) or decimals (0.285714). The floating point
representation used in computers is another representation very
similar to decimals. But the ancient Egyptians (as far as we can
tell from the documents now surviving) used a number system based
on <i>unit fractions</i>: fractions with one in the numerator. This
idea let them represent numbers like 1/7 easily enough; other
numbers such as 2/7 were represented as sums of unit fractions
(e.g. 2/7&nbsp;=&nbsp;1/4&nbsp;+1/28). Further, the same fraction
could not be used twice (so 2/7&nbsp;=&nbsp;1/7&nbsp;+&nbsp;1/7 is
not allowed). We call a formula representing a sum of distinct unit
fractions an <i>Egyptian fraction</i>.</p>

<p>This notation is cumbersome and difficult to compute with, so
the Egyptian scribes made large tables so they could look up the
answers to arithmetic problems. However there is also some
interesting mathematics associated with the problem of <i>
converting</i> modern fraction notation into the Egyptian form. A
number of famous mathematicians have looked at this problem, and
invented different ways of doing this conversion process. Each of
these methods has advantages and disadvantages in terms of the
complexity of the Egyptian fraction representations it produces and
in terms of the amount of time the conversion process takes. There
are still some unsolved problems about whether some of these
processes finish, or whether they get into an infinite loop.</p>

<p>To investigate some of these questions, I wrote a <i>
Mathematica</i> notebook, now called "Algorithms for Egyptian
Fractions", which as the title implies implements on the computer
some of these computation methods. A version of this notebook was
published as "Ten Algorithms for Egyptian Fractions" in <i>
Mathematica in Education and Research</i>, vol. 4, no. 2, 1995, pp.
5-15, available online through
<a href="http://library.wolfram.com/infocenter/Articles/2926/">MathSource</a>.</p>

<p>Since then I have made several changes including improvements to
the binary remainder method and two new sections on reverse greedy
methods and brute force searches. I am making this updated version
available here.</p>

<h2>Algorithms for Egyptian fractions:</h2>

<ul>
<li><a href="intro.html">Algorithms for Egyptian fractions</a> in
HTML format, <a href="/~eppstein/pubs/p-egypt.html">publication
information</a>, and <a href="egypt.ma">Mathematica source code</a>.</li>

<li><a href="egypt.py">Python-based command-line tool for generating
Egyptian fractions</a>.</li>

<li><a href="Egypt.m">Mathematica package</a>, <a href=
"http://library.wolfram.com/infocenter/MathSource/574/">also available
through MathSource</a>, as is
<a href="http://library.wolfram.com/infocenter/MathSource/562/">a different Egyptian fraction package</a>.</li>

<li><a href="efrac.c">C++ source code</a> to brute force search for
representations with few terms and <a href="4nbg.c">C source code</a> to find certain solutions to
4/n&nbsp;=&nbsp;1/x&nbsp;+&nbsp;1/y&nbsp;+&nbsp;1/z</li>
</ul>

<h2>Transcriptions of network conversations:</h2>

<ul>
<li><a href="http://www.livejournal.com/users/11011110/tag/egyptian+fractions">My blog entries on Egyptian fractions</a>.</li>

<li><a href="http://groups.google.com/groups?threadm=b4be2fdf.0405251059.67a1e491@posting.google.com">Polygons
with angles of different k-gons</a>.
Leroy Quet poses a geometric tiling question related to Egyptian fraction
decompositions of 1 and 1/2.</li>

<li><a href="http://groups.google.com/groups?threadm=19daab49.0405211322.5d031bb7@posting.google.com">Egyptian
topology on Q</a>.
Michael Barr defines a topological space in which a sequence of rationals
converges only if its terms have bounded length Egyptian fraction
expansions, and asks how this differs from the usual Euclidean topology.</li>

<li><a href="http://groups.google.com/groups?threadm=19daab49.0403311340.9a745bc@posting.google.com">Sums of unit fractions</a>.
Michael Barr asks for a proof that there can be no constant bound on the
number of terms needed for Egyptian fraction representations.</li>

<li><a
href="http://groups.google.com/groups?threadm=bdfpvq$812$1@morgoth.sfu.ca">1/x
+ 1/y + 1/z = 1/n</a>.
Tim Brooks asks for the solution maximizing z.</li>

<li><a href="carmichael.html">Perfect numbers and Carmichael numbers</a>.
Bill Daly shows how to use Egyptian fraction representations of integers
to generate counterexamples for primality-testing algorithms.</li>

<li><a href="http://mathforum.org/epigone/sci.math/beldlaxyo">Math
forum archive</a> of sci.math messages under the subject of Egyptian fractions.</li>

<li><a href="why.html">Why use Egyptian fractions?</a> Darrah
Chavey gives some explanations for the Egyptians' use of this
seemingly bizarre notation.</li>

<li><a href="perfect.html">Donald T. Davis hypothesizes that
perfect numbers were first studied for their uses in simplifying
Egyptian fraction manipulation</a>.</li>

<li><a href="odd-one.html">Dave Ketcheson asks how to represent the
number one as an Egyptian fraction with odd denominators</a>.</li>

<li><a href="qgrady.html">Quentin Grady uses Egyptian fractions to
make up electrical engineering problems</a>.</li>

<li><a href="3-179.html">Stan Wagon discovers that odd greedy
performs very poorly on 3/179</a>, throwing into question a
heuristic analysis from my paper. 3/2879 and 5/5809 are even
worse.</li>

<li><a href="curtiss.html">Stefan Bartels looks for the maximum
denominator</a> among all <i>k</i>-term representations for a given
number (or equivalently the closest (<i>k</i>-1)-term
underrepresentation), which is often found by the greedy algorithm,
and investigates work on the subject by Curtiss and others.</li>

<li><a href="kterm-minden.html">Kevin Brown looks for the minimum
denominator</a> among all <i>k</i>-term representations for a given
number. In particular for <i>k</i>&nbsp;=&nbsp;12 he finds the representation 

<center>
<table cellpadding="0" cellspacing="0">
<tr align="CENTER" valign="BOTTOM">
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
</tr>

<tr align="CENTER" valign="middle">
<td>1&nbsp;=&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;+&nbsp;</td>
<td>
<hr noshade size="1">
</td>
</tr>

<tr align="CENTER" valign="TOP">
<td></td>
<td>6</td>
<td></td>
<td>7</td>
<td></td>
<td>8</td>
<td></td>
<td>9</td>
<td></td>
<td>10</td>
<td></td>
<td>14</td>
<td></td>
<td>15</td>
<td></td>
<td>18</td>
<td></td>
<td>20</td>
<td></td>
<td>24</td>
<td></td>
<td>28</td>
<td></td>
<td>30</td>
</tr>
</table>
</center>
</li>

<li><a href="plusminus.html">Bill Taylor asks about a conjecture
that for any denominator, all sufficiently large numerators can be
expressed as a sum or difference of at most three unit
fractions</a>.</li>

<li><a
href="http://mathforum.org/library/drmath/view/52702.html">Fibonacci
Algorithm and Egyptian Fractions</a>. Liz asks Dr. Math how to find
numbers for which the greedy algorithm produces long expansions.</li>
</ul>

<h2>Other sites of interest:</h2>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Egyptian_fraction">Wikipedia:
Egyptian fractions</a> and <a
href="http://en.wikipedia.org/wiki/Category:Egyptian_fractions">related articles</a>.</li>

<li><a href="http://www.plover.com/blog/math/egyptian-fractions.html">The
Universe of Discourse: Egyptian Fractions</a>.
Mark Dominus explains why the 2/n table in the Rhind Papyrus is
sufficient for calculation of any more general Egyptian fraction.</li>

<li><a href="http://www.maa.org/editorial/mathgames/mathgames_07_19_04.html">Math
Games: Egyptian Fractions</a>.  Ed Pegg describes the Rhind Papyrus and
the 4/n problem, including a pretty density plot of the number of terms
required in the shortest egyptian fraction representation of rationals
with small numerators and denominators.</li>

<li><a href="http://arxiv.org/abs/math.CA/0502247">Approximating
1 from below by <i>n</i> Egyptian fractions.
A short proof that the greedy algorithm finds the largest <i>n</i>-term
Egyptian fraction less than one.</li>

<li><a href="http://web.archive.org/web/20041011115101/http://www.izzycat.org/math/index.php?p=39">Izzycat
investigates odd Egyptian fraction representations of unity</a>.
See also <a href="http://www.primepuzzles.net/problems/prob_035.htm">more
wrong turns</a>
and <a href="http://www.lboro.ac.uk/departments/ma/research/preprints/papers04/04-11.pdf">this paper by P. Shiu</a>.</li>

<li><a href="http://www.hostsrv.com/webmaa/app1/MSP/webm1010/egypt.msp">Web
Mathematica applet</a> for the greedy Egyptian fraction algorithm.</li>

<li><a href="http://math.ucr.edu/home/baez/week182.html">This
week's finds in Egyptian fractions</a>, John Baez.</li>

<li><a href="http://garnet.acns.fsu.edu/~jlc3724/efraction.html">Madison
Capps' science fair project</a>.</li>

<li><a href="http://www.math.gatech.edu/~ecroot/binary.pdf">Binary
Egyptian Fractions</a> and <a href="">other Egyptian fraction papers
by Ernie Croot</a>.</li>

<li><a href="http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fractions/egyptian.html">Egyptian Fractions</a> page by Ron Knott.</li>

<li><a href="http://www.ms.uky.edu/~carl/ma330/html/egfrac1.html">Lecture
notes</a> from a section on Egyptian fractions in a history of math course
by Carl Eberhart, U. Kentucky, including a Maple implementation of the
greedy algorithm.</li>

<li><a href="http://www.mathnerds.com/mathnerds/best/MagnificentSeven/problem.aspx">Best of Mathnerds:
the magnificent seven</a> asks for seven-term Egyptian fraction decompositions of 1, and describes a method for finding decompositions of any fraction
using a method based on Farey sequences
(essentially equivalent to
<a href="cfrac.html">the continued fraction method</a>).</li>

<li><a href="http://www.christs.cam.ac.uk/bio/papers/1998/samples/sample-paper.html">The 1998 British Informatics Olympiad</a>
used a sample programming question on Egyptian fractions, with
sample solutions including
a <a href="http://www.christs.cam.ac.uk/bio/programs/egyptian-fractions/example-a.html">Java applet for calculating 4-term representations</a>
of a value m/n by choosing a value d (sequentially testing d=1, d=2, d=3
etc), finding the divisors of nd (using a simple brute force loop rather
than any kind of factorization technique),
and looping through all permutations of the divisors testing
which ones have a prefix that sums to md (rather than using any kind of
dynamic program).</li>

<li><a href="http://web.archive.org/web/20010213235749/http://www.math.toronto.edu/~gerg/papers/diss.html">The Distribution of Prime Primitive Roots and Dense Egyptian
Fractions</a>, dissertation by Greg Martin.</li>

<li><a href="http://www.jimloy.com/egypt/fraction.htm">Jim Loy's
Egyptian fraction page</a>.</li>

<li><a href= 
"http://www.math.yorku.ca/Who/Faculty/Steprans/Courses/2042/EgyptianFractions/EgyptianFractions.html">
Julian Steprans uses Egyptian fractions for a homework
assignment</a>.</li>

<li><a href="http://math.uindy.edu/swett/esc.htm">The Erdos-Strauss
conjecture</a>. Allan Swett confirms that 4/n=1/x+1/y+1/z is
solvable for n up to 10<sup>12</sup>.</li>

<li><a href="http://www.3rd-imperium.com/Java/Math/egypt.html">Kris'
Egyptian fraction applet</a>. Seems to be using binary remainders?</li>

<li><a href="http://www.math.uiuc.edu/Bulletin/Abstracts/October/oct31-97analnotheory.html">A loving look at the unitary partition problem</A>.
Which numbers can be partitioned into distinct positive integers, the
reciprocals of which add to one?</li>

<li><a href="http://mathforum.org/wagon/fall97/p848.html">An odd
Egyptian puzzle</a> with <a href= 
"http://compgeom.cs.uiuc.edu/~jeffe/wagon/s848.html">many solutions</a>.
Stan Wagon's problem of the week #848, on odd representations of
3/179.</li>

<li>K. S. Brown's extensive work on Egyptian fractions includes
pages speculating on
<a href="http://www.mathpages.com/home/kmath340.htm">how the Egyptians
did it</a> as well as several on more number-theoretic concerns:
these pages on <a href=
"http://www.mathpages.com/home/kmath315.htm">unit fractions and
Fibonacci</a>, <a href=
"http://www.mathpages.com/home/kmath319.htm">the two Ohm
problem</a>, <a href="http://www.mathpages.com/home/kmath332.htm">
counting unit fraction partitions of unity</a>, <a href= 
"http://www.mathpages.com/home/kmath348.htm">minimizing
denominators in unit fraction expansions</a>,
<a href="http://www.mathpages.com/home/kmath453.htm">minimizing the
max denominator in a t-term expansion of 1</a>,
<a href="http://www.mathpages.com/home/kmath454.htm">odd greedy
stubbornness</a>,
<a href="http://www.mathpages.com/home/kmath455.htm">irrationality of
quadratic sums</a>, and
<a href="http://www.mathpages.com/home/kmath478.htm">wagon
trains and sticky wickets</a>
</li>

<li>The <a href="http://oldweb.cecm.sfu.ca/projects/ISC/">CECM Inverse
Symbolic Calculator</a> also mentions including Egyptian fraction
routines.</li>

<li>Milo Gardner has done extensive research on the <a
href="http://www.ecst.csuchico.edu/~atman/Misc/horus-eye.html">historical
methods used by the Egyptians to construct their tables of
fractions.</a>.</li>

<li><a href="http://www.aloha.net/~hawmtn/pyramid.htm">Terrance
Nevin</a> uses greedy Egyptian fraction methods as a basis for
investigating the dimensions of the Egyptian pyramids. 
</li>

<li><a
href="http://www.maths.usyd.edu.au:8000/u/magma/htmlhelp/text179.html#700">The
Magma symbolic algebra system</a> uses <a href="conflict.html#split">the
splitting method</a> for Egyptian fractions as an example of its sequence
manipulation features.</li>

<li><a href="http://mathforum.org/wagon/fall95/p799.html">
Is there a harmonic integer?</a> Stan Wagon asks if any integer <i>
k</i> has an Egyptian fraction representation 

<center>
<table cellpadding="0" cellspacing="0">
<tr align="CENTER" valign="BOTTOM">
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
<td></td>
<td>1</td>
</tr>

<tr align="CENTER" valign="middle">
<td><i>k</i>&nbsp;&nbsp;=&nbsp;&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;&nbsp;+&nbsp;&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;&nbsp;+&nbsp;&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>&nbsp;&nbsp;+&nbsp;&nbsp;</td>
<td>
<hr noshade size="1">
</td>
<td>
&nbsp;&nbsp;+&nbsp;&nbsp;&middot;&middot;&middot;&nbsp;&nbsp;+&nbsp;&nbsp;</td>
<td>
<hr noshade size="1">
</td>
</tr>

<tr align="CENTER" valign="TOP">
<td></td>
<td>2</td>
<td></td>
<td>3</td>
<td></td>
<td>4</td>
<td></td>
<td>5</td>
<td></td>
<td><i>n</i></td>
</tr>
</table>
</center>

<p>(Hint: consider the largest power of two less than or equal to
<i>n</i>.)</p>
</li>

<li><a href="http://mathworld.wolfram.com/UnitFraction.html">Unit
Fractions</a> from Eric Weisstein's treasure trove of
Mathematics.</li>

<li><a href="http://www.math.ubc.ca/~cayf/theprojects.html">
Undergraduate projects</a>. This list of possible projects includes
a very brief mention of Egyptian fractions.</li>

<li><a href="http://jwilson.coe.uga.edu/emt725/Unit/unit.html">
Problem: sum of unit fractions</a>. Which numbers <i>
n</i>/(<i>n</i>+1) have a two-term Egyptian fraction
representation? Problem from a U. Georgia summer course in
mathematical problem solving.</li>

<li><a
href="http://scienceblogs.com/goodmath/2006/11/egyptian_fractions.php">Good
Math, Bad Math: Egyptian Fractions</a>.</li>
</ul>

<hr>
<p><a href="/~eppstein/numth/">Number-theoretic hacks</a>, <a href= 
"/~eppstein/">David Eppstein</a>, <a href="/">Dept. Inf. &amp;
Comp. Sci.</a>, <a href="http://www.uci.edu/">UC Irvine</a>.</p>

<p><small>Last update: 
13 Jan 2007, 14:18:55 PST</small></p>
</body>
</html>

