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 

Button

Why is this tagged "artificial-intelligence"? – Aldosterone

More of a math / number theory question. See mathworld.wolfram.com/EgyptianFraction.html for lots of links. – Kep

@In silico why did you remove math tag, which I add?? Actually this is a mathematical question. – Bacterium

What do you mean by "good method"? Easy to implement? Shortest length expansion? Quickest to execute? Something else? – Geest

any algorithm that has some features as you said, Quickest to execute is a very nice one – Button

@Ashot Martirosyan: I didn't remove the [math] tag from this question which obviously has to do with math. I'm not math-illiterate. I'm 100% sure I removed the [artificial-intelligence] flag. – Ivers

@In silico: From the timestamps, I guess it was an edit clash. – Hong

@Ashot Martirosyan: According to the revisions page, I submitted my edit 1 second after you submitted your edit, so I obviously didn't see that you have already fixed the [artificial-intelligence] before I submitted my edit. – Ivers

@In silico it's Ok, No problem :) – Bacterium

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

Prevot

Answer 2

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.

Approximate

@quasiverse: It's not, but the Egyptians had special symbols for 2/3 and 3/4 instead of being required to write 1/2+1/6 or 1/2+1/4. – Prevot

Taking @dano04's comment that 2/3 and 3/4 were given special treatment, the second paragraph of the explanation is puzzling to me. Why isn't 3/4 a better starting point than 2/3? 7/8 = 1/2 + 1/4 + 1/8 looks simpler to me than 7/8 = 1/2 + 1/6 + 1/5 + 1/120 (aka: 7/8 = 1/2 + 1/5 + 1/6 + 1/120). One reason might be that the reference didn't recognize 3/4 as having special treatment; I'm not sure whether there are any others. – Claar

Answer 3

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!

Duvall

And how would it work for 6/7, where prime factors are 2, 3 and 7? – Chilon

@Andrey Prime factors are all prime factors of 42. I shouldn't have used the word "union" in there without further clarification. – Duvall

Answer 4

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

Malave