Project Euler/173

Problem Statement

Link: https://projecteuler.net/problem=173

We shall define a square lamina to be a square outline with a square "hole" so that the shape possesses vertical and horizontal symmetry. For example, using exactly thirty-two square tiles we can form two different square laminae.

With one-hundred tiles, and not necessarily using all of the tiles at one time, it is possible to form forty-one different square laminae.

Using up to one million tiles how many different square laminae can be formed?

Explanation

This problem extends the hollow square laminae concept from Problem 173. The key insight is that a square lamina with an inner hole of side length $ s_h $ and outer side length $ s_h + 2k $ requires $ 4k(s_h + k) $ tiles, where $ k $ is the distance between the hole and the outer edge.

For a fixed $ k $, the number of possible laminae is $ \lfloor \frac{T}{4k} - k \rfloor $ where $ T = 10^6 $ is the maximum number of tiles. The maximum $ k $ occurs when $ s_h = 1 $, giving $ k_{\max} = \lfloor \frac{\sqrt{T+1} - 1}{2} \rfloor $.

The answer is obtained by summing over all $ k $ from 1 to $ k_{\max} $.

Answer

1572729