Project Euler 137

http://projecteuler.net/index.php?section=problems&id=137


Fk = Fk-1 + Fk-2 を利用すれば簡単です。

AF(x) + xAF(x) = xF1 + x2(F2 + F1) + x3(F3 + F2) + ... = xF2 + x2F3 + ... = (AF(x) - x) / x
AF(x) = x / (1 - x - x2)

これがnだとすると、

n x2 + (n + 1)x - n = 0

これをxについて解くと、

x = (-(n + 1) ± √(5n2 + 2n + 1)) / 2n

√の中は平方数でなければならないので、

5n2 + 2n + 1 = m2
(5n + 1)2 + 4 = m2
m2 - (5n + 1)2 = 4

ペル方程式ですね。
ところで、Pythonにはunfoldがないんですね。

def unfold(f, s):
    while True:
        x, s = f(s)
        yield x

これだと無限列しかでませんが。

from itertools import *

def unfold(f, s):
    while True:
        x, s = f(s)
        yield x

def gen_Pells():
    def mul(p, q):
        x1, y1 = p
        x2, y2 = q
        return ((x1 * x2 + 5 * y1 * y2) / 2, (x1 * y2 + y1 * x2) / 2)
    
    a = (1, 1)
    return unfold(lambda s: (s, mul(s, a)), a)

def gen_solutions():
    return ((x - 1) / 5 for x, y in gen_Pells() if x % 5 == 1)

N = 15
print next(islice(gen_solutions(), N, N + 1))