Egyptian Fractions in C

Question

The ancient Egyptians only used fractions of the form 1/n so any other fraction had to be represented as a sum of such unit fractions and, furthermore, all the unit fractions were different!

What is a good method to make any fraction an egyptian fraction (the less sums better) in C or java, what algorithm can be used, branch and bound, a*?

for example:

3/4 = 1/2 + 1/4

6/7 = 1/2 + 1/3 + 1/42 

Answer 1

One way is the greedy algorithm. Given the fraction f, find the largest Egyptian fraction 1/n less than or equal to f (i.e., n = ceil(1/f)). Then repeat for the remainder f - 1/n, until f == 0.

So for 3/4, you'd compute:

• n = ceil(4/3) = 2; remainder = 3/4 - 1/2 = 1/4
• n = ceil(4) = 4; remainder = 1/4 - 1/4 = 0
• 3/4 = 1/2 + 1/4

And for 6/7:

• n = ceil(7/6) = 2; remainder = 6/7 - 1/2 = 5/14
• n = ceil(14/5) = 3; remainder = 5/14 - 1/3 = 1/42
• n = ceil(42) = 42; remainder = 1/42 - 1/42 = 0
• 6/7 = 1/2 + 1/3 + 1/42