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.
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.
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.
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.
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.
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.
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\).
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.
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.
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.
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.
Gesucht ist die Fläche, die von einer unendlichen selbstähnlichen Spirale tangierender Kreise erzeugt wird. Die Geometrie wird in der komplexen Ebene beschrieben, indem man einen Skalierungsfaktor \(0<s<1\), einen Drehwinkel \(t\) und einen Abstandsfaktor \(d>0\) wählt und dann Kreis \(i\) mit Mittelpunkt \(z_i=dq^i\) und Radius \(r_i=s^i\) platziert, wobei \(q=se^{it}\) gilt. Die Aufgabe besteht darin, aus dem Tangentialmuster die richtigen Parameter zu bestimmen und anschließend die unendlich vielen krummlinigen Lücken zu summieren.
Die Lösung formt das Spiralproblem in ein kleines nichtlineares Gleichungssystem mit zwei reellen Variablen um. Nach dessen numerischer Lösung wird die Selbstähnlichkeit benutzt, um die unendliche Fläche auf eine geometrische Reihe zurückzuführen.
Man setzt
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
Weil \(|q|=s\) ist, werden beim Übergang von einem Kreis zum nächsten alle Längen mit \(s\) multipliziert und das Bild um den Winkel \(t\) gedreht. Daher ist die Packung selbstähnlich: Jeder tiefere Teil der Spirale ist eine verkleinerte Kopie des vorherigen.
Wenn die Kreise \(i\) und \(i+m\) tangential sind, dann ist der Mittelpunktabstand gleich der Summe ihrer Radien:
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
Einsetzen des Modells liefert
$$|d q^i(q^m-1)|=s^i+s^{i+m}.$$
Nach Division durch \(s^i\) verschwindet die Abhängigkeit von \(i\):
$$d|1-q^m|=1+s^m.$$
Das ist die zentrale Vereinfachung. Für ein festes Offset \(m\) gilt also überall in der Spirale dieselbe Tangentialregel.
Die gewünschte Konfiguration wird durch die tangentialen Abstände \(m=1,7,8\) festgelegt. Also gilt
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
Eliminiert man \(d\) mit der ersten Gleichung, bleiben zwei reelle Gleichungen in \(s\) und \(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.$$
Da \(q^m=s^m e^{imt}\) ist, kann man den Betrag explizit schreiben als
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$$
Damit ist die Geometrie auf ein nichtlineares System mit zwei Variablen reduziert, genau passend für das Newton-Verfahren.
Sobald \((s,t)\) bekannt ist, folgt der verbleibende Abstandsfaktor direkt aus dem Fall \(m=1\):
$$d=\frac{1+s}{|1-q|}.$$
Die numerische Lösung der Implementierungen lautet näherungsweise
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$$
Für diese Werte stimmen die Tangentialgleichungen für \(m=1,7,8\) bis auf numerische Rundungsfehler, was die gefundene Spirale bestätigt.
Für drei paarweise tangierende Kreise mit Radien \(r_1,r_2,r_3\) hat das Mittelpunktdreieck die Seitenlängen
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$$
Seine gewöhnliche Fläche erhält man mit der Heron-Formel:
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
Bezeichnet \(A_1,A_2,A_3\) die entsprechenden Winkel dieses Dreiecks, dann ist die Fläche des zwischen den Kreisen eingeschlossenen krummlinigen Dreiecks
$$\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).$$
Die Winkel liefert der Kosinussatz, zum Beispiel
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
und analog für \(A_2\) und \(A_3\).
Benötigt werden zwei Basisstücke:
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
Jede tiefere Schicht der Spirale ist zur vorherigen ähnlich, wobei alle Längen mit \(s\) multipliziert werden. Flächen skalieren daher mit \(s^2\), und die gesamte unendliche Summe wird zu
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$$
Genau diese geschlossene Form macht die Rechnung trotz unendlicher Packung kurz.
Mit dem konvergierten Wert von \(s\) sind die beiden Basisstücke näherungsweise
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$$
Der gemeinsame Flächenfaktor ist
$$s^2\approx 0.8214366235.$$
Daraus folgt
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
Das ist derselbe numerische Endwert, den die Implementierungen ausgeben.
Die Implementierungen in C++, Python und Java folgen alle derselben Struktur. Sie starten mit einer vernünftigen Anfangsschätzung für \(s\) und \(t\), werten die beiden Tangentialgleichungen aus und approximieren die \(2\times2\)-Jacobi-Matrix durch kleine finite Differenzen. Jeder Newton-Schritt löst dieses lineare System, aktualisiert \((s,t)\), bringt den Winkel wieder in das Intervall \([0,2\pi)\) und stoppt, sobald die Korrektur vernachlässigbar klein wird.
Nach der nichtlinearen Lösung rekonstruiert die Implementierung \(d\) aus der ersten Tangentialgleichung, berechnet die beiden Basisflächen über Heron-Formel plus Sektorabzug und gibt den geometrischen Reihenwert \((A+B)/(1-s^2)\) zurück. Die C++-Implementierung führt zusätzlich eine explizite geometrische Plausibilitätsprüfung aus: Die geforderten Offsets \(1,7,8\) sind tangential, während andere getestete nahe Paare sich nicht überlappen.
Das numerische Problem hat feste Größe: zwei Unbekannte, zwei Gleichungen, zwei Flächenberechnungen und eine beschränkte Menge geometrischer Prüfungen. Sind \(I\) die Anzahl der Newton-Iterationen und \(V\) die Anzahl der geprüften Kreispaaren, dann beträgt die Laufzeit \(O(I+V)\) und der Speicherverbrauch \(O(1)\). Für die konkrete Project-Euler-Aufgabe sind sowohl \(I\) als auch \(V\) kleine Konstanten, also ist das Verfahren effektiv konstant in Zeit und Speicher.
İstenen şey, teğet çemberlerden oluşan sonsuz öz-benzer bir spiralin ürettiği alanı hesaplamaktır. Geometri karmaşık düzlemde, \(0<s<1\) ölçek katsayısı, \(t\) dönme açısı ve \(d>0\) uzaklık katsayısı seçilerek modellenir; sonra \(q=se^{it}\) olmak üzere \(i\). çemberin merkezi \(z_i=dq^i\), yarıçapı ise \(r_i=s^i\) alınır. Görev, teğetlik deseninden doğru geometrik parametreleri bulmak ve ardından sonsuz sayıdaki eğrisel boşluğu toplamaktır.
Çözüm, spiral geometrisini iki gerçek değişkenli küçük bir doğrusal olmayan sisteme indirger. Bu sistem sayısal olarak çözüldükten sonra öz-benzerlik kullanılarak sonsuz alan bir geometrik seriye dönüştürülür.
Şöyle yazalım:
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
\(|q|=s\) olduğu için bir çemberden sonrakine geçerken bütün uzunluklar \(s\) ile çarpılır ve şekil \(t\) kadar döner. Böylece yerleşim öz-benzer olur: spiralin daha içteki her parçası önceki parçanın küçültülmüş bir kopyasıdır.
\(i\). çember ile \(i+m\). çember teğetse merkezler arası uzaklık yarıçaplar toplamına eşittir:
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
Parametrik modeli yerine koyunca
$$|d q^i(q^m-1)|=s^i+s^{i+m}$$
elde edilir. \(s^i\) ile böldüğümüzde \(i\)'ye bağlılık tamamen kaybolur:
$$d|1-q^m|=1+s^m.$$
Temel sadeleşme budur. Sabit bir \(m\) farkı için aynı teğetlik kuralı spiralin her yerinde geçerlidir.
Hedef düzen, teğet olan \(m=1,7,8\) farklarıyla belirlenir. Dolayısıyla
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
İlk denklem yardımıyla \(d\)'yi yok edersek \(s\) ve \(t\) için iki gerçek denklem kalır:
$$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.$$
\(q^m=s^m e^{imt}\) olduğundan mutlak değer açıkça
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}$$
şeklinde yazılır. Böylece geometri, Newton yöntemiyle çözülebilen iki değişkenli doğrusal olmayan bir sisteme dönüşür.
\((s,t)\) bulunduktan sonra kalan uzaklık katsayısı \(m=1\) durumundan doğrudan gelir:
$$d=\frac{1+s}{|1-q|}.$$
Uygulamaların ulaştığı sayısal çözüm yaklaşık olarak
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087$$
şeklindedir. Bu değerlerde \(m=1,7,8\) için teğetlik eşitlikleri sayısal hassasiyet içinde sağlanır; yani bulunan spiral hedef desene uyar.
Yarıçapları \(r_1,r_2,r_3\) olan ve ikişer ikişer teğet üç çember için merkez üçgeninin kenarları
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2$$
olur. Bu üçgenin normal alanı Heron formülüyle bulunur:
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
Merkez üçgeninin açıları \(A_1,A_2,A_3\) ise üç çember arasında kalan eğrisel üçgen alanı
$$\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)$$
olur. Açılar kosinüs teoreminden gelir; örneğin
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
ve benzeri şekilde \(A_2\) ile \(A_3\) elde edilir.
İki temel eğrisel bölge gerekir:
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
Spiralin her sonraki katmanı bir öncekinin benzeridir ve bütün uzunluklar \(s\) ile ölçeklenir. Bu yüzden alanlar \(s^2\) ile ölçeklenir ve sonsuz toplam
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}$$
haline gelir. Sonsuz yerleşimin kısa bir formülle hesaplanabilmesinin nedeni budur.
Yakınsayan \(s\) değeri kullanıldığında iki temel parça yaklaşık olarak
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733$$
çıkar. Ortak alan oranı
$$s^2\approx 0.8214366235$$
olduğundan
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
Bu da uygulamaların ürettiği son sayısal değerle aynıdır.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(s\) ve \(t\) için makul bir başlangıç tahmini alınır, iki teğetlik denklemi hesaplanır ve \(2\times2\) Jacobian matrisi küçük sonlu farklarla yaklaşık bulunur. Her Newton adımı bu doğrusal sistemi çözer, \((s,t)\) değerlerini günceller, açıyı tekrar \([0,2\pi)\) aralığına sarar ve düzeltme ihmal edilecek kadar küçülünce durur.
Doğrusal olmayan çözümden sonra uygulama, ilk teğetlik denkleminden \(d\)'yi geri kurar, Heron formülü ve dairesel sektör çıkarımıyla iki temel eğrisel alanı hesaplar ve \((A+B)/(1-s^2)\) değerini döndürür. C++ uygulaması ayrıca açık bir geometrik tutarlılık kontrolü yapar: gerekli \(1,7,8\) farkları teğettir ve test edilen diğer yakın çiftler üst üste binmez.
Sayısal problemin boyutu sabittir: iki bilinmeyen, iki denklem, iki temel alan hesabı ve sınırlı sayıda geometrik doğrulama vardır. \(I\) Newton iterasyon sayısı, \(V\) ise doğrulanan çember çifti sayısı olsun. Çalışma süresi \(O(I+V)\), bellek kullanımı \(O(1)\) olur. Bu Project Euler örneğinde hem \(I\) hem \(V\) küçük sabitler olduğundan yöntem pratikte sabit zamanlı ve sabit bellekli davranır.
Hay que calcular el area producida por una espiral infinita y autosimilar de circulos tangentes. La geometria se modela en el plano complejo eligiendo un factor de escala \(0<s<1\), un angulo de rotacion \(t\) y un factor de separacion \(d>0\); despues, el circulo \(i\) se coloca con centro \(z_i=dq^i\) y radio \(r_i=s^i\), donde \(q=se^{it}\). La tarea consiste en recuperar los parametros geometricos correctos a partir del patron de tangencia y luego sumar los infinitos huecos curvilineos.
La solucion transforma la geometria de la espiral en un pequeno sistema no lineal de dos variables reales. Una vez resuelto numericamente, la autosimilitud permite convertir el area infinita en una serie geometrica.
Escribimos
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
Como \(|q|=s\), al pasar de un circulo al siguiente todas las longitudes se multiplican por \(s\) y la figura gira un angulo \(t\). Por eso el empaquetamiento es autosimilar: cada parte mas profunda de la espiral es una copia reducida de la anterior.
Si los circulos \(i\) e \(i+m\) son tangentes, la distancia entre sus centros es igual a la suma de sus radios:
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
Al sustituir el modelo se obtiene
$$|d q^i(q^m-1)|=s^i+s^{i+m}.$$
Después de dividir por \(s^i\), desaparece la dependencia respecto de \(i\):
$$d|1-q^m|=1+s^m.$$
Esta es la simplificación clave. Para un desplazamiento fijo \(m\), la misma regla de tangencia vale en toda la espiral.
La configuracion deseada queda determinada por los desplazamientos tangentes \(m=1,7,8\). Por tanto,
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
Si eliminamos \(d\) con la primera ecuacion, quedan dos ecuaciones reales en \(s\) y \(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.$$
Como \(q^m=s^m e^{imt}\), el modulo puede escribirse de forma explicita:
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$$
Asi, la geometria queda reducida a un sistema no lineal de dos variables, justo el tipo de problema que resuelve el metodo de Newton.
Una vez conocido \((s,t)\), el factor de separacion restante sale directamente del caso \(m=1\):
$$d=\frac{1+s}{|1-q|}.$$
La solucion numerica alcanzada por las implementaciones es aproximadamente
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$$
Con esos valores, las identidades de tangencia para \(m=1,7,8\) se cumplen con precision numerica, lo que confirma que la espiral recuperada es la correcta.
Para tres circulos mutuamente tangentes con radios \(r_1,r_2,r_3\), el triangulo formado por sus centros tiene lados
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$$
Su area ordinaria viene dada por la formula de Heron:
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
Si \(A_1,A_2,A_3\) son los angulos correspondientes de ese triangulo de centros, entonces el area atrapada entre los tres circulos es
$$\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).$$
Los angulos salen de la ley de cosenos; por ejemplo,
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
y de forma analoga se obtienen \(A_2\) y \(A_3\).
Se necesitan dos piezas base:
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
Cada capa mas profunda de la espiral es semejante a la anterior, con todas las longitudes multiplicadas por \(s\). Por eso las areas se multiplican por \(s^2\), y la suma infinita se convierte en
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$$
Esta forma cerrada es la razon por la que el calculo sigue siendo corto aunque el empaquetamiento sea infinito.
Usando el valor convergido de \(s\), las dos piezas base valen aproximadamente
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$$
La razon comun de areas es
$$s^2\approx 0.8214366235.$$
Por lo tanto,
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
Ese es el mismo valor numerico final que entregan las implementaciones.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Empiezan con una estimacion razonable para \(s\) y \(t\), evalúan las dos ecuaciones de tangencia y aproximan la matriz Jacobiana \(2\times2\) mediante diferencias finitas pequenas. Cada paso de Newton resuelve ese sistema lineal, actualiza \((s,t)\), vuelve a colocar el angulo en \([0,2\pi)\) y se detiene cuando la correccion ya es despreciable.
Despues de resolver el sistema no lineal, la implementacion reconstruye \(d\) a partir de la primera ecuacion de tangencia, calcula las dos areas curvilineas base con la formula de Heron y la resta de sectores, y devuelve el valor de la serie geometrica \((A+B)/(1-s^2)\). La implementacion en C++ ademas realiza una comprobacion geometrica explicita: los desplazamientos requeridos \(1,7,8\) son tangentes y otros pares cercanos que se prueban no se solapan.
El problema numérico tiene tamaño fijo: dos incógnitas, dos ecuaciones, dos evaluaciones de área base y un conjunto acotado de comprobaciones geométricas. Si \(I\) es el número de iteraciones de Newton y \(V\) el número de pares de círculos validados, el tiempo de ejecución es \(O(I+V)\) y la memoria usada es \(O(1)\). Para esta instancia concreta de Project Euler, tanto \(I\) como \(V\) son constantes pequeñas, así que el método es esencialmente de tiempo constante y espacio constante.
这道题要求计算一个无限自相似圆螺旋所围成的总面积。几何模型放在复平面中：取缩放因子 \(0<s<1\)、旋转角 \(t\) 和距离因子 \(d>0\)，令 \(q=se^{it}\)，再把第 \(i\) 个圆放在中心 \(z_i=dq^i\) 处，半径取为 \(r_i=s^i\)。题目的关键并不是逐个处理无限多个圆，而是先从切触关系中恢复出正确的几何参数，再把无限多个曲边空隙的面积压缩成一个可求的闭式表达式。
实现的核心思路有两步。第一步，把圆的切触条件改写成仅含两个实变量的非线性方程组；第二步，利用整幅图形的自相似性，把无限面积写成一个等比级数。
定义
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
因为 \(|q|=s\)，所以从一个圆走到下一个圆时，所有长度都会乘上 \(s\)，同时整体旋转角度 \(t\)。这说明该圆列具有严格的自相似结构：越往内层走，图形只是前一层按比例缩小并旋转后的复制品。
如果第 \(i\) 个圆与第 \(i+m\) 个圆相切，那么两圆心之间的距离等于半径之和：
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
代入参数化表达式可得
$$|d q^i(q^m-1)|=s^i+s^{i+m}.$$
再把两边同除以 \(s^i\)，就得到与 \(i\) 无关的关系式：
$$d|1-q^m|=1+s^m.$$
这是整个推导里最重要的化简。它说明只要固定偏移量 \(m\)，那么螺旋上所有相距 \(m\) 的圆都会满足同一条切触方程，因此问题从“无限多个圆”变成了“有限个偏移条件”。
目标构型由三个切触偏移量 \(m=1,7,8\) 锁定，因此有
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
用第一式消去 \(d\) 后，只剩下关于 \(s\) 和 \(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.$$
又因为 \(q^m=s^m e^{imt}\)，所以模长可以写成显式实函数
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$$
这样一来，原本的几何问题就被改写成了标准的二维非线性求根问题，非常适合用 Newton 迭代来解。
一旦 \((s,t)\) 求出，剩下的距离因子 \(d\) 可以直接由 \(m=1\) 的切触关系得到：
$$d=\frac{1+s}{|1-q|}.$$
实现中收敛到的数值大约是
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$$
把这些值代回去，\(m=1,7,8\) 的三条切触等式都能在数值精度范围内成立，这说明求出的参数确实对应目标螺旋，而不是别的局部解。
对三个两两相切、半径分别为 \(r_1,r_2,r_3\) 的圆，它们圆心构成的三角形边长为
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$$
这个普通三角形的面积由 Heron 公式给出：
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
如果圆心三角形的三个角分别记为 \(A_1,A_2,A_3\)，那么三圆之间留下的曲边三角形面积就是
$$\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).$$
这里减去的是三个扇形面积。角度则由余弦定理给出，例如
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
其余两个角同理。这样就把“曲边区域”化成了“中心三角形面积减去扇形面积”的标准公式。
实现中首先计算两个基础空隙：
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
由于更深一层的局部图形与前一层相似，所有长度都会再乘以 \(s\)，因此面积会乘以 \(s^2\)。于是整张图中的面积和变成
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$$
这一步是整题真正的收束点：无限结构不需要逐层展开，只要算出两个基础面积，再套上等比级数求和公式即可。
用收敛后的参数代入，可以得到两个基础面积约为
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$$
面积缩放比为
$$s^2\approx 0.8214366235.$$
因此总面积就是
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
这个结果与实现最终输出的数值一致。
C++、Python 和 Java 三个实现采用的是同一条计算路线。它们先从 \(s\) 与 \(t\) 的一个合理初值开始，计算上述两个非线性切触方程，再用很小的有限差分近似 \(2\times2\) Jacobian 矩阵。每一步 Newton 迭代都要解这个线性系统，更新 \((s,t)\)，并把角度重新折回 \([0,2\pi)\) 区间；当修正量已经足够小的时候，迭代就停止。
在非线性求解完成后，实现会根据第一条切触方程恢复 \(d\)，再用 Heron 公式和扇形面积扣除法计算两个基础曲边三角形面积，最后返回 \((A+B)/(1-s^2)\)。其中 C++ 实现还额外做了一次几何一致性检查：偏移量 \(1,7,8\) 的圆对必须相切，而测试过的其他近邻圆对不能发生重叠。
这个数值问题的规模是固定的：只有两个未知量、两个方程、两次基础面积计算，以及一组有上界的几何验证。若用 \(I\) 表示 Newton 迭代次数，用 \(V\) 表示验证过的圆对数量，则时间复杂度为 \(O(I+V)\)，空间复杂度为 \(O(1)\)。在本题的实际设置中，\(I\) 和 \(V\) 都只是很小的常数，因此整个算法可以视为常数时间、常数空间。
Нужно вычислить площадь, порождаемую бесконечной самоподобной спиралью касающихся окружностей. Геометрия задается на комплексной плоскости с помощью коэффициента масштаба \(0<s<1\), угла поворота \(t\) и коэффициента расстояния \(d>0\): центр окружности с номером \(i\) равен \(z_i=dq^i\), а ее радиус равен \(r_i=s^i\), где \(q=se^{it}\). Задача состоит в том, чтобы восстановить правильные параметры по условиям касания, а затем просуммировать площади бесконечно многих криволинейных промежутков.
Решение сводит геометрию спирали к небольшой нелинейной системе с двумя вещественными переменными. После численного решения этой системы самоподобие позволяет записать бесконечную площадь как геометрическую прогрессию.
Запишем
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
Так как \(|q|=s\), переход от одной окружности к следующей умножает все длины на \(s\) и одновременно поворачивает картину на угол \(t\). Поэтому упаковка самоподобна: каждый более глубокий фрагмент спирали является уменьшенной копией предыдущего.
Если окружности \(i\) и \(i+m\) касаются, то расстояние между их центрами равно сумме радиусов:
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
Подстановка параметризации дает
$$|d q^i(q^m-1)|=s^i+s^{i+m}.$$
После деления на \(s^i\) зависимость от \(i\) исчезает:
$$d|1-q^m|=1+s^m.$$
Это и есть главное упрощение. Для каждого фиксированного сдвига \(m\) одна и та же формула касания действует во всей спирали.
Искомая конфигурация задается касаниями при \(m=1,7,8\). Значит, выполняются равенства
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
Если исключить \(d\) с помощью первого равенства, останутся два вещественных уравнения для \(s\) и \(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.$$
Поскольку \(q^m=s^m e^{imt}\), модуль можно записать явно:
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$$
Тем самым геометрическая задача превращается в стандартную двумерную задачу поиска корня, которую удобно решать методом Ньютона.
После нахождения \((s,t)\) оставшийся коэффициент расстояния сразу определяется из случая \(m=1\):
$$d=\frac{1+s}{|1-q|}.$$
Численное решение, к которому приходят реализации, приблизительно равно
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$$
При этих значениях равенства касания для \(m=1,7,8\) выполняются с численной точностью, что подтверждает правильность найденной спирали.
Для трех попарно касающихся окружностей радиусов \(r_1,r_2,r_3\) треугольник их центров имеет стороны
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$$
Его обычная площадь задается формулой Герона:
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
Если \(A_1,A_2,A_3\) обозначают углы этого центрального треугольника, то площадь криволинейного треугольника между окружностями равна
$$\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).$$
Углы находятся по теореме косинусов; например,
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
и аналогично для \(A_2\) и \(A_3\).
Нужны два базовых криволинейных фрагмента:
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
Каждый следующий слой спирали подобен предыдущему, причем все длины умножаются на \(s\). Поэтому площади умножаются на \(s^2\), и вся бесконечная сумма принимает вид
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$$
Именно эта замкнутая формула делает вычисление коротким, несмотря на бесконечную конфигурацию.
Для найденного значения \(s\) два базовых фрагмента имеют приближенные площади
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$$
Общий коэффициент масштабирования площади равен
$$s^2\approx 0.8214366235.$$
Следовательно,
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
Это совпадает с конечным численным результатом, который возвращают реализации.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала выбирается разумное начальное приближение для \(s\) и \(t\), затем вычисляются два уравнения касания, а матрица Якоби размера \(2\times2\) приближается малыми конечными разностями. Каждый шаг метода Ньютона решает эту линейную систему, обновляет \((s,t)\), возвращает угол в интервал \([0,2\pi)\) и прекращается, когда поправка становится пренебрежимо малой.
После решения нелинейной системы реализация восстанавливает \(d\) из первого уравнения касания, вычисляет две базовые криволинейные площади через формулу Герона и вычитание секторных площадей, а затем возвращает значение геометрической прогрессии \((A+B)/(1-s^2)\). В реализации на C++ дополнительно выполняется явная геометрическая проверка: нужные сдвиги \(1,7,8\) действительно дают касание, а другие проверяемые близкие пары не перекрываются.
Размер численной задачи фиксирован: две неизвестные, два уравнения, две базовые оценки площади и ограниченное число геометрических проверок. Если \(I\) обозначает число итераций Ньютона, а \(V\) число проверяемых пар окружностей, то время работы равно \(O(I+V)\), а память равна \(O(1)\). Для конкретной задачи Project Euler обе величины являются малыми константами, так что метод фактически имеет постоянные время и память.
المطلوب هو حساب المساحة الناتجة عن لولب لا نهائي ذاتي التشابه من دوائر متماسة. يوضع النموذج في المستوى العقدي باختيار معامل تصغير \(0<s<1\)، وزاوية دوران \(t\)، ومعامل مسافة \(d>0\)، ثم تكون الدائرة ذات الفهرس \(i\) ذات مركز \(z_i=dq^i\) ونصف قطر \(r_i=s^i\)، حيث \(q=se^{it}\). الفكرة ليست تتبع عدد لا نهائي من الدوائر واحدة واحدة، بل استخراج المعلمات الهندسية الصحيحة من شروط التماس ثم جمع مساحات الفجوات المنحنية كلها بصيغة مغلقة.
يحوّل الحل الهندسة إلى جهاز صغير من معادلتين لا خطيتين في متغيرين حقيقيين. وبعد حل هذا الجهاز عدديًا، تُستعمل خاصية التشابه الذاتي لكتابة المساحة اللانهائية على شكل متسلسلة هندسية.
نكتب
$$q=se^{it},\qquad z_i=dq^i,\qquad r_i=s^i.$$
بما أن \(|q|=s\)، فإن الانتقال من دائرة إلى التي تليها يضرب جميع الأطوال في \(s\) ويُدير الشكل بزاوية \(t\). لهذا يكون الترتيب ذاتي التشابه: كل جزء أعمق من اللولب هو نسخة مصغرة من الجزء السابق.
إذا كانت الدائرتان \(i\) و\(i+m\) متماستين، فإن المسافة بين مركزيهما تساوي مجموع نصفي القطر:
$$|z_{i+m}-z_i|=r_i+r_{i+m}.$$
وبالتعويض في النموذج نحصل على
$$|d q^i(q^m-1)|=s^i+s^{i+m}.$$
وبعد القسمة على \(s^i\) تختفي التبعية للفهرس \(i\):
$$d|1-q^m|=1+s^m.$$
هذا هو التبسيط الحاسم. فلكل فرق ثابت \(m\)، ينطبق قانون التماس نفسه في كل موضع من اللولب.
يتحدد الشكل المقصود من فروق التماس \(m=1,7,8\)، ولذلك نحصل على
$$d|1-q|=1+s,\qquad d|1-q^7|=1+s^7,\qquad d|1-q^8|=1+s^8.$$
بحذف \(d\) باستخدام المعادلة الأولى يبقى لدينا معادلتان حقيقيتان في \(s\) و\(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.$$
ولأن \(q^m=s^m e^{imt}\)، يمكن كتابة المقدار المطلق بصورة صريحة:
$$|1-q^m|=\sqrt{1+s^{2m}-2s^m\cos(mt)}.$$
وهكذا تتحول الهندسة إلى مسألة إيجاد جذر لنظام لا خطي ثنائي المتغيرات، وهو بالضبط النوع المناسب لطريقة نيوتن.
بعد إيجاد \((s,t)\)، نحصل على معامل المسافة الباقي مباشرة من حالة \(m=1\):
$$d=\frac{1+s}{|1-q|}.$$
والحل العددي الذي تصل إليه التطبيقات هو تقريبًا
$$s\approx 0.906331406148595,\qquad t\approx 0.826729539414059,\qquad d\approx 2.473989946674087.$$
وعند هذه القيم تتحقق معادلات التماس الخاصة بـ \(m=1,7,8\) ضمن دقة عددية عالية، وهذا يؤكد أن اللولب المستخرج هو الشكل المقصود.
إذا كانت لدينا ثلاث دوائر متماسة اثنتين اثنتين وأنصاف أقطارها \(r_1,r_2,r_3\)، فإن مثلث المراكز يملك الأضلاع
$$a=r_2+r_3,\qquad b=r_1+r_3,\qquad c=r_1+r_2.$$
ومساحة هذا المثلث العادي تعطى بصيغة هيرون:
$$\Delta=\sqrt{p(p-a)(p-b)(p-c)},\qquad p=\frac{a+b+c}{2}.$$
إذا رمزنا إلى زوايا مثلث المراكز بـ \(A_1,A_2,A_3\)، فإن مساحة المثلث المنحني المحصور بين الدوائر الثلاث هي
$$\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).$$
وتُحسب الزوايا من قانون جيب التمام، مثلًا
$$A_1=\arccos\left(\frac{b^2+c^2-a^2}{2bc}\right),$$
وبالصورة نفسها نحصل على \(A_2\) و\(A_3\).
يحتاج التنفيذ إلى قطعتين أساسيتين:
$$A=\mathcal{C}(1,s,s^8),\qquad B=\mathcal{C}(1,s^7,s^8).$$
كل طبقة أعمق من اللولب مشابهة للطبقة السابقة، مع ضرب جميع الأطوال في \(s\). لذلك تُضرب المساحات في \(s^2\)، وتصبح المساحة الكلية
$$A+B+s^2(A+B)+s^4(A+B)+\cdots=\frac{A+B}{1-s^2}.$$
وهذه الصيغة المغلقة هي التي تجعل الحساب قصيرًا رغم أن البنية نفسها لا نهائية.
باستخدام القيمة المتقاربة لـ \(s\)، نجد أن القطعتين الأساسيتين تقريبًا هما
$$A\approx 0.082310769808360,\qquad B\approx 0.055516558200733.$$
ونسبة تصغير المساحات هي
$$s^2\approx 0.8214366235.$$
ومن ثم
$$\frac{A+B}{1-s^2}\approx \frac{0.137827328009093}{0.1785633765}\approx 0.7718678168.$$
وهذا يطابق القيمة العددية النهائية التي تعيدها التطبيقات.
تتبع تطبيقات C++ وPython وJava البنية نفسها. تبدأ من تخمين عددي معقول للقيمتين \(s\) و\(t\)، ثم تقيم معادلتي التماس وتقرّب مصفوفة Jacobian ذات البعد \(2\times2\) باستعمال فروق منتهية صغيرة. في كل خطوة من خطوات نيوتن يُحل ذلك النظام الخطي، وتُحدَّث \((s,t)\)، وتُعاد الزاوية إلى المجال \([0,2\pi)\)، ثم تتوقف العملية عندما يصبح مقدار التصحيح ضئيلًا جدًا.
بعد حل النظام اللاخطي، تعيد الشفرة بناء \(d\) من معادلة التماس الأولى، وتحسب مساحتي القطعتين الأساسيتين باستخدام صيغة هيرون وطرح مساحات القطاعات الدائرية، ثم تُرجع القيمة \((A+B)/(1-s^2)\). أما تنفيذ C++ فيضيف فحصًا هندسيًا صريحًا أيضًا: الفروق المطلوبة \(1,7,8\) يجب أن تعطي تماسًا، في حين أن الأزواج القريبة الأخرى التي تُفحص لا يجوز أن تتداخل.
المسألة العددية ذات حجم ثابت: مجهولان، معادلتان، حسابان لمساحتين أساسيتين، وعدد محدود من الفحوص الهندسية. إذا رمزنا بعدد خطوات نيوتن بـ \(I\) وعدد أزواج الدوائر المفحوصة بـ \(V\)، فإن زمن التنفيذ هو \(O(I+V)\) واستهلاك الذاكرة هو \(O(1)\). وفي مسألة Project Euler هذه يكون كل من \(I\) و\(V\) ثابتين صغيرين، لذلك تكون الطريقة عمليًا ثابتة الزمن وثابتة الذاكرة.