PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 166 / 十字

0 ≤ d ≤ 9 なる整数 d で埋められた 4x4 の格子がある。以下の格子ではそれぞれの行, 列の和が12であり,斜めの和も12である。

6 3 3 0
5 0 4 3
0 7 1 4
1 2 4 5

0 ≤ d ≤ 9 なる d で 4x4 の格子をそれぞれの行,列,斜めの和が同じとなるように埋める方法は何通りあるか?

Problem 166 - Project Euler


「未知数が16個,等式条件が9個。独立なパラメータは7個なので,データ量は10^7個。楽勝」と思いましたが,実際にやってみたら独立なパラメータは8個で,データ量は10^8個でした。

まず等式条件をReduceで簡約化します。

すべての成分が0以上9以下になるものを数えるとできあがり。30分以上かかりました。ためしに For ループも使ってみましたが,時間はもっとかかります。同じことをC++でやると楽々1分を切れるのですが。

Project Euler 207 / 整数分割方程式

いくつかの正整数 k は整数の分割式
 4^t = 2^t + k
が成り立つ。4^t, 2^t, k はすべて正の整数で, t は実数とする。

最初の 2 つの分割は 4^1 = 2^1 + 2 と 4^1.5849625... = 2^1.5849625... + 6 である。

t も整数である分割を完全と呼ぶ。m≥1をみたす m に対して P(m) を k≤m で分割が完全である割合と定義する。P(6) = 1/2 である。

次の表はいくつかの m に対する P(m) の例である.

  • P(5) = 1/1
  • P(10) = 1/2
  • P(15) = 2/3
  • P(20) = 1/2
  • P(25) = 1/2
  • P(30) = 2/5
  • P(180) = 1/4
  • P(185) = 3/13

P(m) < 1/12345 をみたす最小の m を求めよ。

Problem 207 - Project Euler


 4^t = 2^t + k で 2^t=x(>0) とおきます。x^2=x+k から

 x=2^t=\dfrac{1+\sqrt{4k+1}}{2}\qquad (1)

 \therefore t=\log_2 \dfrac{1+\sqrt{4k+1}}{2}\qquad (2)

(1)から 2^t が整数になる条件は 4k+1 が奇数の平方数であることです。
4k+1=(2a-1)^2とおくと

 k=a(a-1)\qquad (3)

(2)の t が整数になる条件は真数が 2^b の形の数であることです。

 k=2^b(2^b-1)\qquad (4)

1≦k≦m を整理すると

 (3):2\leqq a\leqq \left[\dfrac{1+\sqrt{4m+1}}{2}\right]

 (4):1\leqq b\leqq \left[\log_2\dfrac{1+\sqrt{4m+1}}{2}\right]

これらの個数の比が P(m) です。

P(m) は階段状の関数です。分母が増加するときに減少するので,m を(3)の形のものにしぼって調べました。

Floor 関数の中身の「/2」を「*0.5」に変えると速くなります。

Project Euler 151 / 規格寸法用紙 : 期待値問題

ある印刷屋では毎週16回の定期的な仕事がある。毎回,A5サイズの特殊な色校正用紙を1枚使う。

月曜日の朝に主任はA1サイズの特殊紙が入った新しい封筒を開ける。

彼はA1の紙を半分に切る。するとA2の紙が2枚できる。片方を半分に切るとA3の紙が2枚できる。以下,A5の紙を得るまで繰り返し,1枚をその週の最初の仕事に使う。使われなかった紙はすべて元の封筒に戻す。

f:id:variee:20170903203403g:plain

各仕事の際に主任は封筒からランダムに紙を1枚取り出す。A5の紙を取り出したなら,そのまま仕事に使う。そうでない場合は半分に切ることを繰り返し,A5の紙を1枚使って残りは元の封筒に戻す。

週の最初と最後の仕事以外で封筒に紙が1枚だけ入っている回数の期待値を求めよ。四捨五入して小数点以下6桁で答えること (x.xxxxxxという形)。

Problem 151 - Project Euler


各用紙の枚数の組を (a2, a3, a4, a5) で表します。
1回目の作業が終わった後の状態は (1, 1, 1, 1)で,この後は次のような操作の繰り返しです。

  • 操作1:ある用紙を1枚減らす
  • 操作2:その用紙より小さい用紙を1枚ずつ増やす

各用紙の枚数の変化を追ってもらちがあかないので,「ない用紙は減らせない」「A5の紙に対しては操作2がない」に注意して期待値の漸化式を立式します。

Project Euler 103 / 特殊和集合:最適化(1)

大きさ n の集合 A の要素の和を S(A) で表す。空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば,A を特殊和集合と呼ぼう。

  1. S(B)≠S(C); つまり,部分集合の和はすべて異なる
  2. B が C より多くの要素を含んでいれば S(B) > S(C) となる

ある n に対し S(A) が最小化されていれば,それを最適特殊和集合と呼ぼう。はじめの5つの最適特殊和集合は下に与えられる。

  • n = 1: {1}
  • n = 2: {1, 2}
  • n = 3: {2, 3, 4}
  • n = 4: {3, 5, 6, 7}
  • n = 5: {6, 9, 11, 12, 13}

ある最適特殊和集合 A = {a1, a2, ... , an} に対して次の最適特殊和集合は
B = {b, a1+b, a2+b, ... ,an+b} となりそうである。ここで b は前列の「中央の」要素である。

この「法則」を用いると n = 6 に対する最適特殊和集合は
A = {11, 17, 20, 22, 23, 24} で,S(A) = 117 と予期するだろう。しかし,これは最適特殊和集合ではない。n = 6 に対する最適特殊和集合は
A = {11, 18, 19, 20, 22, 25} で, S(A) = 115 である。
これに対応する集合の文字列は 111819202225 である。

n = 7 に対する最適特殊和集合 A に対応する文字列を求めよ。

Problem 103 - Project Euler


まだ解けていませんが,n=7 の特殊和集合は1つ見つかりました。問題文中の方法で n=6 の例から作れます。
{20, 31, 38, 39, 40, 42, 45}

「最適」を調べる方法としては,これを基準として各項をずらしていく多重ループしか思いつきません。mathematica 的にはかなりダサいような気がしますが,いつか書きます。

Project Euler 90 / 2つの立方体の数字

立方体の6面それぞれに異なる数字(0から9)が書かれている。2番目の立方体も同様になっている。異なる位置に2つの立方体を隣りあわせることで様々な2桁の数を作ることができる。たとえば平方数である64も作ることができる。

f:id:variee:20170812010252g:plain

両方の立方体の数字をうまく選ぶと100以下のすべての平方数(01, 04, 09, 16, 25, 36, 49, 64, 81)を作ることが可能である。

たとえば {0, 5, 6, 7, 8, 9} を一方の立方体に,{1, 2, 3, 4, 8, 9} をもう一方の立方体に配置すればよい。

しかし,6と9を逆さまに回転することを許すと {0, 5, 6, 7, 8, 9} と {1, 2, 3, 4, 6, 7} のような配列で9つすべての平方数をあらわすことができる。

順番ではなくそれぞれの立方体の数字に着目して配列を区別する。

  • {1, 2, 3, 4, 5, 6} は {3, 6, 4, 1, 2, 5} と同じものとし,
  • {1, 2, 3, 4, 5, 6} は {1, 2, 3, 4, 5, 9} と異なるものとする。

6と9を逆さにすることを許すため,最後の例で区別された両方の配列のかわりに {1, 2, 3, 4, 5, 6, 9} という要素数が7つに拡張された配列を使用して2桁の数を作ることにする。

すべての平方数を表示しうる2つの立方体の異なる配列の組はいくつあるか。

Problem 90 - Project Euler

チェック用の関数を作る

まずは問題文中で与えられた2つのサイコロ a, b が条件をみたすことを確かめる関数を作ります。たとえば01を作れる条件は「aが0を含み,bが1を含む」または「aが1を含み,bが0を含む」です。MemberQ を使います。

無事,チェック成功しました。


6と9の扱い

「6しか含まなかったら9を加え,9しか含まなかったら6を加える」と変換することにしました。


本番

Subsets[Range[0, 9], {6}] でサイコロのもとを作ってチェックしました。無事,1.1秒で終了。