Egyptian Fractions

While I was researching yesterdays post on Archimedes integration, one of the things I read reminded me of one of the stranger things about Greek and earlier math. They had a notion that the only valid fractions were *unit* fractions; that is, fractions whose numerator is 1. A fraction that was written with a numerator larger than one was considered *wrong*. Even today, if you look in a lot of math books, they use the term “vulgar fraction” for non-unit fractions.
Obviously, there *are* fractions other that *1/n*. The way that they represented them is now known as *Egyptian fractions*. An Egyptian fraction is expressed as the sum of a finite set of unit fractions. So, for example, instead of writing the vulgar fraction 2/3, the Greeks would write
“1/2 + 1/6”.


History
————
We don’t know that much about the origins of Egyptian fractions. What we do know is that the earliest written record of their use is in an Egyptian scroll from roughly the 18th century BC, which is why they’re known as Egyptian fractions.
That scroll, known as the *Rhind Papyrus* is one of the most fascinating things in the entire history of mathematics. It appears to be something along the lines of a *textbook* of Egyptian mathematics: a set of questions written roughly in the form of test questions, and fully worked answers. The scroll includes tables of fractions written in unit-fraction sum form, as well as numerous algebra (in roughly the equational reasoning form we use today!) and geometry problems. From the wording of the
scroll, it’s strongly implied that the author is recording techniques well-known by the mathematicians of the day, but kept secret from the masses. (What we would call mathematicians were
part of the priestly class in Egypt, usually temple scribes. Things like advanced math were considered a sort of sacred mystery, reserved to the temples.)
So we don’t really know *when* they were invented, or by whom. But from the time of the Egyptians, through the empires of the Greeks and Romans, they continued to be considered the *correct* mathematical notation for fractions.
As I said in the introduction, vulgar fractions were considered to be ugly at best, and incorrect at worst, all the way into the middle ages. Fibonacci defined what is still pretty much the canonical algorithm for computing the Egyptian fraction form of a rational number.
Not too long after Fibonacci, the obsession with avoiding vulgar fractions declined. But they’ve stayed around both because of the historical documents that use them, and because they’re useful as a way for looking at certain problems in number theory. (Not to mention as a foundation for a lot of nifty mathematical puzzles.)
Computing Egyptian Fraction Form
————————————
The primary algorithm for computing the Egyptian fraction form is a classic example of what CS geeks like me call a *greedy algorithm*. The greedy algorithm doesn’t always generate the shortest possible
egyptian fraction form, but it is guaranteed to terminate with a finite (if ugly) sequence.
The basic idea of the algorithm is:
Given a vulgar fraction x/y, the egyptian form egypt(x/y) = 1/(⌈y/x⌉) + egypt(remainder),
where remainder=(-y mod x)/(y×⌈y/x⌉).
Or, in a slightly more useful form, here’s the above written as a Haskell program, which returns the list of unit fractions (For non-Haskell folks out there, x%y is a Haskell type constructor which creates the fraction x/y; and “x:y” creates a list with head “x” and tail “y”.)
egypt :: Rational -> [Rational]
egypt 0 = []
egypt fraction =
(1%denom):(remainders) where
x = numerator fraction
y = denominator fraction
denom = ceiling (y%x)
remx = (-y) `mod` x
remy = y*denom
remainders = egypt (remx%remy)
*(Thanks to Bruno for helping me fix the stupid problem with the code above.) *
And for fun, the reverse process, converting from the Egyptian form to vulgar:
vulgar :: [Rational] -> Rational
vulgar r = foldl (+) 0 r
A few examples of fractions in Egyptian form:
* 4/5 = 1/2 + 1/4 + 1/20
* 9/31 = 1/4 + 1/25 + 1/3100
* 21/50 = 1/3 + 1/12 + 1/300
* 1023/1024 = 1/2 + 1/3 + 1/7 + 1/44 + 1/9462 + 1/373029888
As you can see, the Fibonacci algorithm for Egyptian fractions can generate some really
ugly terms. It often generates sequences of fractions that are longer than necessary, and that include ridiculously large and awkward denominators. For example, the last fraction above can be written more clearly as (1/2 + 1/4 + 1/8 + 1/16 + 1/64 + 1/128 + 1/256 + 1/512 + 1/1024). One of the canonical examples of weakness of the Fibonacci algorithm is 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913+ 1/1527612795642093418846225, which can be written much more simply as 1/33 + 1/121 + 1/363.
The problem, though, is that the Fibonacci algorithm is the only *efficient* method we know for computing Egyptian fractions. *(Actually, I was wrong about the previous sentence. The sources that I was reading when I wrote the article were out of date, and I didn’t check the web the way I should have. In the comments, David Eppstein pointed out that there are much better algorithms that the greedy one, and [his website includes implementations of a number of them](http://www.ics.uci.edu/~eppstein/numth/egypt/)*. We don’t know any particularly *good* ways of computing the minimal length forms. In fact, we don’t even know what the complexity bounds of computing a minimal Egyptian fraction are.
Conclusion
————–
What’s I find particularly interesting about Egyptian fractions is how long they lasted, given how incredibly hard to work with they are. Adding fractions in Egyptian form is difficult; multiplying two fractions is absolutely insane. Multiplying an integer by an Egyptian fraction is a pain, but not as bad as multiplying two Egyptian fractions. From a purely practical standpoint, they seem downright ridiculous. As early as 150 AD, they were roundly critiqued by Ptolemy himself! And yet, they were *the* way that fractions were written for close to three *thousand* years. The aesthetics of
always using unit fractions overwhelmed the practicality of tractable arithmetic.
There are a bunch of interesting open problems involving Egyptian fractions: I’ll just leave you with one example that I found on Wikipedia. Paul Erdös, the great Hungarian mathematician, tried to prove that for any fraction 4/n, there was an Egyptian fraction containing exactly three terms. Doing brute force tests, it’s been shown to be true for every number *n* smaller than 1014, but no one has been able to figure out how to prove it.

0 thoughts on “Egyptian Fractions

  1. Bruno Martínez

    The haskell code can be written like:
    import Ratio
    egypt :: Rational -> [Rational]
    egypt 0 = []
    egypt fraction =
    (1%denom):(remainders) where
    x = numerator fraction
    y = denominator fraction
    denom=ceiling(y%x)
    remx = (-y) `mod` x
    remy = y*denom
    remainders = egypt (remx%remy)

    Reply
  2. Mark C. Chu-Carroll

    Thanks Bruno… That makes sense; by using the “/” operator, I was mixing in real-number operations, which is why it was griping about needing a type constraint for RealFrac.

    Reply
  3. John Armstrong

    Paul Erdös, the great Hungarian mathematician, tried to prove that for any fraction 4/n, there was an Egyptian fraction containing exactly three terms. Doing brute force tests, it’s been shown to be true for every number n smaller than 1014, but no one has been able to figure out how to prove it.

    If someone figures out how to prove it, can they list Erdös as a co-author?

    Reply
  4. Blake Stacey

    From pages 37–38 of George Sarton’s Ancient Science Through the Golden Age of Greece:

    Before describing the contents of the Rhind papyrus, it is necessary to explain the Egyptian idea of a fraction. For some strange reason the only fractions acceptable to them were those of the type 1/n (the nth part); they wrote it “part 125,” meaning 1/125. They also used two “complementary” fractions, 2/3 and 3/4 (each expressing the remainder when “part three” or “part four” is taken away). Their use of the second one — “three parts” — is rare, but that of the first — “two parts” (meaning two thirds) — is very common. The fraction 2/3 was represented by a separate symbol, which occurs frequently in the mathematical texts.

    Reply
  5. D. Eppstein

    The problem, though, is that the Fibonacci algorithm is the only efficient method we know for computing Egyptian fractions.
    This is grossly false. Not only do we know lots of efficient algorithms, but the greedy algorithm isn’t one of them due to its need for ridiculously high precision integer arithmetic.
    See e.g. http://www.ics.uci.edu/~eppstein/numth/egypt/ for descriptions of some better algorithms (along with the greedy one) implemented in Python and Mathematica.

    Reply
  6. Mark C

    I love life’s little goofy coincidences, or whatever they are. Just today I taught a lesson on Egyptian fractions to my advanced 6th grade class. It was a great extension activity and linked perfectly to a history unit on Ancient Egypt. Thanks for the history. The algorithms are a bit over our heads, but otherwise cool stuff.

    Reply
  7. nikita

    Hm… I checked a few sources (wikipedia, mathworld) and nowhere “vulgar fraction” is defined as one with non-unit nominator. It’s either defined as any expression on the form p/q with integer p and q (as opposed to “decimal fraction”), or as a fraction where absolute value of nominator is smaller than absolute value of denominator.
    Incidentially, Unicode has characters like “VULGAR FRACTION ONE QUARTER” (U+00BC, ¼).

    Reply
  8. Mark C. Chu-Carroll

    David:
    Thanks for the correction. My sources were out of date, and I didn’t do the kind of web-lit search that I should have before making a statement like that. I’ve added a correction to the post, and provided a link to your site.

    Reply
  9. Mark C. Chu-Carroll

    nikita:
    I’m not sure *where* I learned the term “vulgar fraction”; it’s something that I’ve known for an incredibly long time. I probably learned it in something like sixth grade! I was definitely taught that it was a fraction with a non-unit numerator, and that that was the reason it was called “vulgar”; unit fractions were considered clean and elegant, but non-unit fractions were considered ugly, and thus vulgar.
    I’m willing to admit that I might be wrong about it, but that is the way I was taught. I suppose that’s what I get for trusting a mediocre schoolteacher. (I didn’t have any really good math teachers until high school; before that, the people who taught math ranged from awful to mediocre.)

    Reply
  10. AJS

    Call me a heretic if you will, but I personally don’t see much practical value in any form of ratiometric notation for fractions. If pressed, I would say that they belong in the same sort of category as Roman numerals. Obviously, rational numbers exist; but I would seriously question the value of teaching all kids that 1/4 + 1/6 = 5/12.
    The “point” (or comma, for our Continental cousins) notation works well enough for day-to-day use. After all, nearly everything in Real Life goes up in powers of ten; a hundred pence in a pound, a hundred cents in a dollar, a thousand millilitres in a litre. Write extra zeros, and you can easily switch between measuring units; 0.5 of a kilogramme is 0.500kg or 500g. (Although it’s often called a decimal point, the notation is equally applicable to any number base; for example, three-quarters in hex is written “0x0.c”. Computers usually use binary fractions and exponential notation internally.)
    In a lot of real-world applications, long fractional parts don’t matter because there will be rounding issues. If I have a space 2m. high and I want to fit in six evenly-spaced shelves, they will be 2 / (6 + 1) = 0.285714285714… m. apart. Seeing as I can’t read a tape measure to anything better than 0.0005m. accuracy, I’ll just space them 285mm. apart and leave a bit of extra space at one end.
    What is interesting is that the exact value of a recurring fraction is given by the recurring part divided by as many 9s (assuming base 10) as there are in that part, followed by as many zeros as precede it. In the example above, we have 2/7 = 0.285714285714… with the recurring part being 285714. And indeed we find that 285714/999999 is equal to 2/7. In the case of 0.001010101… the recurring part is 10 (giving 10/99) but there are 2 digits in front of it, so it is actually 10/9900.

    Reply
  11. Blake Stacey

    MarkCC wrote:

    I’m willing to admit that I might be wrong about it, but that is the way I was taught. I suppose that’s what I get for trusting a mediocre schoolteacher. (I didn’t have any really good math teachers until high school; before that, the people who taught math ranged from awful to mediocre.)

    This sounds like a familiar story. I had good math teachers in fourth, fifth and sixth grades, followed by a long stretch of indifferent or actively harmful ones until my senior year of high school. It probably didn’t help that the Alabama state curriculum required us to waste a year on “pre-calculus”, a year in which my math skills would have atrophied entirely if it weren’t for Feynman books and Project Mathematics! reruns on the NASA Channel.

    Reply
  12. Xanthir, FCD

    Call me a heretic if you will, but I personally don’t see much practical value in any form of ratiometric notation for fractions. If pressed, I would say that they belong in the same sort of category as Roman numerals. Obviously, rational numbers exist; but I would seriously question the value of teaching all kids that 1/4 + 1/6 = 5/12.

    I’d disagree. First, you advocate sticking with decimal notation for everything non-integral. That may be okay for a lot of real-world applications, but it’s approximate, which loses automatically in real math.
    The difference between ‘ratiometric’ fractions and Roman numerals is that we *have* a better way to represent numbers exactly, so we don’t have to use Roman numerals. Radix notation is probably the clearest, most compact, most operationally simple way we’ll ever have of representing integers.
    The same is true of using fractions to represent rationals, imo. When working with radix numbers, radix rationals are easier to work with. When working with ratios, though, fractions are by far easier and more intuitive. Unless, of course, you’re willing to argue that it’s easier to multiply 0.285714 by 3 than it is to multiply 1/7 by 3, in which case I’d call you a liar. ^_^ When you actually need to use the number you’ll convert the fraction to radix, but while you’re working with ratios (cut that in half, then divide it into fifths, and make everything 2/3s larger…) the fractional form is infinitely better.
    Roman numerals were simply an upgrade from unary, and when we discovered radix notation we gained everything and lost nothing. (Modern) fractions hold a similar relationship to Egyptian fractions – the old things were ugly, disgusting bits of work to do anything complex with, while the new ones are quite easy to manipulate. Fractions aren’t perfect for every application, but they very well may be the best we’ll ever have for what they are good at.

    Reply
  13. Blake Stacey

    I don’t think you can get rid of “ratiometric notation”. When you do algebra, you end up forming quotients of variables: a/b, x^2/A and so forth. There is no way to write these in radix notation, so you’re stuck using that old slash and horizontal line. Now, tell a student to substitute x = 3, A = 2 into such an expression and evaluate the result. They’ll be putting numbers above and below a horizontal line, same as always, even if you do make them do extra work and convert to decimal after that.

    Reply
  14. rpsms

    “The aesthetics of always using unit fractions overwhelmed the practicality of tractable arithmetic”
    Perhaps it was dogma (of a priestly class) rather than pure aesthetics.

    Reply
  15. Jonathan Lubin

    Please remember that “vulgar” doesn’t mean obscene here, it means having to do with vulgus the crowd; common. I was under the impression that “vulgar fraction” was the British usage, and that the other was the American.

    Reply
  16. Alon Levy

    In algebra, decimal notation only works when you use analytic properties of convergence. Elements of Q endowed with the absolute value metric can be represented as decimals; but if you want to consider other valuations, the system breaks down. I don’t think anyone’s prepared to casually write 1/3 as not 0.3 in radix 10 but as 132 in radix 5.

    Reply
  17. Mark C. Chu-Carroll

    Harald:
    Yes, you’re right.
    I’m definitely a rank beginner in Haskell. I’ve recently picked it up after not looking at it for about 8 years, and while I remember the basic structure of the language, I’ve completely forgotten the libraries. In particular, I know that the list operators in Haskell are fantastic, but I have trouble remembering which are which; I tend to get scrambled on the differences between fold, map, zip, etc. So I’ve been forcing myself to code using the most basic operators to help get them clear in my head.

    Reply
  18. N@

    Thanks for the Erdos-Straus conjecture mention at the end. It made for a fun beginner project to code an algorithm in Python that finds x, y, and z for a given n. Of course, rather than use the Fibonacci algorithm, I had to invent one based in geometry. It’s not really much different, but I started by picturing a circle sliced n times, and then taking the area of four slices 1/n in size. Basically, what Erdos is saying is that you can slice the circle x, y, and z times, add those slices together, and get 4/n (for some x, y, and zN). First, I tried trisecting the angle so that x = ⌈3n/4⌉. I set y equal to the smallest integer that would satisfy 1/y < 4/n – 1/x, then solved for z. While y < that initial z, I incremented y and checked to see if the resulting zN. Then I decremented x, and repeated the process until x > n/4. I realize it’s not too different from the brute force method described above, but it did find a result for n = 17. Then I did the same thing, but starting with an initial bisection. Not bad for a guy who flunked Calculus in college!

    Reply
  19. Milo Gardner

    Mark,
    Your Egyptian fraction post from 2006 was used by a student John-Yves T. as the basis of an academic paper. Due to your false assumptions and misguided comments, two being the unknown origin(s) of Egyptian fractions, and the reasons behind 3,500 years use of vulgar fractions, John-Yves should be given an F on his paper.
    More than likely he’ll receive an A since your false assumptions, two additional ones — the multiplication and division methods, decoded in aliquot arithmetic, used by Ahmes, are commonly held.
    As an attempt to correct your many false assumptions, my personal blog introduces 20 years of study on the topic — by applying cryptanalysis methods learned 50 years ago —
    Over 12 paper/blogs on the topic are available for your review.
    Read:
    http://rmprectotable.blogspot.com first, since the area of ancient number theory contains the majority of your false assumptions, and then my blog:
    http://milorgardner.blogspot.com/2008/08/milo-gardner-personal-info.html
    Best Regards,
    Milo Gardner

    Reply
  20. milo gardner

    Mark,
    I found a review that was submitted to John-Yves T. My expanded comments may be of interest, as well as a Wikipedia bio.
    Regards,
    Milo Gardner
    Egyptian Fractions (Bad math)
    Category: goodmath > Numbers
    Posted on: November 15, 2006 3:31 PM, by Mark C. Chu-Carroll
    While I was researching yesterdays post on Archimedes integration, one of the things I read reminded me of one of the stranger things about Greek and earlier math. They had a notion that the only valid fractions were unit fractions; that is, fractions whose numerator is 1. A fraction that was written with a numerator larger than one was considered wrong. Even today, if you look in a lot of math books, they use the term “vulgar fraction” for non-unit fractions.
    Obviously, there are fractions other that 1/n. The way that they represented them is now known as Egyptian fractions. An Egyptian fraction is expressed as the sum of a finite set of unit fractions. So, for example, instead of writing the vulgar fraction 2/3, the Greeks would write “1/2 + 1/6”.
    History
    We don’t know that much about the origins of Egyptian fractions. What we do know is that
    ***
    We do know the origins of Egyptian fractions. The Old Kingdom wrote binary fractions in infinite series, rounding off a 1/64 unit, by throwing it away. The Old Kingdom also experimented with unit fractions. Bt 2,000 BCE the 1/64 unit (named dja) was ‘healed’ , as Tanja Pemmerening received a PhD on the topic in 2006. Tanja only reported the practical side of the subject, yet, a rigorous definition of Egyptian division (using binary quotients and scaled remainders) showed that a hekat unity (64/64) was generally divided by n, in the range 1/64 [Rational]
    egypt 0 = []
    egypt fraction =
    (1%denom):(remainders) where
    x = numerator fraction
    y = denominator fraction
    denom = ceiling (y%x)
    remx = (-y) `mod` x
    remy = y*denom
    remainders = egypt (remx%remy)
    *(Thanks to Bruno for helping me fix the stupid problem with the code above.) *
    And for fun, the reverse process, converting from the Egyptian form to vulgar:
    vulgar :: [Rational] -> Rational
    vulgar r = foldl (+) 0 r
    A few examples of fractions in Egyptian form:
    * 4/5 = 1/2 + 1/4 + 1/20
    * 9/31 = 1/4 + 1/25 + 1/3100
    * 21/50 = 1/3 + 1/12 + 1/300
    * 1023/1024 = 1/2 + 1/3 + 1/7 + 1/44 + 1/9462 + 1/373029888
    As you can see, the Fibonacci algorithm for Egyptian fractions can generate some really ugly terms. It often generates sequences of fractions that are longer than necessary, and that include ridiculously large and awkward denominators. For example, the last fraction above can be written more clearly as (1/2 + 1/4 + 1/8 + 1/16 + 1/64 + 1/128 + 1/256 + 1/512 + 1/1024). One of the canonical examples of weakness of the Fibonacci algorithm is 5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913+ 1/1527612795642093418846225, which can be written much more simply as 1/33 + 1/121 + 1/363.
    The problem, though, is that the Fibonacci algorithm is the only efficient method we know for computing Egyptian fractions. (Actually, I was wrong about the previous sentence. The sources that I was reading when I wrote the article were out of date, and I didn’t check the web the way I should have. In the comments, David Eppstein pointed out that there are much better algorithms that the greedy one, and his website includes implementations of a number of them. We don’t know any particularly good ways of computing the minimal length forms. In fact, we don’t even know what the complexity bounds of computing a minimal Egyptian fraction are.
    Conclusion
    What’s I find particularly interesting about Egyptian fractions is how long they lasted, given how incredibly hard to work with they are.
    ***Egyptian fractions were easy to work with. Only modern misgused folks using algorithms have had difficulty with the topic!!! ***
    Adding fractions in Egyptian form is difficult; multiplying two fractions is absolutely insane.
    *** Insanity derives from false definitions of Egyptian multiplication and division. Theoretical multiplication and divison looked and acted much as we consider the subjects today***
    Multiplying an integer by an Egyptian fraction is a pain,
    ***then find a simpler method. Ahmes did!! ***
    but not as bad as multiplying two Egyptian fractions. From a purely practical standpoint, they seem downright ridiculous.
    **yes, your series of false assumptions have created a strawman of great size***
    As early as 150 AD, they were roundly critiqued by Ptolemy himself! And yet, they were the way that fractions were written for close to three thousand years. The aesthetics of always using unit fractions overwhelmed the practicality of tractable arithmetic.
    *** what gibberish***
    There are a bunch of interesting open problems involving Egyptian fractions: I’ll just leave you with one example that I found on Wikipedia. Paul Erdös, the great Hungarian mathematician, tried to prove that for any fraction 4/n, there was an Egyptian fraction containing exactly three terms. Doing brute force tests, it’s been shown to be true for every number n smaller than 1014, but no one has been able to figure out how to prove it.

    *** Erdos has not offer an open question that relates to Ahmes Egyptian fractions. Ahmes converted n/p and n/pq by a small set of rule, maybe five (four of which were cited by Fibonacci), allowing 2-term, 3-term, 4-term and higher seris of Egyptian fractions, if needed, Erdos sadly asked that 4/n be only converte to a 3-term series — Ahmes, Fibonaccu, or any Greek would never have asked such as STUPID question!!!
    Summary
    Modern number theory and its modern programming effortst, i.e. Mathematica, do not understand, and wish not to grash the seven seven rules set down by Fibonacci. When the McLeish’s of this world update their texts, the history of number theory will properly include Fibonacci, Arabs, Greeks and Egyptians as they wrote Egyptian fractons.
    Until that time, we must suffer through Eurocentric rhetoric — that adores base 10 decimals and ‘hates’ every thing about Egyptian fractions.***
    Best Regards,
    Milo

    Reply
  21. Mounir El Araki

    I doubt that egyptians were understanding fraction the way we do now. It is not until late 6th or 7th century AD that algebra and number theory started to develop seriously.
    The fractions have a lot to do with the unity, meaning that when you fraction a unit you should always get more fractions out of it, however unity is never lost. Alkhawarizmi (Algorithm got its name from him) started many of the fraction theories.
    In my opinion, and with the little knowledge I have on ancient egypt, egyptians were more concerned on collecting taxes (one fraction of the harvest, could change depending on nile level). So, in my modest opinion, 1/2, 1/3 or 1/100 were just specific hieroglyphs, and I doubt that 1/371 existed in ancient egypt.

    Reply
  22. pablo

    egypt :: Rational -> [Rational]
    egypt 0 = []
    egypt fraction =
    (1%denom):(remainders) where
    x = numerator fraction
    y = denominator fraction
    denom=ceiling(y%x)
    remx = (-y) `mod` x
    remy = y*denom
    remainders = egypt (remx%remy

    Reply

Leave a Reply to Mark C. Chu-Carroll Cancel reply