読者です 読者をやめる 読者になる 読者になる

今までに解いたProject Euler

Project Euler

ソースファイル:
Microsoft OneDrive - Access files anywhere. Create docs with free Office Online.

Friend Key:
186068_Hw0qIP8ugAzQDdCfJ67GKNC3Q7NO76Pl

Project Euler 68

Project Euler

全てのノードに重複が無いよう,また'10'は外側のノードに来るように1~10の数字を配置しました.
結構早く答えは求まりますが,ソースで入れ子になってるループがなんかダサいです.
スマートな解法はあるのでしょうか・・・

https://ideone.com/S6bSlV

Project Euler 67

Project Euler

ある行のノードへの最大コストは,その前の行の隣り合う2つのノードへの最大コストの大きい方で決まります. よって,1行読むごとに,その行に含まれるノードへの最大コストだけ記録すれば,100行読み終えたときに答えが求まります.

https://ideone.com/TIBWQb

Project Euler 66

Project Euler

 この問題を解くのに必要だったことを以下にメモします.定理の詳しい証明などは他の書籍を見て下さい.
 解答: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}$を求めることで,問題の答えが求まります.

Project Euler 65

Project Euler

{2, 1,2,1, ..., 1,2k,1, ...,1,66,1}
を配列に格納し,これを後ろから使って,連分数を普通の分数に直しました.

Pythonです.

http://codepad.org/DFbRlC4U

Project Euler 64

Project Euler

平方根が,整数部分と小数部分の和で表されるように展開しました.
時間が無いので,解けたという報告だけ.

http://ideone.com/xS6Sqg

Project Euler 63

Project Euler

{i}{n}乗の対数(底10)をとることを考えます.{(i,n\in \mathbf{N})}
それによって{i^n}の桁数が分かるので,
{n - 1 \leq n\log i < n}
を満たせば良いと分かります.右辺より,
{\log i < 1 \Leftrightarrow i < 10}
左辺より,
{\log i \geq 1-\frac{1}{n} \Leftrightarrow i \geq \lceil 10^{1-\frac{1}{n}} \rceil (\because i \in \mathbf{N})}
{\therefore \lceil 10^{1-\frac{1}{n}} \rceil \leq i < 10}
この左辺は,{n \rightarrow}大で,10に近づき,9.0を超えると上の不等式を満たす{i}は存在しなくなります.
{\lceil 10^{1-\frac{1}{n}} \rceil > 9.0}
{\therefore n > 21.8}
を得ます.従って,{1 \leq n \leq 21}について,3つ上の不等式を満たす{i}の個数を足し合わせれば答えが求まります.

https://ideone.com/25WkBn