のてすきあ　− 完全独習非プログラマー −

Haskell で Project Euler を解く素人遊び

Problem 66

Project Euler

次の形式の2次のディオファントス方程式；

x2 - Dy2 = 1

においてxを最小とするD（≦1000）を求める。

　力技でリスト内包表記をぶつけてみても答えは返ってこない。問題でディオファントス方程式とあるが、与えられた式は特別なディオファントス方程式で、名前も特別にペル方程式と呼ばれているらしい。ペル方程式の解は連分数展開と密接な関係があり、実はこの問題は前の2つ（Problem 64, 65）のコードを合体させれば一瞬で解ける。詳しくはWikipedia

ペル方程式 - Wikipedia

を見ていただきたい。

　なるほど、なぜこんな「知っていれば解ける」系の問題が出るのだろうと思ったが、これは「知っていろ」ということだったのだ。Problem 64, 65 の関門を通ってきた我々には、もはや躓く要素は何もない。 　

　

これも数学勝負★

Problem 65

Project Euler

ネイピア数eの連分数展開による有理数近似。

　多分プログラミング的にアレコレやることも可能なのだろう。しかし考えるのが面倒（問題としてあまり魅力を感じない）ので、数学の知識を使ってストレートに漸化式を解くことにする。

　無理数の有理数近似については、以下が知られている。ハッキリ言ってこの問題は、これを知っているかどうかだけで勝負が決まるので、プログラミングクイズとしては悪問であると思う。

無理数 \omega = [a_0,a_1,...,a_n,... ] に対して数列 \{{p_n}\}_{n=-1}^{\infty}

および数列 \{{q_n}\}_{n=-1}^{\infty} を

\begin{eqnarray} \left\{ \begin{array}{l} p_{-1} = 1 \\ q_{-1} = 0 \end{array} \right. \end{eqnarray}
\begin{eqnarray} \left\{ \begin{array}{l} p_{0} = a_0 \\ q_{0} = 1 \end{array} \right. \end{eqnarray}
\begin{eqnarray} \left\{ \begin{array}{l} p_{n} = a_n p_{n-1} + p_{n-2} \\ q_{n} = a_n q_{n-1} + q_{n-2} \end{array} \right. \end{eqnarray}


と定めると

[a_0,a_1,...,a_n ] = \frac{p_n}{q_n}

が成り立つ。


むしろはてなブログでTexを使う練習？…★

Problem 64

Project Euler

無理数の連分数展開

　Project Euler を解き続けて60問。今回初めて諦めようかと思ってしまった。難しい。
　無理数の連分数展開はそんなに難しくない。しかしそれを数値計算でやろうとすると、誤差の問題でうまく行かないのである。引き算を回避したり割り算を回避したりしても、やっぱりうまく行かない。
　ここで考える。数値計算は可能な限り整数の世界で完結するべきではないか。誤差や桁落ちを心配しなくて良い土俵に上がるべきではないか。…。ココから先は完全に数学の世界である。

\displaystyle{ \alpha = \frac{P + \sqrt D}{Q}\\ = \alpha^{\prime} + \frac{(P - \alpha^{\prime} Q ) + \sqrt D}{Q}\\ = \alpha^{\prime} + \frac{((P - \alpha^{\prime} Q ) + \sqrt D)((P - \alpha^{\prime} Q ) - \sqrt D)}{Q((P - \alpha^{\prime} Q ) - \sqrt D)}\\ = \alpha^{\prime} + \frac{(P - \alpha^{\prime} Q )^2 - D}{Q((P - \alpha^{\prime} Q ) - \sqrt D)}\\ = \alpha^{\prime} + \frac{1}{\frac{Q((P - \alpha^{\prime} Q ) - \sqrt D)}{(P - \alpha^{\prime} Q )^2 - D}}\\ = \alpha^{\prime} + \frac{1}{\frac{Q((\alpha^{\prime} Q - P) + \sqrt D)}{D - (P - \alpha^{\prime} Q )^2}}\\ = \alpha^{\prime} + \frac{1}{\frac{(\alpha^{\prime} Q - P) + \sqrt D}{\frac{D - (P - \alpha^{\prime} Q )^2}{Q}}}\\ }

ここで

\alpha^{\prime} = \lfloor \frac{P + \sqrt D}{Q} \rfloor

である。

要するに（という表現が適切かは分からないが）、展開の中で次々に

P \rightarrow \alpha^{\prime} Q - P\\ Q \rightarrow {\frac{D - (P - \alpha^{\prime} Q )^2}{Q}}

と置き換えていけば、連分数を展開できる。ただし

\frac{D - (P - \alpha^{\prime} Q )^2}{Q}

が整数の方が都合が良いので、その辺りは適宜処理をする。漸化式ができてしまえば、Haskell的な課題は何もない。


　

Haskellの練習にならない…★

Problem 63

Project Euler

mnの形をしたn桁の数は全部でいくつあるか

　一行日記である。考えどころは探索範囲だが、数xの桁数はlog_10 x で調べることができることを踏まえれば、mとnをどの範囲まで調べれば良いか判断することができる。

　以下のプログラムではmとnが逆になっているが…。

　

ワンライナー☆

Problem 62

Project Euler

3乗数でお互いに数字の並べ替えとなる5組の数を見つけ、その最小値を求める。

　3乗数を小さい方から順番に調べつつ、[使っている数字の順列が同じ]という分類で同値類にまとめていく。元の数が5つになったところでそれを出力すれば完了である。各3乗数に「使っている数字の順列」のラベルを貼っていきたいなぁ…ということで、これもまた連想リストが使えるケースである。

　

同値類にもData.Mapが使える☆

Problem 61

Project Euler

三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.

三角数P3,n=n(n+1)/21, 3, 6, 10, 15, ...
四角数P4,n=n21, 4, 9, 16, 25, ...
五角数P5,n=n(3n-1)/21, 5, 12, 22, 35, ...
六角数P6,n=n(2n-1)1, 6, 15, 28, 45, ...
七角数P7,n=n(5n-3)/21, 7, 18, 34, 55, ...
八角数P8,n=n(3n-2)1, 8, 21, 40, 65, ...

3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.

  1. この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
  2. それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
  3. 4桁の数の組で上の2つの性質をもつはこの組だけである.

三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる6つの巡回する4桁の数からなる唯一の順序集合の和を求めよ.

　問題の紹介が面倒なのでココより借用した。

　まずは解けた自分を褒めてあげたい。最初の挑戦で律儀に全組み合わせを評価する手法を試みたが、当然のように全く計算が終わらず。これは腰を据えて考えなければならないということで、効率的な検索と評価の方法に悩む。

　全体的な方針は以下；
　最初に与えられた2桁から始まる多角数のリストを得るための関数を作りたいと考えた。実際はこれを関数ではなく連想リストにすることで効率的な検索を図った。
　また、最終的な答えはサイクリックだと分かっているので、探索はどこから始めても良いだろうということで、八角数を与えて、そこから所望の数列が得られるか探すことを基本方針とした。
　あとは下2桁から次の数を見つける連鎖が続く限り数をリストで繋いでいきつつ、n角数のnに重複が出たら打ち止めることにすると6連鎖が見つかる。重複を除外しているので7連鎖以降が見つかる可能性はない。そのようにして見つかった6連鎖の中から先頭と末尾がきちんとサイクルしていることを確認すればOK。findを使っているが、これは問題文より答えが1つしかないことが分かっているから使った。別にfilterを使っても計算時間が余計にかかる（リストの最後まで走査するため）だけで、同じ答えに辿り着く。

…などと書いているが、正解に辿り着くまで暇な細切れ時間を使いつつ5日ほど掛かってしまった。苦労したぶん解けた喜びも大きい。

　

大金星☆

Problem 60

Project Euler

3,7,109,673 の素数の組は、それぞれをつなぎ合わせた数（例：7109, 1097, 673109など）も全て素数になる。そのように連結可能な5つの数の組を探し、その中で5数の和が最も小さくなるものを見つける。

　ある条件を満たす素数を見つけるパターンは、計算に時間がかかりがちだが、その中でもなるべく効率的な方法を見つけたい。ナイーブに全検索すると絶対に計算が終わらないので、いかに実装するかである。
　実装のイメージはネットワークである。3,7,11．．．と素数を順番に空間に配置していき、その度に既に配置されていた数と連結可能なら線を繋いでいく。（実装上は線で繋がっているものをリストにした）
　3から始まって、[3],[7],[7,3],[11],[11,3],[13],[17],[17,3],[19],[19,7],[19,13],[23],[23,11],[29],[31],[31,3],[31,19],[37],[37,3],[41],[43],[47],[47,23],[53],[59],[59,3],[61],[61,7],[61,13],[67],[67,3],[67,37],[67,37,3], ...　と順々に点を打っていくイメージである。（伝わるか？）

　自分の近くに連結可能な仲間がいなくても、ずっと遠くにいる可能性があるため、排除できる数がない。例えば41は近くに友達は見つからないが、ずっと先の227とペアになることができる。また、３つ組があったとしても、そのうち2つと仲間になれる別の数が見つかる可能性もある。そういう可能性を余さず評価していくための関数がfindGroupである。

　mainをdo式にしたのは、単純に数の組とその和の両方を出力するのに、do式の方が書きやすかったからというだけで、あまり意味はない。

　頑張ったつもりだが、それでもコンパイルして結果が返ってくるまで3分かかる。

　

速い方法があるかも知れない★