Problem 174: Counting the Number of Hollow Square Laminae That Can Form One, Two, Three, ... Distinct Arrangements

Project Euler Problem 174 Solution

EulerSolve provides an optimized solution for Project Euler Problem 174, Counting the Number of Hollow Square Laminae That Can Form One, Two, Three, ... Distinct Arrangements, 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$ 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$....

Detailed mathematical approach

Problem Summary

A square lamina is a square outline with a square hole, made of equal square tiles and symmetric about a vertical and a horizontal axis. Eight tiles form exactly one lamina, a $3\times3$ square with a $1\times1$ hole, and thirty-two tiles form two. A tile count $t$ is of type $L(n)$ when exactly $n$ different laminae use exactly $t$ tiles, so $t=8$ is of type $L(1)$ and $t=32$ of type $L(2)$. With $N(n)$ the number of $t\le1\,000\,000$ of type $L(n)$, for which the statement gives $N(15)=832$, we must find $N(1)+N(2)+\dots+N(10)$, the number of tile counts up to one million that form at least one and at most ten laminae. ^[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 the laminae with exactly $t$ tiles are the ways of writing $t/4$ as a product $w\cdot k$ with $w\lt k$, and the programs build every lamina with at most a million tiles, tally the laminae of each tile count and count the tallies between $1$ and $10$.

Mathematical Approach

1. Two numbers describe a lamina

Measure lengths in tiles: the outer square has side $a$ and the hole side $b$, with $1\le b\lt a$. A mirror symmetry maps the outline, the outer square, onto itself, so the two axes are its midlines, and reflecting in them swaps opposite margins of the hole, which are therefore equal. Hence all four margins have the same width $w=(a-b)/2$, a positive whole number, and $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 without its centred $b\times b$ square. So a lamina is such a pair $(a,b)$, and it uses $a^2-b^2$ tiles; a full square, with $b=0$, is not a lamina.

2. The smallest laminae

In order of their tile counts, the smallest laminae are $(3,1)$ with $8$ tiles, $(4,2)$ with $12$, $(5,3)$ with $16$, $(6,4)$ with $20$, $(5,1)$ and $(7,5)$ with $24$, $(8,6)$ with $28$, $(6,2)$ and $(9,7)$ with $32$, $(10,8)$ with $36$, $(7,3)$ and $(11,9)$ with $40$, $(12,10)$ with $44$, and $(7,1)$, $(8,4)$ and $(13,11)$ with $48$, the smallest tile count of type $L(3)$. Every tile count is a multiple of $4$, and some multiples of $4$ have several laminae; the next two sections explain why.

3. Four rectangles

Extend the sides of the hole to the outer edge, all turning the same way around the hole: the top side to the left, the right side upwards, the bottom side to the right and the left side downwards. These cuts split the border into four rectangles arranged like a pinwheel, each $w$ tiles wide and $k=a-w$ tiles long, so

$$a^2-b^2=4wk.$$

The factorisation $a^2-b^2=(a-b)(a+b)$ of a difference of two squares gives the same, ^[2] since $a-b=2w$ and $a+b=2k$. For $(6,2)$ the pieces are four $2\times4$ rectangles, for $(9,7)$ four $1\times8$ strips, $32$ tiles each time. As $a=k+w$ and $b=k-w$, the hole has a positive side exactly when $k\gt w$, and conversely any whole numbers $1\le w\lt k$ give the lamina $(k+w,k-w)$, whose sides have equal parity. So the laminae correspond one to one to the pairs $w\lt k$, and the pair $(w,k)$ uses $4wk$ tiles.

4. Laminae with exactly $t$ tiles

By Section 3 only multiples of $4$ have laminae. For $t=4m$, the number $c(t)$ of laminae with exactly $t$ tiles is the number of ways to write $m=w\cdot k$ with $w\lt k$. Pair every divisor $w$ of $m$ with its partner $m/w$. Of two different partners exactly one is the smaller, and a divisor is its own partner only if $w^2=m$, which happens once if $m$ is a perfect square and never otherwise. So the number $d(m)$ of divisors of $m$ is odd exactly when $m$ is a square, ^[3] and in both cases

$$c(4m)=\Bigl\lfloor\frac{d(m)}{2}\Bigr\rfloor.$$

For $t=32$, the divisor pairs $\{1,8\}$ and $\{2,4\}$ of $8$ give the laminae $(9,7)$ and $(6,2)$. For $t=36$, the pair $\{1,9\}$ of divisors of $9$ gives the lamina $(10,8)$, while the divisor $3$ is its own partner and would give $b=0$, the full $6\times6$ square; so $c(36)=1$. For $t=96$, the eight divisors of $24$ form four pairs, the laminae $(25,23)$, $(14,10)$, $(11,5)$ and $(10,2)$, and $96$ is the smallest tile count of type $L(4)$, as Section 6 confirms. The numbers $\lfloor d(m)/2\rfloor$ for $m=1,2,3,\dots$ form sequence A056924 of the OEIS. ^[4]

5. Types and divisor counts

Hence $t$ is of type $L(n)$, $n\ge1$, exactly when $t=4m$ and $d(m)$ is $2n$ or $2n+1$. If $m=p_1^{e_1}\cdots p_r^{e_r}$ with distinct primes $p_i$, a divisor chooses an exponent between $0$ and $e_i$ for every $p_i$, so ^[3]

$$d(m)=(e_1+1)(e_2+1)\cdots(e_r+1).$$

For example, type $L(1)$ needs $d(m)=2$ or $3$: $m$ is a prime $p$ or a square $p^2$, as for $8=4\cdot2$, $16=4\cdot2^2$ and $36=4\cdot3^2$. The count $t=4$ has no lamina, because $d(1)=1$, while every multiple of $4$ from $8$ on has at least the frame of width $w=1$. As $4m\le10^6$ means $m\le250\,000$, the sum we want is

$$\sum_{n=1}^{10}N(n)=\#\{\,2\le m\le250\,000:\ d(m)\le21\,\}.$$

6. Worked example: up to $100$ tiles

For the limit $100$, $m$ runs from $2$ to $25$, and none of these numbers has more than $8$ divisors, so all $24$ tile counts $8,12,\dots,100$ count:

type $L(1)$, $d(m)\in\{2,3\}$: $m=2,3,4,5,7,9$, $11,13,17,19,23,25$, twelve tile counts;
type $L(2)$, $d(m)\in\{4,5\}$: $m=6,8,10,14$, $15,16,21,22$, eight tile counts;
type $L(3)$, $d(m)\in\{6,7\}$: $m=12,18,20$, that is $t=48,72,80$;
type $L(4)$, $d(m)\in\{8,9\}$: $m=24$, that is $t=96$.

The sum $12+8+3+1=24$ is the checkpoint of the C++ program. A scan of all divisor counts shows that the first $m$ with more than $21$ divisors is $360=2^3\cdot3^2\cdot5$, with $4\cdot3\cdot2=24$, so $t=1440$ is the smallest tile count with more than ten laminae. For the limits $10^3$, $10^4$ and $10^5$ the sum is $249$, $2383$ and $22285$.

7. The checkpoint $N(15)=832$

Type $L(15)$ needs $d(m)=30$ or $31$. As $31$ is prime, $d(m)=31$ forces $m=p^{30}\ge2^{30}$, far too large, so $N(15)$ counts the $m\le250\,000$ with exactly $30$ divisors. The scan of Section 6 finds $832$ of them, the value of the statement; the smallest is $720=2^4\cdot3^2\cdot5$, with $5\cdot3\cdot2=30$, so $t=2880$ is the smallest tile count of type $L(15)$.

8. The order used by the programs

The programs never compute a divisor. They visit the pairs $(a,b)$ row by row, by the outer side $a=3,4,5,\dots$, and in each row from the thinnest border to thicker ones, with the holes $b=a-2,a-4,\dots$ down to $1$ or $2$. Two facts let them stop early:

Along a row the tile count grows. Replacing the hole $b$ by $b-2$ adds $b^2-(b-2)^2=4(b-1)\gt0$ tiles, as $b\ge3$ whenever this step is taken. Once a lamina of the row exceeds the limit, so do all thicker ones.
The thinnest border is the cheapest. Width $1$ uses $4a-4$ 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$ exceeds the limit; for a million tiles, $a\le250\,001$.

For the limit $100$, $a$ runs from $3$ to $26$; in the row $a=11$ the holes $9$, $7$ and $5$ need $40$, $72$ and $96$ tiles, and the hole $3$ would need $112$, so the row ends with three laminae. Each lamina within the limit is visited exactly once, so adding $1$ to a counter for its tile count yields $c(t)$ for every $t$, and the answer is the number of $t$ with $1\le c(t)\le10$. Another route is a sieve that stores the smallest prime factor of every $m\le250\,000$; ^[5] dividing out these factors one by one gives the factorisation, for example $12=2\cdot2\cdot3$, and Section 5 then gives $d(12)=(2+1)(1+1)=6$. The programs do not use it, but the verification below does.

How the Code Works

All three programs follow Section 8. The C++ program ^[6] keeps the tile limit, by default $1\,000\,000$, the largest type, by default $10$, and a checkpoint flag in the struct Options. parse_arguments accepts --limit= and --max-type=, whose digits parse_int_after_prefix reads without an overflow check, and --skip-checkpoints; a repeated option overrides the earlier one, and any other argument, or a final limit or largest type below $1$, gives exit code $1$. Unless skipped, run_checkpoints requires solve(100, 10) to return the $24$ of Section 6, or the program ends with exit code $2$; then main prints the result of solve.

solve creates the tally count, a std::vector<int> of limit + 1 zeros. The outer loop runs outer from $3$ while 4 * outer - 4 <= limit, the bound of the thinnest border; the inner loop starts at inner = outer - 2 and steps inner -= 2 while inner > 0, keeping the parity of Section 1. It computes tiles = outer * outer - inner * inner, leaves the row with break once tiles > limit, as the growth along a row allows, and otherwise increments count[tiles]. A last pass counts the entries with 1 <= c && c <= max_type in the 64-bit answer. Python (while loops in solve, a generator expression for the last pass) and Java (for loops in main, an int array and an int result) do the same with the limit and the bound $10$ built in, without options or checkpoint.

In C++ and Java, outer, inner and tiles are 32-bit ints, and since $46341^2=2\,147\,488\,281$ exceeds $2^{31}-1$, the products overflow as soon as a side reaches $46341$, while the outer side goes up to $250\,001$. The difference stays small: the first value of a row is $4a-4\le10^6$, and a later one is computed only when the previous one was at most $10^6$ and exceeds it by $4(b+1)\le4(a-3)\le10^6-8$, where the hole shrinks from $b+2$ to $b$; so no computed value exceeds $2\cdot10^6-8$. Java defines an overflowing int operation to give the low $32$ bits of the exact result, ^[7] so this difference, far inside the int range, comes out exactly. In C++ signed overflow is undefined behaviour; ^[7] GCC and Clang builds print the same count, but -fsanitize=undefined reports the overflow, which 64-bit products would avoid. Python's integers are unbounded.

Complexity and Verification

The inner loop body runs once per lamina within the limit and at most once more per outer side, for the value that triggers the break: for the limit $100$, $41+16=57$ times. By Section 3 the laminae with at most $4M$ tiles are the pairs $w\lt k$ with $wk\le M$; for each width $w$, $k$ runs from $w+1$ to $\lfloor M/w\rfloor$, so their number is

$$\begin{aligned}&\sum_{w=1}^{W}\Bigl(\Bigl\lfloor\frac{M}{w}\Bigr\rfloor-w\Bigr)\\&\qquad=M\,H_W-\frac{W(W+1)}{2}-\varepsilon,\end{aligned}$$

where $W\approx\sqrt M$ is the largest width with $W(W+1)\le M$, the harmonic number $H_W=1+\frac12+\dots+\frac1W$ is about $\ln W+0.5772$, ^[8] and $0\le\varepsilon\lt W$ collects the fractional parts that the floors remove. This grows like $\tfrac12M\ln M$. For $M=250\,000$ the inner loop runs about $1.8$ million times in all over the $249\,999$ outer sides, of which only the $998$ with $a\le1000$ end without a break. With the final pass, the time for a tile limit $T=4M$ is $O(T\log T)$. The memory is the tally of $T+1$ entries, $O(T)$: about $4$ MB in C++ and Java and $8$ MB of references in Python. On a desktop computer the C++ program needs a few milliseconds, Java about $0.03$ and Python about $0.2$ seconds.

Only the C++ program checks itself, with the limit $100$. Separate checks for this article, not part of the published solutions, confirmed the following. A brute force over all pairs $(a,b)$, without the early stop, gives $c(t)=\lfloor d(t/4)/2\rfloor$ for every multiple of $4$ up to $3000$ and no lamina for any other $t\le3000$. For the limits $10^2$ to $10^5$, the loops of the programs and a count of the $m$ with $2\le d(m)\le21$ agree. At the full limit the tally of the loops equals $\lfloor d(t/4)/2\rfloor$ for every multiple $t\le10^6$ of $4$ and gives $N(15)=832$, and its count of type $L(1)$ is the number of primes up to $250\,000$ plus the number of primes up to $500$, as Section 5 predicts. The count of Section 5, with $d(m)$ from the sieve of Section 8, agrees with the three programs and with GCC and Clang builds at the optimisation levels $0$, $2$ and $3$.

Footnotes and References

The references below supply the background facts used above; the correspondence between laminae and pairs $w\lt k$, the formula for $c(t)$ and the integer bounds are derived in this article.

Project Euler 174 — Hollow Square Laminae II. The official statement: a square lamina is a square outline with a square hole that has vertical and horizontal symmetry; t = 8 tiles is type L(1) and t = 32 type L(2); N(n) counts the t ≤ 1000000 of type L(n), N(15) = 832, and the task asks for the sum of N(n) for n = 1 to 10.
Wikipedia — Difference of two squares. a² − b² = (a + b)(a − b), with a geometric proof that rearranges a square with a smaller square removed into an (a + b) × (a − b) rectangle.
Wikipedia — Divisor function. The number of divisors σ₀(n), also written d(n), is the product of the exponents of the prime factorisation, each increased by 1; it is even when n is not a square, since every divisor d pairs with n/d, and odd when n is a square.
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⌋; by Section 4 the n-th term counts the laminae with exactly 4n tiles.
CP-Algorithms — Linear Sieve. It computes the minimum prime factor of every number from 2 to n, an array that yields the factorisation of each of these numbers in time proportional to its length.
C++ — Euler174.cpp. The linked immutable revision, with solve, the argument parser and the checkpoint, is the implementation record for this article.
cppreference — Arithmetic operators: signed integer overflow is undefined behaviour. Java Language Specification, §15.17.1 and §15.18.2: overflowing integer multiplication and addition keep the low-order bits of the exact result, and a − b equals a + (−b). Python — Numeric types: integers have unlimited precision.
Wikipedia — Harmonic number. H_n − ln n decreases monotonically towards the Euler–Mascheroni constant γ ≈ 0.5772.

Problem 174 source code

C++

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

namespace {

using i64 = std::int64_t;

struct Options {
    int limit = 1000000;
    int max_type = 10;
    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) ||
            parse_int_after_prefix(arg, "--max-type=", options.max_type)) {
            continue;
        }

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

i64 solve(const int limit, const int max_type) {
    std::vector<int> count(static_cast<std::size_t>(limit + 1), 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[static_cast<std::size_t>(tiles)];
        }
    }

    i64 answer = 0;
    for (int n = 1; n <= limit; ++n) {
        const int c = count[static_cast<std::size_t>(n)];
        if (1 <= c && c <= max_type) {
            ++answer;
        }
    }
    return answer;
}

bool run_checkpoints() {
    if (solve(100, 10) != 24) {
        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, options.max_type) << '\n';
    return 0;
}

Python

# Problem 174: Counting the number of "hollow" square laminae that can form one, two, ... distinct arrangements.

def solve():
    limit = 1000000
    max_type = 10
    count = [0]*(limit+1)
    outer = 3
    while 4*outer - 4 <= limit:
        inner = outer - 2
        while inner > 0:
            tiles = outer*outer - inner*inner
            if tiles > limit: break
            count[tiles] += 1
            inner -= 2
        outer += 1
    ans = sum(1 for n in range(1, limit+1) if 1 <= count[n] <= max_type)
    print(ans)

solve()

Java

public class Euler174 {
    public static void main(String[] args) {
        int limit = 1000000;
        int[] count = new int[limit + 1];
        for (int outer = 3; 4 * outer - 4 <= limit; outer++)
            for (int inner = outer - 2; inner > 0; inner -= 2) {
                int tiles = outer * outer - inner * inner;
                if (tiles > limit)
                    break;
                count[tiles]++;
            }
        int ans = 0;
        for (int n = 1; n <= limit; n++)
            if (count[n] >= 1 && count[n] <= 10)
                ans++;
        System.out.println(ans);
    }
}