をk番目のフィボナッチ数(, , からなる数列で、1, 1, 2, 3, 5, 8, ...)として、無限級数を考える。
この問題では、の値が正整数となるようなxについて考える。
驚くべきことに、である。
最初の5つの自然数に対するxの値は次のようになる。
1 2 3 4 5 xが有理数であるようなときのは数を増すごとに稀な物となっていくため、golden nuggetと呼ぶ。例えば、10番目のgolden nuggetは74049690である。
15番目のgolden nuggetを求めよ。
説明
まずだが、を計算すると
が得られる*1。
と置いておいて、xについての式に変形すると、
が得られ、式中のルート内部が平方数になればxが有理数になるということがわかる。
と置いて、右辺を平方完成すると、
さらに両辺を5倍して、とおくと、
ちょっとばかし項を入れ替えると、
となって(拡張)ペル方程式が出てくる(ペル方程式 - Wikipedia)。
よく分からないのでWikipediaを参考にすると、この形のペル方程式は、最小解を, として、
=
という形で全ての解が得られる。ここから解の漸化式を求めると、
となる。
なお、今回は右辺が負なのでiが奇数の時だけ解になる。
さて、途中でとおいたので、が整数となるようなkを求めなければならない。そのようなkが見つかったら、あとはyを逆算すればよい。
解答
x <- 1 y <- 1 limit <- 15 count <- 0 while(count < limit){ xold <- x yold <- y x <- (xold + 5 * yold)/2 y <- (yold + xold)/2 if(x %% 5 == 1) count <- count + 1 } as.character((x - 1) / 5)
ペル方程式さえ解けてしまえば難しいところはない。0.4ms。
*1:ここの話は数学ガール (数学ガールシリーズ 1)にも載ってるので興味のある方はどうぞ