PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 126 / 直方体層

3x2x1 の直方体の表面すべてを覆いつくすのに必要最小限の立方体の数は 22 個である。

f:id:variee:20180608145751g:plain

さらにこの立体に表面を覆いつくすように2層目を追加すると,46 個の立方体が必要である。3層目は 78 個,4層目は 118 個の立方体が必要である。

ところで 5x1x1 の直方体への1層目も 22 個の立方体が必要である。同様に 5x3x1, 7x2x1, 11x1x1 の直方体への1層目もすべて 46 個の立方体である。

何層目かが n 個の立方体からなる直方体の数を C(n) と定義する。
C(22) = 2, C(46) = 4, C(78) = 5, C(118) = 8

154 は C(n) = 10 をみたす最小の n である。C(n)=1000 をみたす最小の n を求めよ。

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

C(n)を求める

受験算数でよくある表面積の問題のように真正面,真上,真横から見た図を描いて数えます。

 C(1)=2(ab+bc+ca)
 C(n+1)=C(n)+4(ab+bc+ca)+8(n-1)

これを使って一般項を求めました。
 C(n)=4n^2+4(a+b+c-3)n
 \qquad\qquad +8-4(a+b+c)+2(ab+bc+ca)

C(n)=1000 をみたす n を探す

a, b, c と層の数 k についての4重ループを使って,C(n)=1000 をみたす最小の n を探します。

アタリをつけるため,はじめは「a, b, c は100以下で,k は10以下」のような条件で探したのですが,この方法では C(n) の正しい値を求められませんし,時間も非常にかかります。

C(n) の上限を20000として検索するよう直したところ,Mathematica を使う意味を感じない,普通の手続き型っぽいソースとなりました。

計算時間は約60秒。C++でやってみたら1秒でした。通常,C++の100倍以上の時間がかかるので,Mathematicaとしては頑張ったほうかなと思います。