けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

ProjectEuler 140 Modified Fibonacci golden nuggets

ペル方程式の練習

問題概要

数列  G_{N} は次の漸化式で定義される。

  •  G_{1} = 1
  •  G_{2} = 4
  •  G_{N} = G_{N-1} + G_{N-2}

この数列の母関数

 f(x) = G_{1}x + G_{2}x^{2} + G_{3}x^{3} + \dots

を定義する。正の整数  k が golden であるとは、 f(x) = k を満たす  x有理数であることをいう。具体的には

  •  f(\frac{2}{5}) = 2
  •  f(\frac{1}{2}) = 5
  • ...

となっている。小さい方から 30 番目までの golden 整数の総和を求めよ。

考えたこと

まずは母関数の表式を得る。

  •  f(x) = G_{1}x + G_{2}x^{2} + G_{3}x^{3} + \dots
  •  xf(x) = G_{1}x^{2} + G_{2}x^{3} + \dots
  •  x^{2}f(x) = G_{1}x^{3} + \dots

によって、

 f(x) - xf(x) - x^{2}f(x) = x + 3x^{2}
 f(x) = \frac{x(1 + 3x)}{1 - x - x^{2}}

となる。これが正の整数になる条件を求める。

 \frac{x(1 + 3x)}{1 - x - x^{2}} = n

とおいて、

 nx^{2} - (n+1)x - (n+3) = 0

有理数解を求める条件を考える。具体的には、判別式が平方数になる条件を考える。

 D = 5n^{2} + 14n + 1 (= m^{2})
 (5n + 7)^{2} - 5m^{2} = 44

とおいて、この整数解  (n, m) を求める。こうしてペル方程式に帰着された。

大前提として  x^{2} - 5y^{2} = 1 の解を求めておく。この最小解は  (x_{0}, y_{0}) = (9, 4) と求められる。一般の整数  k に対する  x^{2} - 5y^{2} = k の解  (x, y) が得られたとき、

  •  (x + y\sqrt{5})(x_{0} + y_{0}\sqrt{5})^{n}
  •  (x + y\sqrt{5})(x_{0} - y_{0}\sqrt{5})^{n}

も解となる。

 x^{2} - 5y^{2} = 4 については一般論がある。 (x, y) = (2, 0), (3, 1) が基本解となることがわかる。 x^{2} - 5y^{2} = 11 についても基本回として  (x, y) = (4, 1) が見つかる。以上から

  •  (4 + \sqrt{5})(2)(9 + 4\sqrt{5})^{n}
  •  (4 + \sqrt{5})(2)(9 - 4\sqrt{5})^{n}
  •  (4 + \sqrt{5})(3 + \sqrt{5})(9 + 4\sqrt{5})^{n}
  •  (4 + \sqrt{5})(3 + \sqrt{5})(9 - 4\sqrt{5})^{n}
  •  (4 + \sqrt{5})(3 - \sqrt{5})(9 + 4\sqrt{5})^{n}
  •  (4 + \sqrt{5})(3 - \sqrt{5})(9 - 4\sqrt{5})^{n}

が一般解を与えることがわかる (これしか解がないことに議論は省略)。このうち  x ≡ 2 \pmod 5 となるものを抽出していく。

5673835352990