Detailed mathematical approach

Problem Summary

A hollow square lamina is a square frame: an outer square of side length \(o\) and a smaller inner square of side length \(i\), sharing the same center. Because the border must have integer thickness, the gap from the outer side to the inner side is even, so \(o-i \ge 2\) and \(o\) and \(i\) have the same parity.

The number of tiles used by such a lamina is the area difference

$T=o^2-i^2.$

For this problem the tile budget is \(L=1{,}000{,}000\). The task is to count how many distinct pairs \((o,i)\) satisfy the geometric constraints and \(T \le L\).

Mathematical Approach

The implementations do not search over pictures. They count admissible integer pairs that represent square frames. The key facts are the difference-of-squares formula, the parity constraint, and the monotone behavior of the tile count when the inner square shrinks.

Encoding a lamina by two side lengths

Once the outer side \(o\) and inner side \(i\) are fixed, the lamina is completely determined. The centered-border condition implies

$o \ge 3,\qquad 1 \le i \lt o,\qquad o-i \equiv 0 \pmod{2}.$

The area removed from the outer square is exactly the inner square, so the tile count is

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

This factorization is useful because it makes the parity restriction visible: \(o-i\) measures twice the border thickness, while \(o+i\) records the corresponding average scale.

Rewriting the problem in terms of border thickness

Let

$k=\frac{o-i}{2},$

so \(k \ge 1\) is the thickness of the square border measured in tiles. Then

$i=o-2k,$

and the positivity of the inner square gives

$1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor.$

Substituting \(i=o-2k\) into the tile formula yields

$T(o,k)=o^2-(o-2k)^2=4k(o-k).$

So the whole counting problem can be written as

$N(L)=\sum_{o=3}^{\lfloor L/4\rfloor+1}\#\left\{k:1 \le k \le \left\lfloor\frac{o-1}{2}\right\rfloor,\ 4k(o-k)\le L\right\}.$

The code does not solve this inequality in closed form for each \(o\); instead it walks through the valid \(k\)-values in increasing order by decreasing the inner side in steps of 2.

The smallest lamina for a fixed outer side

For a fixed outer side \(o\), the smallest possible border is \(k=1\), equivalently \(i=o-2\). That gives the minimum number of tiles for that outer square:

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

This simple expression explains the outer-loop stopping rule. If even the thinnest lamina with outer side \(o\) already exceeds the limit, then every thicker lamina with the same outer side also exceeds the limit. Therefore the outer loop only needs to continue while

$4o-4 \le L.$

For \(L=1{,}000{,}000\), this means

$o \le \frac{L}{4}+1=250001.$

Why the inner loop can stop early

For a fixed outer side, the implementations try inner sides in the order

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

which is the same as trying \(k=1,2,3,\dots\). The crucial point is that the tile count grows strictly in that order. Using the inner-side form,

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

and this is positive for every admissible \(i>1\). In the thickness form, the same fact is

$T(o,k+1)-T(o,k)=4(o-2k-1),$

which stays positive throughout the allowed range \(k \lt (o-1)/2\).

That monotonicity is the invariant that justifies the break in the code: once one candidate exceeds the tile limit, every later candidate for the same outer side will also exceed it.

Worked example

Take a smaller budget, say \(L=50\), and fix the outer side at \(o=8\). The admissible inner sides have the same parity as 8, so they are \(i=6,4,2\).

The corresponding tile counts are

$8^2-6^2=28,\qquad 8^2-4^2=48,\qquad 8^2-2^2=60.$

So the first two laminae are valid, while the third is not. Because the tile counts increase as the inner side decreases, the moment 60 appears the search for \(o=8\) can stop immediately. This is exactly the behavior implemented by the nested loops.

How the Code Works

The C++, Python, and Java implementations all follow the same counting strategy. They sweep the outer side length upward starting from \(o=3\), because \(3\times3\) with a \(1\times1\) hole is the smallest nontrivial square lamina. The outer sweep ends when the minimal tile count \(4o-4\) exceeds the budget.

For each fixed outer side, the implementation starts with the largest possible inner side, \(i=o-2\), and then decreases \(i\) by 2 so that parity is preserved automatically. Each pair \((o,i)\) corresponds to one distinct lamina, and the implementation computes \(o^2-i^2\). If that value is within the limit, the count increases by 1. If it exceeds the limit, the inner loop terminates immediately because all later inner sides would use even more tiles.

The three language versions differ only in presentation details. They implement the same mathematics, the same loop order, and the same early-exit rule. The C++ version additionally includes a small checkpoint confirming that a budget of 100 tiles produces 41 laminae, which matches the example given in the problem statement.

Complexity Analysis

The outer loop runs for \(o=3,4,\dots,\lfloor L/4\rfloor+1\), so there are \(O(L)\) outer iterations as a function of the tile limit \(L\).

For a fixed \(o\), the inner loop explores increasing border thickness \(k\). Since \(k \le \lfloor(o-1)/2\rfloor\) and \(4k(o-k)\le L\), while \(k \le o/2\) we also have \(o-k \ge o/2\), hence

$4k(o-k)\le L \implies 2ko \le L \implies k \le \frac{L}{2o}.$

Therefore the number of successful inner iterations for a given outer side is

$O\!\left(\min\!\left(o,\frac{L}{o}\right)\right).$

Summing over all outer sides gives \(O(L\log L)\) total work. Memory usage is \(O(1)\), because the implementation stores only a few integers and the running count.

Footnotes and References

1. Problem page: Project Euler 173
2. Difference of two squares: Wikipedia - Difference of two squares
3. Lamina in geometry: Wikipedia - Lamina
4. Parity: Wikipedia - Parity