An almost equilateral triangle has integer side lengths of the form \((a,a,a\pm1)\). The task is to sum the perimeters of all such triangles whose area is also an integer and whose perimeter does not exceed \(10^9\).
A direct search over all possible side lengths would be wasteful, because the bound is enormous. The key observation used by the implementations is that the integer-area condition can be rewritten as a Pell equation, and that Pell equation has a simple recurrence that generates every valid triangle in increasing order.
Write the third side as \(a+s\), where \(s\in\{-1,+1\}\). The two cases \(s=+1\) and \(s=-1\) correspond to the triangles \((a,a,a+1)\) and \((a,a,a-1)\).
Drop the altitude from the apex onto the side \(a+s\), and call that altitude \(h\). Because the triangle is isosceles, the altitude bisects the base, so Pythagoras gives
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
The area is then
$$A=\frac{a+s}{2}\,h.$$
So the geometric problem is equivalent to finding those values of \(a\) for which the expression on the right produces an integer altitude and therefore an integer area. For this problem, everything reduces to understanding the arithmetic of that altitude.
Starting from the formula above, multiply by 12 and rearrange:
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
Therefore
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
If we define
$$x=\frac{3a-s}{2},\qquad y=h,$$
then every valid almost equilateral triangle gives a positive integer solution of
$$x^2-3y^2=1.$$
This Pell equation is the central mathematical object in the solution. Instead of testing side lengths directly, the implementations iterate through Pell solutions and reconstruct the corresponding triangles.
The reduction is reversible. Given a positive solution \((x,y)\) of \(x^2-3y^2=1\), try \(s=+1\) and \(s=-1\) in
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
If \(a\) is an integer greater than 1, then \((a,a,a+s)\) is a non-degenerate almost equilateral triangle with altitude exactly \(y\). Its area is
$$A=\frac{a+s}{2}\,y.$$
For each Pell state, at most one sign works. That is exactly what the code checks: it tries both branches and keeps only the one for which \((2x+s)\) is divisible by 3 and produces a positive side length. The two families alternate, giving a long-base triangle, then a short-base triangle, then long-base again, and so on.
The Pell equation \(x^2-3y^2=1\) has fundamental positive solution \(2+\sqrt{3}\). All positive solutions are generated by powers of this unit:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
Multiplying a solution by \(2+\sqrt{3}\) gives the recurrence used verbatim in the implementations:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
starting from \((x_1,y_1)=(2,1)\).
The Pell invariant is preserved exactly, because
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
The initial state \((2,1)\) only leads to the degenerate short-base candidate \(a=1\), so the first real triangle appears one step later. After that, both \(x\) and \(y\) grow exponentially, so the valid triangles are produced in strictly increasing size.
After one Pell update, the state becomes \((x,y)=(7,4)\). Here \(2x+1=15\) is divisible by 3, so \(a=5\) and \(s=+1\). This yields the triangle \((5,5,6)\), with altitude \(4\), area \(12\), and perimeter \(16\).
The next state is \((26,15)\). Now \(2x-1=51\) is divisible by 3, so \(a=17\) and \(s=-1\). That gives \((17,17,16)\), with altitude \(15\), area \(120\), and perimeter \(50\).
Continuing the same recurrence produces \((65,65,66)\) with perimeter \(196\), then \((241,241,240)\) with perimeter \(722\). Therefore the total perimeter below \(1000\) is
$$16+50+196+722=984,$$
which is a useful checkpoint for the method.
The C++, Python, and Java implementations use exactly the Pell formulation above. They never iterate over all possible side lengths and they never perform repeated square-root tests.
The loop stores only two integers, the current Pell solution \((x,y)\). They are initialized to the smallest positive solution \((2,1)\), and each iteration advances to the next solution using
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
with the old values on the right-hand side. This keeps the computation entirely in integer arithmetic.
For every state, the implementation checks both \(s=+1\) and \(s=-1\). It computes \(a=(2x+s)/3\), discards the branch unless \(a\) is an integer greater than 1, then forms the perimeter \(P=3a+s\). If \(P\le 10^9\), that perimeter is added to the running sum.
Because exactly one branch can succeed for each nontrivial Pell state, each iteration contributes at most one triangle. The altitude is already encoded in \(y\), so no extra geometric verification is needed.
The Pell solutions grow roughly by a factor of \(2+\sqrt{3}\approx 3.732\) at each step. Once an iteration produces no admissible perimeter and the current state has already grown past the smallest possible future candidate, every later state is larger as well. That monotonic growth is why the search ends after only a handful of iterations.
Each loop iteration uses only a constant amount of integer arithmetic, so the time per iteration is \(O(1)\). The number of iterations is \(O(\log L)\) for perimeter bound \(L\), because Pell solutions grow exponentially.
For \(L=10^9\), the recurrence produces only 14 valid triangles before the bound is exceeded. Memory usage is \(O(1)\), since the implementation stores only the current Pell state and the running perimeter sum.
Ein fast gleichseitiges Dreieck hat ganzzahlige Seiten der Form \((a,a,a\pm1)\). Gesucht ist die Summe der Umfänge aller solchen Dreiecke, deren Fläche ebenfalls ganzzahlig ist und deren Umfang \(10^9\) nicht überschreitet.
Eine direkte Suche über alle möglichen Seitenlängen wäre unpraktisch, weil die Schranke riesig ist. Der entscheidende Schritt der Implementierungen besteht darin, die Flächenbedingung in eine Pell-Gleichung umzuschreiben. Diese Pell-Gleichung besitzt eine kurze Rekurrenz, die alle gültigen Dreiecke der Größe nach erzeugt.
Schreibe die dritte Seite als \(a+s\) mit \(s\in\{-1,+1\}\). Die beiden Fälle \(s=+1\) und \(s=-1\) entsprechen also den Dreiecken \((a,a,a+1)\) und \((a,a,a-1)\).
Fällt man vom Scheitel die Höhe auf die Seite \(a+s\), so sei diese Höhe \(h\). Weil das Dreieck gleichschenklig ist, halbiert die Höhe die Basis. Mit Pythagoras folgt
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
Die Fläche ist damit
$$A=\frac{a+s}{2}\,h.$$
Das geometrische Problem reduziert sich also darauf, genau diejenigen Werte von \(a\) zu finden, für die diese Höhe ganzzahlig ist und damit auch die Fläche ganzzahlig wird. Bei diesem Problem steckt die gesamte Arithmetik in der Höhe.
Multipliziert man die Gleichung für \(h^2\) mit 12 und formt um, erhält man
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
Daraus folgt
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
Definiert man nun
$$x=\frac{3a-s}{2},\qquad y=h,$$
so liefert jedes gültige fast gleichseitige Dreieck eine positive ganzzahlige Lösung von
$$x^2-3y^2=1.$$
Diese Pell-Gleichung ist das zentrale mathematische Objekt der Lösung. Statt Seitenlängen direkt zu testen, laufen die Implementierungen die Pell-Lösungen ab und rekonstruieren daraus die Dreiecke.
Die Reduktion ist umkehrbar. Ist \((x,y)\) eine positive Lösung von \(x^2-3y^2=1\), dann versucht man \(s=+1\) und \(s=-1\) in
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
Ist \(a\) eine ganze Zahl größer als 1, dann ist \((a,a,a+s)\) ein nicht entartetes fast gleichseitiges Dreieck, dessen Höhe genau \(y\) ist. Seine Fläche lautet
$$A=\frac{a+s}{2}\,y.$$
Für jeden Pell-Zustand kann höchstens ein Vorzeichen funktionieren. Genau das prüft der Code: Er testet beide Zweige und behält nur denjenigen, für den \((2x+s)\) durch 3 teilbar ist und eine positive Seitenlänge ergibt. Die beiden Dreiecksfamilien wechseln sich dadurch ab.
Die Pell-Gleichung \(x^2-3y^2=1\) besitzt die fundamentale positive Lösung \(2+\sqrt{3}\). Alle positiven Lösungen entstehen aus Potenzen dieser Einheit:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
Die Multiplikation mit \(2+\sqrt{3}\) liefert genau die in den Implementierungen verwendete Rekurrenz:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
beginnend mit \((x_1,y_1)=(2,1)\).
Die Pell-Invariante bleibt exakt erhalten, denn
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
Der Anfangszustand \((2,1)\) führt nur auf den entarteten Kurz-Basis-Fall \(a=1\); das erste echte Dreieck erscheint also erst einen Schritt später. Danach wachsen sowohl \(x\) als auch \(y\) exponentiell, und die gültigen Dreiecke erscheinen streng aufsteigend.
Nach einem Pell-Schritt erhält man \((x,y)=(7,4)\). Hier ist \(2x+1=15\) durch 3 teilbar, also \(a=5\) und \(s=+1\). Das ergibt das Dreieck \((5,5,6)\) mit Höhe \(4\), Fläche \(12\) und Umfang \(16\).
Der nächste Zustand ist \((26,15)\). Nun ist \(2x-1=51\) durch 3 teilbar, also \(a=17\) und \(s=-1\). Daraus folgt \((17,17,16)\) mit Höhe \(15\), Fläche \(120\) und Umfang \(50\).
Setzt man die Rekurrenz fort, entstehen \((65,65,66)\) mit Umfang \(196\) und anschließend \((241,241,240)\) mit Umfang \(722\). Damit ist die Umfangssumme unter \(1000\)
$$16+50+196+722=984,$$
was ein nützlicher Kontrollwert für die Methode ist.
Die C++-, Python- und Java-Implementierungen arbeiten direkt mit dieser Pell-Darstellung. Sie iterieren weder über alle möglichen Seitenlängen noch führen sie wiederholt Wurzeltests aus.
Die Schleife speichert nur zwei ganze Zahlen, nämlich die aktuelle Pell-Lösung \((x,y)\). Diese wird auf die kleinste positive Lösung \((2,1)\) initialisiert, und jede Iteration springt mit
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
unter Verwendung der alten Werte zur nächsten Lösung weiter. Die gesamte Rechnung bleibt damit rein ganzzahlig.
Für jeden Zustand prüft die Implementierung die beiden Fälle \(s=+1\) und \(s=-1\). Sie berechnet \(a=(2x+s)/3\), verwirft den Zweig, falls \(a\) keine ganze Zahl größer als 1 ist, und bildet dann den Umfang \(P=3a+s\). Gilt \(P\le 10^9\), wird dieser Umfang zur Summe addiert.
Weil pro nichttrivialem Pell-Zustand genau ein Zweig erfolgreich sein kann, liefert jede Iteration höchstens ein Dreieck. Die Höhe steckt bereits in \(y\), daher braucht der Code keine weitere geometrische Prüfung.
Die Pell-Lösungen wachsen ungefähr mit dem Faktor \(2+\sqrt{3}\approx 3{,}732\) pro Schritt. Sobald eine Iteration keinen zulässigen Umfang mehr liefert und der aktuelle Zustand bereits oberhalb des kleinsten möglichen zukünftigen Kandidaten liegt, sind alle späteren Zustände erst recht zu groß. Genau diese Monotonie macht die Suche so kurz.
Jede Iteration benötigt nur konstant viele ganzzahlige Operationen, also \(O(1)\) Zeit. Die Anzahl der Iterationen ist \(O(\log L)\) für eine Umfangsgrenze \(L\), weil die Pell-Lösungen exponentiell wachsen.
Für \(L=10^9\) entstehen nur 14 gültige Dreiecke, bevor die Schranke überschritten wird. Der Speicherverbrauch ist \(O(1)\), da nur der aktuelle Pell-Zustand und die laufende Umfangssumme gehalten werden.
Neredeyse eşkenar bir üçgenin kenarları \((a,a,a\pm1)\) biçimindedir. İstenen şey, alanı da tamsayı olan ve çevresi \(10^9\) değerini aşmayan bütün bu üçgenlerin çevre toplamını bulmaktır.
Olası tüm kenar uzunluklarını tek tek denemek verimsiz olur; çünkü üst sınır çok büyüktür. Uygulamaların kullandığı temel fikir, tamsayı alan koşulunu bir Pell denklemine dönüştürmektir. Bu denklem, bütün geçerli üçgenleri artan sırayla üreten kısa bir yineleme verir.
Üçüncü kenarı \(a+s\) olarak yazalım; burada \(s\in\{-1,+1\}\). Böylece \(s=+1\) durumu \((a,a,a+1)\), \(s=-1\) durumu ise \((a,a,a-1)\) üçgenine karşılık gelir.
Tepeden \(a+s\) tabanına indirilen yüksekliğe \(h\) diyelim. Üçgen ikizkenar olduğu için bu yükseklik tabanı iki eşit parçaya böler ve Pisagor bize
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}$$
eşitliğini verir. Alan ise
$$A=\frac{a+s}{2}\,h$$
olur. Dolayısıyla geometrik problem, tam olarak hangi \(a\) değerlerinde bu yüksekliğin tamsayı olduğunu anlamaya indirgenir. Bu soruda bütün aritmetik yapı yükseklik içinde saklıdır.
Yukarıdaki bağıntıyı 12 ile çarpıp düzenlersek
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2$$
elde edilir. Buradan
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1$$
sonucu çıkar. Şimdi
$$x=\frac{3a-s}{2},\qquad y=h$$
tanımlarını yaparsak, her geçerli neredeyse eşkenar üçgen şu denklemin pozitif tamsayı çözümünü verir:
$$x^2-3y^2=1.$$
Çözümün merkezindeki matematiksel nesne budur. Uygulamalar kenarları doğrudan taramak yerine Pell çözümlerini üretir ve üçgenleri bu çözümlerden geri kurar.
Dönüşüm tersine de işler. \(x^2-3y^2=1\) denkleminin pozitif bir \((x,y)\) çözümü verildiğinde
$$a=\frac{2x+s}{3},\qquad P=3a+s$$
formülünde \(s=+1\) ve \(s=-1\) ayrı ayrı denenir. Eğer \(a\), 1'den büyük bir tamsayıysa \((a,a,a+s)\) geçerli bir neredeyse eşkenar üçgendir ve yüksekliği tam olarak \(y\)'dir. Alan da
$$A=\frac{a+s}{2}\,y$$
olur. Her Pell durumunda en fazla bir işaret çalışır. Kodun iki dalı denemesi ve sadece \((2x+s)\) sayısı 3'e bölünebildiğinde ilerlemesi tam olarak bu yüzden doğrudur. Sonuçta uzun tabanlı ve kısa tabanlı aileler sırayla gelir.
\(x^2-3y^2=1\) Pell denkleminin temel pozitif çözümü \(2+\sqrt{3}\)'tür. Bütün pozitif çözümler bu birimin kuvvetlerinden gelir:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
\(2+\sqrt{3}\) ile çarpmak, uygulamalarda doğrudan kullanılan yinelemeyi verir:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
başlangıç durumu \((x_1,y_1)=(2,1)\) olmak üzere.
Pell değişmezi tam olarak korunur; çünkü
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2$$
eşitliği sağlanır. İlk durum \((2,1)\) yalnızca \(a=1\) olan yoz kısa-taban adayını verdiği için ilk gerçek üçgen bir sonraki adımda ortaya çıkar. Ondan sonra \(x\) ve \(y\) üstel büyür; dolayısıyla geçerli üçgenler de sıkı biçimde artan sırada üretilir.
Bir Pell adımı sonrasında \((x,y)=(7,4)\) elde edilir. Burada \(2x+1=15\) sayısı 3'e bölünür; dolayısıyla \(a=5\) ve \(s=+1\) olur. Bu da \((5,5,6)\) üçgenini verir: yükseklik \(4\), alan \(12\), çevre \(16\).
Bir sonraki durum \((26,15)\)'tir. Bu kez \(2x-1=51\) sayısı 3'e bölünür; yani \(a=17\) ve \(s=-1\). Böylece \((17,17,16)\) üçgeni elde edilir: yükseklik \(15\), alan \(120\), çevre \(50\).
Aynı yineleme devam ettiğinde \((65,65,66)\) için çevre \(196\), \((241,241,240)\) için ise çevre \(722\) gelir. O halde \(1000\) altındaki toplam çevre
$$16+50+196+722=984$$
olur. Bu değer yöntem için iyi bir kontrol noktasıdır.
C++, Python ve Java uygulamaları yukarıdaki Pell formülasyonunu doğrudan kullanır. Olası tüm kenar uzunluklarını taramazlar ve tekrar tekrar karekök testi yapmazlar.
Döngüde yalnızca iki tamsayı tutulur: mevcut Pell çözümü \((x,y)\). Başlangıçta en küçük pozitif çözüm \((2,1)\) alınır ve her iterasyonda
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
güncellemesiyle, sağ tarafta eski değerler kullanılarak, bir sonraki çözüme geçilir. Böylece hesaplama tamamen tamsayı aritmetiğiyle yürür.
Her adımda uygulama \(s=+1\) ve \(s=-1\) durumlarını ayrı ayrı dener. \(a=(2x+s)/3\) hesaplanır; \(a\) 1'den büyük bir tamsayı değilse o dal atılır. Sonra \(P=3a+s\) çevresi oluşturulur ve \(P\le 10^9\) ise toplam içine eklenir.
Önemsiz olmayan her Pell durumunda en fazla bir dal başarılı olabildiğinden, her iterasyon en fazla bir üçgen üretir. Yükseklik zaten \(y\) içinde kodlandığı için ek bir geometrik doğrulama gerekmez.
Pell çözümleri her adımda yaklaşık \(2+\sqrt{3}\approx 3{,}732\) katsayısıyla büyür. Bir iterasyon artık sınırın altında hiçbir çevre üretmiyorsa ve mevcut durum da gelecekte oluşabilecek en küçük adayın ötesine geçmişse, sonraki bütün durumlar daha da büyük olacaktır. Döngünün çok kısa sürmesinin nedeni bu tekdüze büyümedir.
Her iterasyon sabit sayıda tamsayı işlemi yapar; dolayısıyla iterasyon başına süre \(O(1)\)'dir. İterasyon sayısı ise çevre sınırı \(L\) için \(O(\log L)\)'dir; çünkü Pell çözümleri üstel büyür.
\(L=10^9\) için yineleme yalnızca 14 geçerli üçgen üretir. Bellek kullanımı \(O(1)\)'dir; çünkü sadece güncel Pell durumu ve birikmiş çevre toplamı saklanır.
Un triángulo casi equilátero tiene lados enteros de la forma \((a,a,a\pm1)\). Hay que sumar los perímetros de todos esos triángulos cuya área también es entera y cuyo perímetro no supera \(10^9\).
Buscar directamente entre todas las longitudes posibles sería poco eficiente, porque la cota es enorme. La idea central de las implementaciones es reescribir la condición de área entera como una ecuación de Pell. Esa ecuación tiene una recurrencia corta que genera todos los triángulos válidos en orden creciente.
Escribamos el tercer lado como \(a+s\), con \(s\in\{-1,+1\}\). Los casos \(s=+1\) y \(s=-1\) corresponden a \((a,a,a+1)\) y \((a,a,a-1)\).
Trazamos la altura desde el vértice hasta el lado \(a+s\) y la llamamos \(h\). Como el triángulo es isósceles, esa altura parte la base en dos mitades iguales, y por Pitágoras se obtiene
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
El área es entonces
$$A=\frac{a+s}{2}\,h.$$
Así, el problema geométrico equivale a encontrar aquellos valores de \(a\) para los que la altura es entera y, por tanto, el área también lo es. En este problema, toda la aritmética importante está concentrada en la altura.
Multiplicando la expresión de \(h^2\) por 12 y reordenando, se llega a
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
Por lo tanto,
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
Si definimos
$$x=\frac{3a-s}{2},\qquad y=h,$$
entonces todo triángulo casi equilátero válido produce una solución entera positiva de
$$x^2-3y^2=1.$$
Esta ecuación de Pell es el objeto matemático central de la solución. En vez de probar lados uno por uno, las implementaciones recorren soluciones de Pell y reconstruyen los triángulos a partir de ellas.
La transformación es reversible. Dada una solución positiva \((x,y)\) de \(x^2-3y^2=1\), se prueban \(s=+1\) y \(s=-1\) en
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
Si \(a\) es un entero mayor que 1, entonces \((a,a,a+s)\) es un triángulo casi equilátero no degenerado cuya altura es exactamente \(y\). Su área vale
$$A=\frac{a+s}{2}\,y.$$
Para cada estado de Pell, como mucho un signo puede funcionar. Eso es exactamente lo que comprueba el código: intenta ambas ramas y conserva solo aquella en la que \((2x+s)\) es divisible por 3 y produce una longitud positiva. Por eso las dos familias de triángulos se alternan.
La ecuación de Pell \(x^2-3y^2=1\) tiene solución fundamental positiva \(2+\sqrt{3}\). Todas las soluciones positivas aparecen como potencias de esta unidad:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
Multiplicar por \(2+\sqrt{3}\) produce la recurrencia usada literalmente en las implementaciones:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
partiendo de \((x_1,y_1)=(2,1)\).
El invariante de Pell se preserva exactamente, porque
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
El estado inicial \((2,1)\) solo conduce al caso degenerado de base corta con \(a=1\), de modo que el primer triángulo real aparece un paso después. A partir de ahí, \(x\) y \(y\) crecen exponencialmente y los triángulos válidos aparecen en tamaño estrictamente creciente.
Tras una actualización de Pell, el estado es \((x,y)=(7,4)\). Aquí \(2x+1=15\) es divisible por 3, así que \(a=5\) y \(s=+1\). Eso da el triángulo \((5,5,6)\), con altura \(4\), área \(12\) y perímetro \(16\).
El siguiente estado es \((26,15)\). Ahora \(2x-1=51\) es divisible por 3, así que \(a=17\) y \(s=-1\). Se obtiene \((17,17,16)\), con altura \(15\), área \(120\) y perímetro \(50\).
Continuando la misma recurrencia aparecen \((65,65,66)\) con perímetro \(196\) y luego \((241,241,240)\) con perímetro \(722\). Por tanto, la suma de perímetros por debajo de \(1000\) es
$$16+50+196+722=984,$$
lo cual sirve como comprobación útil del método.
Las implementaciones en C++, Python y Java usan directamente la formulación mediante Pell. No recorren todos los lados posibles ni realizan pruebas repetidas de raíces cuadradas.
El bucle mantiene solo dos enteros: la solución actual de Pell \((x,y)\). Se inicializa con la solución positiva más pequeña \((2,1)\), y cada iteración avanza a la siguiente mediante
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
usando a la derecha los valores antiguos. Toda la computación queda así en aritmética entera.
En cada estado, la implementación prueba \(s=+1\) y \(s=-1\). Calcula \(a=(2x+s)/3\), descarta la rama salvo que \(a\) sea un entero mayor que 1, y luego forma el perímetro \(P=3a+s\). Si \(P\le 10^9\), ese perímetro se añade al acumulador.
Como en cada estado no trivial puede funcionar a lo sumo una rama, cada iteración aporta como mucho un triángulo. La altura ya está codificada en \(y\), así que no hace falta una verificación geométrica adicional.
Las soluciones de Pell crecen aproximadamente por un factor \(2+\sqrt{3}\approx 3.732\) en cada paso. Una vez que una iteración ya no produce ningún perímetro por debajo del límite y el estado actual ha superado el candidato futuro más pequeño posible, todos los estados posteriores serán todavía mayores. Esa monotonía explica por qué la búsqueda termina tan rápido.
Cada iteración hace solo una cantidad constante de aritmética entera, así que el coste por iteración es \(O(1)\). El número de iteraciones es \(O(\log L)\) para una cota de perímetro \(L\), porque las soluciones de Pell crecen exponencialmente.
Para \(L=10^9\), la recurrencia produce solo 14 triángulos válidos antes de sobrepasar la cota. El uso de memoria es \(O(1)\), ya que solo se guardan el estado actual de Pell y la suma acumulada de perímetros.
“几乎等边”三角形的三条边形如 \((a,a,a\pm1)\)，并且都要求是整数。题目要求把所有面积也是整数、且周长不超过 \(10^9\) 的这类三角形的周长全部加起来。
如果直接枚举边长，搜索范围会大到完全不划算。实现真正利用的关键事实是：整数面积条件可以被改写成一个 Pell 方程，而这个 Pell 方程有一个非常短的整数递推，可以按从小到大的顺序生成全部有效三角形。
把第三条边写成 \(a+s\)，其中 \(s\in\{-1,+1\}\)。于是 \(s=+1\) 对应 \((a,a,a+1)\)，\(s=-1\) 对应 \((a,a,a-1)\)。
从顶点向边 \(a+s\) 作高，记为 \(h\)。由于三角形是等腰三角形，这条高会把底边平分，于是由勾股定理可得
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
面积因此为
$$A=\frac{a+s}{2}\,h.$$
所以这个几何问题实际上等价于：找出哪些 \(a\) 会让这条高成为整数，从而面积也成为整数。对这道题来说，真正需要分析的算术对象不是边长本身，而是这条高。
把上面的 \(h^2\) 公式乘以 12 并整理，可以得到
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
因此
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
现在定义
$$x=\frac{3a-s}{2},\qquad y=h,$$
那么每一个有效的几乎等边三角形，都会对应到 Pell 方程
$$x^2-3y^2=1$$
的一个正整数解。这个方程就是整道解法的核心。实现并不是对边长做暴力检查，而是沿着 Pell 方程的整数解前进，再把三角形反推回来。
上述变换可以反向使用。给定 \(x^2-3y^2=1\) 的一个正整数解 \((x,y)\)，分别尝试 \(s=+1\) 和 \(s=-1\)，代入
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
如果得到的 \(a\) 是大于 1 的整数，那么 \((a,a,a+s)\) 就是一个非退化的几乎等边三角形，而且它的高恰好就是 \(y\)。面积随之变成
$$A=\frac{a+s}{2}\,y.$$
对每一个 Pell 状态来说，至多只有一个符号能成立。这正是实现里“两个分支都试一次，再用整除条件筛掉不可能者”的原因。于是两类三角形会交替出现：一次是底边较长，一次是底边较短。
Pell 方程 \(x^2-3y^2=1\) 的最小正解对应于 \(2+\sqrt{3}\)。所有正解都可以写成
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
把一个解乘以 \(2+\sqrt{3}\)，就得到实现中直接使用的递推：
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
初始值是 \((x_1,y_1)=(2,1)\)。
Pell 不变量被精确保留，因为
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
最初的状态 \((2,1)\) 只会对应到退化的短底边候选 \(a=1\)，所以第一个真正的三角形要到下一步才出现。之后 \(x\) 和 \(y\) 都按指数级增长，因此有效三角形会按严格递增的大小依次出现。
做一次 Pell 更新后得到 \((x,y)=(7,4)\)。这时 \(2x+1=15\) 可以被 3 整除，所以 \(a=5\)，\(s=+1\)。于是得到三角形 \((5,5,6)\)，高为 \(4\)，面积为 \(12\)，周长为 \(16\)。
下一组状态是 \((26,15)\)。这时 \(2x-1=51\) 可以被 3 整除，所以 \(a=17\)，\(s=-1\)。于是得到 \((17,17,16)\)，高为 \(15\)，面积为 \(120\)，周长为 \(50\)。
继续递推，还会得到 \((65,65,66)\)，周长 \(196\)；再下一项是 \((241,241,240)\)，周长 \(722\)。因此在上界 \(1000\) 之内，周长总和是
$$16+50+196+722=984,$$
这也是检验推导和程序是否一致的一个很好例子。
C++、Python 和 Java 实现都直接使用上面的 Pell 表述。它们不会去遍历所有可能的边长，也不会对每个候选反复做平方根判定。
整个循环只保存两个整数，也就是当前的 Pell 解 \((x,y)\)。初始值取最小正解 \((2,1)\)，然后每一步用
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
更新到下一组解，其中右边使用更新前的旧值。于是整个过程始终停留在整数运算里。
对每一组 \((x,y)\)，实现都会分别尝试 \(s=+1\) 和 \(s=-1\)。先计算 \(a=(2x+s)/3\)，如果 \(a\) 不是大于 1 的整数，就直接丢弃该分支；否则再形成周长 \(P=3a+s\)。当 \(P\le 10^9\) 时，就把它加到答案里。
由于每个非平凡 Pell 状态最多只会通过一个分支，所以每次迭代最多只贡献一个三角形。高已经编码在 \(y\) 里，因此不需要额外的几何校验。
Pell 解大约按 \(2+\sqrt{3}\approx 3.732\) 的倍数增长。一旦某次迭代已经没有任何周长落在界内，并且当前状态也已经超过未来可能出现的最小候选，那么之后的所有状态只会更大，不可能重新回到有效范围内。这就是整个搜索只需要极少几步的原因。
每次迭代都只做常数次整数运算，所以单次迭代的时间是 \(O(1)\)。由于 Pell 解按指数增长，周长上界为 \(L\) 时，迭代次数是 \(O(\log L)\)。
当 \(L=10^9\) 时，递推只会产出 14 个有效三角形。空间复杂度是 \(O(1)\)，因为程序只保存当前 Pell 状态和累计的周长和。
Почти равносторонний треугольник имеет целые стороны вида \((a,a,a\pm1)\). Нужно просуммировать периметры всех таких треугольников, у которых площадь тоже целая и периметр не превосходит \(10^9\).
Прямой перебор по всем возможным длинам сторон был бы неэффективен, потому что граница очень велика. Основная идея реализаций состоит в том, что условие целой площади сводится к уравнению Пелля. Это уравнение имеет короткую рекуррентную схему, которая порождает все допустимые треугольники в порядке возрастания.
Обозначим третью сторону как \(a+s\), где \(s\in\{-1,+1\}\). Тогда случаи \(s=+1\) и \(s=-1\) соответствуют треугольникам \((a,a,a+1)\) и \((a,a,a-1)\).
Опустим высоту из вершины на сторону \(a+s\) и обозначим её через \(h\). Поскольку треугольник равнобедренный, эта высота делит основание пополам, поэтому по теореме Пифагора
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
Площадь равна
$$A=\frac{a+s}{2}\,h.$$
Значит, геометрическая задача эквивалентна поиску тех значений \(a\), для которых высота оказывается целой, а вместе с ней и площадь. В этой задаче вся существенная арифметика сосредоточена именно в высоте.
Умножим выражение для \(h^2\) на 12 и приведём подобные члены:
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
Следовательно,
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
Если теперь ввести
$$x=\frac{3a-s}{2},\qquad y=h,$$
то каждый допустимый почти равносторонний треугольник даёт положительное целочисленное решение уравнения
$$x^2-3y^2=1.$$
Именно это уравнение Пелля является центральным объектом решения. Вместо прямой проверки сторон реализации перебирают решения уравнения Пелля и восстанавливают по ним треугольники.
Преобразование обратимо. Если \((x,y)\) — положительное решение уравнения \(x^2-3y^2=1\), то нужно попробовать \(s=+1\) и \(s=-1\) в формулах
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
Если \(a\) оказывается целым числом больше 1, то \((a,a,a+s)\) — невырожденный почти равносторонний треугольник, а его высота равна ровно \(y\). Площадь при этом равна
$$A=\frac{a+s}{2}\,y.$$
Для каждого состояния Пелля может подойти не более одного знака. Именно это делает код: он пробует обе ветви и оставляет только ту, в которой \((2x+s)\) делится на 3 и даёт положительную длину стороны. Поэтому две семейства треугольников чередуются.
Уравнение Пелля \(x^2-3y^2=1\) имеет фундаментальное положительное решение \(2+\sqrt{3}\). Все положительные решения получаются как степени этой единицы:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
Умножение на \(2+\sqrt{3}\) даёт ровно ту рекуррентность, которая используется в реализациях:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
с начальным состоянием \((x_1,y_1)=(2,1)\).
Инвариант Пелля сохраняется точно, потому что
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
Начальное состояние \((2,1)\) ведёт только к вырожденному случаю короткого основания \(a=1\), поэтому первый настоящий треугольник появляется лишь на следующем шаге. После этого \(x\) и \(y\) растут экспоненциально, а допустимые треугольники появляются в строго возрастающем порядке.
После одного шага рекуррентности получаем \((x,y)=(7,4)\). Здесь \(2x+1=15\) делится на 3, значит \(a=5\) и \(s=+1\). Получаем треугольник \((5,5,6)\) с высотой \(4\), площадью \(12\) и периметром \(16\).
Следующее состояние — \((26,15)\). Теперь \(2x-1=51\) делится на 3, так что \(a=17\) и \(s=-1\). Это даёт треугольник \((17,17,16)\) с высотой \(15\), площадью \(120\) и периметром \(50\).
Продолжая ту же рекуррентность, получаем \((65,65,66)\) с периметром \(196\), а затем \((241,241,240)\) с периметром \(722\). Поэтому сумма допустимых периметров ниже \(1000\) равна
$$16+50+196+722=984,$$
и это удобная контрольная точка для метода.
Реализации на C++, Python и Java используют описанную выше форму через уравнение Пелля напрямую. Они не перебирают все возможные стороны и не делают повторяющихся проверок квадратных корней.
В цикле хранятся только два целых числа: текущее решение Пелля \((x,y)\). Начинают с наименьшего положительного решения \((2,1)\), а затем каждый шаг переходят к следующему с помощью
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
с использованием старых значений в правой части. Поэтому вся арифметика остаётся целочисленной.
Для каждого состояния реализация проверяет оба случая \(s=+1\) и \(s=-1\). Вычисляется \(a=(2x+s)/3\); если \(a\) не является целым числом больше 1, соответствующая ветвь сразу отбрасывается. Затем строится периметр \(P=3a+s\), и если \(P\le 10^9\), он добавляется к сумме.
Поскольку в каждом нетривиальном состоянии Пелля может сработать не более одной ветви, одна итерация даёт максимум один треугольник. Высота уже закодирована в \(y\), поэтому дополнительная геометрическая проверка не требуется.
Решения уравнения Пелля растут примерно с множителем \(2+\sqrt{3}\approx 3.732\) на каждом шаге. Как только очередная итерация больше не даёт допустимого периметра и текущее состояние уже прошло минимально возможный будущий кандидат, все последующие состояния будут только больше. Именно эта монотонность и делает поиск очень коротким.
Каждая итерация выполняет только постоянное число целочисленных операций, то есть занимает \(O(1)\) времени. Число итераций равно \(O(\log L)\) для ограничения по периметру \(L\), потому что решения Пелля растут экспоненциально.
При \(L=10^9\) рекуррентность порождает лишь 14 допустимых треугольников. Память равна \(O(1)\), поскольку хранятся только текущее состояние Пелля и накопленная сумма периметров.
المثلث شبه المتساوي الأضلاع له أضلاع صحيحة من الصورة \((a,a,a\pm1)\). المطلوب هو جمع محيطات جميع هذه المثلثات التي تكون مساحتها أيضًا عددًا صحيحًا ولا يتجاوز محيطها \(10^9\).
الفحص المباشر لكل القيم الممكنة لـ \(a\) غير عملي لأن الحد كبير جدًا. الفكرة الأساسية المستخدمة في التنفيذات هي أن شرط المساحة الصحيحة يمكن تحويله إلى معادلة بِل، وهذه المعادلة تعطي تكرارًا قصيرًا يولّد جميع المثلثات الصالحة بترتيب تصاعدي.
لنكتب الضلع الثالث على الصورة \(a+s\) حيث \(s\in\{-1,+1\}\). الحالة \(s=+1\) تمثل المثلث \((a,a,a+1)\)، والحالة \(s=-1\) تمثل \((a,a,a-1)\).
لننزل ارتفاعًا من الرأس إلى الضلع \(a+s\) ولنسمّه \(h\). بما أن المثلث متساوي الساقين فإن هذا الارتفاع ينصف القاعدة، ومن ثم يعطي فيثاغورس
$$h^2=a^2-\left(\frac{a+s}{2}\right)^2=\frac{3a^2-2sa-1}{4}.$$
وعندئذ تكون المساحة
$$A=\frac{a+s}{2}\,h.$$
إذًا تصبح المسألة الهندسية مكافئة لتحديد قيم \(a\) التي تجعل هذا الارتفاع عددًا صحيحًا، وبالتالي تجعل المساحة عددًا صحيحًا أيضًا. في هذه المسألة تختبئ البنية الحسابية كلها داخل الارتفاع.
إذا ضربنا صيغة \(h^2\) في 12 وأعدنا الترتيب نحصل على
$$12h^2=9a^2-6sa-3,$$
$$12h^2+4=9a^2-6sa+1=(3a-s)^2.$$
ومن ثم
$$\left(\frac{3a-s}{2}\right)^2-3h^2=1.$$
إذا عرّفنا الآن
$$x=\frac{3a-s}{2},\qquad y=h,$$
فإن كل مثلث شبه متساوي الأضلاع صالح يعطي حلًا صحيحًا موجبًا للمعادلة
$$x^2-3y^2=1.$$
هذه هي المعادلة المركزية في الحل. بدلًا من اختبار الأضلاع مباشرة، تقوم التنفيذات بتوليد حلول بِل ثم تعيد بناء المثلثات منها.
هذا التحويل قابل للعكس. فإذا أُعطي حل موجب \((x,y)\) للمعادلة \(x^2-3y^2=1\)، فإننا نجرب \(s=+1\) و\(s=-1\) في
$$a=\frac{2x+s}{3},\qquad P=3a+s.$$
إذا كانت قيمة \(a\) عددًا صحيحًا أكبر من 1، فالمثلث \((a,a,a+s)\) يكون مثلثًا غير منحل وشبه متساوي الأضلاع، ويكون ارتفاعه بالضبط هو \(y\). أما مساحته فهي
$$A=\frac{a+s}{2}\,y.$$
لكل حالة بِل يمكن أن ينجح اختيار واحد فقط من الإشارتين. ولهذا السبب يجرب الكود الفرعين ثم يحتفظ فقط بالفرع الذي تكون فيه \((2x+s)\) قابلة للقسمة على 3 وتعطي طول ضلع موجب. وهكذا تتناوب عائلتا المثلثات: مرة قاعدة أطول، ثم قاعدة أقصر، ثم أطول من جديد.
لمعادلة بِل \(x^2-3y^2=1\) الحل الموجب الأساسي \(2+\sqrt{3}\). وجميع الحلول الموجبة تأتي من قوى هذا العنصر:
$$x_n+y_n\sqrt{3}=(2+\sqrt{3})^n.$$
والضرب في \(2+\sqrt{3}\) يعطي التكرار المستخدم حرفيًا في التنفيذات:
$$x_{n+1}=2x_n+3y_n,\qquad y_{n+1}=x_n+2y_n,$$
بداية من \((x_1,y_1)=(2,1)\).
ويُحفَظ ثابت بِل تمامًا لأن
$$\bigl(2x+3y\bigr)^2-3\bigl(x+2y\bigr)^2=x^2-3y^2.$$
الحالة الابتدائية \((2,1)\) لا تعطي إلا المرشح المنحل ذي القاعدة الأقصر مع \(a=1\)، لذلك يظهر أول مثلث حقيقي بعد خطوة واحدة فقط. بعد ذلك يكبر كل من \(x\) و\(y\) نموًا أسيًا، فتظهر المثلثات الصالحة بترتيب تصاعدي صارم.
بعد خطوة واحدة من تكرار بِل تصبح الحالة \((x,y)=(7,4)\). هنا يكون \(2x+1=15\) قابلاً للقسمة على 3، ومن ثم \(a=5\) و\(s=+1\). وهذا يعطي المثلث \((5,5,6)\) بارتفاع \(4\)، ومساحة \(12\)، ومحيط \(16\).
الحالة التالية هي \((26,15)\). الآن \(2x-1=51\) قابل للقسمة على 3، ولذلك \(a=17\) و\(s=-1\). فنحصل على \((17,17,16)\) بارتفاع \(15\)، ومساحة \(120\)، ومحيط \(50\).
وبالاستمرار في التكرار نفسه نحصل على \((65,65,66)\) بمحيط \(196\)، ثم \((241,241,240)\) بمحيط \(722\). لذلك فإن مجموع المحيطات تحت الحد \(1000\) هو
$$16+50+196+722=984,$$
وهذا مثال فحص جيد للتأكد من صحة الاشتقاق والتنفيذ.
تستخدم تنفيذات C++ وPython وJava الصياغة المبنية على معادلة بِل مباشرة. فهي لا تمر على جميع أطوال الأضلاع الممكنة، ولا تكرر اختبارات الجذر التربيعي على نحو أعمى.
تحتفظ الحلقة بعددين صحيحين فقط، هما حل بِل الحالي \((x,y)\). تبدأ من أصغر حل موجب \((2,1)\)، ثم تنتقل في كل مرة إلى الحل التالي باستخدام
$$x\leftarrow 2x+3y,\qquad y\leftarrow x+2y$$
مع استخدام القيم القديمة في الطرف الأيمن. وبذلك تبقى الحسابات كلها ضمن الأعداد الصحيحة.
في كل حالة يجرب التنفيذ القيمتين \(s=+1\) و\(s=-1\). يُحسب \(a=(2x+s)/3\)، ويُرفض الفرع إذا لم تكن \(a\) عددًا صحيحًا أكبر من 1. بعد ذلك يُبنى المحيط \(P=3a+s\)، وإذا كان \(P\le 10^9\) يُضاف إلى المجموع.
وبما أن كل حالة بِل غير تافهة لا يمكن أن تنجح فيها إلا إشارة واحدة، فإن كل دورة تضيف في أقصى الأحوال مثلثًا واحدًا. والارتفاع موجود أصلًا في \(y\)، لذلك لا حاجة إلى تحقق هندسي إضافي.
تنمو حلول بِل تقريبًا بعامل \(2+\sqrt{3}\approx 3.732\) في كل خطوة. فإذا وصلت الحلقة إلى مرحلة لا تعطي فيها أي محيط داخل الحد، وكان الوضع الحالي قد تجاوز أصغر مرشح مستقبلي ممكن، فإن جميع الحالات التالية ستكون أكبر بالضرورة. هذه الرتابة هي السبب في أن البحث ينتهي بعد عدد قليل جدًا من الخطوات.
كل دورة تنفذ عددًا ثابتًا فقط من العمليات الصحيحة، لذا فإن زمن الدورة الواحدة هو \(O(1)\). وعدد الدورات يساوي \(O(\log L)\) عندما يكون حد المحيط هو \(L\)، لأن حلول بِل تنمو نموًا أسيًا.
عند \(L=10^9\) لا ينتج التكرار إلا 14 مثلثًا صالحًا قبل تجاوز الحد. واستهلاك الذاكرة هو \(O(1)\)، لأن التنفيذ يحتفظ فقط بحالة بِل الحالية وبالمجموع التراكمي للمحيطات.