Unit Fractions and the Greedy Algorithm
Date: 12/27/2000 at 07:28:12 From: Tok Foon Subject: Express 2000/2001 using unit fractions Dear Dr. Math, I've found many ways to express 1999/2000 as a sum of distinct positive unit fractions. For example, two of the many possible ways are 1/10 + 1/50 + 1/250 + 1/2000 and 1/10 + 1/50 + 1/400 + 1/500. I tried, but don't seem to be able to express 2000/2001 as a sum of distinct positive unit fractions. I'm beginning to wonder if there is any solution. Hope someone can help.
Date: 12/27/2000 at 11:01:55 From: Doctor Rob Subject: Re: Express 2000/2001 using unit fractions Thanks for writing to Ask Dr. Math, Tok Foon. Sorry, but the two sums you gave add up to 249/2000, not to 1999/2000. You apparently left off 1/2 + 1/4 + 1/8 from the front of each sum. What you ask can always be done. One way is to use the Greedy Algorithm. For the first fraction, choose the largest unit fraction not greater than the target number. Subtract that, and repeat. This method will always terminate. For example, for 1999/2000, the largest unit fraction not greater than it is 1/2. Then: 1999/2000 - 1/2 = 999/2000 Next, the largest unit fraction not greater than 999/2000 is 1/3, and: 999/2000 - 1/3 = 997/6000 Continuing in this way, you get: 1999/2000 = 1/2 + 1/3 + 1/7 + 1/43 + 1/18619 + 1/781998000 This won't always give you the shortest sum, or the one with the smallest denominators, but it will always work. There are always infinitely many ways to write any fraction as a sum of distinct unit fractions. For example, you can always replace the smallest fraction in the sum, 1/A, by 1/A = 1/(2*A) + 1/(3*A) + 1/(6*A) and get a different, larger set of fractions with the same sum. Now try 2000/2001 again. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.