Detailed mathematical approach

Problem Summary

The implementations count integer triples \((a,b,c)\) with

$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$

A direct search over \((a,b,c)\) is far too slow for the actual limit. The key reduction is to convert the Diophantine condition into a rational point on a conic, classify primitive solutions once, and then count every scaled multiple in one floor division.

Mathematical Approach

Step 1: Rewrite the Constraint as a Conic

Start from

$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$

After rearranging and dividing by \(b^2c^2\), we obtain

$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$

So if we define

$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$

then \((X,Y)\) is a rational point on the conic \(X^2+Y^2=5\). The ordering \(a<b<c<2a\) translates into

$1<Y<X<2.$

This is the geometric core of the fast solution: the original triple-counting problem becomes a count of rational points in one canonical region of the conic.

Step 2: Pass to Primitive Integer Data

Write the rational point in lowest terms as

$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$

Then

$U^2+V^2=5W^2.$

Because \(1<Y<X<2\), the reduced integers satisfy

$W<V<U<2W.$

Any common divisor of two of \(U,V,W\) would also divide the third, so primitiveness implies pairwise coprimality. Also \(U\) and \(V\) cannot both be odd, hence exactly one of them is even and \(UV/2\) is an integer.

Step 3: Recover All Integer Triples from One Primitive Solution

From \(X=2a/b=U/W\) and \(Y=2a/c=V/W\), we get

$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$

Since \(\gcd(U,W)=\gcd(V,W)=1\), integrality forces \(U\mid 2a\) and \(V\mid 2a\). Because \(\gcd(U,V)=1\), we must have

$UV\mid 2a.$

Therefore every solution in this primitive family is obtained by writing

$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$

The primitive family generator is thus

$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$

and its contribution to \(F(N)\) is exactly

$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$

Step 4: Parametrize Primitive Conic Points

The implementations enumerate coprime pairs \(m>n>m/2\) and define

$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$

A direct expansion shows

$X_0^2+Y_0^2=5W_0^2.$

So \((|X_0|,Y_0,W_0)\) is an integer solution of the same quadratic form. Let

$g=\gcd(|X_0|,Y_0,W_0).$

The reduced primitive data is

$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$

Cases with \(5\mid g\) are discarded by the implementations because they are non-canonical \(5\)-lifts of smaller primitive families and would otherwise be counted twice.

Step 5: Why the Canonical Inequalities Are Automatic

The condition \(n>m/2\) is exactly what puts the parameterization into the correct region. Indeed,

$|X_0|-W_0=2m(2n-m)>0,$

$Y_0-W_0=(m-n)(m+3n)>0,$

$2W_0-|X_0|=3m^2+n^2-4mn>0,$

$2W_0-Y_0=2n(2n-m)>0.$

Hence both \(|X_0|\) and \(Y_0\) lie strictly between \(W_0\) and \(2W_0\). After dividing by \(g\) and sorting the two numerators, we obtain

$W<V<U<2W,$

which is exactly the reduced form corresponding to \(a<b<c<2a\).

Step 6: Why the Common Divisor Is So Small

Suppose an odd prime \(p\) divides all of \(|X_0|,Y_0,W_0\). Then \(p\) divides

$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$

Because \(p\) is odd and \(\gcd(m,n)=1\), the only possible shared cause is

$m\equiv 2n \pmod p.$

Substituting this into \(W_0=m^2+n^2\) gives \(5n^2\equiv 0\pmod p\), so \(p=5\). Thus the only odd common prime factor is \(5\). For the factor \(2\), if \(m\) and \(n\) are both odd then \(|X_0|,Y_0,W_0\) are even but not divisible by \(4\); otherwise at least one of them is odd. Therefore

$g\in\{1,2,5,10\},$

and once the duplicate \(5\)-lifts are skipped, the surviving cases have \(g=1\) or \(g=2\).

Worked Example

Take \((m,n)=(3,2)\). Then

$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$

Here \(g=1\), so after ordering we get

$U=22,\qquad V=19,\qquad W=13.$

The primitive triple generated by this family is

$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$

Thus the whole family is

$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$

and it contributes \(\lfloor N/209\rfloor\) solutions. In particular, this already explains why \(F(100)=0\): the first primitive family starts above \(100\).

How the Code Works

The C++, Python, and Java implementations all follow the same mathematics. They first compute a safe upper bound for \(m\), then iterate every coprime pair \(m>n>m/2\). For each pair they build the quadratic forms above, divide out the common factor, reject the duplicate \(5\)-lift cases, sort the two reduced numerators into the canonical order, and finally add

$\left\lfloor\frac{N}{UV/2}\right\rfloor.$

The C++ and Java implementations parallelize the outer loop over \(m\), while the Python implementation uses the same arithmetic sequentially.

Complexity Analysis

Let \(M\) be the largest \(m\) that can still contribute. Using \(g\le 2\) after the \(5\)-lift filter, we have

$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$

Write \(r=n/m\), so \(r\in(1/2,1)\). Then

$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$

hence

$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$

The factor on the right is increasing on \((1/2,1)\), so its minimum occurs at \(r=1/2\) and equals \(25/16\). Therefore

$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$

So no value \(m>(4N)^{1/4}\) can contribute, which matches the fourth-root cutoff used by the implementations. The enumeration therefore visits \(O(M^2)=O(N^{1/2})\) candidate pairs, with a constant amount of arithmetic and one gcd test per pair. Memory usage is \(O(1)\) apart from thread-local accumulators.

References

1. Problem page: https://projecteuler.net/problem=404
2. Rational parametrization of conics: Wikipedia — Conic section
3. Euclidean algorithm and gcd arguments: Wikipedia — Euclidean algorithm
4. Primitive quadratic-form parametrizations and related ideas: Wikipedia — Pythagorean triple