Detailed mathematical approach

Problem Summary

A hollow square lamina is a square frame: an outer square of side length \(o\) surrounds a smaller concentric square hole of side length \(i\). The number of tiles used by that frame is the area difference \(o^2-i^2\). Because the hole must stay centered with an integer border width, the two side lengths must have the same parity and satisfy \(o-i\ge2\).

For each tile total \(t\le 10^6\), let \(N(t)\) be the number of different laminae that use exactly \(t\) tiles, where different outer/inner side pairs count as different arrangements. The goal is to count how many tile totals satisfy

$1\le N(t)\le 10.$

Mathematical Approach

The implementations solve the problem by enumerating every valid lamina exactly once, recording how often each tile total appears, and then counting the totals whose multiplicity lies between one and ten. The mathematics is therefore about describing the valid state space cleanly and proving that the loops cover it without omissions or duplicates.

Geometry Turned Into Arithmetic

Each lamina is determined by a pair \((o,i)\) with \(o>i\ge1\), \(o\equiv i\pmod2\), and tile count

$T(o,i)=o^2-i^2=(o-i)(o+i).$

If we write the border thickness as \(k=(o-i)/2\ge1\), then \(o=i+2k\), and the same quantity becomes

$T(o,i)=4k(i+k).$

This reformulation exposes two useful invariants. First, every admissible tile total is a multiple of \(4\). Second, a distinct arrangement is exactly a distinct pair of an inner side length and a thickness, or equivalently a distinct pair \((o,i)\).

Bounding the Outer Square

For a fixed outer side length \(o\), the smallest possible lamina is the thinnest one, obtained by taking \(i=o-2\). Its tile count is

$T_{\min}(o)=o^2-(o-2)^2=4o-4.$

If this minimum already exceeds the limit \(L\), then no lamina with that outer side length can contribute. So the only outer squares worth considering are those with

$4o-4\le L.$

That is exactly why the outer loop stops at the first \(o\) for which the thinnest ring would already use too many tiles.

Why the Inner Loop Steps by Two

Once \(o\) is fixed, the hole must remain centered, so the inner side length must keep the same parity as \(o\). The valid inner sizes are therefore

$i=o-2,\ o-4,\ o-6,\dots$

down to the smallest positive value of matching parity. This is not a programming convenience; it is the exact arithmetic description of all legal laminae. Every valid centered square frame appears once in this list, and no impossible half-tile border width is ever generated.

Monotonicity and the Early Break

For fixed \(o\), decreasing \(i\) makes the hole smaller and the frame thicker, so the tile count must increase. The code relies on the explicit identity

$T(o,i-2)-T(o,i)=\bigl(o^2-(i-2)^2\bigr)-\bigl(o^2-i^2\bigr)=4(i-1)\gt0.$

Therefore the sequence of tile counts for a fixed outer square is strictly increasing as the inner loop proceeds. Once some \(i\) gives \(T(o,i)>L\), every later inner value in that same loop will also exceed \(L\), so breaking immediately is mathematically correct.

Counting the Multiplicity Function \(N(t)\)

Define

$N(t)=\#\{(o,i): o>i\ge1,\ o\equiv i\pmod2,\ o^2-i^2=t\}.$

The double loop computes this function directly. Each admissible pair \((o,i)\) contributes one unit to the frequency of the tile total \(t=T(o,i)\). After the enumeration is finished, the required answer is simply

$\#\{t\le L:1\le N(t)\le10\}.$

So Problem 174 is not asking for the number of laminae themselves. It asks for the number of tile totals that can be realized in a small number of distinct ways.

Worked Example: \(t=32\)

The tile total \(32\) illustrates why a frequency table is needed. We have

$6^2-2^2=36-4=32,$

and also

$9^2-7^2=81-49=32.$

Both pairs obey the parity condition and describe different laminae, so \(N(32)=2\). During enumeration, the implementations encounter both pairs separately and increment the same counter twice. Any tile total whose counter ends in the range from \(1\) to \(10\) contributes one to the final answer.

How the Code Works

Phase 1: Build a frequency table of tile totals

The C++, Python, and Java implementations allocate an array of length \(L+1\), initially filled with zeros. Entry \(t\) records how many different laminae use exactly \(t\) tiles.

The outer loop starts at \(o=3\), the smallest outer square that can surround a positive inner hole, and runs while \(4o-4\le L\). For each outer side length, the inner side starts at \(o-2\) and decreases by \(2\), which preserves the parity condition automatically.

Phase 2: Enumerate every legal lamina once

For each pair \((o,i)\), the implementation computes \(t=o^2-i^2\). If \(t\le L\), the corresponding frequency entry is incremented. If \(t>L\), the inner loop stops immediately, because the monotonicity argument above guarantees that all later values of \(i\) would produce even larger tile totals.

This means the double loop is not an unstructured brute force search. It is a precise enumeration of the admissible pairs, with a mathematically justified early exit inside each fixed-outer sweep.

Phase 3: Count the acceptable multiplicities

After all laminae have been generated, the implementation scans the frequency table from \(1\) to \(L\). Every tile total whose frequency lies between \(1\) and the allowed maximum is counted. In the Project Euler instance, that maximum is \(10\), so the program counts the tile totals that have one through ten distinct arrangements.

The C++ version also allows the limit and the upper multiplicity bound to be varied, but all three implementations follow the same mathematical strategy.

Complexity Analysis

Let \(A(L)\) be the number of admissible pairs \((o,i)\) with \(o^2-i^2\le L\). The enumeration phase visits each such pair exactly once, so its running time is \(O(A(L))\). The final pass over the frequency table contributes another \(O(L)\).

Hence the total running time is

$O(A(L)+L),$

while the memory usage is

$O(L),$

because the dominant data structure is the frequency array of size \(L+1\). For \(L=10^6\), this is easily practical: the code reduces the problem to one enumeration pass and one linear tally.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=174
2. Related lamina-counting problem: https://projecteuler.net/problem=173
3. Difference of two squares: Wikipedia - Difference of two squares
4. Parity in mathematics: Wikipedia - Parity
5. Square number: Wikipedia - Square number