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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 82 / 経路の和:3方向

下記の5次の正方行列で一番左の行の任意のセルから開始し一番右の行の任意のセルで終わる道を探索する。ただし上下右にのみ移動できるものとする。一番小さなパスは下で赤の太字で示されたものである。このときの合計は994になる。

13167323410318
20196342965150
630803746422111
537699497121956
80573252437331

今, 31Kのテキストファイル matrix.txt には80×80の行列が書かれている。一番左の行から一番右の行へ移動する際の一番小さなパスの和を求めよ。

Problem 82 - Project Euler


第81問などの類題です。3方向に動けるとかなり自由度が高くなります。

variee.hatenadiary.com

たとえば上から2行目,右から2個目の 422 から出発する場合,5通りの移動ができます。

  • 2つ上がってから右
  • 1つ上がってから右
  • すぐに右
  • 1つ下がってから右
  • 2つ下がってから右

最初は第81問と同じように解こうとしたのですが,最終的に「i 行目から k 行目に移動してから右」の Min をとることに落ちつきました。

Project Euler 205 / サイコロゲーム

ピーターは4面のサイコロを9つ持っている。サイコロの各面には1, 2, 3, 4と書いてある。コリンは6面のサイコロを6つ持っている。サイコロの各面には1, 2, 3, 4, 5, 6と書いてある。

ピーターとコリンはサイコロを投じ,出た目の合計を比べる。合計が多い方が勝ちである。出た目の合計が等しければ引き分けになる。

ピーターがコリンに勝つ確率はいくつだろうか? 10進7桁にroundし, 0.abcdefg という形で回答欄に入力せよ。

Problem 205 - Project Euler


ブルートフォースとまではいきませんが,ストレートに場合の数を計算して解きました。

Reduce で方程式の整数解を求めます。たとえばコリンの目が6,7になるのは次のようなときです。

解が1個のときは各変数の値を &&(=「かつ」)で結ぶのに対し,解が複数個あるときはそれを( )で囲んで ||(=「または」)で結んだものを返します。これによって個数を数える Length の振る舞いが変わるので,解が1個の場合だけ別扱いとして後は普通に計算しました。

Project Euler 74 / 桁の階乗による連鎖

145は各桁の階乗の和が自分自身に一致することで有名である。

1! + 4! + 5! = 1 + 24 + 120 = 145

169の性質はあまり知られていない。これは自分自身に戻る数の中で最長の列をなす。このように他の数を経て自分自身に戻るループは3つしか存在しない。

  • 169 → 363601 → 1454 → 169
  • 871 → 45361 → 871
  • 872 → 45362 → 872

どのような数からスタートしてもループに入ることが示せる。例を見てみよう。

  • 69 → 363600 → 1454 → 169 → 363601 (→ 1454)
  • 78 → 45360 → 871 → 45361 (→ 871)
  • 540 → 145 (→ 145)

69から始めた場合,列は5つの循環しない項を持つ。また,100万未満の数から始めた場合,最長の循環しない項は60個であることが知られている。

100万未満の数から開始する列の中で60個の循環しない項を持つものはいくつあるか?

Problem 74 - Project Euler


素直にループに入るまでの回数を数えました。最初に書いたのがこれ。


1分をこえてしまったのでメモ化して,既出の数が出てきたら即ループを抜けるように変えました。結果は4.3秒。効果てきめんでした。

Project Euler 60 / 素数ペア集合

素数3, 7, 109, 673は非凡な性質を持っている。任意の2つの素数を任意の順でつなげると,また素数になっている。たとえば7と109を用いると,7109と1097の両方が素数である。これら4つの素数の和は792である。これはこのような性質をもつ4つの素数の集合の和の中で最小である。

任意の2つの素数をつなげたときに別の素数が生成される5つの素数の集合の和の中で最小のものを求めよ。

Problem 60 - Project Euler

解を1つ求める

ブルートフォースを覚悟していたのですが,グラフ理論を使ったら意外にすんなり解けました。

  • Prime[i] と Prime[j] からできる数が両方とも素数となるような点 i, j を辺で結んでグラフを作る
  • 5個の点からなるクリーク(フルメッシュな部分グラフ)を探す
  • その頂点に対応する素数の和を求める

ちなみに FindClique の結果は
{6, 692, 751, 868, 1051}
で,素数に直すと
{13, 5197, 5701, 6733, 8389}
です。

最小性の検証

ここまでやったところで本家サイトに答えを入力し,正解となったのですが,よく考えて見ると最小性を示していません。5個目の素数は大きいが和は小さい組があるかもしれないからです。以下,これを検証します。

すでに和として 26033 を得ているので,nmax の上限はわかります。2861です。

解は3組ありました。

{6, 692, 751, 868, 1051}
{91, 160, 317, 2787, 2240}
{4, 203, 347, 1481, 2111}

これらに対応する値の最小値を求めて完全終了です。

Project Euler 62 / 立方数置換

立方数 41063625(=345^3) は桁の順番を入れ替えると2つの立方数になる。56623104(=384^33) と 66430125(=405^33) である。41063625 は立方数になるような桁の置換をちょうど3つもつ最小の立方数である。

立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ。

Problem 62 - Project Euler

第1案:とりあえず答えを出す

立方数を桁ごとに区切ってソートしたもののリストを作って重複を調べました。この場合,
(重複度5の数として得られる数)=(並べ替えで得られる最大の数)
なので,それと同じ数字を使う数の最小値を求めています。

1分を少しオーバーしてしまいました。何度も何度もリストを作るのは無駄なので,次はここを直します。

第2案:リスト作りも集計も1回だけ

重複度が4以下なら新しい数をリストに追加していく方法も考えましたが,毎回集計しなおす点は変わらないので却下。リスト作りも集計も1回で済ませる方法を考えました。

まずはリストの大きさの見積もりです。上のコード中の g[n] を使います。n の値を1000刻み,100刻み,……で調べていくと 8384^3 がわかります。

この数は12桁です。並べ替えで桁数は変わらないので,n^3 が13桁になる n=10^4 まで調べれば十分だとわかります。

コードをそれっぽく直せばできあがり。0.05秒。約1500倍ですね。


第3案:Split でグループ分け

第1案,第2案とも最後にリストを再検索するところが無駄なので,f[n] を定義し直して
{(n^3 を桁ごとに区切ったリスト), n^3}
を返すようにしました。

こうすると Tally で重複度を調べることはできなくなるので,Split でグループ分けして,各グループの要素数を数えます。時間は0.04秒。第2案よりちょっと速くなりました。