Problem 100

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

ついに100問。

¥frac{n(n-1)}{d(d-1)}=¥frac{1}{2}に対して

x:=2d-1,y:=2n-1とすると

x^2-2y^2=-1のpell equationに。

ところで、pell equationの解は最小の解から順に生成できるみたいだけど

なんで?はじめの解をn乗しても解なのはわかるけど

間に解がないってのがなー

import Data.List
naive m = [(n,d)|d<-[1..m],n<-[div d 2..d],2*n*(n-1)==d*(d-1)]
next (x,y) = (3*x+4*y,2*x+3*y)
toDisc (x,y) = ((y+1)`div`2,(x+1)`div`2)
p100 = map toDisc.iterate next $ (1,1)
main = print.find ((>10^12).snd)$p100
More Reading
Newer// Problem 107
Older// Problem 101