Project Euler 174: Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements.

We shall define a square lamina to be a square outline with a square "hole" so that the shape possesses vertical and horizontal symmetry.

Given eight tiles it is possible to form a lamina in only one way: 3×3 square with a 1×1 hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae.

If t represents the number of tiles used, we shall say that t = 8 is type L(1) and t = 32 is type L(2).

Let N(n) be the number of t ≤ 1000000 such that t is type L(n); for example, N(15) = 832.

What is ∑ N(n) for 1 ≤ n ≤ 10?

Analysis

Wanting a solution that could solve both problem 173 and 174 we decided that in a couple of minutes we could put something together that would run quickly. Instead of determining factors for each iteration we just modeled the building of the lamina which is faster than a solution counting even factors. In fact when the scale increases to, say 10,000,000 this program will outperform most others.

One drawback is the use of memory, but for the sake of development time it was of little consequence.

Project Euler 174 Solution

Afterthoughts

• See also, Project Euler 173 Solution: