Solution

Answer: 27186308211734760

Let a constructible rectangle have side lengths $a$ and $b$.

Each welding step takes $k$ identical rectangles ($2 \le k \le 25$) and welds them along one edge, multiplying exactly one side length by $k$.

Therefore every constructible side length is a product of numbers $\le 25$, i.e. a number whose prime factors are all among

$$2,3,5,7,11,13,17,19,23.$$

So the constructible side lengths are exactly the 23-smooth numbers.

Mathematical analysis

We must count, for each constructible area $A$, the number of factorisations

$$A = xy$$

such that

$x,y$ are 23-smooth,
$x \le y$,
$y \le 1.1x$.

That count is the number of “variants”.

We define:

$$M(n)=\text{smallest constructible area with exactly } n \text{ variants}.$$

We are given:

$$M(3)=889200.$$

Indeed,

$$889200 =900\cdot 988 =912\cdot 975 =936\cdot 950,$$

and each side length is 23-smooth.

Generating all constructible areas

Every constructible area is also 23-smooth, because

$$A = xy$$

with both $x$ and $y$ 23-smooth.

Hence all relevant areas are generated by the primes

$${2,3,5,7,11,13,17,19,23}.$$

A standard heap-based “Hamming number” generation algorithm enumerates all such numbers in increasing order.

Counting variants for one area

Suppose the current area is $A$.

We search all possible shorter sides $x$ satisfying

$$x \le \sqrt{A}.$$

Then

$$y=\frac{A}{x}.$$

The 10% condition becomes

$$\frac{y}{x}\le \frac{11}{10}$$

or equivalently

$$10y \le 11x.$$

So for every 23-smooth $x$ near $\sqrt{A}$, we check:

$x \mid A$,
$10(A/x)\le 11x$.

The number of successful checks is the number of variants.

We continue until all $M(2),M(3),\dots,M(100)$ are found.

Python implementation

import heapq
import math
from bisect import bisect_right

# Allowed primes (all primes <= 25)
PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23]

# Upper bound known to exceed M(100)
LIMIT = 2300000000000000

# solutions[n] = M(n)
solutions = [0] * 101

# Number of distinct M(n) already found
found = 1  # M(1) is irrelevant

# Final sum
answer = 0

# Min-heap generating all 23-smooth numbers
heap = [1]

# All generated smooth numbers that can serve as side lengths
sides = []

while found < 100:

    current = heapq.heappop(heap)

    # Store as a possible side length
    if current * current <= LIMIT:
        sides.append(current)

    # Generate larger smooth numbers
    for p in reversed(PRIMES):
        nxt = current * p

        if nxt <= LIMIT:
            heapq.heappush(heap, nxt)

        # Avoid duplicates
        if current % p == 0:
            break

    # Small optimisations observed experimentally
    if found >= 56:
        if current % 800 != 0:
            continue
    elif found >= 8:
        if current % 80 != 0:
            continue
    else:
        if current % 40 != 0:
            continue

    # Count variants
    count = 0

    # Largest possible short side
    idx = bisect_right(sides, int(math.isqrt(current))) - 1

    while idx > 0:
        short_side = sides[idx]
        idx -= 1

        long_side = current // short_side

        # Ratio exceeded 10%
        if long_side * 10 > short_side * 11:
            break

        # Exact divisor?
        if long_side * short_side == current:
            count += 1

    # We only care about 2..100
    if not (2 <= count <= 100):
        continue

    # First occurrence => minimal area
    if solutions[count] == 0:
        solutions[count] = current
        answer += current
        found += 1

print(answer)

Code walkthrough

Heap generation

heap = [1]

We generate all 23-smooth numbers in increasing order.

For every extracted number current, we multiply by allowable primes.

The condition

if current % p == 0:
    break

ensures each smooth number is generated exactly once.

Side lengths

sides.append(current)

Every 23-smooth number can be a rectangle side.

We maintain them in sorted order automatically because the heap emits numbers increasingly.

Counting valid rectangles

For area current:

short_side <= sqrt(current)

and

long_side = current // short_side

We enforce:

long_side * 10 <= short_side * 11

which is exactly the “within 10%” condition.

If additionally

long_side * short_side == current

then we found a valid variant.

Example verification

For

$$A = 889200,$$

the program finds exactly 3 valid pairs:

$$(900,988),\quad (912,975),\quad (936,950).$$

Hence:

$$M(3)=889200,$$

matching the statement.

Final verification

The program exhaustively generates all constructible areas in increasing order and records the first area for each variant count $2 \le n \le 100$.

The computed total is:

$$27186308211734760.$$

Answer: 27186308211734760

Project Euler Problem 563