イントロ
CodeIQで遊んでいたら、数学的背景が似ている問題を見つけて面白かったので、本記事ではその繋がりを説明してみたい。
※既に締め切られています。マヨイドーロの問題文はこちら。ルートパワーは要約すると、「$(1 + \sqrt{2} + \sqrt{3} + \sqrt{5})^n$の整数項を$10^7$で割った余りを求めよ」という問題です。
マヨイドーロ問題の回答
$K$回反転してZまたはYに出るルートを脱出ルートと呼ぶ。脱出ルートの数を$a_K$とする。
- $K=0$のとき、脱出ルートはXBCZの1通りだから$a_0 = 1$である。
- $K=1$のとき、脱出ルートはXBAY, XBCBAYの2通りだから$a_1 = 2$である。
- $K=2m(m \ge 1)$のとき、脱出ルートは下記のいずれかに重複せず分類できる。
- $2m-2$回反転してCにいて、BCZとたどるルート($a_{2m-2}$通り)
- $2m-1$回反転してAにいて、BCZとたどるルート($a_{2m-1}$通り)
- $K=2m+1(m \ge 1)$のとき、脱出ルートは下記のいずれかに重複せず分類できる。
- $2m-1$回反転してAにいて、BAYとたどるルート($a_{2m-1}$通り)
- $2m$回反転してCにいて、BAYとたどるルート($a_{2m}$通り)
よって、$a_K$は下記の漸化式に従う。
\left \{
\begin{array}{ll}
a_0=1 \\
a_1=2 \\
a_{K+2} = a_{K+1} + a_K (K \ge 0)
\end{array}
\right . \tag{1}
$K$が奇数のとき、またそのときに限り脱出ルートの出口がYになるから、$N\ge1$のとき、$P$は$a_K$の$N$以下の奇数項を足したものである。いま、漸化式$(1)$から$a_{K+2} - a_K = a_{K+1}(K \ge 0)$であり、この両辺を$K=0, 2, 4, ..., 2m-2$に渡って足し合わせることで下記が得られる。
a_{2m} - 1 = \sum_{k=0}^{m-1} a_{2k+1}
よって、$M$を$N+1$以下の最大偶数とすると、
P=a_{M}-1 \tag{2}
となる。なお、$N=0$のとき、$P=0=a_{0}-1$であるから、式$(2)$は$N\ge0$の範囲にも適用できる。結局、式$(1)$の隣接三項間漸化式を$K=0$から順番に適用していけば、$P$を求めることができる。漸化式を行列に直す等少し工夫して、提出したコードはこんな感じになった。
ルートパワー問題の回答
$\alpha_\pm$を
\left \{
\begin{array}{ll}
\alpha_{+} = 1 + (\sqrt{2} + \sqrt{3} + \sqrt{5}) \\
\alpha_{-} = 1 - (\sqrt{2} + \sqrt{3} + \sqrt{5}) \\
\end{array}
\right . \tag{3}
で定めると、これらは二次方程式
(x-\alpha_{+})(x-\alpha_{-}) = 0
の解である。この式を展開して
x^2 = 2x + 9+2\sqrt{6}+2\sqrt{10}+2\sqrt{15} \tag{4}
を得る。今、有理数$a, b, c, d$で作られる数$a + b\sqrt{6}+c\sqrt{10}+d\sqrt{15}$に対して、演算子$Z$を
Z(a + b\sqrt{6}+c\sqrt{10}+d\sqrt{15}) = a \tag{5}
で定める($a$が一意に定まることの証明は簡単なので略)。式$(4)$と演算子$(5)$を用いると、
\left \{
\begin{array}{ll}
Z(x^{n+2}) = 2Z(x^{n+1}) + 9 Z(x^{n}) + 2 Z(\sqrt{6} x^n) + 2 Z(\sqrt{10} x^n) + 2 Z(\sqrt{15} x^n) \\
Z(\sqrt{6} x^{n+2}) = 2Z(\sqrt{6} x^{n+1}) + 12 Z(x^{n}) + 9 Z(\sqrt{6} x^n) + 6 Z(\sqrt{10} x^n) + 4 Z(\sqrt{15} x^n) \\
Z(\sqrt{10} x^{n+2}) = 2Z(\sqrt{10} x^{n+1}) + 20 Z(x^{n}) + 10 Z(\sqrt{6} x^n) + 9 Z(\sqrt{10} x^n) + 4 Z(\sqrt{15} x^n) \\
Z(\sqrt{15} x^{n+2}) = 2Z(\sqrt{15} x^{n+1}) + 30 Z(x^{n}) + 10 Z(\sqrt{6} x^n) + 6 Z(\sqrt{10} x^n) + 9 Z(\sqrt{15} x^n)
\end{array}
\right . \tag{6}
という漸化式が得られる。$ \boldsymbol{a}_n = (Z(x^{n}), Z(\sqrt{6} x^{n}), Z(\sqrt{10} x^{n}), Z(\sqrt{15} x^{n}))^T$と置くと、
\left \{
\begin{array}{ll}
\boldsymbol{a}_{0} = (1, 0, 0, 0)^T\\
\boldsymbol{a}_{1} = (1, 0, 0, 0)^T\\
\boldsymbol{a}_{n+2} = 2 \boldsymbol{a}_{n+1} + A \boldsymbol{a}_{n} (n \ge 0)
\end{array}
\right . \tag{7}
となってすっきりする。ただし、
A = \left (
\begin{matrix}
9 & 2 & 2 & 2 \\
12 & 9 & 6 & 4 \\
20 & 10 & 9 & 4 \\
30 & 10 & 6 & 9
\end{matrix}
\right )
と置いた。求める値は$Z(\alpha_+^n)$を$10^7$で割った余りであるから、マヨイドーロと同様、式$(7)$の隣接三項間漸化式を$n=0$から順番に適用していけば答えが得られるが、今回は入力が$10^{10}$と大きいため、高速化を行う必要がある。
式$(7)$には足し算と掛け算しか出てこないから、$\rm{mod} , 10^7$の下で下記の合同式が成立する。
\left \{
\begin{array}{ll}
\boldsymbol{a}_{0} \equiv (1, 0, 0, 0)^T\\
\boldsymbol{a}_{1} \equiv (1, 0, 0, 0)^T\\
\boldsymbol{a}_{n+2} \equiv 2 \boldsymbol{a}_{n+1} + A \boldsymbol{a}_{n} (n \ge 0)
\end{array}
\right . \tag{8}
また、$\rm{mod} , 10^7$の下で
\boldsymbol{a}_{n+6000000} \equiv \boldsymbol{a}_{n}
が言えるため、結局$Z(\alpha_+^n)$を$10^7$で割った余りは、$Z(\alpha_+^{n % 6000000})$を$10^7$で割った余りに等しい。これによって式$(7)$の適用回数を抑えることができる。以上をまとめると、このようなコードになる。
次数下げと漸化式の関係
マヨイドーロ問題も、ルートパワー問題も、本質的には隣接三項間漸化式から$n$番目を求める問題であり、一般項を求めることができる。しかし、これらはいずれも無理数のべき乗を含んでいて扱いが面倒である。実際、マヨイドーロ問題はフィボナッチ数列だから$\sqrt{5}$を含んでいるし、ルートパワー問題に出てくる行列$A$の固有値・固有ベクトルはもっとひどい形をしている。
その一方で、漸化式自体は有理数(整数)の足し算と掛け算で構成されているため、一般項の計算結果それ自体は整数になることが分かる。「一方には無理数が出てくるが、他方には有理数しか出てこない」あるいはもっと一般的に、「一方の属する体が他方の属する体の拡大体になっている」。我々はこういう関係性を持つ数の組み合わせをよく知っている。$n$次方程式の解と係数だ。
フィボナッチ数列$F_n$の一般項は、方程式
x^2 - x - 1 = 0 \tag{9}
の解を大きい順に$\phi_+, \phi_-$とすると、
F_n = \frac{1}{\sqrt{5}}(\phi_+^n - \phi_-^n) \tag{10}
と表せる。$(9)$の係数は有理数体$\mathbb{Q}$に含まれるが、$\phi_{\pm} = (1 \pm \sqrt{5})/2$は$\mathbb{Q}$には含まれない($\mathbb{Q}$に$\sqrt{5}$を加えた添加体$\mathbb{Q}(\sqrt{5})$に含まれる)。よって、$\phi_\pm^n$(やその線形結合である$F_n$)を直接書き下そうとすると$\mathbb{Q}(\sqrt{5})$の要素を$n$乗する必要が出てくるが、式$(9)$を使うと$x^{n+2} = x^{n+1} + x^{n}$より、
\phi_\pm^{n+2} = \phi_\pm^{n+1} + \phi_\pm^n
が得られる。つまり、式$(9)$の解の$n$乗は、$\mathbb{Q}$の要素を係数とした解の$n-1$次式でも表現することができる。
まったく同様に、式$(4)$の係数は$\mathbb{Q}(\sqrt{6}, \sqrt{10}, \sqrt{15})$に含まれる。解は式$(3)$より$\mathbb{Q}(\sqrt{2}, \sqrt{3}, \sqrt{5})$に含まれる。$\sqrt{6}\sqrt{10} = 2\sqrt{15}$, $\sqrt{10}\sqrt{15} = 5\sqrt{6}$, $\sqrt{15}\sqrt{6} = 3\sqrt{10}$に注意すると、
\mathbb{Q}(\sqrt{6}, \sqrt{10}, \sqrt{15}) = \{ p + q\sqrt{6} + r\sqrt{10} + s\sqrt{15} | p, q, r, s \in \mathbb{Q}\}
\mathbb{Q}(\sqrt{2}, \sqrt{3}, \sqrt{5}) = \{ p + q\sqrt{2} + r\sqrt{3} + s\sqrt{5} + t\sqrt{6} + u\sqrt{10} + v\sqrt{15} + w \sqrt{30}| p, q, r, s, t, u, v, w \in \mathbb{Q}\}
が得られる。よって、$\alpha_\pm^n$を直接書き下そうとすると$\mathbb{Q}(\sqrt{2}, \sqrt{3}, \sqrt{5})$の要素を$n$乗する必要が出てくるが、$\alpha_\pm^n$は$\mathbb{Q}(\sqrt{6}, \sqrt{10}, \sqrt{15})$を係数とした$\alpha_\pm$の$n-1$次式でも書けることが分かる。ルートパワー問題の場合、無理数は残ってしまうがその自由度(=次数=添加体を線形空間とみなしたときの基底の数)は直接表現の$8$に比べて半分の$4$に抑えられる。式$(7)$の行列$A$が$4$次に抑えられているのは、次数下げを利用したことによるものである。
まとめ
解の$n$乗は、次の2通りの方法で表現することができる。
- 「解の属する体」の要素
- 「係数の属する体」の要素を係数とする解の$n-1$次式
「係数の属する体」の方が「解の属する体」よりも「同じか小さい」ため、次数下げの繰り返し適用を用いることで表現を簡略化できることが多い。この辺の事情はガロア理論に関係しており、数学ガール／ガロア理論などを読むとより詳しく分かる。なるほど！