Greedy algorithm for Egyptian fractions

greedy-egyptian-fractions.py

# Greedy Algorithm for Egyptian Fractions
# To express a / b as a sum of unit fractions (1 / c_1) + ... + (1 / c_n)

def main():
    print("*** Greedy algorithm for Egyptian fractions ***\n")
    while 1:
        try:
            a = int(input("Enter a: "))
            b = int(input("Enter b: "))
            result = iterate(a,b)
            print(map(prettyfrac,result))
        except TypeError:
            print("Invalid input (both must be integers).")
            continue
        except ValueError:
            print("Exiting.")
            return


def iterate(a, b):
    """generate sequence of unit fractions."""
    l = []
    while 1:
        if b%a == 0:  # a divides into b so already a unit fraction
            l.append(b/a)
            return l
        else:
            aa = b/a + 1
            l.append(aa)
            a = a*(lcm(b,aa)/b) - (lcm(b,aa)/aa) 
            b = lcm(b,aa)


def gcd(a, b):
    """greatest common divisor of two integers"""
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b): 
    """lowest common multiple of two integers"""
    return a * b / gcd(a, b)

def prettyfrac(z):
    return "1/"+str(z)

if __name__ == "__main__":
    main()