Egyptian Fractions

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)

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.

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?

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.

And I thought that "Ancient Egyption Algebra" was just a joke on Futurama.

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.

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.

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, ¼).

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.

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.)

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.

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.

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.

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.

"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.

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.

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.

>vulgar :: [Rational] -> Rational
>vulgar r = foldl (+) 0 r

Shouldn't sum r work just as well?

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.

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 z â N). 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 z â N. 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!

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

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 < x < 64 (in RMP 81), in one column and written in 1/10 hin units in a second column. That is, two weights and measures systems were used in ancient Egypt, the first based on theoretical unity measures, and second, 1/m units (such as 1/10 hin) were written as m/n 'unit'.The second unit system included 1/64 dja, written as 64/n dja and 1/320 ro written as 320/n ro (as needed for 1,000 medical prescriptions --- the topic of Tanja Pemmerening's PhD thesis).***

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.

*** Not true. The oldest complete Egyptian fraction document (Akhmim Wooden Tablet) dates to 2,000 BCE.The AWT gathers dust in a Cairo Museum, though Hana Vymazalova, a graduate student brushed it off for a 2002 paper - that showed that quotient and remainder (64/64)/n answers were proven by multiplying by n, returning n = 3, 7, 10, 11 and 13 to the original 64/64 unity value. Hana also gained a PhD in Egyptology, in another topic. Her breakthrough paper was published at Charles U. Prague.***

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.)

*** there were not secrets from the masses. Plato remarked 1,500 years later that shop keepers were happy to have an accurate system of currency and weights and measures -- since Greeks fully adopted Egyptian econometrics within the Egyptian fraction system***

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.

***Again, yes we do know.Those that declare ignorance - when sufficient facts are in evidence on a topic -- are only laying the ground work for false premises. This paper is filled with false premises. Only a few false premises will be pointed out. ***

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

***Not true. Rational numbers, n/p and n/pq, were concisely written into ciphered Egyptian and Greek alphabets via a small set of conversion rules. Greeks did not improve the 1,500 older system (though Greek texts are mostly lost - so little hard evidence is available), What is available or Arab and medieval texts. Fibonacci had copied Arab texts. Arab texts, around 800 ADE, had re-written ciphered numeration texts into Hindu base 10 numerals.

Fibonacci used the Egyptian fraction system listing seven conversion methods (four of which can easily be dated to the time of Ahmes, as mentioned in an earlier email).***

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.)

*** After the Silk Road was closed in 1454 AD, Europeans created their own routes to India and China, implementing several weights and measures systems, By 1600 base 10 decimals and base 10 metrics came into use, with the two systems replacing 3,6000 years of Egyptian fraction mathematics. The phrase 'avoding vulgar fractions' should only be applied to post -1600 AD base 10 decimal/metrics systems. Prior to 1500 AD everyone used and enjoyed 'vulgar fractions' written into Egyptian fraction series by 7 simple rules!! **
Computing Egyptian Fraction Form

***Egyptians had not used an algorithm, other than the cursive binary numeration system used in the Old Kingdom. Arabs formally created algorithms as we think of the term today, but even they did not use algorithms to convert vulgar fractions. This authors grossly confuses who did what, and when. Fibonacci also understood algorithms, though not as a method to convert vulgar fractions. Read Fibonacci's 7 conversion rules, on pages 124- 125 of Siglers books (and Sigler's incomplete footnotes) and see for yourself! **

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. 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

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.

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