Detailed mathematical approach

Problem Summary

For each integer \(k\), let \(M(k)\) be the smallest rectangle area that has exactly \(k\) manufacturable variants. A variant is an admissible factor pair \((x,y)\) with \(x\le y\), both sides manufacturable, and

$10y\le 11x,$

so the rectangle is within \(10\%\) of a square. The required answer is

$\sum_{k=2}^{100} M(k).$

The implementations encode the manufacturing rule through admissible side lengths: a positive integer side is manufacturable exactly when all of its prime factors belong to \(\{2,3,5,7,11,13,17,19,23\}\).

Mathematical Approach

Let

$P=\{2,3,5,7,11,13,17,19,23\}$

and define the manufacturable side set

$\mathcal{S}=\left\{n\in \mathbb{Z}_{>0}: \text{every prime divisor of } n \text{ lies in } P\right\}.$

For any area \(A\), define its admissible multiplicity by

$r(A)=\#\left\{(x,y)\in \mathcal{S}^2 : x\le y,\ xy=A,\ 10y\le 11x\right\}.$

Then

$M(k)=\min\{A:r(A)=k\}.$

Step 1: Characterize the manufacturable side lengths

The allowed rescalings only introduce prime factors at most \(23\). Conversely, every prime in \(P\) is itself an allowed multiplier, so repeated valid rescalings can build any positive integer whose prime divisors all lie in \(P\).

Therefore the manufacturable side lengths are exactly the \(23\)-smooth positive integers. This converts the original manufacturing constraint into a clean number-theoretic set \(\mathcal{S}\).

Step 2: Turn rectangle variants into near-square factor pairs

After ordering the sides so that \(x\le y\), every rectangle variant corresponds to one factorization \(A=xy\) with

$x\le y,\qquad 10y\le 11x.$

The inequality forces the two factors to lie close to \(\sqrt{A}\), and the condition \(x\le y\) removes the reflected duplicate \((y,x)\).

Because products of \(23\)-smooth numbers are still \(23\)-smooth, every admissible area is itself \(23\)-smooth. Also, every divisor of a \(23\)-smooth number is again \(23\)-smooth, so once an area \(A\) is fixed, counting manufacturable variants is the same as counting admissible divisor pairs of \(A\) near its square root.

Step 3: Define the multiplicity function and the search target

The function \(r(A)\) records how many admissible near-square factorizations produce the same area. Different areas can have the same multiplicity, and \(M(k)\) selects the smallest area with multiplicity exactly \(k\).

So the whole problem becomes

$\sum_{k=2}^{100} M(k).$

This viewpoint separates the task into two layers: enumerate all relevant side lengths, then aggregate areas by the number of admissible factor pairs that generate them.

Step 4: Why the expanding side cap is correct

Suppose we only enumerate side lengths up to some cap \(L\). Let \(r_L(A)\) be the same count as \(r(A)\), but restricted to pairs with \(x,y\le L\). As \(L\) grows, the set of visible pairs only increases, so \(r_L(A)\) is monotone.

Now consider any admissible pair with area \(A\). Since \(x\le y\) and \(xy=A\), we have \(x\le \sqrt{A}\le y\). Combining this with \(10y\le 11x\) gives

$y\le \frac{11}{10}x\le \frac{11}{10}\sqrt{A}.$

Hence every admissible pair for area \(A\) is guaranteed to be visible once

$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{A}\right\rceil \right\rceil.$

If all needed values \(M(2),\dots,M(100)\) have already been found and this inequality also holds for

$A=\max_{2\le k\le 100} M(k),$

then no unseen pair can alter any relevant minimum, so the search is finished.

Step 5: Worked Example Using the Checkpoint \(M(3)=889200\)

The implementations verify the checkpoint

$M(3)=889200.$

For this area, the admissible factor pairs are

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

Each pair satisfies \(x\le y\), each product is \(889200\), and each ratio \(y/x\) is below \(1.1\). Every side is also \(23\)-smooth:

$\begin{aligned} 900&=2^2\cdot 3^2\cdot 5^2, & 988&=2^2\cdot 13\cdot 19,\\ 912&=2^4\cdot 3\cdot 19, & 975&=3\cdot 5^2\cdot 13,\\ 936&=2^3\cdot 3^2\cdot 13, & 950&=2\cdot 5^2\cdot 19. \end{aligned}$

Therefore \(r(889200)=3\), and this area is the first one with multiplicity \(3\).

How the Code Works

The C++, Python, and Java implementations start from a moderate side cap and recursively generate every \(23\)-smooth side length up to that cap. The list is then sorted and deduplicated so each manufacturable side is processed once.

Next, the implementation scans the sorted side list with \(x\le y\). For each shorter side \(x\), it only considers longer sides up to \(\left\lfloor \frac{11x}{10}\right\rfloor\), because larger values would violate the near-square rule. Each admissible pair contributes one count to its area \(A=xy\). After all pairs are processed, the smallest area for each multiplicity \(k\in[2,100]\) is extracted from the area-count table.

If some \(M(k)\) is still missing, the side cap is multiplied by \(10\) and the process repeats. Once every \(M(k)\) from \(2\) through \(100\) has appeared, the implementation checks the coverage bound

$L\ge \left\lceil \frac{11}{10}\left\lceil \sqrt{\max_k M(k)}\right\rceil \right\rceil$

to prove that no admissible pair for any relevant area lies beyond the current cap. At that point the final sum is returned.

Complexity Analysis

Let \(s(L)\) be the number of \(23\)-smooth integers up to the final cap \(L\). Generating the smooth numbers is output-sensitive; after sorting and deduplication it costs \(O(s(L)\log s(L))\) time and \(O(s(L))\) memory.

The pair scan is worst-case \(O(s(L)^2)\), although the constraint \(10y\le 11x\) keeps only a narrow band near the diagonal and makes the practical workload much smaller. The area-count table uses linear memory in the number of distinct admissible areas encountered. Because the cap grows geometrically, the last successful round dominates the total runtime.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=563
2. Smooth numbers: Wikipedia — Smooth number
3. Divisor function and factor pairs: Wikipedia — Divisor function
4. Prime factorization: Wikipedia — Integer factorization
5. Geometric mean and the square-root bound: Wikipedia — Geometric mean