bancaldo™

...
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 100th convergent of the
continued fraction for e.

Analisi:

Problema!

Come per il problema 64, mi sono affidato a Wikipedia.
Per le frazioni continue si possono trovare i numeratori (h) ed
i denominatori (k) secondo queste formule ricorsive:

hn = an * hn-1 + hn-2
kn = an * kn-1 + kn-2

dove i valori iniziali sono:

h-1 = 0
h0 = 1
k-1 = 1
k0 = 0

Considerata la costante ‘e’ con la seguente notazione:

[2; 1, 2, 1, 1, 4, 1, 1, 6, ...]

dovrei ottenere le seguenti convergenze:

[2; 3, 8/3, 11/4,...]

utilizzando la notazione generica fornita da wp, avrei:

[a0; a1, a2, a31, a4, ...]

ma utilizzando le formule ricorsive, non ottengo i numeratori
che sto cercando:

hn = an * hn-1 + hn-2

h1 = a1 * h0 + h-1 = 1 * 1 + 0 = 1  >> dovrei avere 3
h2 = a2 * h1 + h0 = 2 * 1 + 0 = 1  >> dovrei avere 8

il problema è l’errata notazione letterale, che andrebbe aumentata di una
unità (link) e che deve quindi essere:

[a1; a2, a3, a4, a5, ...]

infatti:

[a1; a2, a3, a4, ...]
[2; 1, 2, 1, ...]
[2; 3, 8/3, 11/4,...]

ottengo:

h1 = a1 * h0 + h-1 = 2 * 1 + 0 = 2 (2/1)
h2 = a2 * h1 + h0 = 1 * 2 + 1 = 3 (3/1)
h3 = a3 * h2 + h1 = 2 * 3 + 2 = 8 (8/3)
h4 = a4 * h3 + h2 = 1 * 8 + 3 = 11 (11/4)

Ora il codice viene da sè…

python:

import time

st = time.time()

def get_e_notation():
    start = [2, 1]
    new = [1]*200
    mult = 2
    for i in range(len(new)):
        if i == 0 or i % 3 == 0:
            new[i] = mult
            mult += 2
    start.extend(new)
    return start

e_not = get_e_notation()

hs = [0,1]
i = 0
for n in e_not:
    h = n*hs[i+1] + hs[i]
    hs.append(h)
    i += 1
    if i == 100: break

res = sum([int(n) for n in str(hs[-1])])
print 'euler 65: {}\nelapsed time: {}sec'.format(res, time.time() - st)