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.
\nObviously, 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
\n“1\/2 + 1\/6”.<\/p>\n
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[43],"tags":[],"class_list":["post-212","post","type-post","status-publish","format-standard","hentry","category-numbers"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3q","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/212","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=212"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/212\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nHistory
\n————
\nWe 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.
\nThat 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
\nscroll, 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
\npart of the priestly class in Egypt, usually temple scribes. Things like advanced math were considered a sort of sacred mystery, reserved to the temples.)
\nSo 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.
\nAs 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.
\nNot 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.)
\nComputing Egyptian Fraction Form
\n————————————
\nThe 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
\negyptian fraction form, but it is guaranteed to terminate with a finite (if ugly) sequence.
\nThe basic idea of the algorithm is:
\nGiven a vulgar fraction x\/y, the egyptian form egypt(x\/y) = 1\/(⌈y\/x⌉) + egypt(remainder),
\nwhere remainder=(-y mod x)\/(y×⌈y\/x⌉).
\nOr, 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”.)
\negypt :: Rational -> [Rational]
\negypt 0 = []
\negypt fraction =
\n(1%denom):(remainders) where
\nx = numerator fraction
\ny = denominator fraction
\ndenom = ceiling (y%x)
\nremx = (-y) `mod` x
\nremy = y*denom
\nremainders = egypt (remx%remy)
\n*(Thanks to Bruno for helping me fix the stupid problem with the code above.) *
\nAnd for fun, the reverse process, converting from the Egyptian form to vulgar:
\nvulgar :: [Rational] -> Rational
\nvulgar r = foldl (+) 0 r
\nA few examples of fractions in Egyptian form:
\n* 4\/5 = 1\/2 + 1\/4 + 1\/20
\n* 9\/31 = 1\/4 + 1\/25 + 1\/3100
\n* 21\/50 = 1\/3 + 1\/12 + 1\/300
\n* 1023\/1024 = 1\/2 + 1\/3 + 1\/7 + 1\/44 + 1\/9462 + 1\/373029888
\nAs you can see, the Fibonacci algorithm for Egyptian fractions can generate some really
\nugly 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.
\nThe 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.
\nConclusion
\n————–
\nWhat’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
\nalways using unit fractions overwhelmed the practicality of tractable arithmetic.
\nThere 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<\/sup>, but no one has been able to figure out how to prove it.<\/p>\n","protected":false},"excerpt":{"rendered":"