Project Euler

Triangle of Circular Arcs

Three circles with radii r_a, r_b, r_c are mutually externally tangent, forming a "triangle of circular arcs" between their tangency points. Two special circles are defined: Circumcircle (passes th...

Source sync Apr 19, 2026

Problem #0727

Level Level 20

Solved By 626

Languages C++, Python

Answer 3.64039141

Length 406 words

geometrynumber_theorymodular_arithmetic

Let $r_a$, $r_b$ and $r_c$ be the radii of three circles that are mutually and externally tangent to each other. The three circles then form a triangle of circular arcs between their tangency points as shown for the three blue circles in the picture below.

Problem illustration

Define the circumcircle of this triangle to be the red circle, with centre $D$, passing through their tangency points. Further define the incircle of this triangle to be the green circle, with centre $E$, that is mutually and externally tangent to all the three blue circles. Let $d=\vert DE \vert$ be the distance between the centres of the circumcircle and the incircle.

Let $\mathbb{E}(d)$ be the expected value of $d$ when $r_a$, $r_b$ and $r_c$ are integers chosen uniformly such that $1\leq r_a < r_b < r_c \leq 100$ and $\text{gcd}(r_a,r_b,r_c)=1$.

Find $\mathbb{E}(d)$, rounded to eight places after the decimal point.

Problem 727: Triangle of Circular Arcs

Mathematical Analysis

Descartes Circle Theorem

For three mutually tangent circles with curvatures k_a = 1/r_a, k_b = 1/r_b, k_c = 1/r_c, the Descartes Circle Theorem gives the curvature of the Soddy circle (incircle):

k_s = k_a + k_b + k_c + 2sqrt(k_ak_b + k_bk_c + k_ck_a)

Tangency Points

The tangency point between circles with centers O_a, O_b and radii r_a, r_b is at: T_ab = (r_b * O_a + r_a * O_b) / (r_a + r_b)

Circumcircle

The circumradius R of the triangle formed by the three tangency points can be computed using the standard formula: R = (abc) / (4 * Area)

where a, b, c are the side lengths of the triangle of tangency points.

Distance |DE|

The distance between circumcenter D and incircle center E is computed from:

D: circumcenter of triangle T_ab, T_bc, T_ac
E: center of the inner Soddy circle

Place the three circles with centers at computed positions based on mutual tangency.

Coordinate Setup

Place circle a at origin, circle b at (r_a + r_b, 0). Circle c’s center is found from:

|O_a O_c| = r_a + r_c
|O_b O_c| = r_b + r_c

Enumeration

Count all valid triples (r_a, r_b, r_c) with 1 <= r_a < r_b < r_c <= 100 and gcd(r_a, r_b, r_c) = 1.

For each triple, compute d = |DE| and average.

Editorial

Compute E(d) where d = |DE|, D = circumcenter of tangency triangle, E = inner Soddy circle center. Triples (ra, rb, rc) with 1 <= ra < rb < rc <= 100, gcd = 1. We enumerate all valid triples (r_a, r_b, r_c). We then iterate over each, set up coordinates of three circle centers. Finally, compute tangency points.

Pseudocode

Enumerate all valid triples (r_a, r_b, r_c)
For each, set up coordinates of three circle centers
Compute tangency points
Compute circumcenter D of tangency triangle
Compute inner Soddy circle center E
Compute |DE|
Average over all valid triples

Complexity Analysis

Number of triples: O(100^3/6) ~ 161700, filtered by gcd condition
Each computation: O(1)
Total: O(100^3) ~ very fast

Answer

\boxed{3.64039141}

C++ project_euler/problem_727/solution.cpp

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

// Problem 727: Triangle of Circular Arcs
// Compute E(d) for triples (ra, rb, rc) with 1<=ra<rb<rc<=100, gcd=1

typedef long long ll;

int gcd3(int a, int b, int c) {
    return __gcd(a, __gcd(b, c));
}

struct Point {
    double x, y;
    Point(double x=0, double y=0): x(x), y(y) {}
    Point operator+(const Point& p) const { return {x+p.x, y+p.y}; }
    Point operator-(const Point& p) const { return {x-p.x, y-p.y}; }
    Point operator*(double t) const { return {x*t, y*t}; }
    double norm() const { return sqrt(x*x + y*y); }
};

// Circumcenter of triangle
Point circumcenter(Point A, Point B, Point C) {
    double ax = A.x, ay = A.y;
    double bx = B.x, by = B.y;
    double cx = C.x, cy = C.y;
    double D = 2 * (ax*(by-cy) + bx*(cy-ay) + cx*(ay-by));
    if (fabs(D) < 1e-15) return {0, 0};
    double ux = ((ax*ax+ay*ay)*(by-cy) + (bx*bx+by*by)*(cy-ay) + (cx*cx+cy*cy)*(ay-by)) / D;
    double uy = ((ax*ax+ay*ay)*(cx-bx) + (bx*bx+by*by)*(ax-cx) + (cx*cx+cy*cy)*(bx-ax)) / D;
    return {ux, uy};
}

// Compute the inner Soddy circle center using complex Descartes theorem
// Centers are at complex positions z_a, z_b, z_c with curvatures k_a, k_b, k_c
pair<double,double> soddy_center(double ka, double kb, double kc,
                                   double xa, double ya,
                                   double xb, double yb,
                                   double xc, double yc) {
    double ks = ka + kb + kc + 2*sqrt(ka*kb + kb*kc + kc*ka);

    // Complex Descartes: ks*zs = ka*za + kb*zb + kc*zc + 2*sqrt(ka*kb*za*zb + ...)
    // Using real and imaginary parts
    // We need: sqrt(ka*kb*za*zb + kb*kc*zb*zc + kc*ka*zc*za)
    // where za = xa + i*ya, etc.

    // Compute w = ka*kb*za*zb + kb*kc*zb*zc + kc*ka*zc*za
    double w_real = ka*kb*(xa*xb - ya*yb) + kb*kc*(xb*xc - yb*yc) + kc*ka*(xc*xa - yc*ya);
    double w_imag = ka*kb*(xa*yb + ya*xb) + kb*kc*(xb*yc + yb*xc) + kc*ka*(xc*ya + yc*xa);

    // sqrt(w) = sqrt(|w|) * (cos(arg/2) + i*sin(arg/2))
    double w_abs = sqrt(w_real*w_real + w_imag*w_imag);
    double w_arg = atan2(w_imag, w_real);
    double sq_abs = sqrt(w_abs);
    double sq_real = sq_abs * cos(w_arg/2);
    double sq_imag = sq_abs * sin(w_arg/2);

    double num_real = ka*xa + kb*xb + kc*xc + 2*sq_real;
    double num_imag = ka*ya + kb*yb + kc*yc + 2*sq_imag;

    return {num_real / ks, num_imag / ks};
}

int main() {
    double total_d = 0;
    int count = 0;

    for (int ra = 1; ra <= 100; ra++) {
        for (int rb = ra+1; rb <= 100; rb++) {
            for (int rc = rb+1; rc <= 100; rc++) {
                if (gcd3(ra, rb, rc) != 1) continue;
                count++;

                // Place circles
                double Oax = 0, Oay = 0;
                double Obx = ra + rb, Oby = 0;
                double d_ac = ra + rc;
                double d_bc = rb + rc;
                double d_ab = ra + rb;
                double Ocx = (d_ac*d_ac - d_bc*d_bc + d_ab*d_ab) / (2.0 * d_ab);
                double Ocy = sqrt(max(0.0, d_ac*d_ac - Ocx*Ocx));

                // Tangency points
                Point Tab = Point(Oax, Oay) * ((double)rb/(ra+rb)) + Point(Obx, Oby) * ((double)ra/(ra+rb));
                Point Tac = Point(Oax, Oay) * ((double)rc/(ra+rc)) + Point(Ocx, Ocy) * ((double)ra/(ra+rc));
                Point Tbc = Point(Obx, Oby) * ((double)rc/(rb+rc)) + Point(Ocx, Ocy) * ((double)rb/(rb+rc));

                // Circumcenter
                Point D = circumcenter(Tab, Tac, Tbc);

                // Inner Soddy circle center
                double ka = 1.0/ra, kb = 1.0/rb, kc = 1.0/rc;
                auto [Ex, Ey] = soddy_center(ka, kb, kc, Oax, Oay, Obx, Oby, Ocx, Ocy);

                double dist = sqrt((D.x-Ex)*(D.x-Ex) + (D.y-Ey)*(D.y-Ey));
                total_d += dist;
            }
        }
    }

    printf("Count of valid triples: %d\n", count);
    printf("E(d) = %.8f\n", total_d / count);

    return 0;
}

Python project_euler/problem_727/solution.py

"""
Project Euler Problem 727: Triangle of Circular Arcs

Compute E(d) where d = |DE|, D = circumcenter of tangency triangle,
E = inner Soddy circle center.
Triples (ra, rb, rc) with 1 <= ra < rb < rc <= 100, gcd = 1.
"""

import numpy as np
from math import gcd, sqrt, atan2, cos, sin

def gcd3(a, b, c):
    return gcd(a, gcd(b, c))

def circumcenter(A, B, C):
    """Circumcenter of triangle with vertices A, B, C (as 2D arrays)."""
    ax, ay = A
    bx, by = B
    cx, cy = C
    D = 2 * (ax*(by-cy) + bx*(cy-ay) + cx*(ay-by))
    if abs(D) < 1e-15:
        return np.array([0.0, 0.0])
    ux = ((ax**2+ay**2)*(by-cy) + (bx**2+by**2)*(cy-ay) + (cx**2+cy**2)*(ay-by)) / D
    uy = ((ax**2+ay**2)*(cx-bx) + (bx**2+by**2)*(ax-cx) + (cx**2+cy**2)*(bx-ax)) / D
    return np.array([ux, uy])

def soddy_center(ka, kb, kc, Oa, Ob, Oc):
    """Compute inner Soddy circle center using complex Descartes theorem."""
    ks = ka + kb + kc + 2*sqrt(ka*kb + kb*kc + kc*ka)

    # Complex positions
    za = complex(Oa[0], Oa[1])
    zb = complex(Ob[0], Ob[1])
    zc = complex(Oc[0], Oc[1])

    # w = ka*kb*za*zb + kb*kc*zb*zc + kc*ka*zc*za
    w = ka*kb*za*zb + kb*kc*zb*zc + kc*ka*zc*za

    # sqrt of complex number
    w_abs = abs(w)
    w_arg = atan2(w.imag, w.real)
    sq_w = sqrt(w_abs) * complex(cos(w_arg/2), sin(w_arg/2))

    zs = (ka*za + kb*zb + kc*zc + 2*sq_w) / ks
    return np.array([zs.real, zs.imag])

def compute():
    total_d = 0.0
    count = 0

    for ra in range(1, 101):
        for rb in range(ra+1, 101):
            for rc in range(rb+1, 101):
                if gcd3(ra, rb, rc) != 1:
                    continue
                count += 1

                # Circle centers
                Oa = np.array([0.0, 0.0])
                Ob = np.array([float(ra + rb), 0.0])

                d_ac = ra + rc
                d_ab = ra + rb
                d_bc = rb + rc
                Ocx = (d_ac**2 - d_bc**2 + d_ab**2) / (2.0 * d_ab)
                Ocy = sqrt(max(0, d_ac**2 - Ocx**2))
                Oc = np.array([Ocx, Ocy])

                # Tangency points
                Tab = (rb * Oa + ra * Ob) / (ra + rb)
                Tac = (rc * Oa + ra * Oc) / (ra + rc)
                Tbc = (rc * Ob + rb * Oc) / (rb + rc)

                # Circumcenter D
                D = circumcenter(Tab, Tac, Tbc)

                # Inner Soddy circle center E
                ka, kb, kc_val = 1.0/ra, 1.0/rb, 1.0/rc
                E = soddy_center(ka, kb, kc_val, Oa, Ob, Oc)

                dist = np.linalg.norm(D - E)
                total_d += dist

    expected = total_d / count
    print(f"Count of valid triples: {count}")
    print(f"E(d) = {expected:.8f}")
    return expected

result = compute()