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

More of a math / number theory question. See http://mathworld.wolfram.com/EgyptianFraction.html for lots of links. — Vance Maverick, Mar 20 '11 at 05:56
@In silico why did you remove math tag, which I add?? Actually this is a mathematical question. — UmmaGumma, Mar 20 '11 at 05:59
What do you mean by "good method"? Easy to implement? Shortest length expansion? Quickest to execute? Something else? — Ted Hopp, Mar 20 '11 at 06:05
any algorithm that has some features as you said, Quickest to execute is a very nice one — edgarmtze, Mar 20 '11 at 06:08
@Ashot Martirosyan: I didn't remove the `[math]` tag from this question which obviously has to do with math. [I'm not math-illiterate](http://stackoverflow.com/questions/4159219/angle-measurer-in-c/4159284#4159284). I'm 100% sure I removed the `[artificial-intelligence]` flag. — In silico, Mar 20 '11 at 07:53
@In silico: From the timestamps, I guess it was an edit clash. — Donal Fellows, Mar 20 '11 at 07:55
@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. — In silico, Mar 20 '11 at 08:05

score 8 · Accepted Answer · answered Mar 20 '11 at 06:03

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

score 3 · Answer 2 · answered Mar 20 '11 at 06:00

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.

@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. — dan04, Mar 20 '11 at 06:08
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. — Jonathan Leffler, Apr 16 '11 at 22:27

corsiKa · Answer 3 · 2011-03-20T06:05:45.363

2

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!

edited Mar 20 '11 at 06:05

answered Mar 20 '11 at 05:54

corsiKa

81,495
25
153
204

And how would it work for `6/7`, where prime factors are `2`, `3` and `7`? – AnT stands with Russia Mar 20 '11 at 06:04
@Andrey Prime factors are all prime factors of 42. I shouldn't have used the word "union" in there without further clarification. – corsiKa Mar 20 '11 at 06:05

score 1 · Answer 4 · answered May 03 '16 at 16:28

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

Egyptian Fractions in C

4 Answers4

Linked