PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 137 / フィボナッチ金塊

フィボナッチ数列
Fk = F(k-1) + F(k-2), F1 = 1, F2 = 1
(Fk = 1, 1, 2, 3, 5, 8, ...) によって与えられる無限級数
 A_F(x) = xF_1 + x^2F_2 + x^3F_3 +\cdots
を考える。

この問題では,A_F(x) が正の整数となるような x の値について考える。驚くべきことに

f:id:variee:20170314172345p:plain

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

xAF(x)
√2−11
1/22
(√13−2)/33
(√89−5)/84
(√34−3)/55

x が有理数のときのA_F(x)の値を,非常に稀なので「金塊(golden nugget)」と呼ぶ。10番目の金塊は74049690である。

15番目の金塊を求めよ。

Problem 137 - Project Euler

無限級数を求める

この無限級数は求められます*1

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

A_F(x)=k(整数)とおくと
 kx^2+(k+1)x-k=0

この方程式が有理数解をもつような k が「金塊」です。

ペル型方程式

10番目の金塊の大きさを考えると,各 k に対して方程式を解いて,有理数かどうか調べるのは現実的ではありません。高校数学っぽく「判別式 D = 平方数 n^2」で処理します。整理すると

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

これはペル型方程式なので解けますね。手計算でも解けますが,Mathematica を使ってみましょう。

f:id:variee:20170314173616p:plain

汚い式が3本得られましたが,さすがにこの方法は却下です。

OEISの力を借りる

Mathematicaで最初の5個の金塊を見つけました。

これを OEIS に渡すと A081018がヒット。

f:id:variee:20170314181627p:plain

A081018 - OEIS

リュカ数列もしくは連続する2つのフィボナッチ数の積ですね。これで解けました。

*1:求め方は「フィボナッチ数列 母関数」などでググってください。