We seek isosceles triangles with equal sides \(L\), base \(b\), and altitude \(h\) such that \(h=b\pm1\). The triangles are ordered by increasing \(L\), and the required result is the sum of the first twelve leg lengths.
The altitude of an isosceles triangle bisects the base, so the geometry immediately becomes a right-triangle problem. The valid triangles do not need to be found by brute force; they form a Pell-type sequence, and the implementations use the resulting recurrence directly.
Let \(m=b/2\). Since \(4L^2=4h^2+b^2\), the base must be even, so \(m\) is an integer. Write the sign in the condition \(h=b\pm1\) as \(\sigma\in\{-1,+1\}\), which lets us express the height as \(h=2m+\sigma\).
Splitting the isosceles triangle along its altitude gives a right triangle with legs \(m\) and \(h\), and hypotenuse \(L\). Therefore
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
Multiply by \(5\) and complete the square:
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
If we define
$$X=5m+2\sigma,$$
then every special isosceles triangle produces a solution of
$$X^2-5L^2=-1.$$
So the geometric problem is equivalent to finding the positive nondegenerate solutions of the negative Pell equation \(X^2-5Y^2=-1\), with \(Y=L\).
The converse is just as important. Any solution of \(X^2-5L^2=-1\) satisfies \(X^2\equiv4\pmod{5}\), so \(X\equiv\pm2\pmod{5}\). That congruence determines which sign occurs in \(h=b\pm1\): if \(X\equiv2\pmod{5}\), then \(\sigma=+1\); if \(X\equiv-2\pmod{5}\), then \(\sigma=-1\).
Once \(\sigma\) is known, the triangle parameters are recovered by
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
The smallest Pell solution \((X,L)=(2,1)\) gives \(m=0\), so it is degenerate and must be discarded. Every later positive solution yields a genuine triangle.
The equation \(X^2-5L^2=-1\) has fundamental solution \(2^2-5\cdot1^2=-1\). Consecutive nondegenerate triangle solutions are obtained by multiplying by
$$9+4\sqrt{5}=(2+\sqrt{5})^2.$$
Thus, if \(X_n+L_n\sqrt{5}\) represents one triangle, then the next triangle satisfies
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
Expanding gives the two-variable recurrence
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
with the first nondegenerate pair \((X_1,L_1)=(38,17)\).
Eliminating \(X_n\) yields the scalar recurrence used by the implementations:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
This generates the required leg lengths \(17,305,5473,98209,\dots\). Equivalently, \(L_n=F_{6n+3}/2\), but the second-order recurrence is the most direct computational form.
For the first triangle, \((X_1,L_1)=(38,17)\). Since \(38\equiv-2\pmod{5}\), we take \(\sigma=-1\), and then
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
Indeed, \(15^2+8^2=17^2\), so this is a valid triangle with \(h=b-1\).
Multiply once by \(9+4\sqrt{5}\) to get the next solution:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
Now \(682\equiv2\pmod{5}\), so \(\sigma=+1\), and
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
This second triangle satisfies \(h=b+1\). Because \(X_{n+1}\equiv-X_n\pmod{5}\), the residues \(2\) and \(-2\) alternate, so the family alternates between the cases \(h=b-1\) and \(h=b+1\).
The C++, Python, and Java implementations skip the Pell algebra at runtime and start directly from the first two leg lengths \(17\) and \(305\). A running sum is initialized from the first term because the only requested output is the sum of the first twelve \(L\)-values.
Each loop iteration adds the current term, computes the next one with \(L_{n+2}=18L_{n+1}-L_n\), and shifts the two previous terms forward. The C++ implementation also contains a small built-in checkpoint on the first two terms and can vary the number of generated triangles, while the Python and Java implementations are fixed to twelve. In every language, the program is simply a compact encoding of the Pell-generated sequence.
For the required twelve triangles, the running time is constant. More generally, producing the first \(N\) leg lengths by the recurrence takes \(O(N)\) time and \(O(1)\) extra space.
The values grow roughly like \((9+4\sqrt{5})^n\), but for the first twelve terms both the individual leg lengths and their sum fit comfortably in signed 64-bit integers. That is why the C++ and Java implementations can use fixed-width integer arithmetic, while Python handles the same calculation with arbitrary-precision integers.
Gesucht sind gleichschenklige Dreiecke mit Schenkeln \(L\), Basis \(b\) und Höhe \(h\), für die \(h=b\pm1\) gilt. Die Dreiecke werden nach wachsendem \(L\) geordnet, und verlangt ist die Summe der ersten zwölf Schenkellängen.
Die Höhe eines gleichschenkligen Dreiecks halbiert die Basis. Dadurch wird die Geometrie sofort zu einem rechtwinkligen Dreieck. Man muss also nicht alle Basen durchsuchen; die gültigen Dreiecke liegen auf einer Pell-artigen Folge, und genau diese Rekursion verwenden die Implementierungen.
Setze \(m=b/2\). Aus \(4L^2=4h^2+b^2\) folgt sofort, dass \(b\) gerade sein muss, also ist \(m\) ganzzahlig. Schreibe das Vorzeichen in \(h=b\pm1\) als \(\sigma\in\{-1,+1\}\), dann ist \(h=2m+\sigma\).
Teilt man das gleichschenklige Dreieck entlang der Höhe, erhält man ein rechtwinkliges Dreieck mit Katheten \(m\) und \(h\) sowie Hypotenuse \(L\). Daher gilt
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
Multiplikation mit \(5\) und quadratische Ergänzung liefern
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
Mit
$$X=5m+2\sigma$$
wird daraus
$$X^2-5L^2=-1.$$
Das geometrische Problem ist damit äquivalent zur Bestimmung der positiven nichtentarteten Lösungen der negativen Pell-Gleichung \(X^2-5Y^2=-1\), wobei \(Y=L\) ist.
Auch die Umkehrung ist entscheidend. Jede Lösung von \(X^2-5L^2=-1\) erfüllt \(X^2\equiv4\pmod{5}\), also \(X\equiv\pm2\pmod{5}\). Daraus liest man ab, welches Vorzeichen in \(h=b\pm1\) vorkommt: Gilt \(X\equiv2\pmod{5}\), dann ist \(\sigma=+1\); gilt \(X\equiv-2\pmod{5}\), dann ist \(\sigma=-1\).
Sobald \(\sigma\) feststeht, erhält man die Dreiecksparameter durch
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
Die kleinste Pell-Lösung \((X,L)=(2,1)\) liefert \(m=0\) und ist daher entartet. Jede spätere positive Lösung ergibt dagegen ein echtes Dreieck.
Die Gleichung \(X^2-5L^2=-1\) hat die Fundamentallösung \(2^2-5\cdot1^2=-1\). Aufeinanderfolgende nichtentartete Dreieckslösungen entstehen durch Multiplikation mit
$$9+4\sqrt{5}=(2+\sqrt{5})^2.$$
Wenn also \(X_n+L_n\sqrt{5}\) ein Dreieck beschreibt, dann erfüllt das nächste Dreieck
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
Ausmultipliziert ergibt das die Zweierrekursion
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
mit dem ersten nichtentarteten Paar \((X_1,L_1)=(38,17)\).
Eliminiert man \(X_n\), erhält man genau die skalare Rekursion der Programme:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
Damit entstehen die gesuchten Schenkellängen \(17,305,5473,98209,\dots\). Äquivalent gilt auch \(L_n=F_{6n+3}/2\), aber die Rekursion zweiter Ordnung ist rechnerisch die direkteste Form.
Für das erste Dreieck gilt \((X_1,L_1)=(38,17)\). Weil \(38\equiv-2\pmod{5}\), ist \(\sigma=-1\), also
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
Tatsächlich ist \(15^2+8^2=17^2\), also liegt der Fall \(h=b-1\) vor.
Einmalige Multiplikation mit \(9+4\sqrt{5}\) liefert die nächste Lösung:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
Nun gilt \(682\equiv2\pmod{5}\), also \(\sigma=+1\), und damit
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
Dieses zweite Dreieck erfüllt \(h=b+1\). Weil \(X_{n+1}\equiv-X_n\pmod{5}\) gilt, wechseln die Reste \(2\) und \(-2\) ab, und die Familie alterniert deshalb zwischen den Fällen \(h=b-1\) und \(h=b+1\).
Die C++-, Python- und Java-Implementierungen führen die Pell-Herleitung nicht zur Laufzeit aus, sondern starten direkt mit den ersten beiden Schenkellängen \(17\) und \(305\). Die laufende Summe beginnt beim ersten Term, weil nur die Summe der ersten zwölf \(L\)-Werte gefragt ist.
In jeder Schleifeniteration wird der aktuelle Term addiert, der nächste über \(L_{n+2}=18L_{n+1}-L_n\) berechnet und das Paar der letzten beiden Werte weitergeschoben. Die C++-Implementierung enthält außerdem eine kleine eingebaute Prüfung für die ersten zwei Terme und kann die Anzahl der erzeugten Dreiecke variieren; die Python- und Java-Implementierungen sind auf zwölf Terme festgelegt. In allen drei Sprachen ist der Code nur eine kompakte Darstellung derselben Pell-Folge.
Für die geforderten zwölf Dreiecke ist die Laufzeit konstant. Allgemein benötigt die Erzeugung der ersten \(N\) Schenkellängen per Rekursion \(O(N)\) Zeit und \(O(1)\) zusätzlichen Speicher.
Die Werte wachsen ungefähr wie \((9+4\sqrt{5})^n\), aber für die ersten zwölf Terme passen sowohl die einzelnen Schenkellängen als auch ihre Summe bequem in vorzeichenbehaftete 64-Bit-Ganzzahlen. Deshalb können die C++- und Java-Implementierungen mit festen Ganzzahltypen arbeiten, während Python dieselbe Rechnung mit beliebiger Präzision ausführt.
Eş kenarları \(L\), tabanı \(b\) ve yüksekliği \(h\) olan, \(h=b\pm1\) şartını sağlayan ikizkenar üçgenler aranıyor. Üçgenler \(L\) artan sırada düşünülüyor ve istenen sonuç ilk on iki kenar uzunluğunun toplamı.
İkizkenar üçgende yükseklik tabanı ikiye böldüğü için problem hemen bir dik üçgen problemine dönüşür. Geçerli üçgenleri kaba kuvvetle aramaya gerek yoktur; bunlar Pell tipi bir dizi oluşturur ve uygulamalar doğrudan bu dizinin yinelemesini kullanır.
\(m=b/2\) yazalım. \(4L^2=4h^2+b^2\) eşitliğinden tabanın çift olması gerektiği görülür; dolayısıyla \(m\) tam sayıdır. \(h=b\pm1\) koşulundaki işareti \(\sigma\in\{-1,+1\}\) ile gösterirsek \(h=2m+\sigma\) olur.
İkizkenar üçgeni yükseklik boyunca ikiye ayırınca dik kenarları \(m\) ve \(h\), hipotenüsü \(L\) olan bir dik üçgen elde ederiz. Bu yüzden
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
\(5\) ile çarpıp kare tamamlarsak
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
Şimdi
$$X=5m+2\sigma$$
tanımını yaparsak
$$X^2-5L^2=-1$$
elde edilir. Böylece geometrik problem, \(Y=L\) olacak şekilde negatif Pell denklemi \(X^2-5Y^2=-1\)'in pozitif ve yozlaşmamış çözümlerini bulma problemine dönüşür.
Ters yön de aynı derecede önemlidir. \(X^2-5L^2=-1\) denkleminin her çözümü \(X^2\equiv4\pmod{5}\) sağladığı için \(X\equiv\pm2\pmod{5}\) olur. Bu artık sınıfı, \(h=b\pm1\) içindeki işareti belirler: \(X\equiv2\pmod{5}\) ise \(\sigma=+1\), \(X\equiv-2\pmod{5}\) ise \(\sigma=-1\).
\(\sigma\) bilindiğinde üçgen parametreleri
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma$$
formülleriyle geri elde edilir. En küçük Pell çözümü \((X,L)=(2,1)\) için \(m=0\) çıktığından bu durum yozlaşmıştır ve atılır. Ondan sonraki her pozitif çözüm gerçek bir üçgen verir.
\(X^2-5L^2=-1\) denkleminin temel çözümü \(2^2-5\cdot1^2=-1\)'dir. Ardışık yozlaşmamış üçgen çözümleri
$$9+4\sqrt{5}=(2+\sqrt{5})^2$$
ile çarpılarak üretilir. Yani \(X_n+L_n\sqrt{5}\) bir üçgene karşılık geliyorsa sonraki üçgen
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5})$$
eşitliğiyle gelir.
Bunu açarsak iki değişkenli yineleme
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n$$
elde edilir; başlangıç çifti ilk yozlaşmamış çözüm olan \((X_1,L_1)=(38,17)\)'dir.
\(X_n\)'i elimine edince uygulamaların kullandığı tek değişkenli yineleme çıkar:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
Böylece gereken kenar uzunlukları \(17,305,5473,98209,\dots\) üretilir. Eşdeğer olarak \(L_n=F_{6n+3}/2\) de yazılabilir; ancak hesaplama açısından en doğrudan biçim ikinci dereceden yinelemedir.
İlk üçgende \((X_1,L_1)=(38,17)\) vardır. \(38\equiv-2\pmod{5}\) olduğundan \(\sigma=-1\) alınır ve
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15$$
bulunur. Gerçekten de \(15^2+8^2=17^2\), yani bu üçgende \(h=b-1\).
\(9+4\sqrt{5}\) ile bir kez çarpınca sonraki çözüm gelir:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
Bu kez \(682\equiv2\pmod{5}\) olduğu için \(\sigma=+1\) olur ve
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273$$
elde edilir. İkinci üçgen \(h=b+1\) durumundadır. Üstelik \(X_{n+1}\equiv-X_n\pmod{5}\) olduğundan artık sınıfları \(2\) ve \(-2\) dönüşümlü gelir; dolayısıyla aile de sırayla \(h=b-1\) ve \(h=b+1\) durumları arasında gider gelir.
C++, Python ve Java uygulamaları çalışma anında Pell cebirini tekrar kurmaz; doğrudan ilk iki kenar uzunluğu olan \(17\) ve \(305\) ile başlar. İstenen çıktı yalnızca ilk on iki \(L\) değerinin toplamı olduğu için kümülatif toplam ilk terimden başlatılır.
Her döngü adımı mevcut terimi toplama ekler, sonraki terimi \(L_{n+2}=18L_{n+1}-L_n\) ile üretir ve son iki değeri bir adım ileri taşır. C++ uygulaması ayrıca ilk iki terim için küçük bir yerleşik doğrulama içerir ve üretilen terim sayısını değiştirebilir; Python ve Java uygulamaları ise sabit olarak on iki terim hesaplar. Her üç dilde de kod, Pell kökenli aynı dizinin son derece sıkıştırılmış bir ifadesidir.
İstenen on iki üçgen için çalışma süresi sabittir. Daha genel olarak, ilk \(N\) kenar uzunluğunu bu yineleme ile üretmek \(O(N)\) zaman ve \(O(1)\) ek bellek gerektirir.
Değerler yaklaşık \((9+4\sqrt{5})^n\) hızında büyür; yine de ilk on iki terimde hem tek tek kenar uzunlukları hem de toplam rahatlıkla işaretli 64 bit tamsayı aralığına sığar. Bu yüzden C++ ve Java uygulamaları sabit genişlikli tamsayı kullanabilir, Python ise aynı hesabı doğal olarak keyfi duyarlıklı tamsayılarla yapar.
Se buscan triángulos isósceles con lados iguales \(L\), base \(b\) y altura \(h\) tales que \(h=b\pm1\). Los triángulos se ordenan por \(L\) creciente y hay que sumar las primeras doce longitudes \(L\).
La altura de un triángulo isósceles divide la base en dos partes iguales, así que el problema geométrico se convierte inmediatamente en un problema de triángulos rectángulos. No hace falta explorar todas las bases posibles: los triángulos válidos forman una sucesión de tipo Pell, y las implementaciones usan directamente la recurrencia obtenida de esa estructura.
Sea \(m=b/2\). Como \(4L^2=4h^2+b^2\), la base debe ser par y, por tanto, \(m\) es entero. Escribamos el signo de la condición \(h=b\pm1\) como \(\sigma\in\{-1,+1\}\), de modo que \(h=2m+\sigma\).
Al partir el triángulo isósceles por la altura obtenemos un triángulo rectángulo con catetos \(m\) y \(h\), e hipotenusa \(L\). Entonces
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
Multiplicando por \(5\) y completando el cuadrado se obtiene
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
Si definimos
$$X=5m+2\sigma,$$
entonces todo triángulo especial produce una solución de
$$X^2-5L^2=-1.$$
Por tanto, el problema geométrico equivale a encontrar las soluciones positivas no degeneradas de la ecuación de Pell negativa \(X^2-5Y^2=-1\), con \(Y=L\).
La implicación inversa también es esencial. Toda solución de \(X^2-5L^2=-1\) cumple \(X^2\equiv4\pmod{5}\), así que \(X\equiv\pm2\pmod{5}\). Ese residuo decide qué signo aparece en \(h=b\pm1\): si \(X\equiv2\pmod{5}\), entonces \(\sigma=+1\); si \(X\equiv-2\pmod{5}\), entonces \(\sigma=-1\).
Con \(\sigma\) ya fijado, los parámetros del triángulo se recuperan mediante
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
La solución mínima de Pell \((X,L)=(2,1)\) produce \(m=0\), así que es degenerada y debe descartarse. Toda solución positiva posterior sí genera un triángulo auténtico.
La ecuación \(X^2-5L^2=-1\) tiene solución fundamental \(2^2-5\cdot1^2=-1\). Las soluciones consecutivas no degeneradas se obtienen multiplicando por
$$9+4\sqrt{5}=(2+\sqrt{5})^2.$$
Así, si \(X_n+L_n\sqrt{5}\) representa un triángulo, el siguiente viene dado por
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
Al expandir se obtiene la recurrencia de dos variables
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
con par inicial no degenerado \((X_1,L_1)=(38,17)\).
Eliminando \(X_n\) aparece la recurrencia escalar que usan las implementaciones:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
Esa fórmula produce las longitudes requeridas \(17,305,5473,98209,\dots\). De forma equivalente, \(L_n=F_{6n+3}/2\), aunque para programar la forma más directa es la recurrencia lineal de segundo orden.
Para el primer triángulo se tiene \((X_1,L_1)=(38,17)\). Como \(38\equiv-2\pmod{5}\), tomamos \(\sigma=-1\), y entonces
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
En efecto, \(15^2+8^2=17^2\), así que aquí ocurre el caso \(h=b-1\).
Multiplicando una vez por \(9+4\sqrt{5}\) se obtiene la siguiente solución:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
Ahora \(682\equiv2\pmod{5}\), luego \(\sigma=+1\), y por tanto
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
El segundo triángulo satisface \(h=b+1\). Además, como \(X_{n+1}\equiv-X_n\pmod{5}\), los residuos \(2\) y \(-2\) se alternan, y por eso la familia alterna entre los casos \(h=b-1\) y \(h=b+1\).
Las implementaciones en C++, Python y Java no resuelven la ecuación de Pell en tiempo de ejecución; empiezan directamente con las dos primeras longitudes \(17\) y \(305\). La suma acumulada se inicializa con el primer término porque lo único que se pide es la suma de los primeros doce valores de \(L\).
En cada iteración del bucle se añade el término actual, se calcula el siguiente usando \(L_{n+2}=18L_{n+1}-L_n\) y se desplazan las dos últimas longitudes. La implementación en C++ también incluye una pequeña comprobación interna sobre los dos primeros términos y puede variar la cantidad de triángulos generados, mientras que las de Python y Java están fijadas en doce. En los tres casos, el programa no es más que una forma compacta de la misma sucesión generada por Pell.
Para los doce triángulos pedidos, el tiempo de ejecución es constante. En general, generar las primeras \(N\) longitudes con la recurrencia cuesta \(O(N)\) tiempo y \(O(1)\) espacio adicional.
Los valores crecen aproximadamente como \((9+4\sqrt{5})^n\), pero para los primeros doce términos tanto las longitudes individuales como su suma caben con holgura en enteros con signo de 64 bits. Por eso las implementaciones en C++ y Java pueden usar aritmética de ancho fijo, mientras que Python resuelve el mismo cálculo con enteros de precisión arbitraria.
我们要寻找等腰三角形，其两条相等的边为 \(L\)，底边为 \(b\)，高为 \(h\)，并满足 \(h=b\pm1\)。按 \(L\) 从小到大排列后，需要求出前 12 个这样的 \(L\) 之和。
等腰三角形的高会把底边平分，因此这个几何问题立刻变成一个直角三角形问题。真正关键的不是枚举所有底边，而是看出这些合法三角形落在一个 Pell 型序列上；三个实现都是直接利用这个序列的递推关系。
设 \(m=b/2\)。由 \(4L^2=4h^2+b^2\) 可知 \(b\) 必须是偶数，因此 \(m\) 一定是整数。再把条件 \(h=b\pm1\) 中的符号写成 \(\sigma\in\{-1,+1\}\)，于是可以统一写成 \(h=2m+\sigma\)。
把等腰三角形沿高切开后，会得到一个直角三角形，它的两条直角边分别是 \(m\) 和 \(h\)，斜边是 \(L\)。因此
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
把上式乘以 \(5\)，再配方，可得
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
如果定义
$$X=5m+2\sigma,$$
那么每一个满足题意的三角形都会对应到
$$X^2-5L^2=-1.$$
也就是说，原题等价于求负 Pell 方程 \(X^2-5Y^2=-1\) 的正整数非退化解，其中 \(Y=L\)。
反过来同样成立，而且这一步非常重要。任意满足 \(X^2-5L^2=-1\) 的解都满足 \(X^2\equiv4\pmod{5}\)，因此 \(X\equiv\pm2\pmod{5}\)。这个同余恰好告诉我们 \(h=b\pm1\) 中应该取哪个符号：如果 \(X\equiv2\pmod{5}\)，那么 \(\sigma=+1\)；如果 \(X\equiv-2\pmod{5}\)，那么 \(\sigma=-1\)。
确定 \(\sigma\) 之后，就可以用下面的公式把三角形参数还原出来：
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
最小的 Pell 解 \((X,L)=(2,1)\) 会给出 \(m=0\)，对应退化情形，所以必须丢弃。从那之后的每一个正整数解都会产生一个真正的三角形。
方程 \(X^2-5L^2=-1\) 的基本解是 \(2^2-5\cdot1^2=-1\)。连续的非退化三角形解可以通过乘上
$$9+4\sqrt{5}=(2+\sqrt{5})^2$$
来得到。也就是说，如果 \(X_n+L_n\sqrt{5}\) 对应某一个合法三角形，那么下一个合法三角形满足
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
把它展开，就得到二维递推
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
初始的非退化解是 \((X_1,L_1)=(38,17)\)。
把 \(X_n\) 消掉之后，就得到代码真正使用的一维递推：
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
这就生成了题目要求的边长序列 \(17,305,5473,98209,\dots\)。等价地，也可以写成 \(L_n=F_{6n+3}/2\)，但从实现角度看，二阶线性递推是最直接的形式。
第一个三角形对应 \((X_1,L_1)=(38,17)\)。由于 \(38\equiv-2\pmod{5}\)，所以取 \(\sigma=-1\)，于是
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
验证一下：\(15^2+8^2=17^2\)，因此这是一个满足 \(h=b-1\) 的合法三角形。
接下来把它乘一次 \(9+4\sqrt{5}\)，得到下一个解：
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
这时 \(682\equiv2\pmod{5}\)，所以 \(\sigma=+1\)，从而
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
第二个三角形于是满足 \(h=b+1\)。又因为 \(X_{n+1}\equiv-X_n\pmod{5}\)，余数 \(2\) 与 \(-2\) 会交替出现，所以整族三角形也会在 \(h=b-1\) 和 \(h=b+1\) 两种情形之间交替切换。
C++、Python 和 Java 实现都不会在运行时重新推导 Pell 方程，而是直接从前两个边长 \(17\) 和 \(305\) 开始。由于题目只要求前 12 个 \(L\) 的和，所以累计和一开始就包含第一项。
每次循环都会把当前项加到总和里，然后用 \(L_{n+2}=18L_{n+1}-L_n\) 算出下一项，并把最近两项向前推进。C++ 实现还额外带有一个针对前两项的小型内建校验，并允许改变生成项数；Python 与 Java 实现则固定计算 12 项。三种语言本质上都只是在执行同一个由 Pell 方程导出的序列。
对于题目要求的 12 个三角形，运行时间是常数。更一般地说，用这个递推生成前 \(N\) 个边长需要 \(O(N)\) 时间和 \(O(1)\) 额外空间。
这些数大约按 \((9+4\sqrt{5})^n\) 的速度增长，但在前 12 项范围内，无论是单个边长还是最终总和，都可以轻松放进有符号 64 位整数。因此 C++ 和 Java 可以使用固定宽度整数，而 Python 则自然地用任意精度整数完成同样的计算。
Нужно найти равнобедренные треугольники с равными сторонами \(L\), основанием \(b\) и высотой \(h\), для которых выполняется \(h=b\pm1\). Треугольники упорядочиваются по возрастанию \(L\), и требуется сумма первых двенадцати длин боковой стороны.
Высота равнобедренного треугольника делит основание пополам, поэтому задача сразу превращается в задачу о прямоугольном треугольнике. Перебирать все основания не нужно: все подходящие треугольники лежат на Pell-подобной последовательности, и реализации используют полученную из нее рекурсию напрямую.
Положим \(m=b/2\). Из равенства \(4L^2=4h^2+b^2\) видно, что \(b\) обязано быть четным, значит \(m\) целое. Обозначим знак в условии \(h=b\pm1\) через \(\sigma\in\{-1,+1\}\); тогда \(h=2m+\sigma\).
Если разрезать равнобедренный треугольник по высоте, получится прямоугольный треугольник с катетами \(m\) и \(h\) и гипотенузой \(L\). Поэтому
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
Умножим на \(5\) и дополним до квадрата:
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
Если ввести обозначение
$$X=5m+2\sigma,$$
то получим
$$X^2-5L^2=-1.$$
Тем самым геометрическая задача сводится к поиску положительных невырожденных решений отрицательного уравнения Пелля \(X^2-5Y^2=-1\), где \(Y=L\).
Обратное направление не менее важно. Любое решение \(X^2-5L^2=-1\) удовлетворяет сравнению \(X^2\equiv4\pmod{5}\), а значит \(X\equiv\pm2\pmod{5}\). Именно этот остаток определяет знак в формуле \(h=b\pm1\): если \(X\equiv2\pmod{5}\), то \(\sigma=+1\); если \(X\equiv-2\pmod{5}\), то \(\sigma=-1\).
После этого параметры треугольника восстанавливаются так:
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
Наименьшее решение Пелля \((X,L)=(2,1)\) дает \(m=0\), то есть вырожденный случай, который нужно отбросить. Каждое следующее положительное решение уже задает настоящий треугольник.
Уравнение \(X^2-5L^2=-1\) имеет фундаментальное решение \(2^2-5\cdot1^2=-1\). Последовательные невырожденные решения, соответствующие треугольникам, получаются умножением на
$$9+4\sqrt{5}=(2+\sqrt{5})^2.$$
То есть если \(X_n+L_n\sqrt{5}\) задает один треугольник, то следующий удовлетворяет
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
После раскрытия скобок получаем двухпеременную рекурсию
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
с первым невырожденным решением \((X_1,L_1)=(38,17)\).
Исключая \(X_n\), приходим к скалярной рекурсии, которую и используют реализации:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
Она порождает нужные длины \(17,305,5473,98209,\dots\). Эквивалентно можно записать \(L_n=F_{6n+3}/2\), но для вычислений удобнее именно рекурсия второго порядка.
Для первого треугольника имеем \((X_1,L_1)=(38,17)\). Поскольку \(38\equiv-2\pmod{5}\), берем \(\sigma=-1\), и тогда
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
Проверка дает \(15^2+8^2=17^2\), значит это корректный случай с \(h=b-1\).
Один шаг умножения на \(9+4\sqrt{5}\) дает следующее решение:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
Теперь \(682\equiv2\pmod{5}\), значит \(\sigma=+1\), и
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
Второй треугольник уже удовлетворяет \(h=b+1\). Поскольку \(X_{n+1}\equiv-X_n\pmod{5}\), остатки \(2\) и \(-2\) чередуются, а вместе с ними чередуются и два типа треугольников: \(h=b-1\) и \(h=b+1\).
Реализации на C++, Python и Java не решают уравнение Пелля во время выполнения, а сразу стартуют с двух первых длин \(17\) и \(305\). Накопленная сумма инициализируется первым членом, потому что в задаче нужна только сумма первых двенадцати значений \(L\).
На каждом шаге цикла текущий член добавляется к сумме, следующий вычисляется по формуле \(L_{n+2}=18L_{n+1}-L_n\), после чего два последних значения сдвигаются вперед. Реализация на C++ также содержит небольшую встроенную проверку первых двух членов и позволяет менять число генерируемых треугольников, тогда как реализации на Python и Java всегда считают ровно двенадцать. Во всех трех языках код представляет собой компактную форму одной и той же Pell-последовательности.
Для требуемых двенадцати треугольников время работы постоянно. В более общем виде генерация первых \(N\) длин по этой рекурсии занимает \(O(N)\) времени и \(O(1)\) дополнительной памяти.
Члены растут примерно как \((9+4\sqrt{5})^n\), но для первых двенадцати значений и сами длины, и их сумма уверенно помещаются в знаковый 64-битный тип. Поэтому реализации на C++ и Java используют фиксированную целочисленную арифметику, а Python выполняет тот же расчет с целыми произвольной точности.
نريد إيجاد مثلثات متساوية الساقين يكون طول كل ساق فيها \(L\)، وطول القاعدة \(b\)، والارتفاع \(h\)، مع الشرط \(h=b\pm1\). بعد ترتيب هذه المثلثات تصاعديًا حسب \(L\)، يكون المطلوب هو مجموع أول اثنتي عشرة قيمة من قيم \(L\).
ارتفاع المثلث متساوي الساقين ينصف القاعدة، ولذلك تتحول المسألة الهندسية فورًا إلى مسألة مثلث قائم. لا حاجة إلى تجربة جميع القواعد الممكنة؛ فكل المثلثات الصحيحة تقع على متتالية من نوع Pell، والتنفيذات الثلاثة تستعمل مباشرة العلاقة التكرارية الناتجة عنها.
لنكتب \(m=b/2\). من العلاقة \(4L^2=4h^2+b^2\) نرى أن \(b\) يجب أن يكون عددًا زوجيًا، ولذلك يكون \(m\) عددًا صحيحًا. ولتوحيد الحالتين \(h=b\pm1\)، نرمز إلى الإشارة بـ \(\sigma\in\{-1,+1\}\)، وعندها يصبح \(h=2m+\sigma\).
عند شق المثلث على طول الارتفاع نحصل على مثلث قائم ضلعاه القائمان \(m\) و\(h\)، ووتره \(L\). لذلك
$$L^2=m^2+(2m+\sigma)^2=5m^2+4\sigma m+1.$$
نضرب في \(5\) ثم نكمل المربع فنحصل على
$$5L^2=25m^2+20\sigma m+5=(5m+2\sigma)^2+1.$$
إذا عرّفنا
$$X=5m+2\sigma,$$
فإن كل مثلث يحقق شرط المسألة يعطي حلًا للمعادلة
$$X^2-5L^2=-1.$$
إذن المسألة الهندسية تكافئ إيجاد الحلول الموجبة غير المنعدمة لمعادلة بيل السالبة \(X^2-5Y^2=-1\)، حيث \(Y=L\).
والعكس مهم أيضًا. أي حل للمعادلة \(X^2-5L^2=-1\) يحقق \(X^2\equiv4\pmod{5}\)، ومن ثم \(X\equiv\pm2\pmod{5}\). وهذا الباقي يحدد أي إشارة يجب أخذها في \(h=b\pm1\): إذا كان \(X\equiv2\pmod{5}\) فإن \(\sigma=+1\)، وإذا كان \(X\equiv-2\pmod{5}\) فإن \(\sigma=-1\).
بعد معرفة \(\sigma\)، يمكن استرجاع معلمات المثلث من
$$m=\frac{X-2\sigma}{5},\qquad b=2m,\qquad h=2m+\sigma=b+\sigma.$$
أصغر حل لمعادلة بيل وهو \((X,L)=(2,1)\) يعطي \(m=0\)، أي حالة منعدمة يجب استبعادها. أما كل حل موجب بعد ذلك فيعطي مثلثًا حقيقيًا.
المعادلة \(X^2-5L^2=-1\) لها الحل الأساسي \(2^2-5\cdot1^2=-1\). والحلول غير المنعدمة المتتالية الموافقة للمثلثات تُولد بالضرب في
$$9+4\sqrt{5}=(2+\sqrt{5})^2.$$
أي إذا كان \(X_n+L_n\sqrt{5}\) يمثل مثلثًا واحدًا، فإن المثلث التالي يحقق
$$X_{n+1}+L_{n+1}\sqrt{5}=(9+4\sqrt{5})(X_n+L_n\sqrt{5}).$$
وبتوسيع الطرفين نحصل على العلاقة الثنائية
$$X_{n+1}=9X_n+20L_n,\qquad L_{n+1}=4X_n+9L_n,$$
مع الزوج الأول غير المنعدم \((X_1,L_1)=(38,17)\).
بحذف \(X_n\) نحصل على العلاقة الأحادية التي تستعملها التنفيذات مباشرة:
$$L_{n+2}=18L_{n+1}-L_n,\qquad L_1=17,\qquad L_2=305.$$
وهذه العلاقة تولد القيم المطلوبة \(17,305,5473,98209,\dots\). وبصورة مكافئة يمكن كتابة \(L_n=F_{6n+3}/2\)، لكن العلاقة التكرارية من الدرجة الثانية هي الصورة الحسابية الأبسط.
في المثلث الأول لدينا \((X_1,L_1)=(38,17)\). وبما أن \(38\equiv-2\pmod{5}\)، فإننا نأخذ \(\sigma=-1\)، ومن ثم
$$m=\frac{38+2}{5}=8,\qquad b=16,\qquad h=15.$$
وبالفعل \(15^2+8^2=17^2\)، أي إن هذا المثلث يحقق الحالة \(h=b-1\).
إذا ضربنا مرة واحدة في \(9+4\sqrt{5}\) نحصل على الحل التالي:
$$38+17\sqrt{5}\to682+305\sqrt{5}.$$
الآن \(682\equiv2\pmod{5}\)، ولذلك \(\sigma=+1\)، فنجد
$$m=\frac{682-2}{5}=136,\qquad b=272,\qquad h=273.$$
إذن المثلث الثاني يحقق \(h=b+1\). ولأن \(X_{n+1}\equiv-X_n\pmod{5}\)، فإن الباقيين \(2\) و\(-2\) يتعاقبان، وبالتالي تتعاقب العائلة كلها بين الحالتين \(h=b-1\) و\(h=b+1\).
تنفيذات C++ وPython وJava لا تعيد حل معادلة بيل أثناء التشغيل، بل تبدأ مباشرة من أول قيمتين لطول الساق وهما \(17\) و\(305\). ولأن المطلوب هو مجموع أول اثنتي عشرة قيمة فقط، فإن المجموع التراكمي يبدأ من الحد الأول.
في كل دورة من الحلقة يُضاف الحد الحالي إلى المجموع، ثم يُحسب الحد التالي بواسطة \(L_{n+2}=18L_{n+1}-L_n\)، وبعد ذلك تُزاح آخر قيمتين خطوة إلى الأمام. يحتوي تنفيذ C++ أيضًا على فحص صغير مدمج لأول حدين ويمكنه تغيير عدد المثلثات المولدة، بينما يثبت تنفيذَا Python وJava العدد عند اثني عشر حدًا. في جميع اللغات، البرنامج ليس إلا تمثيلًا مضغوطًا لنفس المتتالية المشتقة من معادلة بيل.
بالنسبة إلى المثلثات الاثني عشر المطلوبة، يكون زمن التنفيذ ثابتًا. وبصورة عامة، فإن توليد أول \(N\) قيم من \(L\) بهذه العلاقة يحتاج إلى زمن \(O(N)\) ومساحة إضافية \(O(1)\).
تنمو القيم تقريبًا مثل \((9+4\sqrt{5})^n\)، لكن ضمن أول اثني عشر حدًا تبقى كل من الأطوال الفردية ومجموعها داخل مجال الأعداد الصحيحة الموقعة ذات 64 بت. ولهذا تستطيع تنفيذات C++ وJava استخدام أعداد صحيحة ثابتة العرض، بينما يتعامل Python مع الحساب نفسه بأعداد صحيحة ذات دقة غير محدودة.