Thread: Help proving if this algorithm terminates

Ancient Egyptians were fond of writing general fractions as sums of fractions with unit numerator. Specifically, they would write 2/3 = 1/2 + 1/6,3/4 = 1/2 + 1/4 and, more exotically,6/7 = 1/2 + 1/3 + 1/42 . To be precise, we say that a rational number in the interval is written as an Egyptian fraction if it is written as a sum of a finite number of distinct unit fractions (so 2/17 = 1/17 + 1/17 is forbidden). Consider the following algorithm for writing a rational number (between 0 and 1) as an Egyptian fraction:

Algorithm E: If for some r = 1/d, output "1/d". Otherwise, find the largest unit fraction 1/d that is less than r ; output "1/d +"; repeat with the rational number r - 1/d .

Prove, using induction, that this process always terminates. (Hint: Try using induction on the numerator of the fraction.)



Alright, this is what I have so far :

Base case: R is of the form 1/d.
If R is of the form 1/d, then the program terminates by the algorithm's definition

So assume R = a/d, a != 0 and d > 0

If a is 1, then the program terminates
else a is greater than 1 and we apply r - 1/d

Examine the case for a + 1, since a + 1 > 1, we apply the second part of the algorithm, namely we repeat with the new fraction r2 = r - 1/d
since r = (a+1)/d,

r2 = (a+1)/d - 1/d
r2 = a/d +1/d - 1/d
r2 = a/d

Since we assume a/d is true, thus the algorithm terminates for all valid input.


I know I am probably way of, because this part of computer science is not my strong part, so I ask for help any guidance will be greatly appreciated. Thanks.

That does not work because the greatest unit fraction less than (or equal to) (a+1)/d is not in general 1/d. For example the greatest unit fraction less than 2/9 is 1/5, not 1/9. Actually I think it's never 1/d.

Strong induction, a bit tricky

Proof that the greedy algorithm for egyptian fractions terminates@Everything2.com

Thanks for the reply and the link. I really do not want to copy other people's work.
If one can provide me some foundation or some hints to work with, then I will greatly appreciate it.

Originally Posted by Matter_Math

Thanks for the reply and the link. I really do not want to copy other people's work.
If one can provide me some foundation or some hints to work with, then I will greatly appreciate it.

Sounds like a good way to go. Hints then: don't try to reduce (a+1)/d to a/d. Rather, write an arbitrary rational 0 < x/y < 1 and assume x does not divide y, then specify an inequality that expresses "1/d is the largest unit fraction less than x/y" and proceed to show that x/y - 1/d has a numerator less than x.

So I am back to this problem. I skipped it until it was the last one left.

So here is what I have so far.

Base Case :
If input r, is of the form 1/d, for some number d, then the algorithm haults.

Inductive step :
Assume the input r, is of the form x/y where not x|y and x != 1. Then 0 < x/y < 1.
Now assume 1/d is the largest unit fraction less than x/y. Thus
x/y - 1/d < x/y < 1
x - y/d < x < y


Am I taking the correct step? I am kind of stuck. I am reading your hints and I get it, but I cannot put it into proper notation. Thanks

Originally Posted by Matter_Math

So I am back to this problem. I skipped it until it was the last one left.

So here is what I have so far.

Base Case :
If input r, is of the form 1/d, for some number d, then the algorithm haults.

Inductive step :
Assume the input r, is of the form x/y where not x|y and x != 1. Then 0 < x/y < 1.
Now assume 1/d is the largest unit fraction less than x/y. Thus
x/y - 1/d < x/y < 1
x - y/d < x < y


Am I taking the correct step? I am kind of stuck. I am reading your hints and I get it, but I cannot put it into proper notation. Thanks

I'd say you're going in the right direction but should reformulate the inequality. Translating "1/d is the largest unit fraction less than x/y" will entail sandwiching x/y between two unit fractions, one of which is less than x/y, one of which is greater...