Continued Fractions Python [closed]

Question

I am new to Python and was asked to create a program that would take an input as a non-negative integer n and then compute an approximation for the value of e using the first n + 1 terms of the continued fraction:

I have attempted to decipher the question but can't exactly understand everything it is asking. I am not looking for an exact answer but hopefully an example to help me on my way.

This is the exact question
Below is a code I have done with continued fractions before.

import math
# Get x from user
x = float(input("Enter x = "))

# Calculate initial variables and print
a0 = x//1
r0 = x-a0
print("a0 =", a0, "\tr0 =", r0)

# Calculate ai and ri for i = 1,2,3 and print results

a1 = 1/r0//1
r1 = 1/r0 - a1
print("a1 =", a1, "\tr1 =", r1)

a2 = 1/r1//1
r2 = 1/r1 - a2
print("a2 =", a2, "\tr2 =", r2)

a3 = 1/r2//1
r3 = 1/r2 - a3
print("a3 =", a3, "\tr3 =", r3)

Woodbridge

It turned out that import math wasn't needed. – Agley

Your code could be simplified by using a loop. And as K. Menyah said, you don't need import math here since you aren't using any of the functions or constants that module defines. – Sexpartite

Answer 1

Without further information, it's probably a Good Idea™ to use the simple continued fraction expansion of e, as shown in Wikipedia:

e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, ...]

This sequence can easily be created using a simple list comprehension.

To evaluate a simple continued fraction expansion we can process the list in reversed order.

The following code will work on Python 2 or Python 3.

#!/usr/bin/env python

''' Calculate e using its simple continued fraction expansion

    See https://mcmap.net/q/1646897/-continued-fractions-python-closed/4014959

    Also see
    https://en.wikipedia.org/wiki/Continued_fraction#Regular_patterns_in_continued_fractions

    Written by PM 2Ring 2016.03.18
'''

from __future__ import print_function, division
import sys

def contfrac_to_frac(seq):
    ''' Convert the simple continued fraction in `seq` 
        into a fraction, num / den
    '''
    num, den = 1, 0
    for u in reversed(seq):
        num, den = den + num*u, num
    return num, den

def e_cont_frac(n):
    ''' Build `n` terms of the simple continued fraction expansion of e
        `n` must be a positive integer
    '''
    seq = [2 * (i+1) // 3 if i%3 == 2 else 1 for i in range(n)]
    seq[0] += 1
    return seq

def main():
    # Get the the number of terms, less one
    n = int(sys.argv[1]) if len(sys.argv) > 1 else 11
    if n < 0:
        print('Argument must be >= 0')
        exit()

    n += 1
    seq = e_cont_frac(n)
    num, den = contfrac_to_frac(seq)

    print('Terms =', n)
    print('Continued fraction:', seq)
    print('Fraction: {0} / {1}'.format(num, den))
    print('Float {0:0.15f}'.format(num / den))

if __name__ == '__main__':
    main()

output

Terms = 12
Continued fraction: [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8]
Fraction: 23225 / 8544
Float 2.718281835205993

Pass the program an argument of 20 to get the best approximation possible using Python floats: 2.718281828459045

---

As Rory Daulton (& Wikipedia) mention, we don't need to reverse the continued fraction list. We can process it in the forward direction, but we need 2 more variables because we need to track 2 generations of numerators and denominators. Here's a version of contfrac_to_frac which does that.

def contfrac_to_frac(seq):
    ''' Convert the simple continued fraction in `seq`
        into a fraction, num / den
    '''
    n, d, num, den = 0, 1, 1, 0
    for u in seq:
        n, d, num, den = num, den, num*u + n, den*u + d
    return num, den

Sexpartite

If you use the Wikipedia formula for the continued fraction of e then it is easy to write a python program just for that. Here is a code I posted here on SO that gives you the continued fraction for any number, by calculating it: #12183201 – Multivibrator

@StefanGruenwald Sure, but when there's a well-known continued fraction for a number, like there is for e and its integer powers, or any rational quadratic, you might as well use it. FWIW, there are better ways to calculate e if you want high precision, my favourite is a version of Eric Jensen's algorithm. – Sexpartite

This looks like a good answer, but it is not true that "we need to process the list in reversed order." There is a simple way to find the value of the convergent of the continued fraction by processing the list in the usual order. That does requires 4 variables to store intermediate results, rather than the 2 that you use. – Nonmetallic

@RoryDaulton Good point! I've updated my code.... Better late than never. :) – Sexpartite

Answer 2

The value e can be expressed as the limit of the following continued fraction:

e = 2 + 1 / (1 + 1 / (2 + 2 / (3 + 3 / (4 + 4 / (...)))))

The initial 2 + 1 / falls outside of the main pattern, but after that it just continues as shown. Your job is to evaluate this up to n deep, at which point you stop and return the value up to that point.

Make sure you carry out the calculation in floating point.

Advent

So if n were 3 it would look like e= 2+1/(1+1/(2+2/(3+3)))? Just clarifying but I think I understand the code more now – Woodbridge

Yes, that looks right. – Advent

What you listed here is the Blazys expansion of e: oeis.org/A233583 – Multivibrator