PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 607 / Marsh Crossing

Frodo and Sam need to travel 100 leagues due East from point A to point B. On normal terrain, they can cover 10 leagues per day, and so the journey would take 10 days. However, their path is crossed by a long marsh which runs exactly South-West to North-East, and walking through the marsh will slow them down. The marsh is 50 leagues wide at all points, and the mid-point of AB is located in the middle of the marsh. A map of the region is shown in the diagram below:

f:id:variee:20171205201150p:plain

The marsh consists of 5 distinct regions, each 10 leagues across, as shown by the shading in the map. The strip closest to point A is relatively light marsh, and can be crossed at a speed of 9 leagues per day. However, each strip becomes progressively harder to navigate, the speeds going down to 8, 7, 6 and finally 5 leagues per day for the final region of marsh, before it ends and the terrain becomes easier again, with the speed going back to 10 leagues per day.

If Frodo and Sam were to head directly East for point B, they would travel exactly 100 leagues, and the journey would take approximately 13.4738 days. However, this time can be shortened if they deviate from the direct path.

Find the shortest possible time required to travel from point A to B, and give your answer in days, rounded to 10 decimal places.

Problem 607 - Project Euler

Marsh = 沼地,湿地だそうです。

第一印象は「スネルの法則を使えば解けそう」でした。
「n*sin θ = (一定)」にしたがって曲がる経路が最短だろうと見当をつけましたが,スタートとゴールが決まっているので,この方法では解けません。
線分ごとの時間の和を求める方法で解きました。

全体を45度回転して,各点を
P1(-50/√2, -50/√2), P2(x1, -25), P3(x2, -15), P4(x3, -5),
P5(x4, 5), P6(x5, 15), P7(x6, 25), P8(50/√2, 50/√2)
と定め,移動速度を
v={10, 9, 8, 7, 6, 5, 10}
とします。必要な時間は
 f=\displaystyle \sum_{i=1}^7 \dfrac{P_i P_{i+1}}{v_i}

NMinimize で f の最小値を数値的に求めます*1

NMinimize ははじめて使ったのですが,変数の範囲を何も制約しないと0.05秒で,
-50/√2 < x1 < x2 < x3 < x4 < x5 < x6 < 50/√2
の制約をつけるとかえって遅くなって 0.2秒になるのが意外でした。

*1:最近の問題なので答えの数値は省略します。

算チャレ1036回を解いてみた

「算数にチャレンジ!!」さんの第1036回の問題を解いてみました。

2つの整数アとイがあります。アとイはともに1以上100以下の整数です。ア+イが偶数で,ア×2+イ×3 が5の倍数となるような(ア, イ)は何組あるでしょうか。
http://www.sansu.org/used-html/index1036.html

www.sansu.org

Mathematicaで解く

まずはそのまま解いてみました。答えは1000組。

妙にきれいな答えが出て不思議に思ったので,一般解も求めてみました。
連立合同式を Reduce すると
 x\equiv y\pmod{10}
が答えだとわかります。

1 ≦ x ≦10, 1 ≦ y ≦10 での解は

 x=y=k\quad (1\leqq k\leqq 10)

の10個。x, y それぞれに「+10」が10回ずつできるので,求める個数は

 10\cdot 10^2=1000\,\text{個}

となります。

手計算で解くなら

手計算で解く場合, 2x+3y\equiv 0\pmod{5} の 3 を -2 に変えることがポイントだと思います。

 2(x-y)\equiv 0\pmod{5}\quad \therefore x-y\equiv 0\pmod{5}

これだけで 1 ≦ x ≦10, 1 ≦ y ≦10 の解の候補が (1, 1), (1, 6) などの 2*10=20 個に減ります。「和が偶数」の条件でさらに半分の10個にしぼれて,これが 1 ≦ x ≦10, 1 ≦ y ≦10 の解です。あとは「+10」が10回ずつできることを使えば解けます。

Project Euler 239 / 擬似フォーチュン数

偶数の正整数 N は 2 の累乗であるか素因数がすべて連続した素数である場合,許容的と呼ぶ。最初の 12 個の許容的な数は 2,4,6,8,12,16,18,24,30,32,36,48 である。

N が許容的であるとき,N+M が素数である最小の整数 M > 1 を N の擬似フォーチュン数(pseudo-Fortunate number)と呼ぶ。

たとえば N=630 は許容的である。630 は偶数で,その素因数は連続する素数 2, 3, 5, 7 である。

631 より大きい次の素数は 641 であり,630 の擬似フォーチュン数は M=11 である。同様に 16 の擬似フォーチュン数は 3 である。

10^9 未満の許容的な数 N に対して, すべての異なる擬似フォーチュン数の合計を求めよ。

Problem 293 - Project Euler


問題文の流れは

  1. 許容的な数を求める
  2. 擬似フォーチュン数を求める

ですが,擬似フォーチュン数の方が簡単なのでこちらから書きました。
NextPrime を使います。

次に許容的な数を求めます。「10^9 未満」の条件から,使える素数は9個です。

「2だけ使った数の集合を作る」→「その各要素に3をかけたものの集合を作る」のような操作を繰り返して,最後に和集合をとります。
NestWhileList と AppendTo で書きました。

計算時間は約0.3秒で,許容的な数は6656個,相異なる擬似フォーチュン数は41個でした。ダブりまくりです。

Project Euler 315 / デジタルルート時計(2)

前回の記事の続きです。Sam と Max の表示コストをそれぞれ計算して差をとるかわりに,両者の差だけ計算します。

variee.hatenadiary.com

桁ごとのコスト差

表示がないことをΦであらわします。ある桁の表示が a から b に変わるとき,Sam は「a→Φ→b」,Max は「a→b」と推移するので表示コストの差は次の形の式で求められます。

 g(a,\, b)=f(a,\, \phi)+f(\phi,\, b)-f(a,\, b)

全体としての差

この問題では 10^7 以上 2*10^7 以下の数が相手なので,時計の表示は次のように変化します。最高でも3回しか推移しません。

  1. 8桁の数
  2. 1+9*7=64以下の数(2桁以下)
  3. 7+9=16以下の数(2桁以下)
  4. 1桁の数

最初に8桁の数を表示するところでは差は生じません。また,8桁→2桁のとき Sam も Max も上位6桁は「a→Φ」型の変化をするので,ここでも差は生じません。
元の数を n,各位の数字の和を f(n) であらわすと

 n→f(n)→f^2(n)→f^3(n)

のかわりに

 \bmod(n,100)→f(n)→f^2(n)→f^3(n)

を考えればいいことになります。

実装

問題文には 10^7 という大きな数が書いてありますが,実際に相手にするのは2桁以下の数から2桁以下の数へ変化するときのコスト差です。

「1桁→2桁」(最初だけおこりうる),「2桁→2桁」,「2桁→1桁」の各場合に対応できる関数を書いてできあがりです。約10秒でした。

Project Euler 315 / デジタルルート時計(1)

Sam と Max は2個のデジタル時計を「デジタルルート(数字根)時計」に作り変えるよう依頼されている。
デジタルルート時計は数字根をステップごとに計算するデジタル時計である。

f:id:variee:20170927013825g:plain

時計に数字が与えられると,時計は数字を表示し,計算を開始する。たとえば,時計に 137 という数が与えられると"137"→"11"→"2" と表示してから真っ黒になり,次の数を待つ。

各デジタル数字はセグメント状のライトから構成される。横セグメントが3本(上,中,下)と縦セグメントが4本(左上,右上,左下,右下)である。数 "1" は右上と右下の縦セグメントでできており,数 "4" は中の横セグメントと左上, 右上, 右下の縦セグメントからできている。数 "8" はすべてのセグメントが点灯する。

時計はセグメントを点灯/消灯させるときに限りエネルギーを消費する。"2" を点灯させるには 5 回の遷移を要する。"7" は 4 回だけ遷移を要する。

Sam と Max は2個の異なる時計を作る。

Sam の時計は 137 のような数を与えられると "137" を表示し,パネルを消灯してから次の数("11")を点灯し,再び消灯してそして最終的に最後の数("2")を点灯,しばらくして消灯する。たとえば 137 では Sam の時計は次のように動く。

  • "137":(2 + 5 + 4) x 2 = 22 回の遷移("137" の点灯/消灯)
  • "11" :(2 + 2) x 2 = 8 回の遷移("11" の点灯/消灯)
  • "2" :(5) x 2 = 10 回の遷移("2" の点灯/消灯)

合計で 40 回の遷移である。

Max の時計は異なる動きをする。パネル全体を消灯するのではなく,次の数に必要のないセグメントのみを消灯するという賢いやり方である。数 137 に対して Max の時計は次のように動く。

"137":2 + 5 + 4 = 11 回の遷移("137" の点灯)
     7 回の遷移(数 "11" に必要ないセグメントの消灯)
"11" :0 回の遷移(数 "11" はすでに正しく点灯済み)
     3 回の遷移(始めの "1" と2つ目の "1" の下部分を消灯;
     上部分は数 "2" と共通である)
"2" :4 回の遷移("2" にするため残りのセグメントを点灯)
     5 回の遷移("2" を消灯)

合計で 30 回の遷移である。

もちろん,Max の時計のほうが Sam より電力の消費が少ない。2つの時計に A = 10^7 から B = 2 x 10^7 の間の素数が与えられる。Sam の時計で必要な遷移の総数と Max の時計で必要な遷移の総数の差を求めよ。

Problem 315 - Project Euler


今回は Sam について考えます。

数字根とは正の整数の各位の和を求める操作を繰り返して最終的に得られる1桁の数のことです。Mathematica の場合,Total@IntegerDigits[n] の NestWhile で計算できます。

パネルを表示するコストは 1→2, 2→5 のような写像で求めます。計算には約10秒かかります。


コストを求める前に Tally で各数字が何回使われるかを数えると若干早くなります。こちらは6.6秒。


Max のコストも同じようにして求められますが,2人のコストを求めた上で差を求めるのは無駄が多いです。次回,最終的な答えを求める記事では Sam と Max の差だけ計算します。