Problem 140

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

{-- 
A_G(x) = frac{x^3 +x}{1-x-x^2} = n
D(n) = 5n^2+14n+1 = d^2
X^2-5Y^2=44
X^2-5Y^2=pm 4 -> X_0=1,Y_0=1
X^2-5Y^2= 11 -> X_0=4,Y_0=1
X^2-5Y^2=-11 -> X_0=3,Y_0=2
 --}
next (x,y) = (div (x+5*y) 2, div (x+y) 2)
nugget = map toN.step2.tail.map fst.f.iterate next $ (1,1)
where f (x:y:zs) = g x : h y : f zs
g (x,y) = (3*x+10*y,2*x+3*y)
h (x,y) = (4*x+5*y,x+4*y)
step2 (x:y:z:v:ws) = x:y:step2 ws
toN x = div (x-7) 5
main = print.sum.take 30$ nugget

これもペル方程式。

とき方は分かるが、なぜこれで正しい解がもれなく得られるのかは、いまだに分からない。