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

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

ProjectEuler 140 Modified Fibonacci golden nuggets

ProjectEuler 数学(整数問題) 方程式 Pell方程式多項式・FPS(形式的冪級数) 漸化式数列 FPSテク:漸化式の母関数を求める

ペル方程式の練習

問題へのリンク

問題概要

数列 $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