Start with an acute triangle whose angles are \((A,B,C)\). One telescoping step replaces it by the new triangle with angles
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
The sum is still \(\pi\), so the transformation preserves the angle-sum identity, but it is only valid as long as all three new angles remain positive and acute. The telescoping depth of a triangle is the number of consecutive valid triangles in this chain, including the original one. Problem 985 asks for the smallest perimeter of an integer-sided triangle whose telescoping depth is exactly \(20\).
The three implementations all revolve around the same fact: telescoping is easiest to study relative to the equilateral triangle.
Write the angles as
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
with
$$\alpha+\beta+\gamma=0.$$
After one telescoping step,
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
and similarly for the other two angles. Therefore the deviation triple evolves by the simple recurrence
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
So every step flips the sign of each deviation and doubles its magnitude.
An angle is acute exactly when it lies in \((0,\pi/2)\), which means a deviation \(d\) from \(\pi/3\) must satisfy
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
After \(j\) telescoping steps the deviation is \((-2)^j d\), so depth at least \(t\) is equivalent to
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
Intersecting those intervals gives a closed form. If \(t=2m\) is even, then
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
while for \(t=2m+1\) one gets
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
For the target \(t=20\), every initial deviation must lie in
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$$
This interval is extremely narrow, so any depth-20 triangle must be very close to equilateral.
Order the sides and opposite angles as \(a\le b\le c\) and \(A\le B\le C\). The law of sines gives
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
Inside the depth-20 window, the largest angle can be at most \(\pi/3+\pi/(3\cdot 2^{19})\), while the smallest can be as low as \(\pi/3-\pi/(3\cdot 2^{20})\). Since \(\sin x\) is increasing on \((0,\pi/2)\),
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
Numerically, \(r_{\max}-1\approx 1.72977337\times 10^{-6}\). That is why the search space collapses to near-equilateral triangles.
An equilateral integer triangle would stay equilateral forever, so it does not have finite depth \(20\). Among non-equilateral integer triangles with fixed smallest side \(a\), the smallest possible perimeter is achieved by choosing the remaining sides as small as the ordering allows:
$$b=a,\qquad c=a+1,$$
which gives perimeter \(3a+1\). Because near-equilateral triangles are the only candidates for depth \(20\), the global minimizer must be the first isosceles triangle \((a,a,a+1)\) that enters the admissible window.
For \((a,a,a+1)\), let \(C\) be the angle opposite the side \(a+1\). The law of cosines yields
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
Set
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
Because the other two angles are equal to \((\pi-C)/2\), the full depth-20 condition for this isosceles family reduces to the single inequality
$$C<\frac{\pi}{3}+K.$$
Since \(\cos x\) decreases on \((0,\pi)\), this is equivalent to
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
If we define
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$$
then the inequality becomes
$$2Va^2-2a-1>0,$$
so the first valid integer is
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
This gives \(a=578111\), hence the minimal perimeter is
$$3a+1=1734334.$$
For this triangle, the excess angle \(C-\pi/3\) is about \(1.99736879\times 10^{-6}\), which is below the depth-20 ceiling \(K\approx 1.99737082\times 10^{-6}\) but above the much smaller depth-21 ceiling \(\pi/(3\cdot 2^{21})\). Therefore the depth is exactly \(20\), not \(21\) or more.
The same mechanism is already visible at very small depth. For \((3,3,4)\), the largest angle satisfies
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
so \(C\approx 83.62^\circ\), and the other two angles are about \(48.19^\circ\). After one telescoping step the new angles are approximately
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$$
which are still acute. After the next step they become approximately
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$$
so the chain stops. That is why \((3,3,4)\) has exact depth \(2\), matching the general recurrence.
The C++ implementation keeps the problem in its full form. It computes triangle angles from side lengths with the law of cosines, simulates the telescoping map directly, and counts how many acute triangles appear before the process fails. Separately, it derives the admissible deviation interval for the requested target depth, converts it into the side-ratio cap \(r_{\max}\), and uses that cap to restrict the enumeration to a very thin strip near the line \(a=b=c\).
The search loops through ordered integer triples \(a\le b\le c\), enforces the triangle inequality, and breaks early whenever the current perimeter can no longer beat the best perimeter already found. That version is useful because it verifies the mathematics without assuming the final closed form in advance.
The Python and Java implementations go one step further. They use the proof that the minimizer must be \((a,a,a+1)\), substitute that family into the law of cosines, and solve a single quadratic inequality for \(a\). Because \(K=\pi/(3\cdot 2^{19})\) is tiny, they evaluate \(\sin K\) and \(\cos K\) with short Taylor expansions, reconstruct \(\cos(\pi/3+K)\) from angle-addition formulas, and then compute the first integer \(a\) above the threshold. The printed answer is simply \(3a+1\).
For the general search, checking one candidate triangle costs \(O(t)\) time because the telescoping chain is followed for at most a small capped number of steps. The candidate region itself is controlled by \(r_{\max}\): for a given \(a\), only \(O(a(r_{\max}-1)+1)\) values of \(c\) are possible, and the admissible range for \(b\) has the same order of magnitude. Since \(r_{\max}-1\) is tiny for \(t=20\), the practical search is far smaller than a naive cubic sweep over all triangles of comparable perimeter.
The Python and Java implementations eliminate enumeration entirely. At the fixed Project Euler target they perform a constant amount of high-precision arithmetic, so both time and memory usage are effectively \(O(1)\).
Man beginnt mit einem spitzwinkligen Dreieck mit Winkeln \((A,B,C)\). Ein Teleskopierungsschritt ersetzt es durch das neue Dreieck mit Winkeln
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
Die Winkelsumme bleibt also gleich \(\pi\), doch der Schritt ist nur zulässig, solange alle drei neuen Winkel positiv und spitz bleiben. Die Teleskopierungstiefe eines Dreiecks ist die Anzahl aufeinanderfolgender gültiger Dreiecke in dieser Kette, einschließlich des Ausgangsdreiecks. Gesucht ist der kleinste Umfang eines ganzzahligen Dreiecks mit Teleskopierungstiefe genau \(20\).
Alle drei Implementierungen stützen sich auf dieselbe zentrale Beobachtung: Relativ zum gleichseitigen Dreieck wird die Dynamik fast trivial.
Schreibe die Winkel als
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
mit
$$\alpha+\beta+\gamma=0.$$
Nach einem Teleskopierungsschritt gilt
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
und analog für die beiden anderen Winkel. Damit folgt für die Abweichungen die Rekursion
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
Jeder Schritt kehrt also das Vorzeichen um und verdoppelt den Betrag jeder Abweichung.
Ein Winkel ist genau dann spitz, wenn er in \((0,\pi/2)\) liegt. Für eine Abweichung \(d\) von \(\pi/3\) bedeutet das
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
Nach \(j\) Schritten ist die Abweichung \((-2)^j d\), also ist Tiefe mindestens \(t\) äquivalent zu
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
Die Schnittmenge dieser Intervalle lässt sich explizit schreiben. Für gerades \(t=2m\) gilt
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
und für ungerades \(t=2m+1\)
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
Für das Ziel \(t=20\) muss daher jede Anfangsabweichung in
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right)$$
liegen. Das ist ein extrem schmales Fenster, also muss ein Tiefe-20-Dreieck nahezu gleichseitig sein.
Ordne Seiten und Gegenwinkel als \(a\le b\le c\) sowie \(A\le B\le C\). Mit dem Sinussatz folgt
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
Im Tiefe-20-Fenster gilt \(C\le \pi/3+\pi/(3\cdot 2^{19})\) und \(A\ge \pi/3-\pi/(3\cdot 2^{20})\). Da \(\sin x\) auf \((0,\pi/2)\) streng wächst, erhält man
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
Numerisch ist \(r_{\max}-1\approx 1{,}72977337\times 10^{-6}\). Genau diese winzige Reserve macht die Suche fast eindimensional.
Ein gleichseitiges ganzzahliges Dreieck bliebe für immer gleichseitig und hätte daher keine endliche Tiefe \(20\). Unter allen nicht gleichseitigen ganzzahligen Dreiecken mit festem kleinsten Schenkel \(a\) erhält man den kleinsten Umfang, indem man die beiden übrigen Seiten so klein wie möglich wählt:
$$b=a,\qquad c=a+1,$$
also Umfang \(3a+1\). Da nur nahezu gleichseitige Dreiecke als Kandidaten übrig bleiben, muss der globale Minimierer das erste gleichschenklige Dreieck \((a,a,a+1)\) sein, das in das zulässige Fenster hineinrutscht.
Für \((a,a,a+1)\) sei \(C\) der Winkel gegenüber der Seite \(a+1\). Mit dem Kosinussatz erhält man
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
Setze
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
Da die beiden anderen Winkel gleich \((\pi-C)/2\) sind, reduziert sich die gesamte Tiefe-20-Bedingung in dieser Familie auf
$$C<\frac{\pi}{3}+K.$$
Wegen der Monotonie von \(\cos\) auf \((0,\pi)\) ist das äquivalent zu
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
Mit
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right)$$
wird daraus
$$2Va^2-2a-1>0,$$
und somit ist das erste zulässige ganze \(a\)
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
Das liefert \(a=578111\) und daher den Minimalumfang
$$3a+1=1734334.$$
Für dieses Dreieck ist die Winkelabweichung \(C-\pi/3\approx 1{,}99736879\times 10^{-6}\). Sie liegt unter der Tiefe-20-Grenze \(K\approx 1{,}99737082\times 10^{-6}\), aber deutlich über der strengeren Tiefe-21-Grenze \(\pi/(3\cdot 2^{21})\). Damit ist die Tiefe genau \(20\).
Schon bei kleiner Tiefe sieht man denselben Mechanismus. Für \((3,3,4)\) gilt
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
also \(C\approx 83{,}62^\circ\), während die beiden anderen Winkel etwa \(48{,}19^\circ\) betragen. Nach einem Teleskopierungsschritt erhält man ungefähr
$$83{,}62^\circ,\ 83{,}62^\circ,\ 12{,}76^\circ,$$
also noch ein spitzes Dreieck. Nach dem nächsten Schritt werden die Winkel zu ungefähr
$$12{,}76^\circ,\ 12{,}76^\circ,\ 154{,}48^\circ,$$
und der Prozess endet. Deshalb hat \((3,3,4)\) genau Tiefe \(2\).
Die C++-Implementierung behandelt das Problem in voller Allgemeinheit. Sie berechnet aus den Seitenlängen per Kosinussatz die Winkel, simuliert die Teleskopierung direkt und zählt, wie viele spitzwinklige Dreiecke entstehen, bevor der Prozess stoppt. Zusätzlich bestimmt sie aus der Zieltiefe das zulässige Abweichungsintervall, übersetzt es in die Verhältnis-Schranke \(r_{\max}\) und beschränkt damit die Aufzählung auf einen extrem dünnen Streifen nahe \(a=b=c\).
Die Suche läuft über geordnete ganzzahlige Tripel \(a\le b\le c\), prüft die Dreiecksungleichung und bricht früh ab, sobald der aktuelle Umfang den besten bereits gefundenen Umfang nicht mehr schlagen kann. Diese Version dient als direkte Verifikation der Herleitung.
Die Python- und Java-Implementierungen gehen noch weiter. Sie verwenden den Beweis, dass der Minimierer die Form \((a,a,a+1)\) haben muss, setzen diese Familie in den Kosinussatz ein und lösen nur noch eine quadratische Ungleichung für \(a\). Weil \(K=\pi/(3\cdot 2^{19})\) winzig ist, werden \(\sin K\) und \(\cos K\) mit kurzen Taylor-Entwicklungen ausgewertet, anschließend \(\cos(\pi/3+K)\) über Additionsformeln rekonstruiert und daraus die erste zulässige ganze Zahl \(a\) bestimmt. Ausgegeben wird dann direkt \(3a+1\).
In der allgemeinen Suche kostet die Prüfung eines Kandidaten \(O(t)\) Zeit, weil die Teleskopierung nur bis zu einer kleinen Obergrenze verfolgt wird. Der Kandidatenraum wird durch \(r_{\max}\) kontrolliert: Für ein festes \(a\) gibt es nur \(O(a(r_{\max}-1)+1)\) mögliche Werte für \(c\), und der zulässige Bereich für \(b\) hat dieselbe Größenordnung. Da \(r_{\max}-1\) bei \(t=20\) extrem klein ist, ist die praktische Suche weit schmaler als ein naiver kubischer Dreiecks-Scan.
Die Python- und Java-Lösungen vermeiden die Enumeration vollständig. Beim festen Project-Euler-Ziel besteht die Arbeit nur aus einer konstanten Menge hochpräziser Arithmetik, also praktisch \(O(1)\) Zeit und \(O(1)\) Speicher.
Başlangıçta açıları \((A,B,C)\) olan bir dar açılı üçgen alınıyor. Bir teleskoplama adımı, bu üçgeni şu açılara sahip yeni üçgene dönüştürüyor:
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
Açıların toplamı yine \(\pi\) kalır; yani dönüşüm üçgen olma koşulunu açı toplamı açısından korur. Ancak adım, yalnızca yeni üç açının da pozitif ve dar olması durumunda geçerlidir. Bir üçgenin teleskoplama derinliği, bu zincirde arka arkaya üretilebilen geçerli üçgen sayısıdır; başlangıç üçgeni de bu sayıya dahildir. Problem 985, teleskoplama derinliği tam olarak \(20\) olan tam sayı kenarlı bir üçgenin en küçük çevresini sorar.
Üç çözümün ortak kalbi şudur: teleskoplama, eşkenar üçgenden sapmalar cinsinden yazılınca çok sade bir doğrusal yinelemeye dönüşür.
Açıları
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
şeklinde yazalım. O zaman
$$\alpha+\beta+\gamma=0$$
olur. Bir teleskoplama adımından sonra
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha$$
elde edilir ve aynı şey diğer iki açı için de geçerlidir. Dolayısıyla sapma üçlüsü şu yinelemeyi izler:
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
Yani her adım işareti ters çevirir ve mutlak değeri iki katına çıkarır.
Bir açının dar olması, \((0,\pi/2)\) aralığında olması demektir. Bu da \(\pi/3\)'ten sapma \(d\) için
$$-\frac{\pi}{3}<d<\frac{\pi}{6}$$
şartını verir. \(j\) adım sonra sapma \((-2)^j d\) olur; dolayısıyla derinliğin en az \(t\) olması
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t$$
ile eşdeğerdir. Bu aralıkların kesişimi kapalı biçimde yazılabilir. Eğer \(t=2m\) çift ise
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
eğer \(t=2m+1\) tek ise
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
Hedef \(t=20\) için her başlangıç sapması mutlaka
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right)$$
içinde olmalıdır. Bu pencere çok dar olduğu için derinliği 20 olan her üçgen neredeyse eşkenardır.
Kenarları ve karşı açıları \(a\le b\le c\) ve \(A\le B\le C\) olacak şekilde sıralayalım. Sinüs teoremi
$$\frac{c}{a}=\frac{\sin C}{\sin A}$$
der. Derinlik-20 penceresi içinde en büyük açı en fazla \(\pi/3+\pi/(3\cdot 2^{19})\), en küçük açı ise en az \(\pi/3-\pi/(3\cdot 2^{20})\) olabilir. \(\sin x\) fonksiyonu \((0,\pi/2)\) üzerinde artan olduğundan
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}$$
elde edilir. Sayısal olarak \(r_{\max}-1\approx 1.72977337\times 10^{-6}\) çıkar. Aramanın neredeyse tek boyutlu hale gelmesinin nedeni budur.
Eşkenar tam sayı üçgeni sonsuza kadar eşkenar kalır; bu yüzden sonlu bir derinlik olan \(20\)'yi vermez. Sabit bir en küçük kenar \(a\) için, eşkenar olmayan tam sayı üçgenler arasında en küçük çevre ancak diğer iki kenar mümkün olan en küçük değerleri alınca oluşur:
$$b=a,\qquad c=a+1.$$
Böylece çevre \(3a+1\) olur. Derinlik 20 için zaten sadece eşkenara çok yakın üçgenler aday kaldığından, küresel minimum bu ailede, yani \((a,a,a+1)\) içinde aranmalıdır.
\((a,a,a+1)\) için \(a+1\) kenarının karşısındaki açıya \(C\) diyelim. Kosinüs teoremi
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}$$
sonucunu verir. Şimdi
$$K=\frac{\pi}{3\cdot 2^{19}}$$
tanımını yapalım. Diğer iki açı \((\pi-C)/2\) olduğundan, bu aile için derinlik-20 koşulu tek bir eşitsizliğe indirgenir:
$$C<\frac{\pi}{3}+K.$$
\(\cos\) fonksiyonu \((0,\pi)\) üzerinde azalan olduğundan bu,
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right)$$
ile eşdeğerdir. Eğer
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right)$$
dersek, eşitsizlik
$$2Va^2-2a-1>0$$
haline gelir. Dolayısıyla ilk geçerli tam sayı
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1$$
olur. Buradan \(a=578111\) ve en küçük çevre
$$3a+1=1734334$$
çıkar. Bu üçgende \(C-\pi/3\approx 1.99736879\times 10^{-6}\) olup derinlik-20 tavanı \(K\approx 1.99737082\times 10^{-6}\)'den küçüktür; ama derinlik-21 için gereken çok daha sıkı sınır \(\pi/(3\cdot 2^{21})\)'den büyüktür. Bu yüzden derinlik tam olarak \(20\)'dir.
Aynı mekanizma küçük derinlikte de açıkça görülür. \((3,3,4)\) için
$$\cos C=\frac{9+9-16}{18}=\frac19$$
olduğundan \(C\approx 83.62^\circ\), diğer iki açı ise yaklaşık \(48.19^\circ\)'dir. Bir teleskoplama adımından sonra yeni açı üçlüsü yaklaşık
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ$$
olur ve hâlâ dar açılıdır. Bir adım daha sonra yaklaşık
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ$$
elde edilir; artık üçgen dar açılı değildir. Dolayısıyla \((3,3,4)\) üçgeninin derinliği tam \(2\)'dir.
C++ uygulaması problemi genel biçimiyle ele alır. Önce kenarlardan kosinüs teoremiyle açıları çıkarır, sonra teleskoplama dönüşümünü doğrudan simüle ederek zincirin kaç adım geçerli kaldığını sayar. Buna paralel olarak hedef derinlik için geçerli sapma aralığını hesaplar, bunu \(r_{\max}\) oran sınırına çevirir ve aday üçgenleri \(a=b=c\) doğrusu çevresindeki çok ince bir bölgeyle sınırlar.
Arama kısmı sıralı tam sayı üçlüleri \(a\le b\le c\) üzerinden gider, üçgen eşitsizliğini uygular ve mevcut çevre artık en iyi bulunan sonucu geçemeyecekse erken durur. Böylece çözüm, kapalı form kullanılmadan da doğrulanmış olur.
Python ve Java uygulamaları bir adım daha ileri gider. Minimum üçgenin \((a,a,a+1)\) ailesinde olması gerektiğini kullandıktan sonra, kosinüs teoreminden yalnızca tek bir kuadratik eşitsizlik kalır. \(K=\pi/(3\cdot 2^{19})\) çok küçük olduğu için \(\sin K\) ve \(\cos K\) kısa Taylor açılımlarıyla hesaplanır; ardından açı toplama formülüyle \(\cos(\pi/3+K)\) elde edilir ve eşik değeri geçen ilk tam sayı \(a\) bulunur. Son çıktı doğrudan \(3a+1\)'dir.
Genel aramada tek bir adayın kontrolü \(O(t)\) zaman alır; çünkü teleskoplama zinciri en fazla küçük bir üst sınıra kadar izlenir. Aday uzayı ise \(r_{\max}\) tarafından belirlenir: sabit bir \(a\) için yalnızca \(O(a(r_{\max}-1)+1)\) kadar \(c\) değeri mümkündür ve \(b\) aralığı da aynı büyüklüktedir. \(t=20\) için \(r_{\max}-1\) son derece küçük olduğundan, pratik arama kaba bir kübik taramadan çok daha dardır.
Python ve Java çözümleri ise aramayı tamamen ortadan kaldırır. Sabit hedef için yalnızca sınırlı sayıda yüksek hassasiyetli aritmetik işlem yaptıklarından zaman ve bellek maliyeti pratikte \(O(1)\)'dir.
Se comienza con un triángulo acutángulo cuyos ángulos son \((A,B,C)\). Un paso de telescopado lo reemplaza por el nuevo triángulo con ángulos
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
La suma sigue siendo \(\pi\), así que la identidad angular de un triángulo se conserva, pero el paso solo es válido mientras los tres ángulos nuevos sigan siendo positivos y agudos. La profundidad telescópica es el número de triángulos válidos consecutivos en esa cadena, contando también el triángulo inicial. El problema pide el menor perímetro de un triángulo de lados enteros cuya profundidad sea exactamente \(20\).
Las tres implementaciones usan la misma idea estructural: medir todo con respecto al triángulo equilátero.
Escribimos
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
con
$$\alpha+\beta+\gamma=0.$$
Después de un paso telescópico,
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
y lo mismo ocurre con los otros ángulos. Por tanto, la recurrencia sobre las desviaciones es
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
Cada paso cambia el signo y duplica el tamaño de la desviación.
Un ángulo es agudo exactamente cuando pertenece a \((0,\pi/2)\). Para una desviación \(d\) respecto de \(\pi/3\), eso equivale a
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
Tras \(j\) pasos, la desviación vale \((-2)^j d\), así que tener profundidad al menos \(t\) es equivalente a exigir
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
La intersección de esos intervalos se puede escribir de forma cerrada. Si \(t=2m\) es par, entonces
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
mientras que para \(t=2m+1\) se obtiene
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
En particular, para \(t=20\) toda desviación inicial debe pertenecer a
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$$
Es una ventana angular extremadamente estrecha, de modo que cualquier triángulo de profundidad 20 debe estar casi pegado al equilátero.
Ordenemos lados y ángulos opuestos como \(a\le b\le c\) y \(A\le B\le C\). La ley de senos dice
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
Dentro de la ventana de profundidad 20, el ángulo mayor no puede superar \(\pi/3+\pi/(3\cdot 2^{19})\), y el menor no puede bajar de \(\pi/3-\pi/(3\cdot 2^{20})\). Como \(\sin x\) es creciente en \((0,\pi/2)\), se obtiene
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
Numéricamente, \(r_{\max}-1\approx 1.72977337\times 10^{-6}\). Por eso el espacio de búsqueda queda comprimido alrededor de los triángulos casi equiláteros.
Un triángulo equilátero de lados enteros permanecería equilátero para siempre y no tendría profundidad finita \(20\). Entre los triángulos enteros no equiláteros con lado menor fijo \(a\), el menor perímetro se logra tomando los otros dos lados tan pequeños como permite el orden:
$$b=a,\qquad c=a+1,$$
de donde el perímetro es \(3a+1\). Como los únicos candidatos reales son casi equiláteros, el mínimo global debe aparecer en la primera figura de esa familia isósceles que entra en la ventana admisible.
Para \((a,a,a+1)\), sea \(C\) el ángulo opuesto al lado \(a+1\). La ley de cosenos da
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
Definimos
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
Como los otros dos ángulos son \((\pi-C)/2\), toda la condición de profundidad 20 para esta familia se reduce a
$$C<\frac{\pi}{3}+K.$$
Puesto que \(\cos x\) es decreciente en \((0,\pi)\), esto equivale a
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
Si ponemos
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$$
la desigualdad se transforma en
$$2Va^2-2a-1>0,$$
y el primer entero válido es
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
Eso produce \(a=578111\) y, por tanto, el perímetro mínimo
$$3a+1=1734334.$$
Para ese triángulo, el exceso angular \(C-\pi/3\) vale aproximadamente \(1.99736879\times 10^{-6}\): está por debajo del techo para profundidad 20, \(K\approx 1.99737082\times 10^{-6}\), pero por encima del umbral mucho más estricto de profundidad 21, \(\pi/(3\cdot 2^{21})\). Así se obtiene profundidad exactamente \(20\).
El mismo mecanismo aparece ya en pequeña escala. Para \((3,3,4)\),
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
de modo que \(C\approx 83.62^\circ\), mientras que los otros ángulos son aproximadamente \(48.19^\circ\). Tras un paso telescópico, los nuevos ángulos son aproximadamente
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$$
que siguen siendo agudos. Después del paso siguiente pasan a ser
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$$
y el proceso se detiene. Por eso \((3,3,4)\) tiene profundidad exacta \(2\).
La implementación en C++ mantiene el problema completo. Obtiene los ángulos a partir de los lados mediante la ley de cosenos, simula directamente el mapa telescópico y cuenta cuántos triángulos agudos aparecen antes de fallar. Además calcula el intervalo de desviaciones permitido para la profundidad objetivo, lo convierte en la cota \(r_{\max}\) y usa esa cota para restringir la enumeración a una franja muy delgada cerca de \(a=b=c\).
La búsqueda recorre ternas enteras ordenadas \(a\le b\le c\), comprueba la desigualdad triangular y corta en cuanto el perímetro actual ya no puede mejorar el mejor perímetro hallado. Esa versión sirve como verificación directa del argumento matemático.
Las implementaciones en Python y Java llevan la derivación hasta el final. Usan que el minimizador debe pertenecer a la familia \((a,a,a+1)\), sustituyen esa forma en la ley de cosenos y resuelven una sola desigualdad cuadrática para \(a\). Como \(K=\pi/(3\cdot 2^{19})\) es diminuto, evalúan \(\sin K\) y \(\cos K\) con series de Taylor cortas, reconstruyen \(\cos(\pi/3+K)\) con fórmulas de suma de ángulos y obtienen el primer entero \(a\) que supera el umbral. La salida final es simplemente \(3a+1\).
En la búsqueda general, verificar un triángulo candidato cuesta \(O(t)\) porque la cadena telescópica se sigue solo hasta una cota pequeña. El tamaño de la región candidata está controlado por \(r_{\max}\): para un valor fijo de \(a\), solo hay \(O(a(r_{\max}-1)+1)\) posibles valores de \(c\), y el intervalo admisible para \(b\) tiene el mismo orden. Como \(r_{\max}-1\) es minúsculo cuando \(t=20\), la búsqueda real es muchísimo más estrecha que un barrido cúbico ingenuo.
Las versiones de Python y Java eliminan toda enumeración. Para el objetivo fijo del problema solo realizan una cantidad constante de aritmética de alta precisión, así que el coste es esencialmente \(O(1)\) en tiempo y memoria.
从一个锐角三角形开始，设其角为 \((A,B,C)\)。一次 telescoping 变换把它变成角为
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr)$$
的新三角形。因为三角形内角和满足 \(A+B+C=\pi\)，变换后仍有
$$ (\pi-2A)+(\pi-2B)+(\pi-2C)=\pi, $$
所以角和这一不变量始终成立。但这个步骤只有在三个新角都仍然为正且小于 \(\pi/2\) 时才算有效。所谓 telescoping depth，就是这条链中连续有效三角形的个数，并把原始三角形也算进去。题目要求的是：在所有边长为整数、telescoping depth 恰好等于 \(20\) 的三角形中，最小周长是多少。
这道题的真正核心不是直接追踪角本身，而是追踪它们相对于正三角形的偏移量。这样一来，递推结构会变得非常清楚。
设
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
则因为 \(A+B+C=\pi\)，必有
$$\alpha+\beta+\gamma=0.$$
做一次 telescoping 之后，
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
另外两个角同理。因此偏移量三元组满足最简单的线性递推：
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
也就是说，每做一步，三个偏移量都会整体翻转符号，并且绝对值扩大 2 倍。这正是整个题目的关键不变量。
一个角是锐角，当且仅当它属于 \((0,\pi/2)\)。对偏移量 \(d\) 来说，这等价于
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
经过 \(j\) 步以后，这个偏移量变成 \((-2)^j d\)。因此“深度至少为 \(t\)”的条件就是
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
把这些区间全部相交，就得到一个显式答案。若 \(t=2m\) 为偶数，则
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right);$$
若 \(t=2m+1\) 为奇数，则
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
特别地，对于题目中的 \(t=20\)，每个初始偏移量都必须满足
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$$
这个窗口极其狭窄，所以深度达到 20 的三角形必然非常接近正三角形。
设边长和对角按大小排序为 \(a\le b\le c\) 与 \(A\le B\le C\)。由正弦定理可得
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
在深度 20 的可行窗口中，最大角不会超过 \(\pi/3+\pi/(3\cdot 2^{19})\)，最小角不会小于 \(\pi/3-\pi/(3\cdot 2^{20})\)。由于 \(\sin x\) 在 \((0,\pi/2)\) 上单调递增，所以
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
数值上，\(r_{\max}-1\approx 1.72977337\times 10^{-6}\)。这说明最短边和最长边之间的差距极小，搜索空间被压缩到了“几乎等边”的一条极窄带状区域。
如果三角形是整数边正三角形，那么它在每一步之后仍然是正三角形，因此深度不是有限的 20，而是无限延续下去。所以真正的最优解必须是“尽可能接近正三角形、但又不完全等边”的整数三角形。
现在固定最短边为 \(a\)。在所有非等边、边长有序的整数三角形中，最小周长显然由最小可能的另外两条边给出：
$$b=a,\qquad c=a+1.$$
此时周长是
$$a+b+c=3a+1.$$
由于深度 20 的候选者已经被迫接近正三角形，所以全局最优解一定出现在这一族等腰三角形 \((a,a,a+1)\) 中。
对三角形 \((a,a,a+1)\)，设 \(C\) 为对边 \(a+1\) 的角。由余弦定理，
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
再记
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
因为另外两个角相等，都是 \((\pi-C)/2\)，所以对于这族三角形，只要满足
$$C<\frac{\pi}{3}+K$$
就已经同时保证另外两个角也留在深度 20 所需的下界之上。由于 \(\cos x\) 在 \((0,\pi)\) 上递减，这等价于
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
若定义
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$$
则得到二次不等式
$$2Va^2-2a-1>0.$$
因此最小可行整数就是
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
算得
$$a=578111,$$
所以最小周长为
$$3a+1=1734334.$$
对这个具体三角形，最大角相对 \(60^\circ\) 的超出量约为 \(1.99736879\times 10^{-6}\)。它略小于深度 20 的上界 \(K\approx 1.99737082\times 10^{-6}\)，却远大于深度 21 所需的更严格上界 \(\pi/(3\cdot 2^{21})\)。因此它的深度恰好是 \(20\)，不是更大。
这个递推规律在小例子里就能直接看出来。对 \((3,3,4)\)，
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
所以 \(C\approx 83.62^\circ\)，另外两个角各约为 \(48.19^\circ\)。做一次 telescoping 后，新角为
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$$
仍然全部是锐角。再做一次之后变成
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$$
此时出现了钝角，过程终止，所以它的深度正好是 2。
C++ 实现保留了问题的完整定义。它先用余弦定理从边长恢复角度，再直接模拟 telescoping 过程，数出在失效之前一共经过了多少个锐角三角形。与此同时，它还根据目标深度推导出允许的偏移区间，再把这个区间转成 \(r_{\max}\) 这种边长比上界，用来大幅压缩候选三角形的枚举范围。
搜索时按 \(a\le b\le c\) 枚举整数边长，并强制满足三角形不等式；一旦当前周长已经不可能优于已知最优周长，就立刻提前停止。这一版的意义在于，它不依赖最终闭式，而是直接把数学推导逐项验证出来。
Python 和 Java 实现则继续把推导做到底。既然已经知道最优解一定在 \((a,a,a+1)\) 这一族里，就只需要求解一个关于 \(a\) 的二次不等式。由于 \(K=\pi/(3\cdot 2^{19})\) 非常小，它们用短的 Taylor 展开式计算 \(\sin K\) 与 \(\cos K\)，再通过和角公式得到 \(\cos(\pi/3+K)\)，最后求出第一个越过阈值的整数 \(a\)。最终输出自然就是 \(3a+1\)。
对于通用搜索法，检查单个候选三角形需要 \(O(t)\) 时间，因为最多只追踪一条长度受控的 telescoping 链。候选区域由 \(r_{\max}\) 主导：对固定的 \(a\)，可能的 \(c\) 数量只有 \(O(a(r_{\max}-1)+1)\)，而 \(b\) 的可行范围也在同一数量级。由于 \(t=20\) 时 \(r_{\max}-1\) 极小，实际搜索远比朴素的三重枚举窄得多。
Python 和 Java 的闭式做法完全消除了枚举。在题目的固定规模下，它们只做常数次高精度运算，因此时间和空间都可以视为 \(O(1)\)。
Рассматривается остроугольный треугольник с углами \((A,B,C)\). Один шаг telescoping заменяет его новым треугольником с углами
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
Сумма углов остаётся равной \(\pi\), поскольку
$$ (\pi-2A)+(\pi-2B)+(\pi-2C)=\pi. $$
Однако шаг допустим только тогда, когда все три новых угла по-прежнему положительны и меньше \(\pi/2\). Глубина telescoping определяется как число подряд идущих допустимых треугольников в этой цепочке, включая исходный. Нужно найти наименьший периметр целочисленного треугольника, у которого эта глубина равна ровно \(20\).
Во всех трёх реализациях используется одна и та же идея: удобнее всего изучать процесс через отклонения от равностороннего треугольника.
Запишем углы в виде
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
где
$$\alpha+\beta+\gamma=0.$$
После одного шага telescoping имеем
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
и аналогично для двух остальных углов. Значит, тройка отклонений подчиняется рекуррентному правилу
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
То есть на каждом шаге знак меняется, а абсолютная величина каждого отклонения удваивается.
Угол острый тогда и только тогда, когда он лежит в интервале \((0,\pi/2)\). Для отклонения \(d\) от \(\pi/3\) это означает
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
Через \(j\) шагов отклонение равно \((-2)^j d\), поэтому условие глубины не меньше \(t\) равносильно системе
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
Пересечение этих интервалов выписывается явно. Если \(t=2m\) чётно, то
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
а если \(t=2m+1\) нечётно, то
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
Для целевого случая \(t=20\) каждое начальное отклонение обязано лежать в интервале
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$$
Этот интервал настолько узок, что любой треугольник глубины 20 должен быть почти равносторонним.
Упорядочим стороны и противоположные им углы как \(a\le b\le c\) и \(A\le B\le C\). По теореме синусов
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
Внутри окна глубины 20 максимальный угол не превосходит \(\pi/3+\pi/(3\cdot 2^{19})\), а минимальный не опускается ниже \(\pi/3-\pi/(3\cdot 2^{20})\). Так как \(\sin x\) возрастает на \((0,\pi/2)\), получаем
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
Численно \(r_{\max}-1\approx 1.72977337\times 10^{-6}\). Именно поэтому область поиска сжимается почти до одной близкой к равносторонней семьи.
Равносторонний целочисленный треугольник оставался бы равносторонним на всех шагах, а значит, не имел бы конечной глубины \(20\). Среди неравносторонних целочисленных треугольников с фиксированной минимальной стороной \(a\) наименьший периметр достигается тогда, когда две другие стороны берутся минимально возможными:
$$b=a,\qquad c=a+1.$$
Тогда периметр равен \(3a+1\). Поскольку для глубины 20 остаются только почти равносторонние треугольники, глобальный минимум обязан лежать в этой изосцелесовой семье \((a,a,a+1)\).
Пусть \(C\) - угол напротив стороны \(a+1\). По теореме косинусов
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
Обозначим
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
Поскольку два остальных угла равны \((\pi-C)/2\), для этой семьи всё условие глубины 20 сводится к одному неравенству
$$C<\frac{\pi}{3}+K.$$
Так как \(\cos x\) убывает на \((0,\pi)\), это эквивалентно
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
Если ввести
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$$
то получаем квадратное неравенство
$$2Va^2-2a-1>0,$$
и первый подходящий целый \(a\) равен
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
Отсюда
$$a=578111,$$
а минимальный периметр равен
$$3a+1=1734334.$$
Для этого треугольника избыток угла \(C\) над \(\pi/3\) составляет примерно \(1.99736879\times 10^{-6}\). Он меньше потолка для глубины 20, \(K\approx 1.99737082\times 10^{-6}\), но больше куда более жёсткого порога для глубины 21, \(\pi/(3\cdot 2^{21})\). Следовательно, глубина действительно равна ровно \(20\).
Та же логика видна уже на маленьком примере. Для \((3,3,4)\)
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
поэтому \(C\approx 83.62^\circ\), а два остальных угла равны примерно \(48.19^\circ\). После одного шага получаются углы
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$$
которые ещё остаются острыми. После следующего шага имеем
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$$
и процесс завершается. Поэтому глубина этого треугольника равна точно 2.
Реализация на C++ сохраняет полную постановку задачи. Она восстанавливает углы по длинам сторон с помощью теоремы косинусов, напрямую имитирует преобразование telescoping и считает, сколько остроугольных треугольников появляется до остановки. Параллельно вычисляется допустимый интервал отклонений для нужной глубины, затем он переводится в ограничение \(r_{\max}\) на отношение сторон, и перебор сжимается к очень тонкой полосе около \(a=b=c\).
Поиск проходит по упорядоченным целочисленным тройкам \(a\le b\le c\), соблюдает неравенство треугольника и делает ранний выход, как только текущий периметр уже не может улучшить найденный минимум. Эта версия важна как прямое подтверждение всей математической схемы.
Реализации на Python и Java идут дальше и используют уже доказанный факт, что минимум обязан иметь вид \((a,a,a+1)\). После подстановки этой семьи в теорему косинусов задача сводится к одному квадратному неравенству для \(a\). Поскольку \(K=\pi/(3\cdot 2^{19})\) очень мал, \(\sin K\) и \(\cos K\) вычисляются короткими рядами Тейлора, затем по формуле сложения углов восстанавливается \(\cos(\pi/3+K)\), и находится первое целое \(a\), проходящее порог. В ответ выводится \(3a+1\).
В общей поисковой версии проверка одного кандидата занимает \(O(t)\) времени, так как цепочка telescoping отслеживается только до небольшой верхней границы. Размер области перебора контролируется числом \(r_{\max}\): для фиксированного \(a\) возможны лишь \(O(a(r_{\max}-1)+1)\) значений \(c\), и допустимый диапазон для \(b\) имеет тот же порядок. Поскольку при \(t=20\) величина \(r_{\max}-1\) чрезвычайно мала, реальный перебор намного уже наивного кубического просмотра всех треугольников.
В версиях Python и Java перебор исчезает совсем. Для фиксированного целевого значения Project Euler остаётся только постоянное число операций высокой точности, так что и время, и память фактически равны \(O(1)\).
نبدأ بمثلث حاد الزوايا زواياه \((A,B,C)\). خطوة telescoping واحدة تستبدله بمثلث جديد زواياه
$$\bigl(\pi-2A,\ \pi-2B,\ \pi-2C\bigr).$$
يبقى مجموع الزوايا مساويًا لـ\(\pi\)، لأن
$$ (\pi-2A)+(\pi-2B)+(\pi-2C)=\pi. $$
لكن هذه الخطوة تكون صالحة فقط إذا بقيت الزوايا الثلاث الجديدة موجبة وأصغر من \(\pi/2\). وعمق telescoping لمثلث ما هو عدد المثلثات الصالحة المتتالية في هذه السلسلة مع احتساب المثلث الأصلي أيضًا. المطلوب في المسألة هو إيجاد أصغر محيط لمثلث ذي أضلاع صحيحة يكون عمقه بالضبط \(20\).
الفكرة الحاسمة في الحلول الثلاثة هي أن العملية تصبح واضحة جدًا إذا قسنا كل شيء بالنسبة إلى المثلث المتساوي الأضلاع.
نكتب الزوايا على الصورة
$$A=\frac{\pi}{3}+\alpha,\qquad B=\frac{\pi}{3}+\beta,\qquad C=\frac{\pi}{3}+\gamma,$$
وبما أن \(A+B+C=\pi\)، فهذا يعني
$$\alpha+\beta+\gamma=0.$$
بعد خطوة واحدة من telescoping نحصل على
$$\pi-2\left(\frac{\pi}{3}+\alpha\right)=\frac{\pi}{3}-2\alpha,$$
والشيء نفسه ينطبق على الزاويتين الأخريين. إذن ثلاثية الانحرافات تحقق التكرار
$$ (\alpha,\beta,\gamma)\longmapsto (-2\alpha,\,-2\beta,\,-2\gamma). $$
أي أن كل خطوة تعكس الإشارة وتضاعف مقدار الانحراف.
الزاوية تكون حادة إذا وفقط إذا كانت في المجال \((0,\pi/2)\). وإذا كانت \(d\) هي الانحراف عن \(\pi/3\)، فذلك يكافئ
$$-\frac{\pi}{3}<d<\frac{\pi}{6}.$$
وبعد \(j\) خطوات يصبح الانحراف \((-2)^j d\)، لذا فإن شرط أن يكون العمق على الأقل \(t\) هو
$$-\frac{\pi}{3}<(-2)^j d<\frac{\pi}{6},\qquad 0\le j<t.$$
تقاطع هذه المجالات يمكن كتابته بصيغة مغلقة. فإذا كان \(t=2m\) زوجيًا فإن
$$I_{2m}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m-1}}\right),$$
أما إذا كان \(t=2m+1\) فرديًا فإن
$$I_{2m+1}=\left(-\frac{\pi}{3\cdot 2^{2m}},\ \frac{\pi}{3\cdot 2^{2m+1}}\right).$$
وبالتحديد عند \(t=20\) يجب أن يقع كل انحراف ابتدائي داخل
$$I_{20}=\left(-\frac{\pi}{3\cdot 2^{20}},\ \frac{\pi}{3\cdot 2^{19}}\right).$$
هذا مجال ضيق جدًا، ولذلك لا بد أن يكون أي مثلث بعمق 20 قريبًا جدًا من المثلث المتساوي الأضلاع.
لنرتب الأضلاع والزوايا المقابلة لها على شكل \(a\le b\le c\) و\(A\le B\le C\). من قانون الجيوب نحصل على
$$\frac{c}{a}=\frac{\sin C}{\sin A}.$$
داخل نافذة العمق 20 لا يمكن أن تتجاوز الزاوية الكبرى \(\pi/3+\pi/(3\cdot 2^{19})\)، ولا يمكن أن تنخفض الزاوية الصغرى تحت \(\pi/3-\pi/(3\cdot 2^{20})\). وبما أن \(\sin x\) دالة متزايدة على \((0,\pi/2)\)، فإن
$$\frac{c}{a}\le \frac{\sin\!\left(\frac{\pi}{3}+\frac{\pi}{3\cdot 2^{19}}\right)}{\sin\!\left(\frac{\pi}{3}-\frac{\pi}{3\cdot 2^{20}}\right)}=:r_{\max}.$$
عدديًا نجد أن \(r_{\max}-1\approx 1.72977337\times 10^{-6}\). وهذا يفسر لماذا تنحصر منطقة البحث عمليًا في مثلثات شبه متساوية الأضلاع.
لو كان المثلث متساوي الأضلاع تمامًا لبقي كذلك إلى الأبد، وبالتالي لن تكون له قيمة نهائية للعمق تساوي \(20\). وبين جميع المثلثات الصحيحة غير المتساوية الأضلاع ذات أصغر ضلع ثابت \(a\)، فإن أصغر محيط يتحقق عندما نأخذ الضلعين الآخرين بأصغر قيم ممكنة مع الحفاظ على الترتيب:
$$b=a,\qquad c=a+1.$$
وعندها يكون المحيط
$$3a+1.$$
وبما أن جميع المرشحين الحقيقيين لعمق 20 قريبون جدًا من الشكل المتساوي الأضلاع، فلا بد أن يظهر الحل الأمثل داخل هذه العائلة المتساوية الساقين \((a,a,a+1)\).
في المثلث \((a,a,a+1)\)، لتكن \(C\) الزاوية المقابلة للضلع \(a+1\). من قانون جيب التمام نحصل على
$$\cos C=\frac{a^2+a^2-(a+1)^2}{2a^2}=\frac12-\frac{2a+1}{2a^2}.$$
ونعرف
$$K=\frac{\pi}{3\cdot 2^{19}}.$$
ولأن الزاويتين الأخريين تساويان \((\pi-C)/2\)، فإن شرط العمق 20 لهذه العائلة يختزل إلى
$$C<\frac{\pi}{3}+K.$$
وبما أن \(\cos x\) دالة متناقصة على \((0,\pi)\)، فهذا يكافئ
$$\frac12-\frac{2a+1}{2a^2}>\cos\!\left(\frac{\pi}{3}+K\right).$$
إذا وضعنا
$$V=\frac12-\cos\!\left(\frac{\pi}{3}+K\right),$$
فإننا نحصل على المتباينة التربيعية
$$2Va^2-2a-1>0.$$
ومن ثم يكون أصغر عدد صحيح صالح هو
$$a=\left\lfloor \frac{1+\sqrt{1+2V}}{2V}\right\rfloor+1.$$
وهذا يعطينا
$$a=578111,$$
ومن ثم أصغر محيط يساوي
$$3a+1=1734334.$$
في هذا المثلث يكون الانحراف \(C-\pi/3\) تقريبًا \(1.99736879\times 10^{-6}\)، وهو أصغر بقليل من حد العمق 20، أي \(K\approx 1.99737082\times 10^{-6}\)، لكنه أكبر من الحد الأكثر تشددًا للعمق 21 وهو \(\pi/(3\cdot 2^{21})\). لذلك فالعمق يساوي بالضبط \(20\).
يمكن رؤية الآلية نفسها على مثال صغير. في المثلث \((3,3,4)\)،
$$\cos C=\frac{9+9-16}{18}=\frac19,$$
ومن ثم \(C\approx 83.62^\circ\)، بينما الزاويتان الأخريان تقربان \(48.19^\circ\). بعد خطوة telescoping واحدة تصبح الزوايا تقريبًا
$$83.62^\circ,\ 83.62^\circ,\ 12.76^\circ,$$
وما تزال كلها حادة. وبعد خطوة أخرى تصبح
$$12.76^\circ,\ 12.76^\circ,\ 154.48^\circ,$$
فتظهر زاوية منفرجة ويتوقف التسلسل. لذلك فعمق هذا المثلث يساوي بالضبط 2.
تنفيذ C++ يتعامل مع المسألة بصيغتها العامة الكاملة. فهو يستخرج الزوايا من أطوال الأضلاع باستخدام قانون جيب التمام، ثم يحاكي تحويل telescoping مباشرة ويحسب عدد المثلثات الحادة التي تظهر قبل التوقف. وفي الوقت نفسه يستنتج مجال الانحرافات المسموح به للعمق المطلوب، ثم يحوله إلى القيد \(r_{\max}\) على نسبة الأضلاع، وبذلك يختزل مساحة البحث إلى شريط رفيع جدًا حول الحالة شبه المتساوية الأضلاع.
يتم تعداد الثلاثيات الصحيحة المرتبة \(a\le b\le c\)، مع فرض متباينة المثلث، واستخدام إيقاف مبكر عندما يصبح المحيط الحالي غير قادر على تحسين أفضل محيط معروف. هذه النسخة مهمة لأنها تتحقق من الاشتقاق الرياضي مباشرة من دون افتراض الصيغة النهائية مسبقًا.
تنفيذا Python وJava يذهبان خطوة إضافية. بعد إثبات أن الحل الأدنى لا بد أن يكون من العائلة \((a,a,a+1)\)، تتحول المسألة إلى متباينة تربيعية واحدة في \(a\). وبما أن \(K=\pi/(3\cdot 2^{19})\) صغير جدًا، فإنهما يحسبان \(\sin K\) و\(\cos K\) بواسطة حدود قصيرة من متسلسلة Taylor، ثم يعيدان بناء \(\cos(\pi/3+K)\) بصيغة جمع الزوايا، وأخيرًا يستخرجان أول عدد صحيح \(a\) يتجاوز العتبة. الخرج النهائي هو ببساطة \(3a+1\).
في نسخة البحث العامة، فحص مثلث مرشح واحد يكلف \(O(t)\) زمنًا لأن سلسلة telescoping لا تُتبع إلا حتى حد صغير مضبوط. أما حجم منطقة المرشحين فيتحكم فيه \(r_{\max}\): فلكل قيمة ثابتة من \(a\) يوجد فقط \(O(a(r_{\max}-1)+1)\) احتمالًا للقيمة \(c\)، ويكون مجال \(b\) في المرتبة نفسها. ولأن \(r_{\max}-1\) صغير للغاية عندما \(t=20\)، فإن البحث العملي أضيق بكثير من تعداد تكعيبي ساذج لكل المثلثات الممكنة.
أما نسختا Python وJava فتزيلان التعداد تمامًا. فعند حجم المسألة الثابت لا يبقى إلا عدد ثابت من العمليات الحسابية عالية الدقة، ولذلك يمكن اعتبار الزمن والذاكرة من رتبة \(O(1)\).