Project Euler Problem 173

Solution

Answer: 1572729

Let the outer square have side length $n$, and the inner square (“hole”) have side length $m$.

Because the lamina is a symmetric square border:

• $n > m$
• $n$ and $m$ must have the same parity (otherwise the border thickness is not integral)
• the number of tiles used is

$$n^2 - m^2$$

We want:

$$n^2 - m^2 \le 10^6$$

and we must count all valid pairs $(n,m)$.

---

Mathematical analysis

1. Rewriting the tile count

Factor:

$$n^2 - m^2 = (n-m)(n+m)$$

Since $n,m$ have the same parity, both factors are even.

Let

$$n-m = 2k$$

where $k \ge 1$ is the border thickness.

Then:

$$m = n-2k$$

Substitute:

$$n^2 - (n-2k)^2$$

Expand:

$$= n^2 - (n^2 - 4kn + 4k^2)$$

$$= 4k(n-k)$$

So every lamina corresponds uniquely to integers:

• $k \ge 1$
• $n > 2k$

with tile count

$$T = 4k(n-k)$$

and we require

$$4k(n-k) \le 10^6$$

---

2. Counting possibilities

Fix a border thickness $k$.

Then:

$$n-k \le \frac{10^6}{4k}$$

so

$$n \le \frac{10^6}{4k} + k$$

Also we need:

$$n \ge 2k+1$$

because the inner hole side length is

$$m=n-2k \ge 1$$

Thus for each $k$, the valid $n$ values are:

$$2k+1 \le n \le \left\lfloor \frac{10^6}{4k} + k \right\rfloor$$

Hence the number of laminae for a fixed $k$ is

$$\left\lfloor \frac{10^6}{4k} + k \right\rfloor - (2k+1) + 1$$

which simplifies to

$$\left\lfloor \frac{10^6}{4k} \right\rfloor - k$$

provided this quantity is positive.

Therefore the total number is

$$\sum_{k\ge1} \max\left(0,\left\lfloor \frac{10^6}{4k}\right\rfloor-k\right)$$

---

Python implementation

LIMIT = 1_000_000

count = 0
k = 1

while True:
    # Number of valid outer sizes for this thickness
    ways = LIMIT // (4 * k) - k

    # Once non-positive, no larger k can work
    if ways <= 0:
        break

    count += ways
    k += 1

print(count)

---

Code walkthrough

LIMIT = 1_000_000

Maximum number of tiles allowed.

---

count = 0
k = 1

• count stores the total number of laminae.
• k is the border thickness.

---

ways = LIMIT // (4 * k) - k

From the derivation:

$$\text{ways} = \left\lfloor \frac{LIMIT}{4k}\right\rfloor - k$$

This counts all valid outer square sizes for thickness $k$.

---

if ways <= 0:
    break

As $k$ increases, the quantity decreases monotonically.

Once it becomes non-positive, no further laminae are possible.

---

count += ways

Add all laminae of thickness $k$.

---

k += 1

Move to the next border thickness.

---

print(count)

Outputs the final number of distinct square laminae.

---

Verification on the small example

The problem states:

With one-hundred tiles, forty-one different square laminae can be formed.

If we change:

LIMIT = 100

the program produces:

41

matching the statement exactly.

---

Final verification

The count should be:

• much larger than $10^5$, since many thin borders are possible,
• but much smaller than $10^7$, because the admissible thicknesses only go up to roughly

$$k^2 < \frac{10^6}{4} \Rightarrow k < 500$$

The resulting value is in the expected range and matches known Project Euler results.

Answer: 1572729