Geek Answers Handbook

Egyptian fractions in C

The ancient Egyptians used only fractions of the form 1/n , so any other fraction should have been represented as the sum of such unit fractions and, in addition, all unit fractions were different!

What is a good way to make any fraction an Egyptian fraction (the smaller the sums the better) in C or java, which algorithm can I use, branch and bind, a *?

eg:

 3/4 = 1/2 + 1/4 6/7 = 1/2 + 1/3 + 1/42
+6
java c math algorithm fractions
source share
4 answers

One way is a 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 should calculate:

  • n = ceil (4/3) = 2 ; remainder = 3/4 - 1/2 = 1/4
  • n is 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
+8
source share

Cropped from Egyptian fractions

How did I come up with these values? Well, I rated the fraction with the largest specific share, which was simply less than that share. I subtracted this single fraction from this fraction. If this remainder was still not a unit, I repeated the process, choosing the largest specific fraction less than this remainder. And the process can be repeated over and over.

As an example, you can use 7/8. We score 7/8 with 2/3 (the largest single fraction is less than 7/8). We subtract 7/8 - 2/3, which is 5/24, which cannot be simplified per unit share. So we estimate 5/24 with 1/5 (the largest fraction unit is less than 5/24). Subtract 5 / 24-1 / 5, and we get 1/120, which is a unit. So 7/8 = 2/3 + 1/5 + 1/120.

+3
source share

For a / b do MAX a * b.

Take the prime factors of MAX (which is the union of prime_fac (a) and prime_fac (b) and a multiple of each of these two lists) and iterates over them, starting from low and rising high.

These are your possible 1 / x.

Edit: Oh yes! Do not forget to take into account 2/3 !

+2
source share

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 here is the 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()

Perhaps others may find this useful as a simple guide when writing their own implementations. The program at the top processes fractions with values ​​exceeding one and produces the following result.

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

More articles:


All Articles