HaskellでProject Euler(Problem 64～66)

連分数展開ラッシュ。
今回は全体的に駄目だった…。
自力では解けず、奥の手的に解法や他に解いている人のコードを参考にしても何故これで解けるのか
きちんと理解できていない。

Problem 64. Odd period square roots(奇数周期の平方根)

うーむ…自力ではお手上げ状態だったのでこの辺のコードを読んでみたが、何をやっているのかよく分からない…。

問題の√23の連分数展開a0 = 4, 1/(√23-4) = (√23+4)/7 = 1 + (√23-3)/7をもう少し詳しく見ていこう。

1/(√23-4) = (√23+4)/7
分子分母に(√23+4)をかけて約分している。
間を補うと1/(√23-4) = (√23+4)/(√23+4)(√23-4) = (√23+4)/(23+4√23-4√23-4^2)か。
ここまでは何をやっているのか理解できた、Haskellのコードに落とし込む事は難しくなさそうだ。
(√23+4)/7 = 1 + (√23-3)/7
うーむ…この仮分数から帯分数への変形がイマイチ理解できていない…。
上記参考リンクのPython版のブログ記事が一番詳しく書かれているので、これを参考にそれっぽく書いてはみたが…。

fの引数に連分数の分子x, 分母y, 終了条件zを渡し、unfoldrで終了条件を満たすまで連分数のリストを作っていく。
x' = (n - (y^2)) `div` xの箇所で、(√n-y)/xの分子に(√n+y)をかけて分母xで割り、新しい分子を作っている。
(q, r) = ((negate y)+m) `divMod` x'の辺りがかなり怪しい…何でこれで帯分数qが出せるんだろう？
新しい分母はこの余りrから元の平方根√nの整数部分を引いた値としている。
漫ろ草 SozoroGusa: プロジェクトオイラー　問６４を参考にしたが、理解が追いついていない…。
終了条件はtermCondは最初のx, yと同じ組み合わせが出現すれば以降同じループになるはずなので、
まずNothingで始めて最初のx, yに置き換え、以降それを保持し続けるようにした。

> sqrts 2
(1,[2])
> sqrts 3
(1,[1,2])
> sqrts 4
(4,[])
> sqrts 5
(2,[4])
> sqrts 6
(2,[2,4])
> sqrts 7
(2,[1,1,1,4])

追記：解説していただいたが正直これでもあまり理解できていない…。「連分数の理論」か…。

Problem 65. Convergents of e(e の近似分数)

これも連分数絡みの問題か…と身構えたが何とか自力で解けた。

euler57-1.hsのsqrt2を元にconvergent関数を作った。
sqrt2と違い[1;(2)]固定ではないため、与えられた引数nsを元に畳み込みで連分数を作っていく。
リストの末尾から畳み込みたいためfoldr1を使っている。

√2の近似分数からなる数列は、以下のようにして作ることができる。

> map convergent $ tail $ inits $ map (%1) [1,2,2,2,2,2,2,2,2,2]
[1 % 1,3 % 2,7 % 5,17 % 12,41 % 29,99 % 70,239 % 169,577 % 408,1393 % 985,3363 % 2378]

Problem 66. Diophantine equation(ディオファントス方程式)

問題を読んで考えても自力で解法を導き出せず、まずディオファントス方程式について調べる。
今回与えられた問題の式はディオファントス方程式の中でもペル方程式という特殊例らしい。
ペル方程式から最小解を出すには…また連分数展開か！

x^2 - Dy^2 = 1の値Dについて、√Dの連分数を[n;(m,...)]の形式で表すためにeuler64.hsで作ったsqrtsを、
[n;(m,...)]の形式の連分数から有理数を算出するためにeuler65.hsで作ったconvergentを利用する。
D ≤ 1000までのDとxの組み合わせのリストを作り、xが最大となるDを解としている。