Project Eulerに挑戦: 問題2

Table of Contents

問題2

4000000未満の偶数のフィボナッチ数の総和を求めよ.

Cで解く

フィボナッチ数は,以下の漸化式を用いて再帰的に求めることもできるが, 再帰の回数が指数的になり効率が悪い. \begin{eqnarray*} F_1 & = & 1 \\ F_2 & = & 2 \\ F_n & = & F_{n-1} + F_{n-2} \qquad (n > 2) \end{eqnarray*} 以下のようにすれば,より効率よくn番目のフィボナッチ数を求めることができる.

 1:  int fib(int n) {
 2:      int f0 = 1;
 3:      int f1 = 1;
 4:      int i, f;
 5:      for (i = 1; i < n; i++) {
 6:          f = f0 + f1;
 7:          f0 = f1;
 8:          f1 = f;
 9:      }
10:      return f1;
11:  }

したがって,以下のようにすれば回答が得られる.

 1:  int e002() {
 2:      int s = 0;
 3:      int i;
 4:      for (i = 1; ; i++) {
 5:          int f = fib(i);
 6:          if (f > 4000000)
 7:              break;
 8:          if (f % 2 == 0)
 9:              s += f;
10:      }
11:      return s;
12:  }

このプログラムも,何度もフィボナッチ数を最初から求めているので, まだ改善の余地がある.

Scalaで解く

まず,与えられた上限以下のフィボナッチ数のリストを求める関数を定義する.

1:  def fibList(f0: Int, f1: Int, lim: Int): List[Int] = {
2:    val f2 = f0 + f1
3:    if (f2 > lim) Nil else f2 :: fibList(f1, f2, lim)
4:  }
5:  def fibList(lim: Int): List[Int] =
6:    1 :: 2 :: fibList(1, 2, lim)

fibListの実行結果は以下のようになる.

scala> fibList(100)
res: List[Int] = List(1, 2, 3, 5, 8, 13, 21, 34, 55, 89)

filterで偶数のフィボナッチ数だけを取り出す.

scala> fibList(100).filter(_ % 2 == 0)
res: List[Int] = List(2, 8, 34)

sumで合計を求める.

scala> fibList(100).filter(_ % 2 == 0).sum
res: Int = 44

したがって回答は以下で求められる.

scala> fibList(4000000).filter(_ % 2 == 0).sum

手で解く

φ を以下のように置く. \begin{eqnarray*} \phi & = & \frac{1+\sqrt{5}}{2} \end{eqnarray*} φ は黄金比 (Golden ratio)と呼ばれ,約 1.618 である.

φ は x2 - x - 1 = 0 の解の一つであり, 他の解 \(\psi = \frac{1-\sqrt{5}}{2}\) は \(-\frac{1}{\phi}\) に一致している. また φ2=φ+1 および ψ2=ψ+1 に注意する.

n番目のフィボナッチ数 Fn は以下の式で与えられる(後述). \begin{eqnarray*} F_n & = & \frac{1}{\sqrt{5}}(\phi^{n+1} - \psi^{n+1}) \end{eqnarray*} Fn の値は近似的には \(\phi^{n+1} / \sqrt{5}\) で表され, 小数部を四捨五入すれば良いことが知られている.

これを4000000と比較して得られる式 \((\log 4000000\sqrt{5})/(\log \phi) - 1\) の値が 約32.263であることから, F32 = 3524578 が 4000000未満の最大のフィボナッチ数であることがわかる.

次に, 偶数のフィボナッチ数は F2, F5, F8, … のように 3番目毎に現れる点に注意する. したがって以下の式で \(n=11\) とした場合, 4000000未満の偶数フィボナッチ数の総和となる. \begin{eqnarray*} \sum_{k=0}^{n-1} F_{3k+2} & = & \frac{1}{\sqrt{5}} \sum_{k=0}^{n-1} (\phi^{3(k+1)} - \psi^{3(k+1)}) \end{eqnarray*} ここで \(\sum_{k=0}^{n-1} x^k = (x^n - 1)/(x - 1)\) および φ3-1 = 2φ と ψ3-1 = 2ψ を用いると, 以下が得られる. \begin{eqnarray*} \sum_{k=0}^{n-1} \phi^{3(k+1)} & = & \phi^3 (\phi^{3n} - 1)/(\phi^3 - 1) = \frac{1}{2}(\phi^{3n+2} - \phi^2) \\ \sum_{k=0}^{10} \psi^{3(k+1)} & = & \psi^3 (\psi^{3n} - 1)/(\psi^3 - 1) = \frac{1}{2}(\psi^{3n+2} - \psi^2) \end{eqnarray*} これから,以下がわかる. \begin{eqnarray*} \sum_{k=0}^{n-1} F_{3k+2} & = & \frac{1}{2} (F_{3n+1} - F_1) \end{eqnarray*} したがって,求める回答の値は (F34 - 1)/2 を計算すれば良い.

母関数による Fn の計算

無限項の多項式 \(F(z)\) を以下のように定義する. ただし \(F_0 = 1\) とする. \begin{eqnarray*} F(z) & = & \sum_{n=0}^{\infty} F_n z^n \end{eqnarray*} \(F(z)\) はフィボナッチ数列 Fn の母関数 (generating function)と呼ばれる.

\(F(z)-z F(z)-z^2 F(z)\) を考えると, フィボナッチ数の定義より,以下が成り立つ. \begin{eqnarray*} F(z)-z F(z)-z^2 F(z) & = & F_0 + (F_1 - F_0)z + (F_2 - F_1 - F_0)z^2 + \cdots \\ (1-z-z^2)F(z) & = & 1 \\ F(z) & = & -\frac{1}{z^2+z-1} \end{eqnarray*} ここから以下のようにして -1/(z2+z-1) の マクローリン展開 (Maclaurin series)を求める.

z2+z-1=0 の2解を \(\alpha = (-1+\sqrt{5})/2\) と \(\beta = (-1-\sqrt{5})/2\) として, -1/(z2+z-1) を部分分数分解すると以下の形で表せる. \begin{eqnarray*} -\frac{1}{z^2+z-1} & = & \frac{A}{z-\alpha} + \frac{B}{z-\beta} \end{eqnarray*} また,\(1/(z-a) = - \sum_{n=0}^{\infty} a^{-n-1} z^n\) および 1/α = φ と 1/β = ψ より \begin{eqnarray*} -\frac{1}{z^2+z-1} & = & \sum_{n=0}^{\infty} (-A\phi^{n+1}-B\psi^{n+1}) z^n \end{eqnarray*} となり, \(F_n = -A\phi^{n+1}-B\psi^{n+1}\) である.

ここで \(F_0 = F_1 = 1\) より,以下の式が得られる. \begin{eqnarray*} -A\phi-B\psi & = & 1 \\ -A\phi^2-B\psi^2 & = & 1 \end{eqnarray*} これを解くと \(A = -1/\sqrt{5}\), \(B = 1/\sqrt{5}\) であり, Fn の一般式として以下が得られる. \begin{eqnarray*} F_n & = & \frac{1}{\sqrt{5}} (\phi^{n+1} - \psi^{n+1}) \end{eqnarray*}

Date: 2017-09-29 21:44:06 JST

Author: 田村直之

Validate XHTML 1.0