Problem 137 - もうカツ丼はいいよな

Problem 137 - Project Euler

$F_k$ をk番目のフィボナッチ数( $F_k = F_{k-1} + F_{k_2}$ , $F_1=1$ , $F_2=1$ からなる数列で、1, 1, 2, 3, 5, 8, ...)として、無限級数 $A_F(x)=xF_1 + x^2F_2 + x^3F_3 + ...$ を考える。
この問題では、 $A_F(x)$ の値が正整数となるようなxについて考える。
驚くべきことに、 $A_F(\frac{1}{2})=2$ である。
最初の5つの自然数に対するxの値は次のようになる。

$x$ $A_F(x)$

$\sqrt{2}-1$ 1

$\frac{1}{2}$ 2

$\frac{\sqrt{13}-2}{3}$ 3

$\frac{\sqrt{89}-5}{8}$ 4

$\frac{\sqrt{34}-3}{5}$ 5

xが有理数であるようなときの $A_F(x)$ は数を増すごとに稀な物となっていくため、golden nuggetと呼ぶ。例えば、10番目のgolden nuggetは74049690である。
15番目のgolden nuggetを求めよ。

$x$	$A_F(x)$
$\sqrt{2}-1$	1
$\frac{1}{2}$	2
$\frac{\sqrt{13}-2}{3}$	3
$\frac{\sqrt{89}-5}{8}$	4
$\frac{\sqrt{34}-3}{5}$	5

説明

まず $A_F(x)$ だが、 $A_F(x)x^2+A_F(x)*x-A_F(x)$ を計算すると
$A_F(x) = \frac{x}{1-x-x^2}$
が得られる*1。
$A_F(x)=y$ と置いておいて、xについての式に変形すると、
$\frac{\sqrt{5y^2+2y+1}-y-1}{2y}$
が得られ、式中のルート内部が平方数になればxが有理数になるということがわかる。
$a^2=5y^2+2y+1$
と置いて、右辺を平方完成すると、
$a^2=5(y+\frac{1}{5})^2+\frac{4}{5}$
さらに両辺を5倍して、 $k=5y+1$ とおくと、
$5a^2=k^2+4$
ちょっとばかし項を入れ替えると、
$k^2-5a=-4$
となって(拡張)ペル方程式が出てくる(ペル方程式 - Wikipedia)。
~~よく分からないのでWikipediaを参考にすると、~~この形のペル方程式は、最小解を $k_1$ , $a_1$ として、
$\frac{k_i+a_i\sqrt{D}}{2}$ = $\left(\frac{k_1+a_1\sqrt{D}}{2}\right)^i$
という形で全ての解が得られる。ここから解の漸化式を求めると、
$k_{i+1}=\frac{k_1k_i+a_1a_iD}{2}$
$a_{i+1}=\frac{k_1a_i+a_1k_i}{2}$
となる。
なお、今回は右辺が負なのでiが奇数の時だけ解になる。
さて、途中で $k=5y+1$ とおいたので、 $\frac{k-1}{5}$ が整数となるような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)にも載ってるので興味のある方はどうぞ