[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? -- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
Yes, since sum 1/n diverges, even though you omit a finitenumber of terms. R. On Mon, 12 Sep 2005, Mike Stay wrote:
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Or: Should such an r appear, replace it with {r/2,r/3,r/6}. Lather, rinse, repeat. At 11:35 AM 9/12/2005, Richard Guy wrote:
Yes, since sum 1/n diverges, even though you omit a finitenumber of terms. R.
On Mon, 12 Sep 2005, Mike Stay wrote:
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Harumph. Suppose R = {1, 1/2, 1/3}, and the problem is to rerepresent 3/2? The starting rep is 1 + 1/2. We replace 1 with 1/2 + 1/3 + 1/6, giving 2*1/2 + 1/3 + 1/6. Replacing the 1/2 in turn with 1/4 + 1/6 + 1/12 isn't progress -- we'll never get rid of the duplicated children of the duplicate 2*1/2. Thm: Given any integer N, any rational q can be represented as the finite sum of unit fractions whose denominators are all distinct and >= N. The number of terms doesn't exceed <messy formula>. Proof sketch: Start with 1/N + 1/(N+1) + ..., debiting q until eventually q' < 1/N'. Then follow the usual greedy strategy of subtracting 1/ceiling[1/q']. The first step will terminate becuase sum(1/N) diverges. We can estimate the place of termination with the log estimate for sum(1/N). The numerator and denominator of q' are potentially huge, but there is a formulaic bound, some factorial. The ceiling step terminates because the numerator decreases at each stage. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Marc LeBrun Sent: Mon 9/12/2005 12:56 PM To: math-fun Cc: math-fun; metaweta@gmail.com Subject: Re: [math-fun] Egyptian fractions question Or: Should such an r appear, replace it with {r/2,r/3,r/6}. Lather, rinse, repeat. At 11:35 AM 9/12/2005, Richard Guy wrote:
Yes, since sum 1/n diverges, even though you omit a finitenumber of terms. R.
On Mon, 12 Sep 2005, Mike Stay wrote:
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
e.g., 3/2=1/4+1/5+1/6+1/7+1/8+1/9+1/10+1/11+1/12+1/13+1/14+1/15+1/70+1/1386+1/10296 R. On Mon, 12 Sep 2005, Schroeppel, Richard wrote:
Harumph. Suppose R = {1, 1/2, 1/3}, and the problem is to rerepresent 3/2? The starting rep is 1 + 1/2. We replace 1 with 1/2 + 1/3 + 1/6, giving 2*1/2 + 1/3 + 1/6. Replacing the 1/2 in turn with 1/4 + 1/6 + 1/12 isn't progress -- we'll never get rid of the duplicated children of the duplicate 2*1/2.
Thm: Given any integer N, any rational q can be represented as the finite sum of unit fractions whose denominators are all distinct and >= N. The number of terms doesn't exceed <messy formula>.
Proof sketch: Start with 1/N + 1/(N+1) + ..., debiting q until eventually q' < 1/N'. Then follow the usual greedy strategy of subtracting 1/ceiling[1/q']. The first step will terminate becuase sum(1/N) diverges. We can estimate the place of termination with the log estimate for sum(1/N). The numerator and denominator of q' are potentially huge, but there is a formulaic bound, some factorial. The ceiling step terminates because the numerator decreases at each stage.
Rich
-----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Marc LeBrun Sent: Mon 9/12/2005 12:56 PM To: math-fun Cc: math-fun; metaweta@gmail.com Subject: Re: [math-fun] Egyptian fractions question
Or: Should such an r appear, replace it with {r/2,r/3,r/6}. Lather, rinse, repeat.
At 11:35 AM 9/12/2005, Richard Guy wrote:
Yes, since sum 1/n diverges, even though you omit a finitenumber of terms. R.
On Mon, 12 Sep 2005, Mike Stay wrote:
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Another option (though not as elegant) would be, given n repetitions, to find n more sets that sum to one such that the denominators between sets are coprime and apply those. On 9/12/05, Richard Guy <rkg@cpsc.ucalgary.ca> wrote:
e.g., 3/2=1/4+1/5+1/6+1/7+1/8+1/9+1/10+1/11+1/12+1/13+1/14+1/15+1/70+1/1386+1/10296 R.
On Mon, 12 Sep 2005, Schroeppel, Richard wrote:
Harumph. Suppose R = {1, 1/2, 1/3}, and the problem is to rerepresent 3/2? The starting rep is 1 + 1/2. We replace 1 with 1/2 + 1/3 + 1/6, giving 2*1/2 + 1/3 + 1/6. Replacing the 1/2 in turn with 1/4 + 1/6 + 1/12 isn't progress -- we'll never get rid of the duplicated children of the duplicate 2*1/2.
Thm: Given any integer N, any rational q can be represented as the finite sum of unit fractions whose denominators are all distinct and >= N. The number of terms doesn't exceed <messy formula>.
Proof sketch: Start with 1/N + 1/(N+1) + ..., debiting q until eventually q' < 1/N'. Then follow the usual greedy strategy of subtracting 1/ceiling[1/q']. The first step will terminate becuase sum(1/N) diverges. We can estimate the place of termination with the log estimate for sum(1/N). The numerator and denominator of q' are potentially huge, but there is a formulaic bound, some factorial. The ceiling step terminates because the numerator decreases at each stage.
Rich
-----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of Marc LeBrun Sent: Mon 9/12/2005 12:56 PM To: math-fun Cc: math-fun; metaweta@gmail.com Subject: Re: [math-fun] Egyptian fractions question
Or: Should such an r appear, replace it with {r/2,r/3,r/6}. Lather, rinse, repeat.
At 11:35 AM 9/12/2005, Richard Guy wrote:
Yes, since sum 1/n diverges, even though you omit a finitenumber of terms. R.
On Mon, 12 Sep 2005, Mike Stay wrote:
Given a finite set R of unit fractions, is it possible to represent all rationals as Egyptian fractions without using elements of R?
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay metaweta@gmail.com http://math.ucr.edu/~mike
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
It could be tricky to prove termination. You're replacing one fraction with two. Rich -----Original Message----- From: math-fun-bounces+rschroe=sandia.gov@mailman.xmission.com on behalf of 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
participants (4)
-
Marc LeBrun -
Mike Stay -
Richard Guy -
Schroeppel, Richard