Detailed mathematical approach

Problem Summary

Let

$T_n=\left\{(a,b,c)\in \mathbb{Z}_{>0}^3:1\le a\le b\le c,\ c\le a+b-1,\ a+b\le n\right\}.$

For each integer triangle in \(T_n\), place the incircle first. Then, in every corner, continue packing circles that are tangent to the two sides of that angle and to the previous circle in the same corner. The quantity being averaged is the total area of the incircle together with the two largest additional circles that appear after this first placement.

If we write that triangle contribution as \(F(a,b,c)\), then the implementations compute

$S(n)=\frac{1}{|T_n|}\sum_{(a,b,c)\in T_n} F(a,b,c).$

The numerical checkpoints used by the implementations are

$S(2)=0.31998,\qquad S(5)=1.25899.$

Mathematical Approach

Fix one triangle with side lengths \(a\le b\le c\), and let \(A\le B\le C\) be the opposite angles. The geometry simplifies because the side ordering already tells us which corners can contain the largest packed circles.

Step 1: Describe the admissible triangles and angle order

The inequalities

$1\le a\le b\le c,\qquad c\le a+b-1,\qquad a+b\le n$

say that we average over all nondegenerate integer triangles in sorted side order. Since larger sides face larger angles, the ordering of the angles is

$A\le B\le C.$

This matters because a narrower corner produces a larger next tangent circle. So once the sides are sorted, the smallest angle \(A\) is the first place to look for the biggest circle after the incircle.

Step 2: Compute the incircle radius from the side lengths

Set

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

Then \(x=2(s-a)\), \(y=2(s-b)\), and \(z=2(s-c)\). If \(\Delta\) is the triangle area, Heron's formula gives

$\Delta^2=s(s-a)(s-b)(s-c).$

The inradius is \(r=\Delta/s\), so

$r^2=\frac{\Delta^2}{s^2}=\frac{(s-a)(s-b)(s-c)}{s}=\frac{xyz}{4p}.$

This is exactly the compact formula used by the implementations. It avoids computing the area explicitly before the final multiplication by \(\pi\).

Step 3: Derive the geometric ratio inside one corner

Consider one angle \(\theta\). Any circle tangent to both sides of that angle has its center on the angle bisector. If the radius is \(\rho\), then the center is at distance

$d=\frac{\rho}{\sin(\theta/2)}$

from the vertex.

Now take two consecutive circles in the same corner, with radii \(R\) and \(R'\), both tangent to the sides and tangent to each other. Their centers lie on the same bisector, and external tangency gives

$\frac{R-R'}{\sin(\theta/2)}=R+R'.$

Solving for the ratio yields

$\frac{R'}{R}=\frac{1-\sin(\theta/2)}{1+\sin(\theta/2)}=:q(\theta).$

So each corner generates a geometric chain of radii

$r,\ rq(\theta),\ rq(\theta)^2,\ rq(\theta)^3,\dots$

starting from the incircle. For the two angles that actually matter in the final comparison, the half-angle identities are

$\sin^2\left(\frac{A}{2}\right)=\frac{(s-b)(s-c)}{bc}=\frac{yz}{4bc},$

$\sin^2\left(\frac{B}{2}\right)=\frac{(s-a)(s-c)}{ac}=\frac{xz}{4ac}.$

Step 4: Identify the two largest extra circles

The function \(q(\theta)\) decreases as \(\theta\) increases on \((0,\pi)\). Because \(A\le B\le C\), we have

$q_A\ge q_B\ge q_C,$

where \(q_A=q(A)\), \(q_B=q(B)\), and \(q_C=q(C)\).

Therefore the largest circle after the incircle is always the first corner-circle in angle \(A\), with radius \(rq_A\).

For the third selected circle, only two candidates can survive:

$rq_B,\qquad rq_A^2.$

The first circle in angle \(C\) is no larger than the first circle in angle \(B\), and every later circle in any corner is no larger than the first unused circle in that same corner. So the third radius is

$r\max\{q_B,q_A^2\}.$

Squaring the radii to convert them into area factors, the two extra contributions are

$q_A^2,\qquad \max\{q_B^2,q_A^4\}.$

Step 5: Final contribution of one triangle

The incircle area is \(\pi r^2\). Adding the two largest extra circles gives

$F(a,b,c)=\pi r^2\left(1+q_A^2+\max\{q_B^2,q_A^4\}\right).$

This is the exact formula accumulated by the implementations for every admissible triangle.

Worked Example: The equilateral triangle \((1,1,1)\)

For \(a=b=c=1\), we have

$p=3,\qquad s=\frac{3}{2},\qquad x=y=z=1.$

Hence

$r^2=\frac{xyz}{4p}=\frac{1}{12}.$

All angles equal \(\pi/3\), so

$\sin\left(\frac{A}{2}\right)=\sin\left(\frac{\pi}{6}\right)=\frac{1}{2},\qquad q_A=q_B=\frac{1-\frac12}{1+\frac12}=\frac13.$

Therefore

$F(1,1,1)=\pi\cdot\frac{1}{12}\left(1+\frac{1}{9}+\max\left\{\frac{1}{9},\frac{1}{81}\right\}\right)=\pi\cdot\frac{1}{12}\left(1+\frac{1}{9}+\frac{1}{9}\right)=\frac{11\pi}{108}.$

Numerically,

$\frac{11\pi}{108}\approx 0.31998.$

Since \(T_2\) contains only this one triangle, we get \(S(2)=0.31998\), matching the checkpoint.

How the Code Works

The C++, Python, and Java implementations all evaluate the same formula. They enumerate the admissible triangles in sorted order by looping over \(a\), then \(b\), then every feasible \(c\) with

$b\le c\le a+b-1.$

For each triangle, the implementation computes \(p\), \(x\), \(y\), and \(z\), obtains \(r^2=xyz/(4p)\), then evaluates the half-angle terms needed for \(A\) and \(B\). From those values it builds \(q_A\) and \(q_B\), forms

$\pi r^2\left(1+q_A^2+\max\{q_B^2,q_A^4\}\right),$

adds that quantity to a running total, and increments the triangle counter.

The final answer is the total divided by the number of triangles. The Java implementation uses compensated accumulation to reduce floating-point loss, while the C++ computation uses extended precision. The Python implementation delegates to the same compiled numerical routine, so all three implementations share the same geometry and the same checkpoints.

Complexity Analysis

The number of admissible triangles is

$|T_n|=\sum_{a=1}^{\lfloor n/2\rfloor}\sum_{b=a}^{n-a} a,$

because for fixed \(a\) and \(b\), the value of \(c\) runs from \(b\) to \(a+b-1\), which gives exactly \(a\) possibilities. This count is \(\Theta(n^3)\), so the overall runtime is \(\Theta(n^3)\).

The work done for each triangle is constant-time arithmetic with a few square roots and one maximum comparison. Memory usage is \(O(1)\), since the implementations only maintain a running total, a counter, and a small number of temporary floating-point values.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=476
2. Incircle and excentral geometry: Wikipedia — Incircle and excircles of a triangle
3. Heron's formula: Wikipedia — Heron's formula
4. Half-angle identities: Wikipedia — Half-angle formulae