Convert fraction to continued fraction

Question

How would I convert a fraction to a continued fraction in Python? I tried looking around and found people using the Fraction module to do things similar to my problem, but I did not manage to modify them. An example with an image I found:

So if the input is 181 101, then the output should be 1 1 3 1 4 4. Thanks ahead!

Answer 1

Ok, let's start with some mathematics. The rationale behind that is simple. For the fraction n/d, the euclidian division is n = d * q + r with r < d

We simply have n/d = (d * q + r) / d = q + r/d with r < d

Now we iterate with 1/(r/d) = d/r to get your continued fraction

It will lead to a finished sequence of q, because the denominator of the sequence of fractions constitute a stricly decreasing integer sequence which will reach 0 in at most d operations.

A possible Python implementation could be:

def cf(n, d):
    """Return the terms of the continued fraction when n is the numerator
and d the divisor as a list"""
    if d == 0: return []         # Ok it is finished
    q = n//d                     # compute the integer quotient
    r = n - q*d                  # the rest
    return [q] + cf(d, r)        # and recurse...

We get as expected:

>>> cf(181, 101)
[1, 1, 3, 1, 4, 4]

Answer 2

Similar to Serge's answer, we can write an iterative version (Python3):

def cf(n, d):
    res = []
    q, r = divmod(n, d)
    while r != 0:
        res = res + [q]
        prev_r = r
        q, r = divmod(d, r)
        d = prev_r
    return res + [q]