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