PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 174 / 穴あき正方形の数え上げ

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。8個のタイルが与えられると,3x3の1x1の穴をもつlaminaしか作れないが,32個のタイルならば2つの異なったlaminaeが作れる。

f:id:variee:20170526000013g:plain

タイルの枚数を t で表すと,t=8 は L(1) 型, t=32 は L(2) 型であるといえる。

L(n) 型となるような t (≤ 1000000) の数を N(n) とする。たとえば,N(15)=832 である。

∑ N(n) (1 ≤ n ≤ 10) を求めよ。

Problem 174 - Project Euler


第173問の類題です。

variee.hatenadiary.com

外側,内側の正方形の一辺の長さを y+2x, y とおいて,タイルの枚数を n とおきます。

 n=(y+2x)^2-y^2=4x(x+y)

n は4の倍数です。(x, y) の個数を求めるため,n/4 の約数を数えます。

コード中,2で割って Floor をとっているのは平方数対策です。たとえば n/4=4 の約数は 1, 2, 4 で x+y>x を考えると1と4はペアにできますが,2は自分自身とペアにできません。こういうケースを除いています。