Detailed mathematical approach

Problem Summary

A unit circle contains three equal circles, each tangent to the other two and also tangent to the outer circle. The curved triangular gaps that remain are then filled recursively: in every gap bounded by three mutually tangent circles, insert the unique new circle tangent to all three boundary circles, and repeat this for a fixed number of generations. The problem asks for the fraction of the unit disk that is still uncovered after 10 iterations.

The geometry looks two-dimensional, but the implementations never need explicit coordinates. The entire computation can be driven by curvatures alone, which turns the packing into a clean recursive area sum.

Mathematical Approach

The key idea is to represent every circle by its signed curvature \(k=1/r\). Inner circles have positive curvature, while the enclosing unit circle is treated as a circle of curvature \(-1\). With that convention, every local configuration is governed by Descartes' circle theorem.

Signed Curvatures and the Starting Configuration

For four mutually tangent circles with curvatures \(k_1,k_2,k_3,k_4\), Descartes' theorem says

$2\left(k_1^2+k_2^2+k_3^2+k_4^2\right)=\left(k_1+k_2+k_3+k_4\right)^2.$

If we fix the outer circle as \(k_1=-1\) and the three equal inner circles as \(k_2=k_3=k_4=k\), then

$2(1+3k^2)=(-1+3k)^2,$

which simplifies to

$3k^2-6k-1=0,\qquad k=1+\frac{2}{\sqrt3}.$

This is the only positive solution, so each initial inner circle has radius

$r=\frac{1}{k}.$

Its area is therefore \(\pi/k^2\), and the three original circles already cover \(3\pi/k^2\) of the unit disk.

Filling a Single Gap

Suppose a gap is bounded by three mutually tangent circles with curvatures \(a,b,c\). Solving Descartes' theorem for the fourth curvature gives

$x=a+b+c\pm2\sqrt{ab+ac+bc}.$

The minus sign recovers the already existing fourth circle of the Descartes configuration, while the plus sign gives the new smaller circle that fits inside the open gap. So the inserted circle has curvature

$x=a+b+c+2\sqrt{ab+ac+bc}$

and area

$\frac{\pi}{x^2}.$

After that insertion, the original gap is split into exactly three smaller gaps bounded by the triples \((a,b,x)\), \((a,c,x)\), and \((b,c,x)\). This is why a depth-\(d\) computation has a ternary recursive structure.

The Four Initial Gaps

The starting picture has only two geometric gap types. There is one central gap enclosed by the three equal circles, and there are three congruent boundary gaps, each enclosed by the outer circle and two adjacent inner circles. If \(G_d(a,b,c)\) denotes the total area added inside a gap with boundary curvatures \(a,b,c\) over \(d\) generations, then

$G_0(a,b,c)=0,$

and for \(d\ge1\),

$G_d(a,b,c)=\frac{\pi}{x^2}+G_{d-1}(a,b,x)+G_{d-1}(a,c,x)+G_{d-1}(b,c,x),$

where

$x=a+b+c+2\sqrt{ab+ac+bc}.$

Therefore the total covered area after \(d\) iterations is

$C_d=\frac{3\pi}{k^2}+G_d(k,k,k)+3G_d(-1,k,k),$

and the required uncovered ratio is

$R_d=1-\frac{C_d}{\pi}.$

Worked Example: The First Generation

The first recursive step already shows every ingredient of the full solution. In the central gap we use \((k,k,k)\), so the new curvature is

$k_{\text{center}}=3k+2\sqrt{3k^2}=k(3+2\sqrt3)=7+4\sqrt3.$

In a boundary gap we use \((-1,k,k)\), so

$k_{\text{edge}}=-1+2k+2\sqrt{k^2-2k}=1+2\sqrt3.$

Thus depth 1 adds one central circle and three congruent edge circles, giving

$R_1=1-\left(\frac{3}{k^2}+\frac{1}{k_{\text{center}}^2}+\frac{3}{k_{\text{edge}}^2}\right)\approx0.198133880558.$

This matches the checkpoint used in the C++ implementation, so the recurrence is not just plausible geometry; it reproduces the numeric behavior exactly.

Why This Recursion Is Exact

Nothing is being approximated except the final floating-point evaluation. Every gap in the packing is determined completely by the three circles that bound it, and Descartes' theorem gives the unique circle that can be inserted next. Because each new circle partitions its parent gap into three disjoint child gaps, summing the recursively generated areas counts every inserted circle once and only once.

How the Code Works

The C++, Python, and Java implementations all follow the formula above literally. They first compute \(k=1+2/\sqrt3\), evaluate the area of the three original equal circles, and then make one recursive call for the central gap and one recursive call for a boundary gap, multiplying the latter by 3 because of symmetry.

Each recursive call receives the three boundary curvatures and the remaining depth. If the depth is zero, it contributes no new area. Otherwise it computes the Descartes curvature \(x\), adds the area \(\pi/x^2\), and recurses on the three child gaps. After the recursion returns, the implementation divides the total covered area by \(\pi\) and subtracts from 1 to obtain the uncovered fraction.

The three languages differ only in presentation details. The C++ version keeps the arithmetic in extended precision, optionally accepts a different depth from the command line, and checks the depth-0 and depth-1 values before printing the final result. The Python and Java versions use the same recurrence with standard floating-point arithmetic and print the depth-10 value directly.

Complexity Analysis

One starting gap produces a ternary recursion tree. The number of inserted circles inside a single gap up to depth \(d\) is

$1+3+3^2+\cdots+3^{d-1}=\frac{3^d-1}{2}.$

There are four starting gaps in total, so the full computation inserts

$4\cdot\frac{3^d-1}{2}=2(3^d-1)$

circles beyond the initial three. Hence the running time is \(\Theta(3^d)\), and the recursion stack uses \(\Theta(d)\) memory. For the actual input \(d=10\), this is only 118096 inserted circles, which is easily manageable.

Footnotes and References

1. Project Euler problem page: Problem 199 - Iterative Circle Packing
2. Descartes' theorem: Wikipedia - Descartes' theorem
3. Apollonian gasket: Wikipedia - Apollonian gasket
4. Soddy circles: MathWorld - Soddy Circles