Detailed mathematical approach

Problem Summary

The problem asks for the area generated by an infinite self-similar spiral of tangent circles. The geometry is modeled in the complex plane by choosing a scale factor \(0<s<1\), a rotation angle \(t\), and a spacing factor \(d>0\), then placing circle \(i\) at center \(z_i=dq^i\) with radius \(r_i=s^i\), where \(q=se^{it}\). The job is to recover the correct geometric parameters from the tangency pattern and then sum the infinitely many curvilinear gaps.

Mathematical Approach

The implementation turns the spiral geometry into a small nonlinear system in two real variables. After solving that system numerically, it uses self-similarity to convert the infinite area into a geometric series.

Step 1: Parametrize the Spiral

Write

$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$

Because \(|q|=s\), moving from one circle to the next multiplies all lengths by \(s\) and rotates the picture by angle \(t\). This makes the packing self-similar: every deeper part of the spiral is a scaled copy of what came before.

Step 2: Translate Tangency into Equations

If circles \(i\) and \(i+m\) are tangent, then the distance between their centers equals the sum of their radii:

$|z_{i+m}-z_i|=r_i+r_{i+m}.$

Substituting the model gives

$|d q^i(q^m-1)|=s^i+s^{i+m}.$

After dividing by \(s^i\), the dependence on \(i\) disappears:

$d|1-q^m|=1+s^m.$

This is the crucial simplification. For any fixed offset \(m\), the same tangency rule applies everywhere in the spiral.

Step 3: Use the Three Required Offsets

The intended configuration is pinned down by the tangent offsets \(m=1,7,8\). Therefore

$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$

Eliminating \(d\) with the first equation leaves two real equations in \(s\) and \(t\):

$F_7(s,t)=(1+s)|1-q^7|-(1+s^7)|1-q|=0,$

$F_8(s,t)=(1+s)|1-q^8|-(1+s^8)|1-q|=0.$

Since \(q^m=s^m e^{imt}\), the magnitude can be written explicitly as

$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$

So the geometry has been reduced to a two-variable nonlinear system, which is exactly what Newton's method is designed to solve.

Step 4: Recover the Spiral Scale

Once \((s,t)\) is known, the remaining spacing factor follows immediately from the offset \(m=1\):

$d=\frac{1+s}{|1-q|}.$

The numerical solution reached by the implementations is approximately

$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$

At these values, the tangency identities for \(m=1,7,8\) hold to numerical precision, which confirms that the recovered spiral matches the intended pattern.

Step 5: Compute a Single Curvilinear Gap

For three mutually tangent circles with radii \(r_1,r_2,r_3\), the triangle formed by their centers has side lengths

$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$

Its ordinary area is given by Heron's formula:

$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$

If \(A_1,A_2,A_3\) are the corresponding angles of that center triangle, then the area trapped between the three circles is

$\mathcal{C}(r_1,r_2,r_3)=\Delta-\frac{1}{2}\left(r_1^2A_1+r_2^2A_2+r_3^2A_3\right).$

The angles come from the law of cosines, for example

$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$

and similarly for \(A_2\) and \(A_3\).

Step 6: Sum the Infinite Spiral by Self-Similarity

The implementations need two base curvilinear pieces:

$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$

Every deeper layer of the spiral is similar to the previous one, with all lengths multiplied by \(s\). Areas therefore scale by \(s^2\), so the entire infinite sum is

$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$

This closed form is the reason the computation stays short even though the packing itself is infinite.

Worked Example

Using the converged value of \(s\), the two base pieces are approximately

$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$

The common area ratio is

$s^2\approx 0.8214366235.$

Therefore

$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$

This matches the final numerical value returned by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same structure. They start from a reasonable guess for \(s\) and \(t\), evaluate the two tangency equations, and approximate the \(2\times2\) Jacobian with small finite differences. Each Newton step solves that linear system, updates \((s,t)\), wraps the angle back into \([0,2\pi)\), and stops when the correction becomes negligible.

After the nonlinear solve, the implementation reconstructs \(d\) from the first tangency equation, evaluates the two base curvilinear areas using Heron's formula and sector subtraction, and returns the geometric-series value \((A+B)/(1-s^2)\). The C++ implementation also performs an explicit geometric sanity check: the required offsets \(1,7,8\) are tangent, while other nearby tested pairs do not overlap.

Complexity Analysis

The numerical problem has fixed size: two unknowns, two equations, two base area evaluations, and a bounded set of geometric checks. If \(I\) is the number of Newton iterations and \(V\) is the number of validated circle pairs, then the running time is \(O(I+V)\) and the memory usage is \(O(1)\). For the actual Project Euler instance, both \(I\) and \(V\) are small constants, so the method is effectively constant-time and constant-space.

Footnotes and References

1. Problem page: Project Euler 894
2. Newton's method: Wikipedia — Newton's method
3. Circle packing: Wikipedia — Circle packing
4. Heron's formula: Wikipedia — Heron's formula
5. Law of cosines: Wikipedia — Law of cosines
6. Geometric series: Wikipedia — Geometric series