Egyptian Fractions in C

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 

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

Cropped from Egyptian Fractions

How did I come up with these values? Well, I estimated the fraction with the largest unit fraction that was just smaller than the given fraction. I subtracted this unit fraction from the given fraction. If this remainder was still not a unit fraction, I repeated the process, choosing the largest unit fraction that is smaller than this remainder. And the process could be repeated over and over.

Let's use 7/8 as an example. We estimate 7/8 with 2/3 (the largest unit fraction less than 7/8). We subtract 7/8 - 2/3, which is 5/24, which cannot be simplified into a unit fraction. So we estimate 5/24 with 1/5 (the largest unit fraction less than 5/24). We subtract 5/24-1/5, and we get 1/120, which is a unit fraction. So, 7/8=2/3 + 1/5 + 1/120.

For a / b, make MAX a * b.

Take the prime factors of MAX (which is the union of prime_fac(a) and prime_fac(b) and the multiples one each from those two lists) and iterate through them, starting low and going high.

Those are your possible 1/x's.

Edit: Oh yeah! Don't forget to take into consideration 2/3!

You asked a question on a website where people usually provide code in their answers. There are no other answers with code, C and Java are not my specialty, and so here is some code in Python.

#! /usr/bin/env python3
import fractions
import functools
import math


def main():
    f = fractions.Fraction(3, 4)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')
    f = fractions.Fraction(6, 7)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')
    f = fractions.Fraction(7654, 321)
    e = to_egyptian_fractions(f)
    print(*e, sep=' + ')


def validate(function):
    @functools.wraps(function)
    def wrapper(fraction):
        total = fractions.Fraction(0)
        for egyptian in function(fraction):
            if 1 not in {egyptian.numerator, egyptian.denominator}:
                raise AssertionError('function has failed validation')
            yield egyptian
            total += egyptian
        if total != fraction:
            raise AssertionError('function has failed validation')
    return wrapper


@validate
def to_egyptian_fractions(fraction):
    quotient = math.floor(fraction.numerator / fraction.denominator)
    if quotient:
        egyptian = fractions.Fraction(quotient, 1)
        yield egyptian
        fraction -= egyptian
    while fraction:
        quotient = math.ceil(fraction.denominator / fraction.numerator)
        egyptian = fractions.Fraction(1, quotient)
        yield egyptian
        fraction -= egyptian


if __name__ == '__main__':
    main()

Maybe others with find this to be useful as a simple guide while writing their own implementations. The program up above handles fractions with values greater than one and produces the following output.

1/2 + 1/4
1/2 + 1/3 + 1/42
23 + 1/2 + 1/3 + 1/92 + 1/29532