Problem 143: Investigating the Torricelli Point of a Triangle

Mathematical Development

Theorem 1. At the Torricelli point T of a triangle with all angles less than $120°$, each pair of vertices subtends an angle of exactly $120°$ at T. In particular, for side $c = |AB|$:

Proof. The Torricelli point minimizes $|AT| + |BT| + |CT|$ and, when all angles are less than $120°$, lies in the interior with $\angle ATB = \angle BTC = \angle ATC = 120°$. Applying the law of cosines to triangle ATB:

The other two equations follow by cyclic symmetry. $\square$

Definition. A pair $(u, v)$ with $u \geq v \geq 1$ is called 120-compatible if $u^2 + uv + v^2$ is a perfect square.

Theorem 2. All primitive 120-compatible pairs (with $\gcd(u,v) = 1$) are parametrized by:

where $m > n \geq 1$, $\gcd(m, n) = 1$, and $m \not\equiv n \pmod{3}$. The corresponding square root is $s = m^2 + mn + n^2$.

Proof. We verify: $u^2 + uv + v^2 = (m^2 - n^2)^2 + (m^2 - n^2)(2mn + n^2) + (2mn + n^2)^2$.

Expanding each term:

• $(m^2 - n^2)^2 = m^4 - 2m^2 n^2 + n^4$
• $(m^2 - n^2)(2mn + n^2) = 2m^3 n + m^2 n^2 - 2mn^3 - n^4$
• $(2mn + n^2)^2 = 4m^2 n^2 + 4mn^3 + n^4$

Summing: $m^4 + 2m^3 n + 3m^2 n^2 + 2mn^3 + n^4 = (m^2 + mn + n^2)^2$.

For primitivity: if $3 \mid (m - n)$, then $m \equiv n \pmod{3}$, which implies $u = m^2 - n^2 \equiv 0 \pmod{3}$ and $v = 2mn + n^2 \equiv 2n^2 + n^2 = 3n^2 \equiv 0 \pmod{3}$, so $\gcd(u,v) \geq 3$, violating primitivity. The converse (that $\gcd(m,n) = 1$ and $m \not\equiv n \pmod{3}$ imply $\gcd(u,v) = 1$) can be verified by checking that any common prime factor of $u$ and $v$ must divide $m^2 + mn + n^2 = s$, and showing this leads to a contradiction using the Eisenstein integer norm. $\square$

Lemma 1. All 120-compatible pairs are of the form $(ku, kv)$ where $(u,v)$ is a primitive pair and $k \geq 1$.

Proof. If $(U, V)$ is 120-compatible with $g = \gcd(U, V)$, then $U^2 + UV + V^2 = g^2(u^2 + uv + v^2)$ where $u = U/g$, $v = V/g$, $\gcd(u,v) = 1$. Since $u^2 + uv + v^2$ is a perfect square (being $g^{-2}$ times a perfect square), $(u,v)$ is a primitive 120-compatible pair. $\square$

Lemma 2. A valid Torricelli triple $(p, q, r)$ corresponds to a 3-clique in the graph $G$ whose vertices are positive integers and whose edges connect all 120-compatible pairs.

Proof. The three Torricelli equations require $(p,q)$, $(p,r)$, and $(q,r)$ to each be 120-compatible. This is exactly the condition that $\{p, q, r\}$ forms a clique of size 3 in $G$. $\square$

Editorial

The hard part is not checking a single triple, but generating only the pairs that could possibly belong to one. The parametrization of primitive 120-compatible pairs gives exactly that: every edge in the compatibility graph comes from a primitive pair generated by $(m,n)$, together with all of its positive multiples that still fit under the perimeter bound.

The implementation stores this graph in a directed way. For every compatible pair, the larger endpoint keeps the smaller endpoint in an adjacency set. Once that graph is built, a Torricelli triple $(p,q,r)$ is simply a 3-clique: $p$ must be compatible with $q$ and $r$, and $q$ must also be compatible with $r$. Iterating over the adjacency lists therefore becomes a direct clique search, and every valid perimeter sum $p+q+r \le 120000$ is inserted into a set so that repeated constructions are counted only once.

Pseudocode

Set the perimeter limit to 120000 and create an adjacency structure `smaller`.

Generate primitive 120-compatible pairs from parameters $m>n$:
    Skip pairs that are not coprime or have $m \equiv n \pmod 3$.
    Form the primitive pair $(u,v)$.
    For each positive multiple that still satisfies $u+v \le 120000$:
        Store the smaller endpoint in the adjacency set of the larger endpoint.

Create an empty set of valid perimeter sums.

For each largest value $p$ in the graph:
    For each compatible $q<p$ attached to $p$:
        Discard this branch if $p+q$ already leaves no room for a positive $r$.
        Look through all $r<q$ that are attached to $q$.
        Whenever $r$ is also attached to $p$, the three values form a clique.
        Record $p+q+r$ if it does not exceed the limit.

Return the sum of the distinct recorded perimeter sums.

Complexity Analysis

• Time: Pair generation is $O(L \cdot M)$ where $M$ is the number of primitive pairs with parameters up to $\sqrt{L}$, which is $O(L / \log L)$ by density estimates for Eisenstein primes. Clique enumeration depends on graph density; in practice, the neighbor sets are small enough that intersection is fast. Overall: $O(L^{3/2})$ in the worst case.
• Space: $O(L + E)$ where $E$ is the number of 120-compatible pairs, for storing the adjacency lists.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Problem 143: Torricelli point distances
    // Find sum of all distinct p+q+r <= 120000
    // where all three pair-wise expressions u^2+uv+v^2 are perfect squares.
    //
    // Primitive 120-compatible pairs: u = m^2-n^2, v = 2mn+n^2
    // with m > n >= 1, gcd(m,n) = 1, (m-n) % 3 != 0.
    // Then u^2+uv+v^2 = (m^2+mn+n^2)^2.
    // All solutions are k*(u,v) for k >= 1.

    const int LIMIT = 120000;

    // smaller[u] = sorted vector of v < u compatible with u
    vector<vector<int>> smaller(LIMIT + 1);

    auto addPrimitive = [&](int a, int b) {
        if (a <= 0 || b <= 0) return;
        int u = max(a, b), v = min(a, b);
        for (int k = 1; (long long)k * (u + v) <= LIMIT; k++) {
            smaller[k * u].push_back(k * v);
        }
    };

    for (int m = 2; (long long)m * m < LIMIT; m++) {
        for (int n = 1; n < m; n++) {
            if (__gcd(m, n) != 1) continue;
            if ((m - n) % 3 == 0) continue;
            int a = m * m - n * n;
            int b = 2 * m * n + n * n;
            addPrimitive(a, b);
        }
    }

    // Sort and deduplicate each adjacency list
    for (int i = 0; i <= LIMIT; i++) {
        sort(smaller[i].begin(), smaller[i].end());
        smaller[i].erase(unique(smaller[i].begin(), smaller[i].end()), smaller[i].end());
    }

    // Find triangles
    set<int> valid_sums;

    for (int p = 1; p <= LIMIT; p++) {
        if (smaller[p].empty()) continue;
        // For quick lookup, use a set for smaller[p]
        unordered_set<int> sp_set(smaller[p].begin(), smaller[p].end());

        for (int q : smaller[p]) {
            int max_r = LIMIT - p - q;
            if (max_r <= 0) continue;

            for (int r : smaller[q]) {
                if (r >= q) continue;
                if (r > max_r) continue;
                if (sp_set.count(r)) {
                    valid_sums.insert(p + q + r);
                }
            }
        }
    }

    long long ans = 0;
    for (int s : valid_sums) ans += s;
    cout << ans << endl;

    return 0;
}

"""
Problem 143: Investigating the Torricelli Point of a Triangle

At the Torricelli point T, angles ATB = BTC = CTA = 120 degrees.
By cosine rule: a^2 = q^2 + qr + r^2, etc.

We need p, q, r positive integers with p^2+pq+q^2, p^2+pr+r^2, q^2+qr+r^2
all perfect squares, and p+q+r <= 120000.

120-compatible pairs: (u,v) with u^2+uv+v^2 a perfect square.
Primitive parametrization: u = m^2-n^2, v = 2mn+n^2
with m > n >= 1, gcd(m,n) = 1, (m-n) not divisible by 3.
Then u^2+uv+v^2 = (m^2+mn+n^2)^2.
All solutions are k*(u,v) for positive integer k.
"""

from math import gcd, isqrt
from collections import defaultdict

def solve():
    LIMIT = 120000

    # Build adjacency: smaller[u] = set of v < u compatible with u
    smaller = defaultdict(set)

    def add_primitive(a, b):
        """Add primitive pair (a,b) and all its multiples."""
        if a <= 0 or b <= 0:
            return
        u, v = max(a, b), min(a, b)
        k = 1
        while k * (u + v) <= LIMIT:
            smaller[k * u].add(k * v)
            k += 1

    # Generate all primitive pairs: (m^2-n^2, 2mn+n^2)
    # with m > n >= 1, gcd(m,n) = 1, (m-n) % 3 != 0
    m = 2
    while m * m < LIMIT:  # rough bound
        for n in range(1, m):
            if gcd(m, n) != 1:
                continue
            if (m - n) % 3 == 0:
                continue
            a = m * m - n * n
            b = 2 * m * n + n * n
            add_primitive(a, b)
        m += 1

    # Find triangles: p > q > r >= 1, all three pairs compatible, p+q+r <= LIMIT
    valid_sums = set()

    for p in sorted(smaller.keys()):
        sp_set = smaller[p]
        for q in sorted(sp_set, reverse=True):
            max_r = LIMIT - p - q
            if max_r <= 0:
                continue
            if q not in smaller:
                continue
            for r in smaller[q]:
                if r >= q:
                    continue
                if r > max_r:
                    continue
                if r in sp_set:
                    valid_sums.add(p + q + r)

    answer = sum(valid_sums)
    print(answer)

if __name__ == '__main__':
    solve()