Detailed mathematical approach

Problem Summary

Take three pairwise externally tangent circles with integer radii \(a\), \(b\), and \(c\), where

$1 \le a \lt b \lt c \le 100,\qquad \gcd(a,b,c)=1.$

Let \(D\) be the circumcenter of the triangle formed by the three tangency points of the original circles, and let \(E\) be the center of the inner Soddy circle tangent to all three of them. For each primitive triple define

$d(a,b,c)=\operatorname{dist}(D,E).$

The goal is to average \(d(a,b,c)\) over all primitive triples in the range. The implementation therefore needs an exact constant-time geometric formula for one triple and then a complete enumeration of all admissible triples.

Mathematical Approach

The geometry becomes straightforward once the three original circle centers are placed in coordinates. Every later quantity in the implementation is derived from that coordinate model.

Step 1: Place the three circle centers

Let \(O_a\), \(O_b\), and \(O_c\) be the centers of the circles of radii \(a\), \(b\), and \(c\). Because the circles are externally tangent, the distances between centers are

$|O_aO_b|=a+b,\qquad |O_aO_c|=a+c,\qquad |O_bO_c|=b+c.$

Choose coordinates

$O_a=(0,0),\qquad O_b=(a+b,0).$

The third center lies above the \(x\)-axis. By projecting onto the base segment and applying the law of cosines, its coordinates are

$x_c=\frac{(a+c)^2+(a+b)^2-(b+c)^2}{2(a+b)},$

$y_c=\sqrt{(a+c)^2-x_c^2},$

so

$O_c=(x_c,y_c).$

Step 2: Build the tangency triangle and locate \(D\)

The tangency point between the circles of radii \(a\) and \(b\) lies on segment \(O_aO_b\), at distance \(a\) from \(O_a\) and \(b\) from \(O_b\). Therefore

$T_{ab}=O_a+\frac{a}{a+b}(O_b-O_a)=(a,0).$

By the same ratio argument, the other two tangency points are

$T_{ac}=O_a+\frac{a}{a+c}(O_c-O_a)=\frac{a}{a+c}O_c,$

$T_{bc}=O_b+\frac{b}{b+c}(O_c-O_b).$

Point \(D\) is the circumcenter of triangle \(T_{ab}T_{ac}T_{bc}\). For any non-collinear points \(T_i=(x_i,y_i)\), the circumcenter is given by

$\Delta=2\bigl(x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)\bigr),$

$D_x=\frac{(x_1^2+y_1^2)(y_2-y_3)+(x_2^2+y_2^2)(y_3-y_1)+(x_3^2+y_3^2)(y_1-y_2)}{\Delta},$

$D_y=\frac{(x_1^2+y_1^2)(x_3-x_2)+(x_2^2+y_2^2)(x_1-x_3)+(x_3^2+y_3^2)(x_2-x_1)}{\Delta}.$

This is the exact formula used in the C++, Python, and Java implementations.

Step 3: Compute the inner Soddy circle radius

Let the curvatures of the three given circles be

$k_1=\frac1a,\qquad k_2=\frac1b,\qquad k_3=\frac1c.$

For the inner tangent circle, Descartes' circle theorem gives the positive fourth curvature

$k_4=k_1+k_2+k_3+2\sqrt{k_1k_2+k_2k_3+k_3k_1}.$

Hence the inner Soddy radius is

$r=\frac1{k_4}.$

If \(E=(x_E,y_E)\) denotes the center of that circle, tangency implies

$|EO_a|=a+r,\qquad |EO_b|=b+r,\qquad |EO_c|=c+r.$

Step 4: Solve directly for the center \(E\)

Square the three distance conditions. From \(O_a\) we get

$x_E^2+y_E^2=(a+r)^2.$

From \(O_b=(a+b,0)\) we get

$(x_E-(a+b))^2+y_E^2=(b+r)^2.$

Subtracting these equations cancels the quadratic terms and leaves a linear equation:

$2(a+b)x_E=(a+b)^2+(a+r)^2-(b+r)^2.$

So

$x_E=\frac{(a+b)^2+(a+r)^2-(b+r)^2}{2(a+b)}.$

Now use the equation for \(O_c=(x_c,y_c)\):

$(x_E-x_c)^2+(y_E-y_c)^2=(c+r)^2.$

Subtract the equation for \(O_a\) again to obtain

$2x_cx_E+2y_cy_E=x_c^2+y_c^2+(a+r)^2-(c+r)^2,$

hence

$y_E=\frac{x_c^2+y_c^2+(a+r)^2-(c+r)^2-2x_cx_E}{2y_c}.$

The center of the inner Soddy circle is therefore obtained from two linear equations after one square root for \(r\).

Step 5: Restrict to primitive triples and average

The outer search runs over all increasing triples

$1 \le a \lt b \lt c \le 100$

and keeps only those with

$\gcd(a,b,c)=1.$

This primitive condition removes scaled copies of the same similarity class. Indeed, if every radius is multiplied by a factor \(t\), then every center, every tangency point, the circumcenter \(D\), and the Soddy center \(E\) all scale by \(t\), so

$d(ta,tb,tc)=t\,d(a,b,c).$

After summing \(d(a,b,c)\) over all primitive triples, the final result is just the arithmetic mean of those values.

Worked Example: \((a,b,c)=(1,2,3)\)

This example is especially clean because the center triangle has side lengths \(3\), \(4\), and \(5\). Therefore

$O_a=(0,0),\qquad O_b=(3,0),\qquad O_c=(0,4).$

The three tangency points are

$T_{ab}=(1,0),\qquad T_{ac}=(0,1),\qquad T_{bc}=\left(\frac95,\frac85\right).$

The circumcenter of triangle \(T_{ab}T_{ac}T_{bc}\) is

$D=(1,1).$

The three curvatures are \(1\), \(1/2\), and \(1/3\), so

$k_1k_2+k_2k_3+k_3k_1=\frac12+\frac16+\frac13=1.$

Descartes then yields

$k_4=1+\frac12+\frac13+2=\frac{23}{6},\qquad r=\frac{6}{23}.$

Substituting into the linear formulas gives

$E=\left(\frac{21}{23},\frac{20}{23}\right).$

Finally,

$d(1,2,3)=|DE|=\sqrt{\left(1-\frac{21}{23}\right)^2+\left(1-\frac{20}{23}\right)^2}=\frac{\sqrt{13}}{23}\approx 0.1567630989,$

which matches the sample value checked by the implementation.

How the Code Works

The C++, Python, and Java implementations all follow the same algorithm. They enumerate every increasing triple in the allowed range, discard non-primitive triples with a gcd test, and then evaluate the geometry for each surviving triple. For one triple, the implementation constructs the center triangle, derives the three tangency points, and applies the circumcenter formula to obtain \(D\).

Next it applies Descartes' theorem to find the inner radius \(r\), rewrites the three tangency conditions as two linear equations, and solves them to obtain \(E\). The contribution of that triple is the Euclidean distance between \(D\) and \(E\). After all primitive triples have been processed, the accumulated sum is divided by the number of valid triples. One implementation also verifies several sample cases and checks that the loop count is \(135739\).

Complexity Analysis

The search space consists of all triples with \(1 \le a \lt b \lt c \le 100\), so the total enumeration cost is \(O(100^3)\). For each triple, the program performs only a fixed number of arithmetic operations, square roots, and gcd evaluations, which is constant work. The memory usage is \(O(1)\), since only a small set of coordinates and accumulators is kept at any time.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=727
2. Descartes' circle theorem: Wikipedia - Descartes' theorem
3. Circumcenter and circumcircle formulas: Wikipedia - Circumscribed circle
4. Tangent circles: Wikipedia - Tangent circles
5. Euclidean distance: Wikipedia - Euclidean distance