Problem 173: Using Up to One Million Tiles How Many Different Hollow Square Laminae Can Be Formed

Project Euler Problem 173 Solution

EulerSolve provides an optimized solution for Project Euler Problem 173, Using Up to One Million Tiles How Many Different Hollow Square Laminae Can Be Formed, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

A square lamina is a square outline with a square hole, laid out from equal square tiles so that the shape is symmetric about a vertical and about a horizontal axis. With exactly $32$ tiles one can form two different square laminae, and with at most $100$ tiles, not necessarily using all of them, one can form $41$ different square laminae. We must count the different square laminae that can be formed with at most one million tiles. ^[1]

The whole solution in one sentence: a lamina whose border is $w$ tiles wide can be cut into four equal rectangles of $w$ by $k$ tiles with $k\gt w$, so it uses $4wk$ tiles, and counting the laminae with at most one million tiles means counting the pairs of positive whole numbers $w\lt k$ with $wk\le250\,000$, which the programs do by trying, for every size of the outer square, thicker and thicker borders until the tiles run out.

Mathematical Approach

1. Two numbers describe a lamina

Measure lengths in tiles: let the outer square have side $a$ and the hole side $b$, with $1\le b\lt a$. A vertical mirror axis of the shape must also be one of the outer square, its vertical midline, and reflecting in it swaps the margins to the left and to the right of the hole, so these two margins are equal; in the same way the horizontal axis makes the top and bottom margins equal. Each pair of opposite margins adds up to $a-b$, so all four margins have the same width $w=(a-b)/2$, and because the border consists of whole tiles, $w$ is a positive whole number. Hence $a$ and $b$ are both even or both odd. Conversely, any $a\gt b\ge1$ of the same parity give exactly one lamina: the $a\times a$ square with the centred $b\times b$ square removed. So a lamina is the same thing as such a pair $(a,b)$, two laminae are different exactly when their pairs differ, and the lamina $(a,b)$ uses $a^2-b^2$ tiles. The hole must have a positive side length: a full $10\times10$ square uses $100$ tiles, but it is not a lamina.

2. The smallest laminae

Going through the pairs in order of their tile counts gives the smallest laminae: $(3,1)$ with $8$ tiles, $(4,2)$ with $12$, $(5,3)$ with $16$, $(6,4)$ with $20$, then $(5,1)$ and $(7,5)$ with $24$ each, $(8,6)$ with $28$, and $(6,2)$ and $(9,7)$ with $32$ each. The last two are the two laminae of the statement, and altogether nine laminae use at most $32$ tiles. All these tile counts are multiples of $4$, and some of them belong to two laminae; Sections 4 and 5 explain both observations.

3. Four rectangles

Extend each side of the hole to the outer edge in one direction, going around the hole: its top side to the left, its right side upwards, its bottom side to the right and its left side downwards. These four cuts split the border into four rectangles arranged like a pinwheel, each $w$ tiles wide and $a-w$ tiles long; a quarter turn about the centre carries each piece onto the next. They do not overlap and together cover the whole border, so

$$a^2-b^2=4w(a-w).$$

The same identity follows from the factorisation $a^2-b^2=(a-b)(a+b)$ of a difference of two squares, ^[2] since $a-b=2w$ and $a+b=2(a-w)$. For the lamina $(6,2)$, with $w=2$, the pieces are four $2\times4$ rectangles, $4\cdot8=32$ tiles; for $(9,7)$, with $w=1$, they are four $1\times8$ strips, again $32$ tiles.

4. A lamina is a pair $w\lt k$

Call the long side of the pieces $k=a-w$. Then $a=k+w$ and $b=k-w$, so the condition $b\ge1$ says exactly that $k\gt w$, and the lamina uses $4wk$ tiles. Conversely, any whole numbers $1\le w\lt k$ give $a=k+w$ and $b=k-w$ with $a\gt b\ge1$ and $a-b=2w$ even, that is, a lamina, and different pairs $(w,k)$ give different pairs $(a,b)$. So the laminae correspond one to one to the pairs $w\lt k$: a lamina is four copies of a $w\times k$ rectangle that is longer than it is wide. Placed as a $2\times2$ block, the four copies form a $2w\times2k$ rectangle, which is the $(a-b)\times(a+b)$ rectangle of the factorisation above.

5. Laminae with exactly $t$ tiles

By Section 4 a lamina uses $t=4wk$ tiles, so $t$ is always a multiple of $4$. For $t=4n$, the laminae with exactly $t$ tiles correspond to the ways of writing $n=w\cdot k$ with $w\lt k$, that is, to the divisors $w$ of $n$ with $w^2\lt n$. Their numbers for $n=1,2,3,\dots$ are $0,1,1,1,1,2,1,2,\dots$, sequence A056924 of the OEIS. ^[5] For $t=32$, the number $n=8$ has the divisors $1$ and $2$ below $\sqrt8$: $w=1$, $k=8$ gives the lamina $(9,7)$, and $w=2$, $k=4$ gives $(6,2)$, the two laminae of the statement. For $t=100$, the number $25$ has only the divisor $1$ below $5$, so exactly one lamina, $(26,24)$, uses all $100$ tiles; the factorisation $5\cdot5$ has $w=k$ and would give $b=0$, the full $10\times10$ square of Section 1.

6. Counting points under a hyperbola

A lamina fits into $N$ tiles when $4wk\le N$. Since $wk$ is a whole number, this is the same as $wk\le M$ with $M=\lfloor N/4\rfloor$. So the number $L(N)$ of laminae with at most $N$ tiles is the number of points $(w,k)$ with whole coordinates and $1\le w\lt k$ that lie on or below the hyperbola $wk=M$. For a fixed $w$, the long side $k$ runs from $w+1$ to $\lfloor M/w\rfloor$, and such a $k$ exists only while $w(w+1)\le M$. Therefore

$$L(N)=\sum_{w=1}^{W}\Bigl(\Bigl\lfloor\frac{M}{w}\Bigr\rfloor-w\Bigr),$$

where $W$ is the largest whole number with $W(W+1)\le M$. A second formula uses symmetry. The pairs $(w,k)$ and $(k,w)$ have the same product, so once the $\lfloor\sqrt M\rfloor$ pairs with $w=k$ are set aside, exactly half of the remaining pairs with $wk\le M$ have $w\lt k$:

$$L(N)=\frac{D(M)-\lfloor\sqrt M\rfloor}{2}.$$

Here $D(M)=\sum_{j\le M}\lfloor M/j\rfloor$ counts all points with positive whole coordinates on or below the hyperbola; it is the divisor summatory function, the total number of divisors of $1,2,\dots,M$. ^[3] Dirichlet's hyperbola method evaluates it with about $\sqrt M$ divisions, by splitting the points at $\sqrt M$ just as the first formula does. ^[4] The values of $L(4M)$ for $M=1,2,3,\dots$ are $0,1,2,3,4,6,7,9,\dots$, sequence A211264 of the OEIS. ^[5]

7. Worked example: $100$ tiles

For $N=100$ we get $M=25$ and $W=4$, because $4\cdot5=20\le25\lt30=5\cdot6$. The four terms of the sum are:

$w=1$: $k=2,\dots,25$, so $24$ laminae, the frames of width $1$ with outer sides $3$ to $26$;
$w=2$: $k=3,\dots,12$, so $10$ laminae with outer sides $5$ to $14$;
$w=3$: $k=4,\dots,8$, so $5$ laminae with outer sides $7$ to $11$;
$w=4$: $k=5,6$, so $2$ laminae with outer sides $9$ and $10$.

Together $24+10+5+2=41$, the value of the statement. The second formula agrees: $D(25)=87$ and $\lfloor\sqrt{25}\rfloor=5$ give $(87-5)/2=41$.

8. The order used by the programs

The programs count the same pairs in another order: by the outer side $a$, and for each $a$ from the thinnest border to thicker ones, that is, with the holes $b=a-2,a-4,\dots$ down to $1$ or $2$. Two facts make this order work.

Along a row the tile count grows. Replacing the hole $b$ by $b-2$ adds $b^2-(b-2)^2=4(b-1)$ tiles, a positive number for $b\ge3$, which is exactly when the next hole $b-2$ still has a positive side. So as soon as one lamina with outer side $a$ needs more than $N$ tiles, so do all thicker ones, and the row can be abandoned.
The thinnest border is the cheapest. Width $w=1$ uses $4(a-1)$ tiles, and $4w(a-w)-4(a-1)$${}=4(w-1)(a-w-1)\ge0$ for $1\le w\le a-1$. So no lamina with outer side $a$ fits once $4a-4\gt N$, and the outer side never needs to exceed $\lfloor N/4\rfloor+1$.

For $N=100$ the outer side runs from $3$ to $26$. With $a=11$, for example, the holes $9$, $7$ and $5$ need $40$, $72$ and $96$ tiles, and the hole $3$ would need $112$, so this row ends with three laminae. Row by row the counts are $1,1,2,2,3,3,4,4$ for $a=3,\dots,10$, then $3,2,2,2$ for $a=11,\dots,14$ and $1$ for each $a=15,\dots,26$: again $29+12=41$.

How the Code Works

All three programs count in the order of Section 8. The C++ program ^[8] keeps its settings in a struct Options: the tile limit limit, by default $1\,000\,000$, and the flag run_checkpoints. parse_arguments accepts --skip-checkpoints and --limit= followed by decimal digits, which parse_int_after_prefix reads into an int without an overflow check; any other argument, or a limit below $1$, ends the program with exit code $1$. Unless the checkpoints are skipped, run_checkpoints checks that solve(100) returns $41$, the value of the statement, and otherwise ends the program with exit code $2$. Finally main prints solve(options.limit).

solve consists of two loops. The outer loop runs outer from $3$ while 4 * outer - 4 <= limit, the bound of Section 8. The inner loop starts with inner = outer - 2, the border of width $1$, and steps inner -= 2 while inner > 0, which keeps the parity of Section 1. It computes tiles = outer * outer - inner * inner, leaves the row with break as soon as tiles > limit, which the growth along a row justifies, and otherwise adds one to the 64-bit counter count. In this way every lamina within the limit is visited exactly once, as its pair $(a,b)$. The Python program runs the same two loops as while loops in a function solve, and the Java program as for loops in main with a long counter; both have the limit $1\,000\,000$ built in, and neither has options or a checkpoint.

In C++ the variables outer, inner and tiles are ints, which have 32 bits on all common platforms, and Java evaluates outer * outer - inner * inner in its 32-bit int as well. The largest int is $2^{31}-1=2\,147\,483\,647$, and since $46341^2=2\,147\,488\,281$, the product outer * outer overflows for every outer side from $46341$ up to $250\,001$, and inner * inner from $46343$ on. The difference itself stays small: the first value in a row is $4a-4\le N$, and every later one is a value of at most $N$ plus at most $4(a-3)$, so it is at most $2N-8$, that is $1\,999\,992$ for $N=10^6$. Java defines the result of an overflowing int operation as the low $32$ bits of the exact result, ^[7] so the computed difference agrees with the exact one modulo $2^{32}$; as both lie between $-2^{31}$ and $2^{31}-1$, they are equal. In C++, signed overflow is undefined behaviour, ^[7] so for every limit of at least $4\cdot46341-4=185\,360$ the language no longer guarantees the printed count. In tests with Clang and GCC builds, with and without optimisation, the C++ program printed the same count as the other two, and a build with -fsanitize=undefined reports the overflows; computing the products in 64 bits would remove them. Python's integers have no fixed size, so the question does not arise there.

Complexity and Verification

The body of the inner loop runs once for every lamina within the limit and at most once more per outer side, for the value that triggers the break; for $N=100$ that is $41+16=57$ runs over the $24$ outer sides. The work is therefore $L(N)+O(N)$ steps. In the sum of Section 6 the main part is $M$ times the harmonic number $H_W=1+\frac12+\dots+\frac1W$, while the rounding and the subtracted $w$ change it by less than $W+W^2\le M$. The harmonic numbers satisfy $0\lt H_n-\ln n\le1$, because $H_n-\ln n$ decreases from $1$ towards Euler's constant $\gamma\approx0.5772$, ^[6] and $W(W+1)\le M\lt(W+1)(W+2)$ gives $\sqrt M-\tfrac32\lt W\le\sqrt M$, so $H_W=\tfrac12\ln M+O(1)$ and $L(N)=\tfrac12M\ln M+O(M)$. Counting each operation on the program's integers as one step, the running time is therefore $O(N\log N)$, and the memory is $O(1)$: a few integers and the counter. For the full problem the outer loop makes $249\,999$ passes, for $a=3,\dots,250\,001$. Timed on a desktop computer as the median of $11$ runs, each including the start of its process, the C++ program built by Clang with -O2 takes about $3$ milliseconds, about $2$ of them for the start alone, the Java program about $0.03$ seconds and the Python program about $0.14$ seconds. The first formula of Section 6 would need only $O(\sqrt N)$ time: $W=499$ terms for $M=250\,000$, since $499\cdot500=249\,500\le M\lt500\cdot501$.

The C++ checkpoint confirms the value $41$ for $100$ tiles. For this article, separately written checks, which are not part of the published solutions, confirmed the following. For every $N\le1200$, and for every seventh $N$ up to $20\,000$, the double loop of the programs, the sum of Section 6 and the formula with $D(M)$ agree; for $N\le400$ so does a brute force over all pairs $(a,b)$ without the early stop. For every $t\le1000$ the number of laminae with exactly $t$ tiles is $0$ unless $t$ is a multiple of $4$, and for $t=4n$ it equals the number of divisors of $n$ below $\sqrt n$. For every $a\le30$ and every position of a square hole, building the shape tile by tile confirms that it is symmetric about both axes exactly when the hole is centred, and that the four pieces of Section 3 cover the border without overlap. Finally, at $N=10^6$ the three programs, the C++ program built with Clang and GCC with and without optimisation, and the $499$-term sum of Section 6 all give the same count.

Footnotes and References

The references below supply the background facts used above. The correspondence between laminae and pairs $w\lt k$, the counting formulas and the integer bounds are derived in this article.

Project Euler 173 — Hollow Square Laminae I. The official statement defines a square lamina as a square outline with a square hole that has vertical and horizontal symmetry, says that exactly 32 tiles form two different laminae and that up to 100 tiles, not necessarily all used, form 41, and asks how many different square laminae can be formed with up to one million tiles.
Wikipedia — Difference of two squares. Every difference of two squares factors as a² − b² = (a + b)(a − b). The geometric proof in the article cuts a square of side a with a square of side b removed into two rectangles that together form an (a + b) × (a − b) rectangle.
Wikipedia — Divisor summatory function. D(x) is the sum of the number of divisors d(n) over n ≤ x, equal to the sum of ⌊x/k⌋ over k ≤ x; it counts the lattice points bounded by the axes and the hyperbola jk = x. The article gives D(x) = 2 Σ ⌊x/k⌋ − u² with the sum over k ≤ u = ⌊√x⌋, and D(x) = x log x + x(2γ − 1) + O(√x).
Wikipedia — Dirichlet hyperbola method. Summing over the lattice points under the hyperbola xy = n and splitting them at √n gives D(n) = 2 Σ ⌊n/x⌋ − ⌊√n⌋², with the sum over x ≤ √n, which can be evaluated in O(√n) operations.
OEIS A056924 — Number of divisors of n that are smaller than sqrt(n): 0, 1, 1, 1, 1, 2, 1, 2, …, equal to ⌊d(n)/2⌋ for n > 1; by Section 5 it counts the laminae with exactly 4n tiles. OEIS A211264 — Number of integer pairs (x, y) such that 0 < x < y ≤ n and xy ≤ n: 0, 1, 2, 3, 4, 6, 7, 9, …, the partial sums of A056924, with a(n) = (A006218(n) − A000196(n)) / 2, where A006218 is the divisor summatory function and A000196 the integer square root. By Section 6 the number of laminae with at most N tiles is a(⌊N/4⌋); for example a(25) = 41.
Wikipedia — Harmonic number. The harmonic number H_n = 1 + 1/2 + ⋯ + 1/n is about ln n: the difference H_n − ln n decreases monotonically towards the Euler–Mascheroni constant γ ≈ 0.5772.
cppreference — Arithmetic operators: when a signed integer arithmetic operation overflows, the behaviour is undefined; it may wrap around, trap, saturate or be optimised out by the compiler. Java Language Specification, §15.17.1: if an integer multiplication overflows, the result is the low-order bits of the mathematical product in a sufficiently large two's-complement format, and §15.18.2 says the same for addition. Python — Numeric types: integers have unlimited precision.
C++ — Euler173.cpp. The linked immutable revision, with solve, the argument parser and the checkpoint for 100 tiles, is the implementation record for this article.

Problem 173 source code

C++

#include <cstdint>
#include <iostream>
#include <string>

namespace {

using i64 = std::int64_t;

struct Options {
    int limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }

    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 1;
}

i64 solve(const int limit) {
    i64 count = 0;

    for (int outer = 3; 4 * outer - 4 <= limit; ++outer) {
        for (int inner = outer - 2; inner > 0; inner -= 2) {
            const int tiles = outer * outer - inner * inner;
            if (tiles > limit) {
                break;
            }
            ++count;
        }
    }

    return count;
}

bool run_checkpoints() {
    if (solve(100) != 41) {
        std::cerr << "Checkpoint failed for limit=100" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

# Problem 173: Using up to one million tiles how many hollow square laminae can be formed?

def solve():
    limit = 1000000
    count = 0
    outer = 3
    while 4*outer - 4 <= limit:
        inner = outer - 2
        while inner > 0:
            tiles = outer*outer - inner*inner
            if tiles > limit: break
            count += 1
            inner -= 2
        outer += 1
    print(count)

solve()

Java

public class Euler173 {
    public static void main(String[] args) {
        int limit = 1000000;
        long count = 0;
        for (int outer = 3; 4 * outer - 4 <= limit; outer++)
            for (int inner = outer - 2; inner > 0; inner -= 2) {
                if (outer * outer - inner * inner > limit)
                    break;
                count++;
            }
        System.out.println(count);
    }
}