Detailed mathematical approach

Problem Summary

For an \(m \times n\) grid, we count every axis-aligned sub-rectangle. The target is \(2{,}000{,}000\) rectangles, but the problem asks for the grid whose count is closest to that value, not necessarily equal to it. The closest grid is \(36 \times 77\) (or \(77 \times 36\)), which contains \(1{,}999{,}998\) rectangles and therefore has area \(2772\).

Mathematical Approach

The key observation is that a sub-rectangle is determined entirely by its boundary lines. Once that is written down, the geometry collapses to a product of two triangular numbers, and the remaining task is a very small monotone search.

Choosing Boundary Lines

An \(m \times n\) grid has \(m+1\) horizontal grid lines and \(n+1\) vertical grid lines. To form a sub-rectangle, choose two distinct horizontal lines and two distinct vertical lines. Therefore

$R(m,n)=\binom{m+1}{2}\binom{n+1}{2}=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}.$

If we denote the \(k\)-th triangular number by \(T_k=k(k+1)/2\), then the count becomes

$R(m,n)=T_mT_n.$

This is the central mathematical object of the problem: every candidate grid corresponds to a product of two triangular numbers.

The Same Formula from Rectangle Sizes

The closed form also appears if we count by size. A rectangle of height \(h\) and width \(w\) can start in \(m-h+1\) vertical positions and \(n-w+1\) horizontal positions, so

$R(m,n)=\sum_{h=1}^{m}\sum_{w=1}^{n}(m-h+1)(n-w+1).$

Because the horizontal and vertical choices are independent, the double sum factors as

$R(m,n)=\left(\sum_{i=1}^{m} i\right)\left(\sum_{j=1}^{n} j\right)=T_mT_n.$

The implementations use this factorized form directly, so each candidate can be evaluated with constant-time arithmetic.

Worked Example: A \(3 \times 2\) Grid

For \(m=3\) and \(n=2\), we get

$R(3,2)=\frac{3 \cdot 4}{2}\cdot\frac{2 \cdot 3}{2}=6 \cdot 3=18.$

So a \(3 \times 2\) grid contains exactly 18 sub-rectangles and has area \(6\). This is a useful check because it can be verified by hand and matches the sample behavior built into the solutions.

Symmetry, Monotonicity, and Search Reduction

The count is symmetric:

$R(m,n)=R(n,m).$

That means we only need to examine pairs with \(m \le n\). For fixed \(m\), the count grows strictly with \(n\):

$R(m,n+1)-R(m,n)=T_m(T_{n+1}-T_n)=T_m(n+1) > 0.$

Once a fixed row of candidates has crossed the target, larger values of \(n\) only move farther away, so the inner search can stop early. The implementations also use a generous hard cap of \(2000\); this is already beyond the scale where even a \(1 \times 2000\) strip has

$R(1,2000)=T_1T_{2000}=2{,}001{,}000$

rectangles, so the optimum is safely contained inside that window.

The Winning Grid

After the problem has been reduced to minimizing

$\left|T_mT_n-2{,}000{,}000\right|,$

the best pair found by the implementations is

$m=36,\qquad n=77.$

Indeed,

$T_{36}=666,\qquad T_{77}=3003,\qquad 666 \cdot 3003=1{,}999{,}998,$

so the target is missed by only \(2\). The reported area is therefore

$36 \cdot 77=2772.$

How the Code Works

Enumerating Candidate Dimensions

The C++, Python, and Java implementations all perform the same search. They iterate over the smaller side first and then iterate over the larger side starting from that value, which avoids visiting both \((m,n)\) and \((n,m)\). For each pair, they compute \(R(m,n)=m(m+1)n(n+1)/4\) and compare its absolute distance from the target with the current best distance.

Updating the Best Area

Whenever a closer grid is found, the stored best area is updated. Because the rectangle count is monotone in the second dimension, the inner loop stops after the overshoot point instead of scanning the rest of the row. One implementation writes that stopping condition a little more conservatively and also includes a small sample checkpoint plus an optional target override, but the mathematical core is identical in all three languages.

Complexity Analysis

If the outer cap is \(B\), then symmetry reduces the worst-case search to the pairs \(1 \le m \le n \le B\), which is at most

$\frac{B(B+1)}{2}$

candidate grids. With the literal bound \(B=2000\), that is \(2{,}001{,}000\) evaluations before early termination is even taken into account.

Each evaluation uses only constant-time integer arithmetic, so the worst-case running time is \(O(B^2)\) and the memory usage is \(O(1)\). In practice the code is faster than the raw bound suggests because the monotone inner loop usually breaks well before reaching the cap.

Footnotes and References

1. Problem page: Project Euler 85 - Counting rectangles
2. Binomial coefficient: Wikipedia - Binomial coefficient
3. Triangular number: Wikipedia - Triangular number
4. Combination: Wikipedia - Combination