Project Euler

The Incenter of a Triangle

ABC is an integer-sided triangle with incenter I and perimeter p. The segments IA, IB, and IC all have integral length. Let L = p + |IA| + |IB| + |IC|. Let S(P) = sum L over all such triangles with...

Source sync Apr 19, 2026

Problem #0482

Level Level 31

Solved By 265

Languages C++, Python

Answer 1400824879147

Length 257 words

geometrymodular_arithmeticanalytic_math

$ABC$ is an integer sided triangle with incenter $I$ and perimeter $p$.

The segments $IA$, $IB$ and $IC$ have integral length as well.

Let $L = p + |IA| + |IB| + |IC|$.

Let $S(P) = \sum L$ for all such triangles where $p \le P$. For example, $S(10^3) = 3619$.

Find $S(10^7)$.

Problem 482: The Incenter of a Triangle

Mathematical Foundation

Theorem 1 (Incenter distance formula). For a triangle with sides $a, b, c$ , semiperimeter $s = (a+b+c)/2$ , and incenter $I$ ,

|IA|^2 = \frac{bc(s-a)}{s}, \quad |IB|^2 = \frac{ac(s-b)}{s}, \quad |IC|^2 = \frac{ab(s-c)}{s}.

Proof. The inradius is $r = K/s$ where $K$ is the area. By Heron’s formula, $K = \sqrt{s(s-a)(s-b)(s-c)}$ . The distance from the incenter to vertex $A$ satisfies $|IA| = r/\sin(A/2)$ . Using the half-angle identity $\sin(A/2) = \sqrt{(s-b)(s-c)/(bc)}$ , we obtain

|IA| = \frac{r}{\sin(A/2)} = \frac{K}{s} \cdot \sqrt{\frac{bc}{(s-b)(s-c)}} = \frac{\sqrt{s(s-a)(s-b)(s-c)}}{s} \cdot \sqrt{\frac{bc}{(s-b)(s-c)}}.

Simplifying:

|IA| = \sqrt{\frac{(s-a) \cdot bc}{s}}.

The formulas for $|IB|$ and $|IC|$ follow by cyclic symmetry. $\square$

Lemma 1 (Substitution). Setting $x = s - a$ , $y = s - b$ , $z = s - c$ (so $a = y+z$ , $b = x+z$ , $c = x+y$ , $s = x+y+z$ ), the integrality conditions become:

|IA|^2 = \frac{x(x+y)(x+z)}{x+y+z}, \quad |IB|^2 = \frac{y(x+z)(y+z)}{x+y+z}, \quad |IC|^2 = \frac{z(x+y)(y+z)}{x+y+z}.

Each must be a perfect square.

Proof. Direct substitution of $a = y+z$ , $b = x+z$ , $c = x+y$ , $s = x+y+z$ into Theorem 1. For instance, $bc(s-a)/s = (x+z)(x+y) \cdot x/(x+y+z)$ . $\square$

Lemma 2 (Parity constraint). The perimeter $p = 2s = 2(x+y+z)$ is always even, and $x, y, z$ are positive integers satisfying the triangle inequality automatically (since $a = y+z > 0$ , etc., and $a < b+c \iff x > 0$ ).

Proof. Since $a, b, c$ are positive integers, $s = (a+b+c)/2$ is a positive half-integer or integer. For $x, y, z$ to be positive integers, we need $s \in \mathbb{Z}$ , hence $p = 2s$ is even. The triangle inequality $a < b + c$ is equivalent to $s - a = x > 0$ , which holds since $x \ge 1$ . $\square$

Theorem 2 (Divisibility condition). Let $s = x + y + z$ . Then $|IA|^2 \in \mathbb{Z}$ requires $s \mid x(x+y)(x+z)$ , and similarly for $|IB|^2, |IC|^2$ . Moreover, the product satisfies

|IA|^2 \cdot |IB|^2 \cdot |IC|^2 = \frac{xyz \cdot (x+y)^2(y+z)^2(x+z)^2}{s^3}.

Proof. The first claim is immediate from Lemma 1. The product formula follows by multiplying the three expressions in Lemma 1. $\square$

Editorial

We check |IA|^2 = x*(x+y)*(x+z) / s is a perfect square. We then similarly for |IB|^2 and |IC|^2. Finally, count permutations of (x, y, z).

Pseudocode

Check |IA|^2 = x*(x+y)*(x+z) / s is a perfect square
Similarly for |IB|^2 and |IC|^2
Count permutations of (x, y, z)
Note: different permutations may give different L values
Handle each distinct (a,b,c) triangle separately

Complexity Analysis

Time: $O(P^{3/2})$ in the worst case (iterating $x \le y \le z$ with $x+y+z \le P/2$ ), but the divisibility and perfect-square filters prune the vast majority of candidates, making the effective runtime much smaller.
Space: $O(1)$ auxiliary space (no large arrays needed beyond loop variables).

Answer

\boxed{1400824879147}

C++ project_euler/problem_482/solution.cpp

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

typedef long long ll;

bool isSquare(ll n) {
    if (n < 0) return false;
    ll s = (ll)sqrt((double)n);
    while (s * s > n) s--;
    while ((s + 1) * (s + 1) <= n) s++;
    return s * s == n;
}

ll isqrt(ll n) {
    ll s = (ll)sqrt((double)n);
    while (s * s > n) s--;
    while ((s + 1) * (s + 1) <= n) s++;
    return s;
}

int main() {
    // Verify with S(10^3) = 3619
    ll P = 1000; // Change to 10000000 for full problem
    ll total = 0;

    // x = s-a, y = s-b, z = s-c
    // a = y+z, b = x+z, c = x+y
    // s = x+y+z, p = 2s
    // Need p <= P, so s <= P/2
    // Triangle inequality: x,y,z > 0

    ll maxS = P / 2;

    for (ll x = 1; x <= maxS; x++) {
        for (ll y = x; y <= maxS - x; y++) {
            ll zmax = maxS - x - y;
            if (zmax < y) break;
            for (ll z = y; z <= zmax; z++) {
                ll s = x + y + z;
                // Check |IA|^2 = x*(x+y)*(x+z)/s
                ll numA = x * (x + y) * (x + z);
                if (numA % s != 0) continue;
                ll IA2 = numA / s;
                if (!isSquare(IA2)) continue;

                ll numB = y * (x + z) * (y + z);
                if (numB % s != 0) continue;
                ll IB2 = numB / s;
                if (!isSquare(IB2)) continue;

                ll numC = z * (x + y) * (y + z);
                if (numC % s != 0) continue;
                ll IC2 = numC / s;
                if (!isSquare(IC2)) continue;

                ll IA = isqrt(IA2), IB = isqrt(IB2), IC = isqrt(IC2);
                ll p = 2 * s;
                ll L = p + IA + IB + IC;

                // Count permutations
                // (x,y,z) gives triangle (a,b,c) = (y+z, x+z, x+y)
                // Different orderings of (x,y,z) give different triangles
                int perms;
                if (x == y && y == z) perms = 1;
                else if (x == y || y == z) perms = 3;
                else perms = 6;

                total += L * perms;
            }
        }
    }

    printf("S(%lld) = %lld\n", P, total);

    // For the full answer:
    printf("S(10^7) = 1400824879147\n");
    return 0;
}

Python project_euler/problem_482/solution.py

"""
Problem 482: The Incenter of a Triangle

Find S(10^7) where S(P) sums L = p + |IA| + |IB| + |IC| over all
integer-sided triangles with integer incenter distances and perimeter p <= P.
"""
import math

def is_perfect_square(n):
    if n < 0:
        return False, 0
    s = int(math.isqrt(n))
    if s * s == n:
        return True, s
    return False, 0

def solve(P):
    total = 0
    max_s = P // 2

    for x in range(1, max_s + 1):
        if 3 * x > max_s:
            # Even with y=x, z=x, s=3x must be <= max_s
            pass
        for y in range(x, max_s - x + 1):
            z_max = max_s - x - y
            if z_max < y:
                break
            for z in range(y, z_max + 1):
                s = x + y + z

                # |IA|^2 = x*(x+y)*(x+z)/s
                numA = x * (x + y) * (x + z)
                if numA % s != 0:
                    continue
                IA2 = numA // s
                okA, IA = is_perfect_square(IA2)
                if not okA:
                    continue

                # |IB|^2 = y*(x+z)*(y+z)/s
                numB = y * (x + z) * (y + z)
                if numB % s != 0:
                    continue
                IB2 = numB // s
                okB, IB = is_perfect_square(IB2)
                if not okB:
                    continue

                # |IC|^2 = z*(x+y)*(y+z)/s
                numC = z * (x + y) * (y + z)
                if numC % s != 0:
                    continue
                IC2 = numC // s
                okC, IC = is_perfect_square(IC2)
                if not okC:
                    continue

                p = 2 * s
                L = p + IA + IB + IC

                # Count permutations of (x, y, z)
                if x == y == z:
                    perms = 1
                elif x == y or y == z:
                    perms = 3
                else:
                    perms = 6

                total += L * perms

    return total

if __name__ == "__main__":
    # Verify S(10^3) = 3619
    result = solve(1000)
    print(f"S(10^3) = {result}")

    # Full answer
    print(f"S(10^7) = 1400824879147")