Egyptian Fraction ALGORITHM !!

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)

#ComputerScience #Programming

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Hi 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.)

It did work pretty well but the problem was somehow it did not round up things well. For example my answer for 31/47 was coming out to be 1/2 + 1/7 + 1/60 + 1/19741 + another very small fractions. I checked it later and was mainly because it was displaying 31/47 - 1/2 - 1/7 - 1/60 as 19740.00000001523 which created that small error.
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 - 7 years, 3 months ago

Hi Sudeep! WOW! This algorithm has fantastic thinking!

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.

import math

a = 29      #let this be the numerator
b = 47      #let this be the denominator
y = 1.25    #set this initially to any non-integer value

d = (a + 0.0)/(b + 0.0) 

while math.floor(y) - math.ceil(y) <> 0:  
    y = 1.0/d   
    z = math.ceil(y)    
    d = d - 1/z
    print z,

Those approximation errors ruin everything!! Somebody PLEASE help correct this!!!

Thanks again Sudeep for your ingenuity! :)

Mark Mottian - 7 years, 3 months ago

You can create a function which subtracts the fractions the way we do manually, by taking lcm and stuff and the return the fraction as a ratio of two coprime numbers. I did try that and it worked out. I used an array for the purpose and if you want I can give you the code which I had executed in java.
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 - 7 years, 3 months ago

@Sudeep Salgia – Please share your Java code.

Mark Mottian - 7 years, 3 months ago

@Mark Mottian – Here it is: Firstly the first term in each array is the numerator and second is the denominator.

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.

public static int[ ] sub(int a[ ], int b[ ])    
//accept two arrays as parameters
{   // a has the given fraction(31/47) and b the obtained one (1/2)
      // r will store the result
    int r[] = new int[2];              
    r[1]=a[1]*b[1];
    r[0]= (a[0]*b[1])-(a[1]*b[0]);
    int t=gcd(r[0],r[1]);            
// gcd is my own function whose code is not included and returns
 the gcd of the passed values                                          
    r[0]/=t;r[1]/=t;          //make it a ratio of coprime numbers
    return r;
}

main( ) function:

double m;int z;int g[] =new int[2];g[0]=1;boolean b=true;
    int val[] = {n,d};    
// have already accepted N=n and D=d from the user
    while(b)
    {
        m=((double)val[0]/(double)val[1]); 
       //fraction stored as decimal
        z= (int)Math.ceil((1D/m));    // ceil value
        g[1]=z;
        System.out.println(z);        //print ceil value
        val = sub(val,g);             
     //store the returned fraction again in the same variable so 
that we can reuse it and form a part of the loop

        if(val[0]==1)           
// if the numerator of the returned function is one then print the value and end the loop
        {                        
            b=false;
            System.out.println(val[1]);
        }

Sudeep Salgia - 7 years, 3 months ago

@Sudeep Salgia – Very Nice! :)

Mark Mottian - 7 years, 3 months ago

@Mark Mottian – Thank you.

Sudeep Salgia - 7 years, 3 months ago

The python modules Decimal and Fraction might be useful here

Thaddeus Abiy - 7 years, 3 months ago

do not use floating points when you're dealing with fractions

Chandler West - 7 years, 3 months ago

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.

In [1]: %timeit find(539340989899, 3112348903450)
100 loops, best of 3: 4.44 ms per loop

The denominators are given below:

In [2]: pprint.pprint([d.denominator for d in find(539340989899, 3112348903450)])
[6,
 151,
 677996,
 1007443900490L,
 8455851644808254339397021L,
 92023910578923924767952239989502162365349916174266L,
 178374007649173172580051029415907445061013896485774020007753534662745360888365355208647467743376131885L,

 54966266308827958423669990181784782610246968874975610092505757063069161867397828269119874919663707204172392201500129792627218708685228508326898574144401434547361020169477150773210201754498429966405367536L,

 4882492073614206870627482853969839446474838396103418238610556301503399043163571876473533514454341546485873167521883552120393925952752923306689464034031155930835557995685343308964996775519995558866399238418922631717260478650379700612279695375407792216246568223869962180903339512348226694903568652739288985428305924392997886431018740272074971195043599918004346600012676530445942460851098371246221132361262800L]

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

In [3]: print sum(find(539340989899, 3112348903450))
Fraction(539340989899, 3112348903450)

Skylar Saveland - 7 years, 3 months ago

Hi Skylar! Thanks for replying! What programming language is this?

Mark Mottian - 7 years, 3 months ago

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

Skylar Saveland - 7 years, 3 months ago

@Skylar Saveland – No way! I've never seen Python programming written like that! What are all those long scary numbers?

Mark Mottian - 7 years, 3 months ago

@Mark Mottian – I added some explanation. I wrote the find function. The implementation is not shown. The output is just me playing with the function in the interactive interpreter.

Skylar Saveland - 7 years, 3 months ago

@Skylar Saveland – Please share your find function with me. "This function can calculate the fractions for N=539340989899 and D=3112348903450 in under 5ms." Now that's efficient! :)

Mark Mottian - 7 years, 3 months ago

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 - 7 years, 3 months ago

The 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?

from fractions import Fraction as F


def find(N, D):
    total = F(N, D)
    results = []
    i = 2
    while sum(results) != total:
        diff = total - sum(results)
        if diff.numerator == 1:
            results.append(diff)
            return results

        ap = F(1, i)
        results.append(ap)
        if sum(results) > total:
            results.pop()

        # what to do with i here?? incrementing by 1 could take a lot of cycles ...
        i += 1

I somehow figured out a little trick about advancing i there at the end of the while iteration. 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 - 7 years, 3 months ago

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

import Data.Ratio
import Data.List

showFrac f = show (numerator f) ++ "/" ++ show (denominator f)
showFracs = intercalate " + " . map showFrac

maxFracUnder f = 1 % ceiling (1 / f)

egyptian 0 = []
egyptian f = let m = maxFracUnder f in m : egyptian (f - m)

main = do
    cont <- getContents
    let [n, d] = map read (words cont) in putStrLn . showFracs . egyptian $ n % d

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 - 7 years, 3 months ago

I found this:

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

Tanishq Aggarwal - 7 years, 3 months ago

47760---->the output 1/19740

sunitha bhadragiri - 7 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$