# 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: EASY
Tags: Fundamentals

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)
	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):
	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)))