# Convergents of e
The square root of 2 can be written as an infinite continued fraction.
![img](http://img0.ph.126.net/x1Hyc4iHQg0Jz2EInmT3ag==/6597639313681841979.png)  
The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for √2.
![img](http://img1.ph.126.net/xme9gNBQdA7bvQkwIftznQ==/6597819633588793645.png)  
Hence the sequence of the first ten convergents for √2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the mth convergent of the continued fraction for e.


- Powered by [Project Euler](https://projecteuler.net/problem=65)

Difficulty: introductory

Starter code:

def convergents_of_e(n):
	

Solutions:
e = [1, 2]
for n in range(1, 10 ** 4):
    for f in 1, 2 * n, 1:
        e.append(f * e[-1] + e[-2])
convergents_of_e = lambda n: sum(map(int, str(e[n])))

def convergents_of_e(n):
    def b(n):
        return n // 3 * 2 if n % 3 == 0 else 1
    x, y = b(n), 1
    for k in range(n - 1, 0, -1):
        x, y = b(k) * x + y, x
    return sum(int(d) for d in str(x + y))

def fracte():
    yield 2
    i=2
    while True:
        yield 1
        yield i
        yield 1
        i+=2        
def convergents_of_e(n):
    fe=fracte()
    an=[next(fe) for f in range(n)]
    n,d=1,an.pop()
    while an:d,n=(d*an.pop()+n),d
    return sum(map(int,str(d)))

import itertools
from fractions import Fraction as F
import functools

def convergents_of_e(n):
    print(n)
    
    for i in range(200,n,200): h(cont_e_2, i) # recursion depth error prevent by precalculating
    
    return sum_dig(h(cont_e_2, n-1))
    
def sum_dig(n):
    return sum(map(int, str(n)))
    
def cont_e():
    for i in [2,1,2]: yield i
    for i in itertools.count(start=2):
        yield 1
        yield 1
        yield 2*i

@functools.lru_cache(None)      
def cont_e_2(n):
    if n==0: return 2
    if n%3 == 2: return ((n+1)*2)//3
    return 1
    

@functools.lru_cache(maxsize=None)
def h(func, n):
    # source: https://en.wikipedia.org/wiki/Continued_fraction#Some_useful_theorems
    a = func(n)
    if n<0:
        val = 2+n
    else:
        val =  a*h(func, n-1) + h(func, n-2)
    return val


import math

 
a_vals = [2]


for i in range(2,50000): 
    if i % 3 != 0:
        a_vals.append(1)
    else:
        a_vals.append(int(i/3)*2)
h_vals = [0,1]
for s in a_vals:
    h = s*h_vals[-1] + h_vals[-2]
    h_vals.append(h)



def convergents_of_e(n):
    
    

    
    output = sum([int(x) for x in str(h_vals[n+1])])
    print(output)
    return(output)
    
    



def convergents_of_e(n):
    a0, a1, i = 1, 2, 2
    
    while i <= n: 
        f =  1 if i % 3 else 2 * i // 3
    
        a = a0 + a1 * f
        a0, a1 = a1, a
        i += 1
    
    return sum(map(int, str(a1)))


def convergents_of_e(n):
    
    n0, n1, L = 1, 2, n
    for i in range(2, n + 1):
        if i % 3 != 0:
            m = 1
        else:
            m = 2 * i // 3
        n0, n1 = n1, n0 + n1 * m
    return sum((int(i) for i in str(n1)))


def convergents_of_e(m):
    old=2
    new=3
    for i in range(3,m+1):
        temp = old
        old = new
        if i % 3 == 0:
            new = old*((i // 3) * 2) + temp
        else:
            new = old*1+ temp

    new=[int(i) for i in str(new)]
    s=sum(new)
    
    return s

from fractions import gcd

def convergents_of_e(n):
    def b(n):
        return n // 3 * 2 if n % 3 == 0 else 1
    x, y = b(n), 1
    for k in range(n - 1, 0, -1):
        x, y = b(k) * x + y, x
    x = (x + y) // gcd(x + y, x)
    return sum(int(d) for d in str(x))


def e_coeffs(n):
    def gen():
        i = 1
        while True:
            yield 1
            yield 2*i
            i += 1
            yield 1
    x = gen()
    return [next(x) for _ in range(n)]

def convergents_of_e(n):
    if n <= 1: return 2
    xs = e_coeffs(n - 1)
    xs.reverse()
    p, q = 1, xs[0]
    for x in xs[1:]:
        p, q = q, x * q + p
    return sum(int(x) for x in str(2*q+p))