PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 173 / 100万枚以下のタイルで何通りの穴あき正方形を作れるか

輪郭が正方形で,正方形の穴を持ち,縦にも横にも対称性をもつものをlaminaeと定義する。たとえば32個のタイルを使うと以下の二つの異なったlaminaeが作れる。

f:id:variee:20170526000013g:plain

100個以下のタイルを使うと41種類のlaminaeが作れる。

100万個以下のタイルを使うと何種類のlaminaeが作れるか?

Problem 173 - Project Euler


外側,内側の正方形の一辺の長さを y+2x, y とおいて格子点を数える問題に帰着させます。タイルの枚数を n とすると

 (y+2x)^2 - y^2 \leqq n

 \therefore 1\leqq y\leqq \left[\dfrac{n-4x^2}{4x}\right]

右辺が1以上になる条件は

 1\leqq x\leqq \left[\dfrac{\sqrt{n+1}-1}{2}\right]

あとは定石通り「x=k 上の格子点を数える → k に対する和をとる」で解けます。