Sum of Unit FractionsDate: 07/17/2001 at 20:28:27 From: Candyce Subject: Java programing class Suppose that p/q is a fraction in lowest terms such that 1/(n+1) < p/q < 1/n for some positive integer n. Show that (p/q) - (1/(n+1)) is a fraction which in its lowest terms has numerator less than p. Hence by induction, prove that every proper fraction p/q with p < q can be written as a finite sum of distinct reciprocals of positive integers. For example, 19/15 = 1/2 + 1/3 + 1/4 + 1/6 + 1/60. Use this technique to express 5/7 as a sum of reciprocals. The example given here is correct, though it's not true that all fractions greater than 1 can be expressed finitely in this way (e.g. 2) - you've been asked to prove the statement only when the fraction is less than 1 (which is always true). If you want an example for this case, then 14/17 = 1/2 + 1/4 + 1/14 + 1/476. The problem is the PROFF part. I can understand that it works. Date: 07/18/2001 at 10:53:15 From: Doctor Paul Subject: Re: Java programing class Here's how to do it for fractions less than one (assumed to be in lowest terms): I'll show you how it works for 14/17 and you should be able to generalize it for any p/q. Given 14/17, find the largest unit fraction less than 14/17. I think the easiest way to do this is to systematically increment the denominator by one until the fraction reduces to a unit fraction. The reduced unit fraction will be the largest unit fraction less than the given number. In the case of 14/17, we first consider: 14/18 = 7/9, which is not a unit fraction, so we next consider 14/19, 14/20 = 7/10, 14/21 = 2/3, which is not a unit fraction, so we next consider 14/22, .... , 14/28 = 1/2. So we know that 1/2 is a unit fraction and we know that it is less than 14/17. Thus we can write: 14/17 = 1/2 + a/b where a/b is to be determined. subtract 1/2 from both sides to obtain: a/b = 14/17 - 1/2 = 11/34 Thus we have: 14/17 = 1/2 + 11/34 If a/b had turned out to be a unit fraction, we would be done. But since it isn't a unit fraction, we do the process again. We now want to convert 11/34 into a sum of unit fractions: Increase the denominator until you get a unit fraction: 11/35, 11/36, ... , 11/44 = 1/4 so 11/34 = 1/4 + c/d Hence, c/d = 11/34 - 1/4 = 5/68 So we have: 14/17 = 1/2 + 1/4 + 5/68 If c/d had been a unit fraction, we would be done. But since c/d was equal to 5/68, we now need to repeat the process and convert 5/68 into a unit fraction. increase denominators: 5/68, ..., 5/70 = 1/14 so we have: 5/68 = 1/14 + e/f e/f = 1/476 Since e/f is a unit fraction, we're done. We can now write the final result: 14/17 = 1/2 + 1/4 + 1/14 + 1/476, which is exactly the answer you gave above. This method is attributed to the British mathematician J.J. Sylvester (1814-1897). In general, the decomposition of a fraction into a sum of unit fractions is not unique. For example, 3/8 = 1/4 + 1/8 = 1/3 + 1/24. Since your subject is "Java programming class" I'm guessing that you have to implement this algorithm in Java. Obviously, you're going to need to run some sort of 'for' or 'until' loop to get this thing to run properly. I've never programmed in Java, but I think it's a great assignment in any programming language! Good luck. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/