Greedy algorithm odd behavior

Question

I've implemented the Greedy algorithm to solve Egyptian fractions, however I'm getting some unexpected results. Here's my code

from math import ceil
from fractions import Fraction

def go(frac):
    ret = []
    while frac > 0:
        if frac.numerator == 1:
            ret.append(frac)
            break
        x = Fraction(1, ceil(frac.denominator / frac.numerator))
        frac -= x
        ret.append(x)
    return ret

input1 = int(raw_input('numerator: '))
input2 = int(raw_input('denominator: '))

print go(Fraction(input1, input2))

I constantly am getting the error "TypeError: both arguments should be Rational instances"

I've been logging and it crashes upon the first iteration of the while loop.

EDIT: the error in detail is:

File "egypt.py", line 19, in <module>
print go(Fraction(input1, input2))
File "egypt.py", line 10, in go
x = Fraction(1,ceil(frac.denominator / frac.numerator))
File "/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/fractions.py", line 158, in __new__
raise TypeError("both arguments should be "
TypeError: both arguments should be Rational instances

Why is this? Thank you.

Answer 1

Try changing this:

x = Fraction(1, ceil(frac.denominator / frac.numerator))

to this:

x = Fraction(1,int(ceil(frac.denominator / float(frac.numerator))))

Answer 2

You have 2 problems in your code.

1. you're dividing int with int which always returns an int; in your case, you're dividing a / b where a < b so it'll always be rounded down to 0.
2. Then, you ceil() that, which returns a float (0.0) which is something Fraction doesn't like;it wants ints.

So try this instead:

Fraction(1, int(ceil(float(frac.denominator) / frac.numerator)))

The rest of the code looks good.