Project Euler 66
この問題を解くのに必要だったことを以下にメモします.定理の詳しい証明などは他の書籍を見て下さい.
解答:https://ideone.com/WF6K5w
ペル方程式
Project Eulerの問題文中では「2次のディオファントス方程式を考えよう」と書かれていますが, $$\begin{equation} x^{2}+Dy^{2}=\pm{1} \tag{1} \end{equation}$$ は特にペル方程式と呼ばれるようです.そしてペル方程式には「最小解」があり,今回の問題では各$D$に対する最小解$(x,y)$を求め,その中で$x$が最大となる$D$を答えれば良かったです.
1次分数変換の記法
行列を用いて1次分数変換(メビウス変換と言うらしい)を表します: $$\begin{equation} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \alpha =\frac{a\alpha +b}{c\alpha +d} \tag{2} \end{equation}$$ ($a,b,c,d,\alpha \in \mathbb{C}$)そして,この変換の2つの合成を表す行列は2つの行列の積と一致することが直接(行列の成分を仮定して)確かめることができます.つまり,$B(A\alpha)=(BA)\alpha$です.
連分数を行列表記する
以下では,今回の問題を意識して,実数のみを扱います.
$$\begin{equation}
\begin{pmatrix}
c & 1 \\
1 & 0
\end{pmatrix}\alpha=
c+\frac{1}{\alpha}
\end{equation}$$
より,連分数$[c_0,c_1,\ldots ,c_{n-1},\alpha_n]$は
$$\begin{eqnarray} [c_0,c_1,\ldots ,c_{n-1},\alpha_n] &=& c_0+\frac{1}{[c_1,\ldots c_{n-1},\alpha_n]} \\ &=& \begin{pmatrix} c_0 & 1 \\ 1 & 0 \end{pmatrix}[c_1,\ldots c_{n-1},\alpha_n] \\ &=& \begin{pmatrix} c_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} c_1 & 1 \\ 1 & 0 \end{pmatrix}\cdots \begin{pmatrix} c_{n-1} & 1 \\ 1 & 0 \end{pmatrix}\alpha_n \end{eqnarray}$$
と行列で書くことが出来ます.上の章で書いたように行列のかけ算を初めにしてもいいので,左からかけ算をしてみると,ある法則に気付きます:
$$\begin{eqnarray} &=& \begin{pmatrix} c_0c_1+1 & c_0 \\ c_1 & 1 \end{pmatrix} \begin{pmatrix} c_2 & 1 \\ 1 & 0 \end{pmatrix}\cdots \begin{pmatrix} c_{n-1} & 1 \\ 1 & 0 \end{pmatrix}\alpha_n \\ &=& \begin{pmatrix} c_0c_1c_2+c_0+c_2 & c_0c_1+1 \\ c_1c_2+1 & c_1 \end{pmatrix} \begin{pmatrix} c_3 & 1 \\ 1 & 0 \end{pmatrix}\cdots \begin{pmatrix} c_{n-1} & 1 \\ 1 & 0 \end{pmatrix}\alpha_n \end{eqnarray}$$
かけた後の行列の2列目が,かける前の左の行列の1列目と一致しています.そこで,数列${p_k}$,${q_k}$を以下で定義します:
$$\begin{equation} \begin{pmatrix} p_k & p_{k-1} \\ q_k & q_{k-1} \end{pmatrix}:= \begin{pmatrix} c_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} c_1 & 1 \\ 1 & 0 \end{pmatrix}\cdots \begin{pmatrix} c_{k-1} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} c_k & 1 \\ 1 & 0 \end{pmatrix} \end{equation}$$ $$\therefore \begin{cases} p_k = c_kp_{k-1} + p_{k-2} p_0 = c_0, p_{-1} = 1 & \\ q_k = c_kq_{k-1} + q_{k-2} q_0 = 1, q_{-1} = 0 & \tag{3} \end{cases} $$
$\sqrt{D}$を連分数展開
$\sqrt{D}$の連分数展開により,ペル方程式の解が得られることを示します.
今回の問題では,$D$は平方数でない正の整数です.そして,その連分数展開が周期的であることはProblem 64で見ました.$\sqrt{D}=[c_0;(c_1,c_2,\ldots ,c_k)]$,$x_1 = [(c_1,c_2,\ldots ,c_k)]$とすると,
$$\begin{eqnarray}
\sqrt{D} &=&
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}x_1 \\
&=&
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
c_1 & 1 \\
1 & 0
\end{pmatrix}\cdots
\begin{pmatrix}
c_k & 1 \\
1 & 0
\end{pmatrix}x_1 \ \ (\because 周期がk) \\
&=&
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}
\left\{\begin{pmatrix}
c_1 & 1 \\
1 & 0
\end{pmatrix}\cdots
\begin{pmatrix}
c_k & 1 \\
1 & 0
\end{pmatrix}\right\}^2 x_1 \\
&=& \cdots \\
&=&
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}
\left\{\begin{pmatrix}
c_1 & 1 \\
1 & 0
\end{pmatrix}\cdots
\begin{pmatrix}
c_k & 1 \\
1 & 0
\end{pmatrix}\right\}^m x_1 \ \ (m\in \mathbb{N}) \\
&=& \begin{pmatrix}
P_{mk} & P_{mk-1} \\
Q_{mk} & Q_{mk-1}
\end{pmatrix} x_1
\end{eqnarray}
$$
と書けます.ここで,
$$\begin{pmatrix}
P_{mk} & P_{mk-1} \\
Q_{mk} & Q_{mk-1}
\end{pmatrix}
:= \begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}
\left\{\begin{pmatrix}
c_1 & 1 \\
1 & 0
\end{pmatrix}\cdots
\begin{pmatrix}
c_k & 1 \\
1 & 0
\end{pmatrix}\right\}^m \tag{4}
$$
としました.$P_{mk}$,$Q_{mk}$も式(3)の漸化式に従います.
一方,
$$\sqrt{D} =
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}x_1
$$より,
$$x_1 =
\begin{pmatrix}
c_0 & 1 \\
1 & 0
\end{pmatrix}^{-1}\sqrt{D}
=\begin{pmatrix}
0 & 1 \\
1 & -c_0
\end{pmatrix}\sqrt{D}
$$
$$
\begin{eqnarray}
\therefore \sqrt{D} &=& \begin{pmatrix}
P_{mk} & P_{mk-1} \\
Q_{mk} & Q_{mk-1}
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -c_0
\end{pmatrix}\sqrt{D} \\
&=& \begin{pmatrix}
P_{mk-1} & P_{mk}-c_0P_{mk-1} \\
Q_{mk-1} & Q_{mk}-c_0Q_{mk-1}
\end{pmatrix}\sqrt{D} \tag{5}
\end{eqnarray}
$$
という式が得られました.この最後の等号が$\sqrt{D}$によらず成立する条件を調べます.
$$
\begin{pmatrix}
p & q \\
r & s
\end{pmatrix} =
\begin{pmatrix}
P_{mk-1} & P_{mk}-c_0P_{mk-1} \\
Q_{mk-1} & Q_{mk}-c_0Q_{mk-1}
\end{pmatrix}
$$
とすると,式(2)より,
$$
\sqrt{D} = \begin{pmatrix}
p & q \\
r & s
\end{pmatrix}\sqrt{D} = \frac{p\sqrt{D}+q}{r\sqrt{D}+s} \\
\therefore rD-q+(s-p)\sqrt{D}=0
$$
$$
\therefore rD=q, p=s \tag{6}
$$
となりました.ここで,式(5)の行列の行列式を考えます.
$$
\begin{eqnarray}
\begin{vmatrix}
P_{mk-1} & P_{mk}-c_0P_{mk-1} \\
Q_{mk-1} & Q_{mk}-c_0Q_{mk-1}
\end{vmatrix} &=&
\begin{vmatrix}
p & q \\
r & s
\end{vmatrix} \\
&=& p^{2}-Dr^{2} \ \ (\because (6))\\
&=& P_{mk-1}^{2}-DQ_{mk-1}^{2}
\end{eqnarray}
$$
また,
$$
\begin{eqnarray}
\begin{vmatrix}
P_{mk-1} & P_{mk}-c_0P_{mk-1} \\
Q_{mk-1} & Q_{mk}-c_0Q_{mk-1}
\end{vmatrix} &=&
\begin{vmatrix}
P_{mk} & P_{mk-1} \\
Q_{mk} & Q_{mk-1}
\end{vmatrix}
\begin{vmatrix}
0 & 1 \\
1 & -c_0
\end{vmatrix} \\
&=& \begin{vmatrix}
c_0 & 1 \\
1 & 0
\end{vmatrix}
\left\{\begin{vmatrix}
c_1 & 1 \\
1 & 0
\end{vmatrix}\cdots
\begin{vmatrix}
c_k & 1 \\
1 & 0
\end{vmatrix}\right\}^m
\begin{vmatrix}
0 & 1 \\
1 & -c_0
\end{vmatrix} \\
&=& (-1)^{mk}
\end{eqnarray}
$$
従って,式(5)の行列の行列式を考えると,
$$
P_{mk-1}^{2}-DQ_{mk-1}^{2} = (-1)^{mk}
$$
を得ます.これはペル方程式です.つまりこの式は,$\sqrt{D}$を連分数展開して得られる各整数がペル方程式の解になると言っています.
今回の問題を解く
今回の問題では,式(1)の右辺は$+1$です.従って,$mk$は偶数である必要があります.なので,まずは$\sqrt{D}$の周期$k$を求めます.これはProblem 64でやりました.
次に$m$がいくつであるべきか考えます.今回の問題の条件に,$x(=P_{mk-1})$は最小である,とあるので,$m$はできるだけ小さい方が良いと考えました.なぜなら,$c_l>0(l=0,1,\ldots ,k)$なので,式(3)より$m$の増加とともに$P_{mk}$も増加するからです.従って,周期$k$により$m$は$1$か$2$のどちらかとなります.「最小解」とは,この$m$に対する$P_{mk-1}$,$Q_{mk-1}$のようです.
$m$,$k$が決まれば,後は$D\leq 1000$に対し,式(3)から$P_{mk-1}$を求めることで,問題の答えが求まります.