PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 128 / 六角形タイルの差分

六角形のタイルを図のように反時計回りに置いていく。

f:id:variee:20180602222929g:plain

タイル n とそれに隣接するタイルのうち,書いてある数字と n の差が素数となるタイルの枚数を PD(n) と定義する。

たとえばタイル8の場合,まわりのタイルの数字と8の差は 12, 29, 11, 6, 1, 13 となるので PD(8) = 3 であり,同様に PD(17) = 2 である。

PD(n) の最大値は3であることが示せる。
PD(n) = 3 をみたす n を昇順に並べた数列の10番目の項は271である。

この数列について2000番目のタイルを求めよ。

本家:Problem 128 - Project Euler
日本語訳:Problem 128 - PukiWiki

実験

与えられた図をもとに調べると最初の6項は 1, 2, 8, 19, 20, 37 で,まわりの数や差は次のようになっています。カッコで囲んだ数は素数です。

n まわりの数 差(ソート後)
1 2,3,4,5,6,7 1,(2),(3),4,(5),6 1,(2),(3),4,(5),6
2 1,3,7,8,9,19 1,1,(5),6,(7),(17) 1,1,(5),6,(7),(17)
8 2,9,19,20,21,37 6,1,(11),12,(13),(29) 1,6,(11),12,(13),(29)
19 2,7,8,18,36,37 (17),12,(11),1,(17),18 1,(11),12,(17),(17),18
20 8,21,37,38,39,61 12,1,(17),18,(19),(41) 1,12,(17),18,(19),(41)
37 8,19,20,36,60,61 (29),18,(19),1,(23),24 1,18,(19),(23),24,(29)

規則性があるのかないのかはっきりしない感じですが,中央のマスの数字をxとして,まわりに x+1 や x-1 があったり,連続する2数(または3数)があったりすることがわかります。

以下,8~19や20~37のような並びを「周期」と呼ぶことにし,n 個目の周期の先端を H(n),末端を T(n) であらわします。8~19について考えます。

まわりのタイルのパターンは4つ

中央のマスの数字をxとして,そのまわりの6枚のタイルに書かれた数字のパターンを分類してみました。

辺の途中

9, 11, 13, 15, 17, 19は
{x-1, x+1, y, y+1, z, z+1} 型です。

  • x-(x-1)=1, (x+1)-x=1 は素数ではない
  • x-y, x-(y+1) のうち素数はたかだか1個
  • z-x, (z+1)-x のうち素数はたかだか1個

素数はたかだか1+1=2個しかありません。

先端,末端以外の頂点

10, 12, 14, 16, 18は
{x-1, x+1, y, z-1, z, z+1} 型です。
x-1, x+1が素数を与えないことは上で見たので,他の数について考えます。

たとえばx=10のときy=3, z=23です。H(1)=2, H(2)=8, H(3)=20から順に1,2,3進んだところにy=3, x=10, z=23があり,一般に
{z-H(n+1)} - {x-H(n)} と {x-H(n)}-{y-H(n-1)} は一致します。H(n)はつねに6の倍数なので,次のことが言えます。

  • y, zの偶奇は等しい
  • zとz+1, z-1の偶奇は異なる

要するに偶奇に注目するとxのまわりの残り4数は {y, z}, {z+1, z-1} の2グループに分類できるので,素数はたかだか2個しかありません。

先端

H(n) =3n(n-1)+2 の真上から反時計回りに
H(n+1), H(n+1)+1, H(n)+1, H(n-1), T(n), T(n+1)
が並びます。H(n), T(n) を6で割った余りが0, 5であることを考えると,素数を与える可能性があるのは次の3箇所です。
H(n+1)+1, T(n), T(n+1)

末端

T(n) の真上から反時計回りに
T(n+1), H(n), H(n-1), T(n-1), T(n)-1, T(n+1)-1
が並びます。先端の場合と同様,素数を与える可能性があるのは3箇所です。
H(n), H(n-1), T(n+1)-1

解法

先端と末端について調べればOK。0.5秒でした。

tail[n] - head[n]などを展開した式(すべて1次式)を使うと0.3秒に縮まりますが,この差は誤差の範囲内ですね。

Project Euler 111 / 重複桁を持つ素数

重複した桁を含む 4 桁の素数を考える。
各桁に1は最大3個含まれ,このような素数は9つある。

1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111


n 桁の素数を考える。各桁に d が最大 M(n, d) 個含まれるとする。このような素数が N(n, d) 個あり,それらの和が S(n, d) であるとする。


Digit, d M(4, d) N(4, d) S(4, d)
0 2 13 67061
1 3 9 22275
2 3 1 2221
3 3 12 46214
4 3 2 8888
5 3 1 5557
6 3 1 6661
7 3 9 57863
8 3 1 8887
9 3 7 48073

S(4, d) (0 <= d <= 9) の総和は 273700 である。
S(10, d) の総和を求めよ。

本家:Problem 111 - Project Euler
日本語訳:Problem 111 - PukiWiki

n=4の場合

4桁の素数のうち,1を3個含むものは9個あります。これは

 \{1,1,1,x\}\quad (x=0,\, 1,\, \cdots,\, 9)

の permutation が素数になるかどうか調べればわかります。

0を2個含むものが13個あることは {0, 0, x, y} の permutation について調べればわかります。

n=10の場合

以上を一般化すればn=10の場合も解けます。ただ,桁数が増える分,調べる回数も増えます。本当は

「ある数を9個含むものがあるかどうか調べる」
→「なければ8個含むものを調べる」
→「なければ7個含むものを調べる」
→……

のようにして解くべきなのですが,面倒だったので8個までで十分なことを事前に調べた上で答えを出しました。


内訳はこうなっていました。

d M(10,d) N(10,d) S(10,d)
0 8 8 38000000042
1 9 11 12882626601
2 8 39 97447914665
3 9 7 23234122821
4 9 1 4444444447
5 9 1 5555555557
6 9 1 6666666661
7 9 9 59950904793
8 8 32 285769942206
9 9 8 78455389922

n=4 の場合もそうですが,M(n, d)=n-1, n-2 まで考えれば十分なのが不思議です。

Project Euler 109 / ダーツ

問題の概要

ダーツをダブルアウト方式でプレイするとき,100点未満の状態からチェックアウトする方法は何通りあるか求めよ。
各回に得られる点数は1~20点の1倍(シングル),2倍(ダブル),3倍(トリプル)の他,ブルの25点,ブルのダブルの50点である。

本家:Problem 109 - Project Euler
日本語訳:Problem 109 - PukiWiki

解法

ダーツのルールを初めて知りました。

  • 最後は必ずダブル。
  • 最後以外の回はシングル,ダブル,トリプルどれでもいい。

この条件で3回(以下)の合計得点を99点以下にする方法が何通りあるか求めます。第31問と同様にべき級数を使いました。

variee.hatenadiary.com

6点の場合

問題文中で与えられている6点でチェックアウトする場合を考えます。素点が1点~4点の場合を考えればOKです。ダブルの級数は
 p_2=x^2+x^4+x^6+x^8

シングル,トリプルはそれぞれ次のようになります。
 p_1=x+x^2+x^3+x^4
 p_3=x^3+x^6+x^9+x^{12}

素朴に考えるとq=p1+p2+p3として
 q^2\times p_2+q\times p_2+p_2
を展開すればよさそうですが,この式を展開したときのx^6の係数は11ではなく14です。このズレの原因を調べるため,q^2*p2+q*p2+p2 の各項の6次の係数を見てみましょう。
以下,素点 x のシングル,ダブル,トリプルを Sx, Dx, Tx であらわし,最後の回の得点はカッコつきであらわします。

p2 の6次の係数1は
 6=(D3)
と対応。これは問題なし。

q*p2 の6次の係数4は
 2+4=S2+(D2)=D1+(D2)
 4+2=S4+(D1)=D2+(D1)
と対応。これも問題なし。

q^2*p2 の6次の係数は9。実際には次の6通りしかなく,ここで3個のズレが生じています。
 1+1+4=S1+S1+(D2)
 1+3+2=S1+S3+(D1)=S1+T1+(D1)
 2+2+2=S2+S2+(D1)=S2+D1+(D1)=D1+D1+(D1)

これは1回目と2回目の得点について次のようにダブルカウントしているためです。
 S1+S3+(D1)=S3+S1+(D1)
 S1+T1+(D1)=T1+S1+(D1)
 S2+D1+(D1)=D1+S2+(D1)

1回目と2回目の点のとり方が違う場合はこういう重複が起こり,同じ場合は起こりません。

1回目と2回目が同じ場合の多項式は
x^(1+1)+x^(1*2+1*2)+x^(1*3+1*3)
のような項の和です。一旦,これを q^2に足して2で割ることで重複を避けることに成功しました。

100点未満の場合

以上をもとに計算したところ,約0.2秒で終了。これが解答です。


一般の場合

ついでに全パターンを調べてみました。0点以上170点以下のチェックアウトの場合の数は次のようになります。

プロットすると2本の曲線のような変わったグラフになります。

f:id:variee:20180601014447p:plain

Project Euler 107 / 最短ネットワーク

問題の概要

頂点数40の重みつき有向グラフgが与えられる。その最小全域木をg'とする。gの重みの総和とg'の重みの総和の差を求めよ。

本家:Problem 107 - Project Euler
日本語訳:Problem 107 - PukiWiki

解法

頂点数7のとき

WeightedAdjacencyGraph でグラフを作り,FindSpanningTree で最小全域木を求めます。問題文中で与えられているサンプルでやってみましょう。

まずはグラフ作成。

f:id:variee:20180531161218p:plain

最小全域木は赤い点線のようになります。

f:id:variee:20180531161428p:plain

頂点数40のとき

同じ要領で頂点数40の場合を処理し,重みの総和の差を計算します。

約3秒かかっていますが,これはデータファイルをダウンロードしているためです。ローカルでやると0.004秒ほどで答えが出ます。

どんなグラフになるか

実際にどんな最小全域木ができるのか見てみましょう。

f:id:variee:20180531162455p:plain

元のグラフと重ねるとこうなります。

f:id:variee:20180531162510p:plain

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:最近の問題なので答えの数値は省略します。