読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 140 / 変形フィボナッチ金塊

Gk = G(k-1) + G(k-2), G1 = 1, G2 = 4 によって与えられる無限級数

 A_G(x) = xG_1 + x^2G_2 + x^3G_3 +\cdots

がある。この問題では AG(x) が正の整数となるような x の値について考える。

最初の5つの自然数に対する x の値を下表に示す。

xAG(x)
(√5−1)/41
2/52
(√22−2)/63
(√137−5)/144
1/25

x が有理数となるときの A_G(x) の値を「金塊(golden nugget)」と呼ぶことにする。金塊は次第に稀になっていき,20番目の金塊は 211345365 である。最初の30個の金塊の和を求めよ。

Problem 140 - Project Euler


第137問を難しくした問題です。

variee.hatenadiary.com

途中まではやることは同じです。無限級数は

 A_G(x)=\dfrac{-3x^2-x}{x^2+x-1}

A_G(x)=k(整数)とおいて xの2次方程式にして,「判別式=n^2(平方数)」とおきます。

 5k^2+14k+1=n^2

第137問ではOEISの力を借りて k の一般項を得ましたが,この問題では Pell 方程式をまともに相手にしなければなりません。まず両辺5倍します。

(5k+7)^2 -5n^2=44

この後は「初期解を求める」→「一般解を求める」と進むわけですが,初期解が複数あるのと 5k+7 を k に戻すのが面倒だったので,ネットでいろいろ探しました。一番役立ったのがここ。

www.alpertron.com.ar

初期解だけでなく,漸化式も教えてくれます。

 x_{n+1}= -9 x_n - 4 y_n - 14,\, y_{n+1}= -20 x_n - 9 y_n - 28

あとはMathematicaに頑張ってもらいましょう。

各グループの探索数15は適当に決めた数字なので,これは完全解ではありません。いつか直したいと思います。