Detailed mathematical approach

Problem Summary

For each positive integer \(m\), let \(P(m)\) denote the sum of the perimeters of all integer-sided quadrilaterals whose maximal possible area is exactly \(m\). The target quantity is

$SP(n)=\sum_{m=1}^{n} P(m).$

The implementations verify the approach with the checkpoints \(SP(10)=186\) and \(SP(100)=23238\), then evaluate the full case \(n=10^6\).

Mathematical Approach

The geometry becomes manageable after rewriting the maximal-area condition as a factorization problem for \(m^2\).

Step 1: Start from the maximal-area formula

For side lengths \(a,b,c,d\), write the semiperimeter as

$s=\frac{a+b+c+d}{2}.$

Among all quadrilaterals with these side lengths, the area is maximized when the quadrilateral is cyclic. Brahmagupta's formula then gives

$A_{\max}^2=(s-a)(s-b)(s-c)(s-d).$

Problem 681 asks us to study the cases where \(A_{\max}=m\), so the defining equation is

$m^2=(s-a)(s-b)(s-c)(s-d).$

Step 2: Introduce a symmetric substitution

Set

$x=s-a,\qquad y=s-b,\qquad z=s-c,\qquad w=s-d.$

Then the area condition becomes

$xyzw=m^2.$

The side lengths are recovered by solving the linear system:

$a=\frac{-x+y+z+w}{2},\qquad b=\frac{x-y+z+w}{2},$

$c=\frac{x+y-z+w}{2},\qquad d=\frac{x+y+z-w}{2}.$

The perimeter is especially simple:

$a+b+c+d=x+y+z+w.$

So once a valid quadruple \((x,y,z,w)\) is known, its contribution to \(P(m)\) is exactly the sum \(x+y+z+w\).

Step 3: Characterize the valid quadruples

Permuting the side lengths only permutes \(x,y,z,w\), so we sort them and count only

$x\ge y\ge z\ge w\ge 1.$

Under this ordering, \(a\) is the smallest recovered side because it subtracts the largest term \(x\). Therefore positivity of all four sides is equivalent to the single inequality

$a>0\iff x<y+z+w.$

Integrality is controlled by parity. Since each recovered side is half of an integer expression, it is enough to require

$x+y+z+w\equiv 0 \pmod{2}.$

Hence valid quadrilaterals with maximal area \(m\) are in bijection with ordered positive integer quadruples satisfying

$xyzw=m^2,\qquad x\ge y\ge z\ge w,\qquad x<y+z+w,\qquad x+y+z+w\equiv 0\pmod{2}.$

Step 4: Reduce the search to divisors of \(m^2\)

If

$m=\prod_i p_i^{e_i},$

then

$m^2=\prod_i p_i^{2e_i}.$

Every candidate value \(w,z,y,x\) must therefore be a divisor of \(m^2\). The implementation generates the full divisor list of \(m^2\), sorts it, chooses \(w\le z\le y\), and determines the last factor by

$x=\frac{m^2}{wzy}.$

This automatically enforces the product constraint, and the sorted divisor list makes monotone early stopping possible: once a partial product is too large, all later divisors are too large as well.

Step 5: Worked example for \(m=4\)

Here \(m^2=16\). The ordered factor quadruples \((x,y,z,w)\) with product \(16\) are

$\begin{aligned} &(16,1,1,1),\\ &(8,2,1,1),\\ &(4,4,1,1),\\ &(4,2,2,1),\\ &(2,2,2,2). \end{aligned}$

The first two fail \(x<y+z+w\). The fourth has odd perimeter \(4+2+2+1=9\), so it does not produce integer side lengths. The remaining two are valid:

$\begin{aligned} (4,4,1,1)&\longrightarrow (a,b,c,d)=(1,1,4,4),\quad x+y+z+w=10,\\ (2,2,2,2)&\longrightarrow (a,b,c,d)=(2,2,2,2),\quad x+y+z+w=8. \end{aligned}$

Therefore

$P(4)=10+8=18.$

Step 6: Sum over all maximal areas

For each fixed \(m\), the program adds the perimeters of all valid quadruples to obtain \(P(m)\). The final answer is then

$SP(n)=\sum_{m=1}^{n}P(m).$

Because different values of \(m\) are independent, the outer summation is a natural place for parallel execution.

How the Code Works

The C++, Python, and Java implementations begin by preparing prime-factor information for all integers up to \(n\). For a given \(m\), the implementation factors \(m\), doubles the exponents to describe \(m^2\), and recursively generates every divisor of \(m^2\).

After sorting those divisors, the implementation scans candidates in the order \(w\le z\le y\). Whenever a partial product already forces the missing factor to fall below the required order, the loop stops early. If the remaining quotient is divisible by the chosen factors, that quotient becomes \(x\), and the code applies exactly the two mathematical filters derived above: the positivity inequality \(x<y+z+w\) and the parity condition \(x+y+z+w\equiv 0\pmod{2}\).

Each surviving quadruple contributes its perimeter \(x+y+z+w\) to \(P(m)\). The C++ and Java implementations distribute distinct values of \(m\) across worker threads, while the Python implementation reuses the compiled C++ computation path and returns the parsed final result.

Complexity Analysis

Let \(D(m)=\tau(m^2)\) be the number of divisors of \(m^2\). Building the prime-factor table up to \(n\) uses \(O(n)\) memory and \(O(n\log\log n)\) time in the usual sieve analysis, with the C++ version using a linear smallest-prime-factor construction. For one fixed \(m\), generating all divisors costs \(O(D(m))\). The subsequent ordered scan over divisor triples has worst-case \(O(D(m)^3)\) behavior, but the monotone break conditions and divisibility tests cut away most combinations in practice. Extra working memory beyond the sieve is dominated by the divisor list for one value of \(m\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=681
2. Brahmagupta's formula: Wikipedia — Brahmagupta's formula
3. Cyclic quadrilateral: Wikipedia — Cyclic quadrilateral
4. Divisor function: Wikipedia — Divisor function