Project Euler 70

解答:https://ideone.com/IxvPb3

解法

 $\frac{n}{\varphi(n)}$が最小となる条件を考えると,$\varphi(n)=n-1$($n$は素数)なので,$n$が大きな素数であることが考えられます.しかし,このとき$n$と$\varphi(n)$で桁の置換はできません.
 $n$が2つの素数の積の場合を考えます.$n=p_1 \cdot p_2$で$\varphi(n)=(p_1 - 1)(p_2 - 1)$なので,$\frac{n}{\varphi(n)}$が十分小さく,かつ桁の置換ができる可能性はあります.実際,問題の例にある$n=87109$は2つの素数の積です.
 2つの素数の上限についてですが,$n<10^{7}$より,$p_1,p_2 < \sqrt{10^{7}}=3163$です.従って,その上限までの素数の中から2組選び,調べることで答えが求まります.私は素数リストの上限を多く見積もって4000にしました.

Project Euler 69

解答:http://codepad.org/AWFZdG1J
最後にも述べていますが,プログラムを書く必要がない問題だと分かりました.電卓があれば良いです.

解説

 次の公式(2)を使用します:
$n$を素因数分解して, $$ \begin{equation} n = {p_1}^{\alpha_1}{p_2}^{\alpha_2}\cdots {p_k}^{\alpha_k}  (p_1 < p_2 < \cdots < p_k) \tag{1} \end{equation} $$ と書けるとすると, $$ \begin{equation} \varphi(n) = n\left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_k} \right) \tag{2} \end{equation} $$ 式(2)の証明は調べるといろいろ出てきます.
 式(2)の両辺を$n$で割り,逆数をとると, $$ \begin{equation} \frac{n}{\varphi(n)} = \frac{p_1 p_2 \cdots p_k}{(p_1 - 1)(p_2 - 1) \cdots (p_k - 1)} \tag{3} \end{equation} $$ と書けます.左辺は今回の問で求めるべき関数です.右辺は,式(1)で出てきた$\alpha$に依らない,素数だけの関数です.
 さらに,右辺の関数は$k$について単調増加です.従って,$n$は1,000,000以下でかつ$n = 2 * 3 * 5 * \cdots $です.プログラムを組むまでもないんですね.

Project Euler 68

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

https://ideone.com/S6bSlV

Project Euler 67

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

https://ideone.com/TIBWQb

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}$を求めることで,問題の答えが求まります.