Detailed mathematical approach

Problem Summary

Let \(T\) be the Torricelli point of a triangle \(ABC\), and write \(p=TA\), \(q=TB\), \(r=TC\). The problem asks for the sum of all distinct values of \(p+q+r\) with \(p+q+r \le 120{,}000\), under the condition that \(p\), \(q\), and \(r\) are integers and that the three side lengths of the triangle are integers as well.

The decisive fact is that the three angles at \(T\) are all \(120^\circ\). That turns the geometry into an arithmetic question about when expressions of the form \(x^2+xy+y^2\) are perfect squares. The implementations exploit that arithmetic structure directly and never need to reconstruct coordinates.

Mathematical Approach

Write the triangle sides as \(a=BC\), \(b=CA\), and \(c=AB\). Since the angles \(\angle ATB\), \(\angle BTC\), and \(\angle CTA\) are each \(120^\circ\), every side length is determined by a cosine-law identity.

From the Torricelli point to a Diophantine system

Applying the law of cosines with \(\cos 120^\circ=-\tfrac12\) gives

$a^2=q^2+qr+r^2,\qquad b^2=r^2+rp+p^2,\qquad c^2=p^2+pq+q^2.$

So a triple \((p,q,r)\) is admissible exactly when all three quadratic forms

$p^2+pq+q^2,\qquad q^2+qr+r^2,\qquad r^2+rp+p^2$

are perfect squares. Once this happens, the corresponding triangle sides are integers, and the point with three \(120^\circ\) rays is precisely the Torricelli configuration described in the problem.

The basic arithmetic object: a 120-degree integer pair

Call two positive integers \(x\) and \(y\) compatible if

$x^2+xy+y^2=z^2$

for some integer \(z\). Geometrically, \(x\) and \(y\) can then appear as two Torricelli distances meeting at \(120^\circ\), and \(z\) is the opposite triangle side. The full problem is therefore not about arbitrary triples first; it is about finding three distances that are pairwise compatible.

That observation turns the search into a graph problem. Take the integers \(1,2,\dots,N\) with \(N=120{,}000\) as vertices, and join \(x\) and \(y\) by an edge whenever they are compatible. Then every valid \((p,q,r)\) is exactly a 3-clique in this graph, because all three pairwise square conditions must hold simultaneously.

Generating all compatible pairs efficiently

The optimized implementations do not test every pair \((x,y)\) from scratch. They use the standard parametrization of primitive solutions of

$x^2+xy+y^2=z^2,$

namely, up to swapping \(x\) and \(y\),

$x_0=m^2-n^2,\qquad y_0=n(2m+n),\qquad z_0=m^2+mn+n^2,$

with

$m>n>0,\qquad \gcd(m,n)=1,\qquad m-n\not\equiv 0 \pmod 3.$

Every non-primitive compatible pair is then just a multiple \((kx_0,ky_0)\). This is why the fast versions loop over \((m,n)\), generate primitive seeds, and then scale them by \(k\) until the limit is reached. The side length \(z\) never needs to be stored, because the existence of an edge is all that matters later.

Why triangle enumeration becomes common-neighbor intersection

Suppose \(p<q<r\). In graph language, \((p,q,r)\) is valid exactly when \(q\) and \(r\) are both neighbors of \(p\), and \(r\) is also a neighbor of \(q\). So after building sorted adjacency lists, one can fix \(p\), choose \(q>p\) among the neighbors of \(p\), and then look for common neighbors of \(p\) and \(q\) that are larger than \(q\). Intersecting the two sorted tails finds precisely those \(r\).

This ordered search has two important invariants. First, \(p<q<r\) prevents the same triple from being generated in six different permutations. Second, the problem asks for distinct sums \(p+q+r\), not distinct triples, so the final sums are inserted into a set before being added together. Two different triples may contribute the same perimeter, and that perimeter must be counted once.

Worked example: the perimeter 784

A concrete solution is

$ (p,q,r)=(195,264,325). $

Indeed,

$195^2+195\cdot264+264^2=399^2,$

$195^2+195\cdot325+325^2=455^2,$

$264^2+264\cdot325+325^2=511^2.$

So the three sides of the triangle are \(399\), \(455\), and \(511\), all integral, and the corresponding Torricelli-distance sum is

$195+264+325=784.$

This is the small example used by the implementations as a sanity check before attacking the full limit.

How the Code Works

Building the compatibility graph

The C++, Python, and Java implementations all work with the same graph of compatible distance pairs. The optimized C++ and Python versions build that graph from the parametrization above, adding each generated pair to both adjacency lists because compatibility is symmetric. After generation, each list is sorted and deduplicated so that later intersections are linear scans over ordered data.

Closing 3-cliques into Torricelli triples

Once the graph exists, the next phase is to enumerate every ordered triple \(p<q<r\) that forms a clique. For a fixed \(p\), the implementation scans its neighbors \(q\) with \(q>p\). Any admissible \(r\) must be a common neighbor of \(p\) and \(q\) and must also satisfy \(r>q\). The sorted-list intersection enforces all of that at once, and whenever \(p+q+r \le 120{,}000\), the sum is recorded.

Optimized versus direct construction

The Java implementation illustrates the same mathematics in a more direct style. Instead of generating compatible pairs from the parametrization, it checks every \(p<q\) with \(p+q \le N\), tests whether \(p^2+pq+q^2\) is a square, stores the successful pairs, and then searches for common neighbors to complete triangles. That approach is conceptually simple but spends much more time on failed pair tests. The C++ and Python implementations avoid most of that work by generating only genuine compatible pairs from the start.

Complexity Analysis

Let \(E\) be the number of compatible pairs up to the limit \(N\). The optimized construction spends \(O(E)\) time generating scaled pairs from primitive seeds, plus the cost of sorting the adjacency lists, plus the cost of all ordered list intersections used to enumerate cliques. A conservative worst-case bound is still quadratic in \(N\), but the arithmetic graph is sparse enough that the full limit is practical.

The direct construction used in the Java version performs \(O(N^2)\) pair tests just to build the graph, and only afterward begins the common-neighbor search. All versions use \(O(E)\) memory for the adjacency structure, together with a set of distinct perimeter sums. The main speedup comes from replacing a naive search over triples of distances with a search over edges and their common neighbors.

Footnotes and References

1. Problem page: Project Euler 143
2. Torricelli or Fermat point: Wikipedia - Fermat point
3. Cosine law: Wikipedia - Law of cosines
4. The quadratic form \(x^2+xy+y^2\) as an Eisenstein norm: Wikipedia - Eisenstein integer