Detailed mathematical approach

Problem Summary

The local C++ validator shows that every admissible triangle can be represented in centered form

$P_1=(x_1,y_1),\qquad P_2=(x_2,y_2),\qquad P_3=(-x_1-x_2,-y_1-y_2),$

so automatically

$x_1+x_2+x_3=0,\qquad y_1+y_2+y_3=0.$

The ellipse condition is already converted by the implementation into the Diophantine system

$ (2x_1+x_2)y_1 + (x_1+2x_2)y_2 = 0, $

$ x_1^2+x_1x_2+x_2^2 - (y_1^2+y_1y_2+y_2^2) = 39. $

We must sum the Euclidean areas of all non-degenerate integer triangles whose coordinates lie inside \([-N,N]^2\), for the real target \(N=10^9\). The brute-force search in solve_bruteforce_small is only feasible for tiny \(N\), so the fast solver rewrites the problem as a finite family of Pell-type recurrences.

Mathematical Approach

1. Extract a primitive direction from the \(x\)-coordinates

Write the three \(x\)-coordinates as

$x_1=du,\qquad x_2=dv,\qquad x_3=-d(u+v),$

where \(d>0\) and \(\gcd(u,v)=1\). The linear constraint then becomes

$a y_1 + b y_2 = 0,\qquad a=2u+v,\qquad b=u+2v.$

All integer solutions of this linear equation have the form

$y_1=\frac{b}{m}k,\qquad y_2=-\frac{a}{m}k,\qquad y_3=-y_1-y_2=\frac{u-v}{m}k,$

where \(m=\gcd(a,b)\) and \(k\in\mathbb{Z}\). Because

$2a-b=3u,\qquad 2b-a=3v,$

every common divisor of \(a\) and \(b\) must divide \(3\). Since \((u,v)\) is primitive, \(m\in\{1,3\}\). The admissible primitive directions kept by the program always satisfy \(m=3\).

2. Substitute into the quadratic constraint

Define the norm

$q_0=u^2+uv+v^2.$

Then the \(x\)-part of the quadratic equation becomes

$x_1^2+x_1x_2+x_2^2=d^2q_0.$

For the \(y\)-part, using \(m=3\), \(a=2u+v\), and \(b=u+2v\), we obtain

$y_1^2+y_1y_2+y_2^2=\frac{b^2-ab+a^2}{9}k^2.$

Now

$a^2-ab+b^2=3(u^2+uv+v^2)=3q_0,$

so

$y_1^2+y_1y_2+y_2^2=\frac{q_0}{3}k^2.$

Substituting into the validator equation gives

$39=q_0d^2-\frac{q_0}{3}k^2=\frac{q_0}{3}(3d^2-k^2),$

hence

$q_0(3d^2-k^2)=117,\qquad k^2-3d^2=-\frac{117}{q_0}.$

This identity is the algebraic backbone of the fast method.

3. Why only \(q_0=3\) and \(q_0=39\)

The previous formula shows that \(q_0\) must divide \(117\). The code then enumerates primitive pairs \((u,v)\) satisfying

$u^2+uv+v^2=q_0,\qquad \gcd(u,v)=1,\qquad \gcd(2u+v,u+2v)=3.$

A direct enumeration leaves exactly two norm families:

$q_0=3 \quad\text{with 6 primitive directions},\qquad q_0=39 \quad\text{with 12 primitive directions}.$

No admissible primitive direction exists for \(q_0=117\), so the whole search collapses to \(18\) direction templates. That is why build_directions loops only over q0 in (3, 39).

4. Pell equations and boundary cutoffs

The two surviving norms lead to

$q_0=3 \Longrightarrow k^2-3d^2=-39,\qquad q_0=39 \Longrightarrow k^2-3d^2=-3.$

The implementations use the smallest positive seeds found by inspection:

$ (d,k)=(4,3),(5,6)\ \text{for }-39,\qquad (d,k)=(2,3)\ \text{for }-3. $

All larger solutions are generated by multiplication with the fundamental unit \(2+\sqrt{3}\), which yields the recurrence

$k_{n+1}=2k_n+3d_n,\qquad d_{n+1}=k_n+2d_n.$

For one fixed direction \((u,v)\), the coordinate bounds are

$x_{\mathrm{scale}}=\max(|u|,|v|,|u+v|),$

$y_{\mathrm{scale}}=\frac{\max(|2u+v|,|u+2v|,|u-v|)}{3},$

so the code keeps only pairs with

$d\le \left\lfloor\frac{N}{x_{\mathrm{scale}}}\right\rfloor,\qquad k\le \left\lfloor\frac{N}{y_{\mathrm{scale}}}\right\rfloor.$

5. Area formula, worked example, and deduplication

Using the explicit coordinates, the doubled area simplifies to

$2A=\left|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\right|=2q_0|dk|,$

so the actual area is

$\boxed{A=q_0|dk|}.$

Take the primitive direction \((u,v)=(1,1)\), which belongs to the \(q_0=3\) family. With the seed \((d,k)=(4,3)\), we get

$ (x_1,y_1)=(4,3),\qquad (x_2,y_2)=(4,-3),\qquad (x_3,y_3)=(-8,0), $

and therefore

$A=3\cdot 4\cdot 3=36.$

This is one of the triangles contributing to the checkpoint value \(72\) at \(N=8\). Because different direction/sign choices can reconstruct the same triangle, the implementations sort the three vertices and use the sorted triple as a hash key. If a duplicate is seen, the code checks that the area is identical before merging.

How the Code Works

The three solution files implement the same pipeline. build_directions enumerates the \(18\) primitive direction templates and computes their personal \((d_{\max},k_{\max})\) cutoffs. generate_pell_pairs precomputes all Pell solutions for the two negative right-hand sides up to the largest cutoff required by any direction. build_triangle_key reconstructs the three vertices, rejects out-of-range or degenerate cases, and returns the sorted vertex triple together with the closed-form area \(q_0|dk|\).

The main loop selects the correct Pell list for each direction, tries both signs of \(k\), and inserts the triangle into a hash map keyed by its sorted vertices. The C++ version adds extra validation: checkpoint values \(72\), \(252\), \(34632\), and \(3529008\) for \(N=8,10,100,1000\), plus a brute-force cross-check against solve_bruteforce_small(20). The Python and Java versions use the same fast construction without the checkpoint harness.

Complexity Analysis

For this problem the number of direction templates is constant: \(18\). Each Pell sequence grows exponentially because the recurrence multiplies by \(2+\sqrt{3}\), so the number of generated \((d,k)\) pairs below the bounds is \(O(\log N)\) per family. The total running time is therefore proportional to the number of generated candidates and hash insertions, rather than to any polynomial scan over lattice coordinates. Memory usage is \(O(T)\), where \(T\) is the number of distinct triangles stored in the hash map.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=385
2. Primary derivation source in this repository: solutionsCpp/Euler385.cpp, solutionsPython/Euler385.py, solutionsJava/Euler385.java
3. Pell equation: Wikipedia — Pell equation
4. Binary quadratic forms: Wikipedia — Binary quadratic form
5. Triangle area / determinant formula: Wikipedia — Shoelace formula