Detailed mathematical approach

Problem Summary

We consider integer-sided triangles \(ABC\) whose perimeter \(p\) does not exceed a bound \(P\). Let \(I\) be the incenter, and define

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

The task is to sum \(L\) over exactly those triangles for which the three distances from the incenter to the vertices are integers. A brute-force scan over all side triples is far too expensive for the real limit, so the solution rewrites the triangle in coordinates that expose the arithmetic structure of the incenter directly.

Mathematical Approach

The key observation is that the incenter conditions become much simpler after switching from side lengths to semiperimeter coordinates.

Step 1: Replace the Sides by Semiperimeter Offsets

Let

$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$

Then \(x,y,z>0\), and the original sides can be recovered from

$a=y+z,\qquad b=x+z,\qquad c=x+y.$

Because \(s=x+y+z\), the perimeter is

$p=2s=2(x+y+z).$

Using Heron's formula \(\Delta^2=s(s-a)(s-b)(s-c)\) together with \(\Delta=rs\), we obtain

$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$

So every admissible triangle corresponds to positive integers \(x,y,z,r\) satisfying that identity.

Step 2: Encode the Integer Vertex Distances

The tangency point on side \(BC\) forms a right triangle with legs \(r\) and \(x\), so

$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$

Therefore each of \(x,y,z\) must participate in a Pythagorean relation with the same inradius \(r\). For a fixed \(r\), write

$t^2-x^2=r^2,$

or equivalently

$\left(t-x\right)\left(t+x\right)=r^2.$

If we set \(d=t-x\) and \(e=t+x\), then \(de=r^2\), \(d\le e\), and \(d\) and \(e\) must have the same parity. This gives

$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$

So enumerating divisors \(d\mid r^2\) generates all possible integer pairs \((x,t)\) with \(x^2+r^2=t^2\). The same list serves for \(y\) and \(z\) as well.

Step 3: Recover the Third Coordinate from Two Choices

Once two entries \(x\) and \(y\) are chosen from that list, the inradius formula determines \(z\). Starting from

$r^2=\frac{xyz}{x+y+z},$

we solve for \(z\):

$z=\frac{r^2(x+y)}{xy-r^2}.$

This immediately explains the filters used by the implementation: the denominator must be positive, so

$xy>r^2,$

and the numerator must be divisible by that denominator so that \(z\) is an integer. Finally, \(z\) must itself belong to the previously generated Pythagorean list; otherwise \(IC\) would not be integral.

Step 4: Avoid Duplicates and Enforce the Perimeter Bound

The variables \(x,y,z\) are symmetric, so we may impose

$x\le y\le z$

to count each triangle once. The perimeter condition becomes

$2(x+y+z)\le P,$

or equivalently

$z\le \frac{P}{2}-x-y.$

For each valid triple the contribution is

$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$

There is also a global bound on \(r\). Among triangles with fixed perimeter, the equilateral triangle maximizes the inradius, so

$r\le \frac{P\sqrt{3}}{18}.$

That turns the search into a finite loop over

$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$

Step 5: Worked Example

Take \(r=21\), so \(r^2=441\). Factor pairs of \(441\) with the same parity give several Pythagorean options. Two useful ones are

$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$

and

$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$

Now choose \(x=y=28\). Then

$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$

Because \(72\) is already in the same Pythagorean list, all three vertex distances are integral:

$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$

The corresponding sides are

$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$

so the perimeter is \(256\) and the contribution is

$L=256+35+35+75=401.$

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. First they compute the upper limit \(\left\lfloor P\sqrt{3}/18\right\rfloor\) for the inradius and build a smallest-prime-factor sieve up to that value. The sieve makes it cheap to factor each candidate \(r\).

For a fixed inradius, the implementation doubles the exponents in the factorization of \(r\) to enumerate every divisor of \(r^2\). Each divisor pair produces one candidate \((x,t)\) with \(x^2+r^2=t^2\), and these candidates are stored in sorted order by \(x\).

It then loops over ordered pairs \(x\le y\), computes the forced value of \(z\), and rejects the pair unless the divisibility condition, the positivity condition, and the perimeter bound all hold. A binary search checks whether that \(z\) already appears in the candidate list, which is equivalent to checking that \(z^2+r^2\) is a square. Every surviving triple contributes the perimeter plus the three already-determined vertex distances to the running total.

The larger implementations can split the inradius interval into chunks and sum those chunks independently. They also use small direct checks and the known checkpoint at \(P=1000\), namely \(3619\), before evaluating the full bound.

Complexity Analysis

Let

$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$

Building the smallest-prime-factor sieve costs \(O(R\log\log R)\) time and \(O(R)\) memory. For a fixed \(r\), suppose \(m(r)\) candidate values survive the divisor-to-leg conversion. Factoring \(r\) and generating divisors is essentially proportional to the number of divisors of \(r^2\), sorting costs \(O(m(r)\log m(r))\), and the pair search costs \(O(m(r)^2\log m(r))\) because each pair uses one binary search for \(z\).

Thus the total running time is

$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$

with \(O(R+m_{\max})\) memory. In practice \(m(r)\) is small, so this arithmetic reformulation is dramatically faster than scanning all integer side triples.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=482
2. Heron's formula: Wikipedia - Heron's formula
3. Incenter and incircle formulas: Wikipedia - Incircle and excircles of a triangle
4. Pythagorean triples and difference of squares: Wikipedia - Pythagorean triple