Continued Fractions Python

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

Solution 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 http://stackoverflow.com/q/36077810/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

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

defe_cont_frac(n):
    ''' Build `n` terms of the simple continued fraction expansion of e
        `n` must be a positive integer
    '''
    seq = [2 * (i+1) // 3if i%3 == 2else1for i inrange(n)]
    seq[0] += 1return seq

defmain():
    # Get the the number of terms, less one
    n = int(sys.argv[1]) iflen(sys.argv) > 1else11if 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=12Continued fraction: [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8]
Fraction:23225/8544Float2.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.

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

Solution 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.