Detailed mathematical approach

Problem Summary

A Heron envelope can be modeled as a rectangle of width \(2a\) and height \(h\), topped by an isosceles flap whose base is also \(2a\), whose equal side length is \(s\), and whose altitude is \(t\). Its outer perimeter is

$P=2(a+h+s).$

The task is to compute \(S(p)\), the sum of all such perimeters with \(P\le p\), subject to the geometric condition \(t<h\) and the integrality conditions encoded by the three reference implementations. Writing \(L=p/2\) is convenient, because every valid envelope then satisfies

$a+h+s\le L.$

Mathematical Approach

The key observation is that every admissible envelope is governed by three right triangles sharing the same half-width \(a\). Once those right triangles are parameterized, the problem becomes a structured matching problem rather than a brute-force search over polygons.

Step 1: Convert the Geometry into Three Square Conditions

The flap itself splits into two congruent right triangles, so its side length \(s\) must satisfy

$a^2+t^2=s^2.$

The rectangle has full width \(2a\), so its diagonal condition is

$\left(2a\right)^2+h^2=d^2$

for some integer \(d\).

The long diagonal running from a lower corner to the top vertex of the flap has horizontal offset \(a\) and vertical offset \(h+t\), so it must satisfy

$a^2+(h+t)^2=q^2$

for some integer \(q\).

Therefore a valid envelope is exactly a quadruple \((a,h,t,s)\) with

$a^2+t^2=s^2,\qquad \left(2a\right)^2+h^2=d^2,\qquad a^2+(h+t)^2=q^2,\qquad t<h,\qquad a+h+s\le L.$

Step 2: Enumerate All Relevant Right Triangles

Every primitive Pythagorean triple can be written as

$x=m^2-n^2,\qquad y=2mn,\qquad z=m^2+n^2,$

with \(m>n\), \(\gcd(m,n)=1\), and opposite parity. Multiplying by a positive scale \(k\) gives every non-primitive triple:

$x=k(m^2-n^2),\qquad y=k(2mn),\qquad z=k(m^2+n^2).$

For flap candidates, one leg is \(a\), the other is \(t\), and the hypotenuse is \(s\). Since either leg may play the role of \(a\), the implementations keep both leg orders from each generated triple.

For rectangle candidates, the full width must be \(2a\). So whenever a generated leg is even, that leg can be halved to obtain \(a\), while the other leg becomes \(h\). This is why the rectangle catalogue is built from Pythagorean triples with an even leg.

The perimeter bound gives safe search limits. Because \(a+h+s\le L\), we only need flap triples with \(s\le L\), and rectangle triples with \(2a\le 2L\) and \(h\le L\).

Step 3: Group Everything by the Shared Half-Width

Define

$T(a)=\left\{y\in\mathbb{Z}_{>0}:a^2+y^2\text{ is a perfect square}\right\}.$

Then the flap condition says \(t\in T(a)\), and the long-diagonal condition says \(h+t\in T(a)\).

The rectangle condition is separate: \(h\) must belong to the set of heights for which \(\left(2a\right)^2+h^2\) is a square.

This immediately suggests the data organization used by the implementations: build all flap candidates and all rectangle candidates, then group both collections by the same value of \(a\). Each group can be processed independently.

Step 4: Match Rectangle Heights with Flap Heights

Fix one half-width \(a\). For every rectangle height \(h\) in that group and every flap candidate \((t,s)\) in the same group, we test three conditions:

$t<h,\qquad s\le L-a-h,\qquad h+t\in T(a).$

The first inequality is the sensible-envelope condition. The second is just the perimeter bound rewritten from \(a+h+s\le L\). The third guarantees that the long diagonal is integral.

If all three tests pass, then the envelope is valid and contributes

$2(a+h+s)$

to \(S(p)\).

This is much cheaper than checking arbitrary polygons, because the search only combines already-valid right-triangle building blocks.

Step 5: Why Sorting Helps

Within a fixed \(a\)-group, the flap candidates are sorted by \(t\). For fixed \(a\), the flap side length is

$s=\sqrt{a^2+t^2},$

so increasing \(t\) also increases \(s\). Therefore, once \(t\ge h\), no later flap can satisfy \(t<h\); and once \(s>L-a-h\), no later flap can satisfy the perimeter bound. Both facts allow early exits in the inner scan.

The rectangle heights are also sorted, so if \(L-a-h\le 0\), no larger height can work either. These monotonicity properties are exactly what make the grouped scan practical.

Worked Example

One concrete valid envelope is obtained from

$a=60,\qquad h=119,\qquad t=25,\qquad s=65.$

The flap is integral because

$60^2+25^2=65^2.$

The rectangle diagonal is integral because

$120^2+119^2=169^2.$

The long diagonal is also integral because

$60^2+(119+25)^2=60^2+144^2=156^2.$

Since \(25<119\), the flap is lower than the rectangle height as required. Its perimeter is

$P=2(60+119+65)=488.$

So this envelope contributes \(488\) to \(S(p)\) whenever \(p\ge 488\).

How the Code Works

The C++, Python, and Java implementations all follow the same mathematical plan. They first set \(L=p/2\), generate all flap right triangles up to hypotenuse \(L\), and generate all rectangle candidates by taking Pythagorean triples whose even leg can serve as the full width \(2a\).

Next, they regroup both catalogues by the shared half-width \(a\). Inside each group, flap candidates are stored as altitude-side pairs \((t,s)\), and rectangle candidates are stored by their heights \(h\). A lookup structure containing all admissible values of \(t\) for that \(a\) lets the implementation test the long-diagonal condition \(h+t\in T(a)\) in constant expected time.

Each group is then scanned in sorted order. For every rectangle height, the implementation checks flap candidates until either \(t\ge h\) or \(s>L-a-h\). Every successful match adds \(2(a+h+s)\) to the running total. The C++ version additionally parallelizes these independent \(a\)-groups for large limits, while the Python and Java versions keep the same logic in a single thread.

Complexity Analysis

Let \(T\) be the number of generated flap candidates and \(R\) the number of generated rectangle candidates after the Euclidean enumeration and scaling steps. Building those candidate lists is \(O(T+R)\) in output size, up to the arithmetic cost of the gcd filters and loop bounds in the triple generator.

Grouping and sorting cost

$O(T\log T+R\log R)$

overall. The matching phase is best described groupwise: if \(M\) is the total number of flap-rectangle pairs actually inspected before the early breaks trigger, then the scan costs \(O(M)\), and each long-diagonal test is \(O(1)\) on average thanks to the lookup structure.

Memory usage is linear in the stored candidates, plus the auxiliary membership structure used for the \(h+t\) test. In practice, the method is efficient because it never searches arbitrary envelopes directly; it only combines prevalidated right triangles with the same half-width.

Footnotes and References

1. Problem page: Project Euler 583 - Heron Envelopes
2. Pythagorean triples: Wikipedia - Pythagorean triple
3. Euclid's formula: Wikipedia - Generating a Pythagorean triple
4. Isosceles triangles: Wikipedia - Isosceles triangle
5. Heron's formula: Wikipedia - Heron's formula