Date: 06/11/2001 at 07:33:18 From: Andrew Subject: Egyptian Fractions I just got a problem solving a puzzle for maths that involves Egyptian fractions, e.g. 2/7 = 1/4 + 1/28. The Egyptians wrote all their fractions as a sum of different fractions with a numerator of 1. I need to find a way to work out what fractions should be added together to get the answer I require. I worked out that in the example 2/7 = 1/4 + 1/28, 2/(2i+1) = 1/(i+1) + 1/x, and that x is equal to 7 multiplied by 4. This rule only works, however, if the numerator of the number you are working out is 2, and even then only sometimes. Any suggestions?
Date: 06/11/2001 at 15:22:46 From: Doctor Rob Subject: Re: Egyptian Fractions Thanks for writing to Ask Dr. Math, Andrew. There is something called the Greedy Algorithm that always works. Suppose you are trying to write a/b as such a sum. Take for your first fraction 1/n, where n is the smallest integer greater than or equal to b/a. Then write a/b - 1/n = (n*a-b)/(b*n) = a'/b'. Repeat this procedure until a'/b' = 0, and stop. Example: a/b = 38/199, b/a = 199/38 = 5 + 9/38, so n = 6. Then 38/199 - 1/6 = (228-199)/1194 = 29/1194. Repeat with 29/1194. 1194/29 = 41 + 5/29, so n = 42 is next. Then 29/1194 - 1/42 = 2/4179. Repeat with 2/4179. 4179/2 = 2089 + 1/2, so n = 2090 is next. Then 2/4179 - 1/2090 = 1/8734110. Putting this all together, you get 38/199 = 1/6 + 1/42 + 1/2090 + 1/8734110. This always works, but it doesn't always give you the fewest fractions or the smallest denominators. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum