On 9/13/05, Schroeppel, Richard <rschroe@sandia.gov> wrote:
It could be tricky to prove termination. You're replacing one fraction with two.
Let's say we're trying to represent p/q as an EF without using elements of R. We write p copies of 1/q. If any unit fraction is in R, split it. Repeat until none are in R. Since R is finite, there's a largest denominator. Since the denominators increase, that has to terminate. Now we have a sum of unit fractions that might contain repetitions. Keep one copy and split the others. That process also terminates. The number of repetitions may increase due to collisions with terms already in the list, but it does so at most a finite number of times, and then it must decrease at each step after that: 1/3 + 1/3 + 1/4 + 1/12 + 1/20 one pair 1/3 + 1/4 + 1/12 + 1/4 + 1/12 +1/20 increases here to two pairs 1/3 + 1/4 + 1/12 + 1/5 + 1/20 + 1/20 decreases to one pair 1/3 + 1/4 + 1/12 + 1/5 + 1/20 + 1/21 + 1/420 done
Rich
-----Original Message----- From: Mike Stay Sent: Tue 9/13/2005 12:12 PM To: math-fun Subject: Re: [math-fun] Egyptian fractions question
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
(Slaps forehead) Just use the splitting relation 1/x = 1/(x+1) + 1/(x^2 + x). -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike