This is a programming challenge to all those avid programmers out there.

An Egyptian fraction is a fraction that can be expressed as a sum of two or more fractions, each with numerator 1. For example, 7/8 = 1/2 + 1/3 + 1/24 (notice all numerators are 1).There may be more than one possible answer. For example, 7/8 could also be equal to 1/2 + 1/4 + 1/8. You must output the one that *maximises* the first fraction output. Ties are broken by **maximising** the second fraction, then the third etc.

In the case of 7/8, the correct output should be 1/2 + 1/3 + 1/24

**TASK**

You will be given a numerator value "N" and a denominator value "D" and your programme must output the Egyptian fraction expansion.

Example:

Enter N: 31

Enter D: 47

Output: 1/2 + 1/7 + 1/60 + 1/19740

Constraints:

0 < D < N < 50

(Adapted from the South African Programming Olympiad 2002)

## Comments

Sort by:

TopNewestHi Mark! I did find an algorithm for it. Well I don't exactly know how efficient it is. But you can have a look at it. I tried it executing it in java and almost* got the answer. Here is how it is.

Divide the numerator by denominator.Express it as a decimal, say equal to d.

Invert the value of d and store it in some other variable say y. Using the ceil function on it to get the first denominator and store the integer value in say z.

Subtract the value of (1/z) from d.

Repeat the loop until y is an integer.( I checked whether y was an integer by checking whether the difference between the floor/ceil value of y and the value of y is zero. )

(Display the obtained values of z as you wish to within the loop before it gets changed.)

Rest it did work out pretty well and I think that if you can help resolve that small approximation error it would work out to be a good method because this one of the most efficient algorithms i could think of.

If anyone can come up with a better way I would love to know that as well. – Sudeep Salgia · 2 years, 8 months ago

Log in to reply

I've implemented your algorithm into a Python program so that the other Python programmers on Brilliant can better understand your algorithm and try correct those minor approximation errors.

Those approximation errors ruin everything!!

Somebody PLEASE helpcorrect this!!!Thanks again Sudeep for your ingenuity! :) – Mark Mottian · 2 years, 8 months ago

Log in to reply

Decimal and Fraction might be useful here – Thaddeus Abiy · 2 years, 7 months ago

The python modulesLog in to reply

It did solve the small error but somehow compromise on the efficiency a little bit in terms of computing values (which is pretty obvious, I believe). – Sudeep Salgia · 2 years, 8 months ago

Log in to reply

– Mark Mottian · 2 years, 8 months ago

Please share your Java code.Log in to reply

Secondly I have included the main code corresponding to the algorithm and have omitted all those lines where I accept the values from the user etc.

main( ) function:

– Sudeep Salgia · 2 years, 7 months agoLog in to reply

– Mark Mottian · 2 years, 7 months ago

Very Nice! :)Log in to reply

– Sudeep Salgia · 2 years, 7 months ago

Thank you.Log in to reply

– Chandler West · 2 years, 8 months ago

do not use floating points when you're dealing with fractionsLog in to reply

47

760---->the output 1/19740 – Sunitha Bhadragiri · 2 years, 5 months agoLog in to reply

I found this:

http://en.wikipedia.org/wiki/Greedy

algorithmforEgyptianfractions – Tanishq Aggarwal · 2 years, 7 months agoLog in to reply

If Python's Fraction makes this easy, Haskell's Ratio makes it trivial...

There are no sacrifices for speed, either;

`egyptian`

can compute the expansion of 539340989899 % 3112348903450 in under 0.6ms, without any optimization. (Note: Haskell uses % to denote ratios.) – Brian Chen · 2 years, 8 months agoLog in to reply

Come on guys! Let's see what efficient algorithm you can come up with for this problem!!

(p.s. I really struggling to come up with something unique.

PLEASE HELP!!) – Mark Mottian · 2 years, 8 months agoLog in to reply

`fractions.Fraction`

abstraction in Python's stdlib is super useful for this problem.Here is my find with one tricky line missing. How to efficiently move

i?I somehow figured out a little trick about advancing

ithere at the end of thewhileiteration. I'll let you get the joy of figuring it out. This algo will run. But, it will not do every 0 < D < N < 50 in a reasonable amount of time. Try 5 / 31, for instance. – Skylar Saveland · 2 years, 8 months agoLog in to reply

It's possible to find an efficient algorithm that can compute much larger Ns and Ds. I wrote a Python function,

find. This function can calculate the fractions for N=539340989899 and D=3112348903450 in under 5ms.The denominators are given below:

The sum of these fractions really does add up to \( \frac{539340989899}{3112348903450} \)

– Skylar Saveland · 2 years, 8 months agoLog in to reply

– Mark Mottian · 2 years, 8 months ago

Hi Skylar! Thanks for replying! What programming language is this?Log in to reply

– Skylar Saveland · 2 years, 8 months ago

Hi Mark :D It's Python. There is an interactive interpreter called IPython that makes debugging and experimenting fun and easy.Log in to reply

– Mark Mottian · 2 years, 8 months ago

No way! I've never seen Python programming written like that! What are all those long scary numbers?Log in to reply

findfunction. The implementation is not shown. The output is just me playing with the function in the interactive interpreter. – Skylar Saveland · 2 years, 8 months agoLog in to reply

findfunction with me. "This function can calculate the fractions for N=539340989899 and D=3112348903450 in under 5ms." Now that's efficient! :) – Mark Mottian · 2 years, 8 months agoLog in to reply