Project Euler 140

プロジェクトオイラー
http://projecteuler.net/index.php

Q140.
GnをG1 = 1、G2 = 4、Gk = Gk-1 + Gk-2、AG(x) = xG1 + x2G2 + x3G3 + ...とする。
n = AG(x)が自然数であるxが有理数であるようなnの30番目。

Q137と同じようにすると、

(5A + 7)2 - 5m2 = 44

となるが、この解法がわからない。
しかたがないので、ある程度小さい解をしらみつぶしに探して、あとは

92 - 5 * 42 = 1

を利用した。



from math import sqrt

def gen(v_init):
ary_gen = [ gen_P(v[0], v[1]) for v in v_init ]
while True:
for g in ary_gen:
a = g.next()[0]
if a % 5 == 2 and a >= 12:
A = (a - 7) / 5
yield A

def gen_P(a, b):
while True:
yield a, b
a, b = a * 9 + b * 20, a * 4 + b * 9

v_init = [ ]
for b in range(2000):
a_sq = 44 + 5 * b * b
a = int(sqrt(a_sq + 0.5))
if a * a == a_sq:
v_init.append((a, b))

print v_init
N = 30
s = set()
for A in gen(v_init):
s.add(A)
m = int(sqrt((5 * A + 14) * A + 1.5))
if len(s) == N + 5:
break

a = list(s)
a.sort()
print sum(a[:N])