Torricelli Triangles

Let $ABC$ be a triangle with all interior angles being less than $120$ degrees. Let $X$ be any point inside the triangle and let $XA = p$, $XC = q$, and $XB = r$.
Fermat challenged Torricelli to find the position of $X$ such that $p + q + r$ was minimised.
Torricelli was able to prove that if equilateral triangles $AOB$, $BNC$ and $AMC$ are constructed on each side of triangle $ABC$, the circumscribed circles of $AOB$, $BNC$, and $AMC$ will intersect at a single point, $T$, inside the triangle. Moreover he proved that $T$, called the Torricelli/Fermat point, minimises $p + q + r$. Even more remarkable, it can be shown that when the sum is minimised, $AN = BM = CO = p + q + r$ and that $AN$, $BM$ and $CO$ also intersect at $T$.

If the sum is minimised and $a, b, c, p, q$ and $r$ are all positive integers we shall call triangle $ABC$ a Torricelli triangle. For example, $a = 399$, $b = 455$, $c = 511$ is an example of a Torricelli triangle, with $p + q + r = 784$.
Find the sum of all distinct values of $p + q + r \le 120000$ for Torricelli triangles.

This problem is from the Project Euler (Problem 143), and it is considered quite difficult even among other Project Euler problems. To solve this problem, we need a good understanding of number theory and geometry.

Firstly, realising that Torricelli’s triangle is actually an equilateral triangle is crucial. This can be deduced by noticing from the formulas derived from the Law of Cosines that any triangle, in which the distances from an internal point to the corners are equal, must be equilateral.

Secondly, it’s important to realise the distinct relationship that this problem proposes. If $AN=BM=CO=p+q+r$, they must be the sides of an equilateral triangle where p, q, r are the sides of the triangles $TAC, TBC, TBA$ respectively. By the law of cosines, we can therefore say $p^2 + a^2 – pq = q^2 + b^2 – qr = r^2 + c^2 – rp$.

We are then interested in solving the system of Diophantine equations of the form $a^2 + b^2 = c^2 + 3ab$. This can be systematically done by iterating through all values of p, q, r and checking which ones satisfy the equation. This is done by brute forcing a solution.

However, to avoid needless repetition and reduce computational complexity, it is required to use memoization. This stores already calculated values in a map, and these stored values may be reused. Moreover, since you only need to find the sum of distinct sums $p+q+r$, you need to keep track of these in a set, for example.

The distinct Torricelli sums are then summed up to get the solution.

It’s important to note that this kind of problem requires not only mathematical knowledge, but also programming skills to implement an efficient solution. Due to the combinatorial nature of this problem, a brute force solution would simply take too long.

However, keep in mind that Project Euler problems are designed to be solvable within a minute with an efficient algorithm on a modest computer, so it’s all about finding an efficient way to get to the solution.

Unfortunately, solving these Diophantine equations for $p+q+r \le 120000$ and summing up would require more computing power and is typically done via code in Python or some other programming language rather than by hand.

More Answers: