Project Euler 2 - Essaytial Machine Learning

問題

　フィボナッチ数列の $N$ 以下の偶数項の総和を $PE2(N)$ と置いて $PE2(4000000)$ を求める。

記号

[ 表記 ]：[ 返り型 ]：[ 説明 ]
$y // x$ ：整数：切り捨て除算、 $y / x$ を超えない最大の整数
$\lfloor x \rfloor$ ：整数： $x$ を超えない最大の整数、ガウス関数

解法

　 $F(n)$ （ $n \in \mathbb{N}$ ）を $F(1) = F(2) = 1$ から始まるフィボナッチ数列とする。つまり漸化式 $F(n+2) = F(n+1)+F(n)$ で定義され、一般項の式は

$\displaystyle F(n) = \frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n \right)$

で与えられる。この偶奇は

$F(n)$ ：奇、 $F(n+1)$ ：奇 $\Rightarrow$ $F(n+2)$ ：偶、
$F(n)$ ：奇、 $F(n+1)$ ：偶 $\Rightarrow$ $F(n+2)$ ：奇、
$F(n)$ ：偶、 $F(n+1)$ ：奇 $\Rightarrow$ $F(n+2)$ ：奇、

で循環するので $E(p) := F(3p)$ に関する総和を取ればいいことが分かる。 $E(p)$ は

$\displaystyle \begin{align} E(p) & = \frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^{3p}-\left( \frac{1-\sqrt{5}}{2} \right)^{3p} \right) \\ & = \frac{1}{\sqrt{5}}\left( (2+\sqrt{5})^p-(2-\sqrt{5})^p \right) \end{align}$

で、その $p = 1, \dots, m$ での総和は

$\displaystyle \begin{align} \sum_{p=1}^m E(p) & = \frac{1}{\sqrt{5}}\sum_{p=1}^m \left( (2+\sqrt{5})^p-(2-\sqrt{5})^p \right) \\ & = \frac{1}{\sqrt{5}} \left( (2+\sqrt{5})\frac{(2+\sqrt{5})^m-1}{1+\sqrt{5}}-(2-\sqrt{5})\frac{(2-\sqrt{5})^m-1}{1-\sqrt{5}} \right) \\ & = \frac{1}{4\sqrt{5}} \left( (3+\sqrt{5})(2+\sqrt{5})^m-(3-\sqrt{5})(2-\sqrt{5})^m \right)-\frac{1}{2} \end{align}$

となる。これ以上の簡約化は知らない。

　後は $E(p)$ が $N$ を超えない最大の $p$ を探せば良い。 $(2-\sqrt{5})^{-1} = -(2+\sqrt{5})$ に注意して $\phi_p = (2+\sqrt{5}) ^ p$ とおくと、 $E(p)$ が $N$ 以下になる $p$ は

$\displaystyle E(p) = \frac{1}{\sqrt{5}}\left( \phi_p+(-1)^{p+1}\phi_p^{-1} \right) \leq N,$
$\displaystyle \phi_p^2-\sqrt{5}N\phi_p+(-1)^{p+1} \leq 0,$
$\displaystyle \frac{1}{2}\left( \sqrt{5}N-\sqrt{5N^2+4(-1)^p} \right) \leq \phi_p \leq \frac{1}{2}\left( \sqrt{5}N+\sqrt{5N^2+4(-1)^p} \right),$
$\displaystyle p \leq \frac{\log{\left( \sqrt{5}N+\sqrt{5N^2+4(-1)^p} \right)}-\log{2}}{\log{(2+\sqrt{5})}}$

を満たすことが必要になる。右辺が $p$ に依存しているのが厄介だが、とりあえず

$\displaystyle p_N = \left\lfloor \frac{\log{\left( \sqrt{5}N+\sqrt{5N^2+4} \right)}-\log{2}}{\log{(2+\sqrt{5})}} \right\rfloor$

を考えよう。この時、

$\displaystyle p_N \leq \frac{\log{\left( \sqrt{5}N+\sqrt{5N^2+4} \right)}-\log{2}}{\log{(2+\sqrt{5})}},$
$\displaystyle \phi_{p_N} \leq \frac{1}{2}\left( \sqrt{5}N+\sqrt{5N^2+4} \right),$
$\displaystyle \phi_{p_N}^2-\sqrt{5}N\phi_{p_N}-1 \leq 0,$
$\displaystyle \frac{1}{\sqrt{5}}\left( \phi_{p_N}-\phi_{p_N}^{-1} \right) \leq N$

であり、同様に $\frac{1}{\sqrt{5}}\left( \phi _ {p_N+1}-\phi_{p_N+1}^{-1} \right) \gt N$ が分かる。 $p_N$ が偶数ならば、

$\displaystyle E(p_N) = \frac{1}{\sqrt{5}}\left( \phi_{p_N}-\phi_{p_N}^{-1} \right) \leq N,$ $\displaystyle E(p_N+1) = \frac{1}{\sqrt{5}}\left( \phi_{p_N+1}+\phi_{p_N+1}^{-1} \right) \gt \frac{1}{\sqrt{5}}\left( \phi_{p_N+1}-\phi_{p_N+1}^{-1} \right) \gt N$

となる。 $p_N$ が奇数ならば $E(p_N) = \frac{1}{\sqrt{5}}\left( \phi _ {p_N}+\phi _ {p_N}^{-1} \right) \gt \frac{1}{\sqrt{5}}\left( \phi _ {p_N}-\phi _ {p_N}^{-1} \right)$ だが、 $E(p_N)$ は整数で $\left| \frac{1}{\sqrt{5}}\phi _ {p_N}^{-1} \right| \lt \frac{1}{2}$ なので $E(p_N) \leq N$ が分かる。また、この時 $E(p_N+1) = \frac{1}{\sqrt{5}}\left( \phi _ {p_N+1}-\phi_{p_N+1}^{-1} \right) \gt N$ となるので、 $p_N$ は $E(p)$ が $N$ を超えない最大の $p$ を与える。

　よって求める総和は

$\displaystyle PE2(N) = \frac{1}{4\sqrt{5}} \left( (3+\sqrt{5})(2+\sqrt{5})^{p_N}-(3-\sqrt{5})(2-\sqrt{5})^{p_N} \right)-\frac{1}{2}. //$

近似手法

　 $N$ がフィボナッチ数として取り得ないだろう値（ $4000000$ とか）の場合、 $p_N$ をもう少し簡単に見積もれる。つまり $\phi_p^{-1} \lt 1$ から $E(p) \simeq \frac{1}{\sqrt{5}}(2+\sqrt{5}) ^ p$ で、 $p_N^* = \left\lfloor \frac{2\log(N)+\log(5)}{2\log(2+\sqrt{5})} \right\rfloor$ と取るとほぼほぼ正しい値が得られる。//

解

　 $p_{4000000} = \left\lfloor \frac{\log{\left( 4000000\sqrt{5}+\sqrt{5\cdot4000000 ^ 2+4} \right)}-\log{2}}{\log{(2+\sqrt{5})}} \right\rfloor = 11$ より

$\displaystyle PE2(4000000) = \frac{1}{4\sqrt{5}} \left( (3+\sqrt{5})(2+\sqrt{5})^{11}-(3-\sqrt{5})(2-\sqrt{5})^{11} \right)-\frac{1}{2} = 4613732.$

この場合は近似手法でも $p_{4000000}^* = \left\lfloor \frac{2\log(4000000)+\log(5)}{2\log(2+\sqrt{5})} \right\rfloor = 11$ が得られる。