Project Euler/174

Problem Statement

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

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: a 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 \le 1000000 $ such that $ t $ is type $ L(n) $; for example, $ N(15) = 832 $.

What is $ \sum_{n=1}^{10} N(n) $?

Explanation

This problem builds on Problem 173. A square lamina with inner hole side $ s_h $ and thickness $ k $ uses $ t = 4k(s_h + k) $ tiles.

The type $ L(n) $ of $ t $ is the number of distinct laminae that can be formed using exactly $ t $ tiles. For each valid lamina (with $ t \le 10^6 $), count how many distinct $ (s_h, k) $ pairs produce that exact $ t $. Then tally how many $ t $ values have each type $ n $ for $ n = 1 $ through $ 10 $, and sum those counts.

Answer

20956691