We want the number of integer-sided triangles \((a,b,c)\) with perimeter at most \(75{,}000{,}000\) such that
$$a^2+b^2=c^2-1.$$
Equivalently, \(c^2=a^2+b^2+1\), so the longest side is only one unit of square-length beyond the right-triangle relation. By the law of cosines, the angle opposite \(c\) satisfies
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
which explains the title: the triangle is obtuse, but only barely.
The fast solution does not scan all possible side lengths. Instead it walks through a ternary tree of integer triples that preserves the quadratic form
$$Q(a,b,c)=c^2-a^2-b^2.$$
Once \(a\) and \(b\) are positive, the triangle inequality is automatic. Indeed,
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
so \(c \lt a+b\). The code still checks \(a+b \gt c\), but mathematically every positive solution already gives a genuine triangle.
The parity is also forced. Squares are \(0\) or \(1\) modulo \(4\), so
$$a^2+b^2+1\equiv c^2 \pmod 4$$
rules out the cases where one of \(a,b\) is odd or both are odd. Therefore every solution has
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
The smallest positive solution is then \((2,2,3)\).
Write a triple as the column vector \(t=(a,b,c)^T\). The implementations repeatedly apply the three matrices
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
If \(G=\mathrm{diag}(-1,-1,1)\), then \(Q(t)=t^T G t\), and each matrix satisfies
$$M_i^T G M_i=G.$$
So every transform preserves \(Q\):
$$Q(M_i t)=Q(t).$$
Since the root triple \((2,2,3)\) has \(Q=1\), every descendant automatically satisfies \(c^2-a^2-b^2=1\), or equivalently \(a^2+b^2=c^2-1\).
The search starts from
$$(2,2,3),$$
the smallest positive point on \(Q=1\). The three matrices above form a Berggren-type tree for this quadratic form: keeping orientation, repeated application generates the positive integer solutions without duplicates. The implementation relies on that structure, and the C++ version also confirms it against direct enumeration for several small perimeter bounds.
The equation is symmetric in \(a\) and \(b\), but the tree is built on ordered triples. To count each geometric triangle once, the algorithm uses the canonical orientation
$$a\le b.$$
That test is applied only when counting, not when traversing, because an intermediate state with \(a\gt b\) can still lead to later descendants with \(a\le b\).
Applying the three matrices to the root gives
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
All three satisfy
$$a^2+b^2+1=c^2.$$
The third child is not counted immediately because \(8\gt 4\). Nevertheless it cannot be discarded. Applying \(M_1\) once more gives
$$M_1(8,4,9)^T=(18,30,35)^T,$$
and now \(18\le 30\), so this branch contributes a new valid triangle. This is why the traversal keeps both orientations even though counting uses only one orientation.
The third coordinate of each child is
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
Because
$$c^2=a^2+b^2+1\gt (a-b)^2,$$
we have \(c\gt |a-b|\). Therefore
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
So the tree always moves toward larger triples. Once a node has perimeter \(a+b+c\gt P\), every deeper descendant is even larger, so a depth-first search with perimeter pruning visits exactly the finite portion of the tree that matters. In other words, the answer is
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
where \(\mathcal{T}\) is the ternary tree generated from \((2,2,3)\) by \(M_1,M_2,M_3\).
The C++, Python, and Java implementations perform an explicit depth-first search. They begin with the root triple \((2,2,3)\) on a stack, pop one triple at a time, compute its perimeter, and discard it immediately if the perimeter exceeds the limit.
If the node survives that test, the implementation increments the answer when \(a\le b\) and \(a+b\gt c\). The second condition is mathematically redundant for positive solutions of this equation, but keeping it in the code makes the intended triangle filter completely explicit.
Each visited node is then multiplied by the three fixed matrices. Children with any nonpositive coordinate are rejected, and children already above the perimeter limit are not pushed. Because the invariant \(c^2-a^2-b^2=1\) is preserved by construction, the fast path never needs a square-root check.
The C++ implementation also contains a direct verifier for several small perimeter values. That slower routine enumerates \(a\le b\), reconstructs \(c\) from \(a^2+b^2+1\), tests whether \(c\) is an integer, and compares the result with the tree-based count. Matching on those checkpoints is strong evidence that the matrix tree and the counting rule are aligned correctly before the large bound is used.
Let \(N(P)\) be the number of generated tree nodes with perimeter at most \(P\). Every visited node costs only constant work: one perimeter computation, one counting test, and three fixed \(3\times 3\) matrix applications. Therefore the running time is
$$O(N(P)).$$
This is output-sensitive: it depends on how many almost-right triangles actually exist below the perimeter bound, not on the much larger search box \(1\le a,b,c\le P\). The explicit DFS stack stores only the current frontier of a constant-branching tree, so the auxiliary memory is \(O(D(P))\), where \(D(P)\) is the maximum depth reached under the perimeter limit.
Gesucht ist die Anzahl ganzzahliger Dreiecke \((a,b,c)\) mit Umfang höchstens \(75{,}000{,}000\), für die
$$a^2+b^2=c^2-1$$
gilt. Äquivalent ist also \(c^2=a^2+b^2+1\): Die längste Seite ist nur um eine Quadrateinheit größer als im rechtwinkligen Fall. Mit dem Kosinussatz erhält man für den Winkel gegenüber von \(c\)
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
weshalb das Dreieck stumpf, aber nur ganz knapp stumpf ist.
Die schnelle Lösung durchsucht nicht alle möglichen Seitenlängen. Stattdessen verwendet sie einen ternären Baum ganzzahliger Transformationen, der die quadratische Form
$$Q(a,b,c)=c^2-a^2-b^2$$
erhält.
Sobald \(a\) und \(b\) positiv sind, ist die Dreiecksungleichung automatisch erfüllt. Denn
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
also gilt \(c \lt a+b\). Der Code prüft zwar trotzdem \(a+b \gt c\), mathematisch liefert aber jede positive Lösung bereits ein echtes Dreieck.
Auch die Parität ist fest vorgegeben. Quadrate sind modulo \(4\) nur \(0\) oder \(1\), daher erzwingt
$$a^2+b^2+1\equiv c^2 \pmod 4$$
dass weder genau eine von \(a,b\) ungerade noch beide ungerade sein können. Folglich gilt für jede Lösung
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
Die kleinste positive Lösung ist damit \((2,2,3)\).
Schreibe ein Tripel als Spaltenvektor \(t=(a,b,c)^T\). Die Implementierungen wenden wiederholt die drei Matrizen
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}$$
an. Setzt man \(G=\mathrm{diag}(-1,-1,1)\), so ist \(Q(t)=t^T G t\), und jede dieser Matrizen erfüllt
$$M_i^T G M_i=G.$$
Damit bleibt \(Q\) unter jeder Abbildung erhalten:
$$Q(M_i t)=Q(t).$$
Da das Wurzeltripel \((2,2,3)\) den Wert \(Q=1\) hat, erfüllt jeder Nachfolger automatisch \(c^2-a^2-b^2=1\), also \(a^2+b^2=c^2-1\).
Die Suche beginnt bei
$$(2,2,3).$$
Das ist der kleinste positive Punkt auf \(Q=1\). Die drei Matrizen bilden einen Berggren-artigen Baum für diese quadratische Form: Wenn man die Orientierung beibehält, erzeugt wiederholte Anwendung alle positiven ganzzahligen Lösungen ohne Duplikate. Darauf bauen die Implementierungen auf; zusätzlich vergleicht die C++-Version bei kleinen Umfangsgrenzen mit einer direkten Enumeration.
Die Gleichung ist zwar symmetrisch in \(a\) und \(b\), der Baum arbeitet aber mit geordneten Tripeln. Damit jedes geometrische Dreieck nur einmal gezählt wird, verwendet der Algorithmus die kanonische Orientierung
$$a\le b.$$
Diese Bedingung wird nur beim Zählen geprüft, nicht beim Traversieren, denn ein Zwischenzustand mit \(a\gt b\) kann später durchaus Nachfolger mit \(a\le b\) besitzen.
Wendet man die drei Matrizen auf die Wurzel an, erhält man
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
Alle drei erfüllen
$$a^2+b^2+1=c^2.$$
Das dritte Kind wird nicht sofort gezählt, weil \(8\gt 4\). Trotzdem darf es nicht abgeschnitten werden. Wendet man noch einmal \(M_1\) an, so entsteht
$$M_1(8,4,9)^T=(18,30,35)^T,$$
und jetzt gilt \(18\le 30\). Dieser Ast liefert also ein neues gültiges Dreieck. Genau deshalb werden beide Orientierungen traversiert, obwohl nur eine davon gezählt wird.
Die dritte Koordinate der drei Kinder lautet
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
Aus
$$c^2=a^2+b^2+1\gt (a-b)^2$$
folgt \(c\gt |a-b|\). Daher gilt
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
Der Baum bewegt sich also stets zu größeren Tripeln. Sobald ein Knoten den Umfang \(P\) überschreitet, sind alle tieferen Nachfolger erst recht zu groß. Eine Tiefensuche mit der Schranke \(a+b+c\le P\) besucht daher genau den endlichen relevanten Teil des Baums. Gesucht ist also
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
wobei \(\mathcal{T}\) der von \((2,2,3)\) durch \(M_1,M_2,M_3\) erzeugte ternäre Baum ist.
Die C++-, Python- und Java-Implementierungen führen eine explizite Tiefensuche aus. Sie starten mit dem Wurzeltripel \((2,2,3)\) auf einem Stack, entnehmen jeweils einen Knoten, berechnen dessen Umfang und verwerfen ihn sofort, falls die Grenze überschritten ist.
Besteht der Knoten diesen Test, wird der Zähler erhöht, wenn \(a\le b\) und \(a+b\gt c\) gilt. Die zweite Bedingung ist für positive Lösungen dieser Gleichung mathematisch redundant, macht aber im Code sehr klar, dass nur echte Dreiecke gezählt werden.
Anschließend wird der aktuelle Knoten mit den drei festen Matrizen multipliziert. Kinder mit nichtpositiven Koordinaten werden verworfen, und Kinder oberhalb der Umfangsgrenze werden nicht mehr auf den Stack gelegt. Da die Invariante \(c^2-a^2-b^2=1\) konstruktiv erhalten bleibt, braucht der schnelle Pfad keine Quadratwurzeltests.
Die C++-Implementierung enthält zusätzlich Kontrolltests für mehrere kleine Umfangsgrenzen. Dort wird langsamer direkt über \(a\le b\) iteriert, aus \(a^2+b^2+1\) ein Kandidat \(c\) rekonstruiert, auf Ganzzahligkeit geprüft und das Ergebnis mit dem Baumzähler verglichen. Dass beide Methoden auf diesen Punkten übereinstimmen, stützt die Korrektheit der Matrixerzeugung und der Zählregel, bevor die große Schranke verwendet wird.
Sei \(N(P)\) die Anzahl der erzeugten Baumknoten mit Umfang höchstens \(P\). Jeder besuchte Knoten verursacht nur konstanten Aufwand: eine Umfangsberechnung, einen Zähltest und drei feste \(3\times 3\)-Transformationen. Daher beträgt die Laufzeit
$$O(N(P)).$$
Das Verfahren ist ausgabesensitiv: Entscheidend ist die Zahl der tatsächlich existierenden fast rechtwinkligen Dreiecke unterhalb der Schranke, nicht die viel größere Box \(1\le a,b,c\le P\). Der explizite DFS-Stack speichert nur die aktuelle Front eines Baums mit konstanter Verzweigung, daher ist der Zusatzspeicher \(O(D(P))\), wobei \(D(P)\) die maximale erreichte Tiefe unter der Umfangsgrenze bezeichnet.
Çevresi en fazla \(75{,}000{,}000\) olan ve
$$a^2+b^2=c^2-1$$
eşitliğini sağlayan tam sayılı üçgenlerin sayısı isteniyor. Yani \(c^2=a^2+b^2+1\): en büyük kenarın karesi, dik üçgen bağıntısından sadece \(1\) kadar fazla. Kosinüs teoremine göre \(c\) karşısındaki açı için
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab}$$
olur; dolayısıyla üçgen geniş açılıdır ama tam sınırdadır.
Hızlı çözüm tüm olası kenarları taramaz. Bunun yerine
$$Q(a,b,c)=c^2-a^2-b^2$$
ikinci dereceden formunu koruyan bir üç dallı tamsayı dönüşüm ağacında dolaşır.
\(a\) ve \(b\) pozitif olduğu anda üçgen eşitsizliği zaten otomatik gelir. Çünkü
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
buradan da \(c \lt a+b\) çıkar. Kod yine de \(a+b \gt c\) kontrolünü yapar; fakat matematiksel olarak her pozitif çözüm zaten gerçek bir üçgendir.
Parite de zorlanır. Kareler mod \(4\) altında yalnızca \(0\) veya \(1\) olabilir; bu yüzden
$$a^2+b^2+1\equiv c^2 \pmod 4$$
bağıntısı, \(a,b\) kenarlarından yalnızca birinin tek olmasını ya da ikisinin birden tek olmasını dışlar. Sonuçta her çözüm için
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2$$
olmalıdır. En küçük pozitif çözüm de \((2,2,3)\) olur.
Bir üçlüyü sütun vektörü olarak \(t=(a,b,c)^T\) yazalım. Uygulamalar şu üç matrisi tekrar tekrar uygular:
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
\(G=\mathrm{diag}(-1,-1,1)\) dersek \(Q(t)=t^T G t\) olur ve her matris için
$$M_i^T G M_i=G$$
eşitliği sağlanır. Bu da
$$Q(M_i t)=Q(t)$$
demektir. Kök üçlü \((2,2,3)\) için \(Q=1\) olduğundan, bütün torunlar da otomatik olarak \(c^2-a^2-b^2=1\), yani \(a^2+b^2=c^2-1\) denklemini sağlar.
Arama
$$(2,2,3)$$
noktasından başlar; bu, \(Q=1\) yüzeyindeki en küçük pozitif çözümdür. Bu üç matris, söz konusu ikinci dereceden form için Berggren-benzeri bir ağaç oluşturur: yön korunursa, tekrar tekrar uygulanmaları pozitif tam sayı çözümlerini tekrarsız üretir. Uygulamalar bu yapıya dayanır; ayrıca C++ sürümü birkaç küçük çevre sınırında doğrudan sayımla eşleşme kontrolü yapar.
Denklem \(a\) ile \(b\) arasında simetriktir, fakat ağaç sıralı üçlüler üzerinde kuruludur. Aynı geometrik üçgeni bir kez saymak için algoritma kanonik yön olarak
$$a\le b$$
koşulunu kullanır. Bu koşul yalnızca sayım anında uygulanır; dolaşım sırasında \(a\gt b\) olan ara bir durum daha sonra \(a\le b\) sağlayan yeni torunlar üretebilir.
Kök üzerinde üç dönüşümü uygularsak
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T$$
elde edilir. Üçü de
$$a^2+b^2+1=c^2$$
eşitliğini sağlar. Üçüncü çocuk, \(8\gt 4\) olduğu için hemen sayılmaz; ama yine de atılamaz. Çünkü bir kez daha \(M_1\) uygularsak
$$M_1(8,4,9)^T=(18,30,35)^T$$
olur ve bu defa \(18\le 30\) geçerlidir. Yani bu dal gerçekten yeni bir üçgene gider. Bu nedenle dolaşım, sayım tek yönlü olsa bile iki yönü de tutmak zorundadır.
Her çocuğun üçüncü bileşeni
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c$$
şeklindedir. Ayrıca
$$c^2=a^2+b^2+1\gt (a-b)^2$$
olduğundan \(c\gt |a-b|\) elde edilir. Bu yüzden
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
Yani ağaç her adımda daha büyük üçlülere gider. Bir düğüm için \(a+b+c\gt P\) olduğunda, daha aşağıdaki tüm torunlar da daha büyük olacaktır. Bu nedenle \(a+b+c\le P\) budamasıyla yapılan derinlik öncelikli arama, ağacın tam olarak gerekli sonlu kısmını ziyaret eder. Başka bir deyişle aranan sayı
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\}$$
olup burada \(\mathcal{T}\), \((2,2,3)\) kökünden \(M_1,M_2,M_3\) ile üretilen ternary ağaçtır.
C++, Python ve Java uygulamaları açık bir yığın kullanarak derinlik öncelikli arama yapar. Başlangıçta yığına \((2,2,3)\) konur; sonra her adımda bir üçlü alınır, çevresi hesaplanır ve sınırı aşıyorsa hemen atılır.
Düğüm sınırın içindeyse, \(a\le b\) ve \(a+b\gt c\) koşulları altında sayaç artırılır. İkinci koşul bu denklemin pozitif çözümleri için aslında gereksizdir, fakat kodda gerçekten üçgen sayıldığını açıkça gösterir.
Ardından mevcut düğüm üç sabit matrisle çarpılır. Herhangi bir bileşeni pozitif olmayan çocuklar elenir; çevresi sınırı aşan çocuklar ise yığına hiç eklenmez. \(c^2-a^2-b^2=1\) invarianti yapısal olarak korunduğu için hızlı yol üzerinde karekök testi gerekmez.
C++ uygulaması ayrıca birkaç küçük çevre değeri için doğrudan doğrulama da içerir. Bu yavaş yöntem \(a\le b\) üzerinde dolaşır, \(a^2+b^2+1\) ifadesinden \(c\) adayını kurar, \(c\)'nin tam sayı olup olmadığını kontrol eder ve sonucu ağaç tabanlı sayaçla karşılaştırır. Bu küçük eşleşmeler, büyük sınıra geçmeden önce matris ağacının ve sayım kuralının doğru hizalandığını güçlü biçimde destekler.
\(N(P)\), çevresi en fazla \(P\) olan üretilmiş ağaç düğümü sayısı olsun. Ziyaret edilen her düğüm yalnızca sabit maliyet üretir: bir çevre hesabı, bir sayım testi ve üç sabit \(3\times 3\) dönüşüm. Dolayısıyla çalışma süresi
$$O(N(P))$$
olur. Bu yaklaşım output-sensitive'dir; maliyet, \(1\le a,b,c\le P\) kutusunun büyüklüğüne değil, gerçekten var olan neredeyse dik üçgenlerin sayısına bağlıdır. Açık DFS yığını, sabit dallanmalı bir ağacın yalnızca güncel cephesini tuttuğu için ek bellek \(O(D(P))\)'dir; burada \(D(P)\), çevre sınırı altında ulaşılan en büyük derinliktir.
Se pide contar los triángulos de lados enteros \((a,b,c)\) con perímetro no mayor que \(75{,}000{,}000\) tales que
$$a^2+b^2=c^2-1.$$
De forma equivalente, \(c^2=a^2+b^2+1\): el lado mayor es apenas más largo de lo que sería en un triángulo rectángulo. Por la ley de cosenos, el ángulo opuesto a \(c\) cumple
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
de modo que el triángulo es obtuso, pero solo por un margen mínimo.
La solución rápida no recorre todas las longitudes posibles. En lugar de eso, avanza por un árbol ternario de transformaciones enteras que preserva la forma cuadrática
$$Q(a,b,c)=c^2-a^2-b^2.$$
En cuanto \(a\) y \(b\) son positivos, la desigualdad triangular ya queda garantizada. En efecto,
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
así que \(c \lt a+b\). El código sigue comprobando \(a+b \gt c\), pero matemáticamente toda solución positiva ya produce un triángulo verdadero.
La paridad también está forzada. Los cuadrados son \(0\) o \(1\) módulo \(4\), y por tanto
$$a^2+b^2+1\equiv c^2 \pmod 4$$
descarta tanto el caso en que solo uno de \(a,b\) es impar como el caso en que ambos lo son. Por ello, toda solución verifica
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
La menor solución positiva es entonces \((2,2,3)\).
Escribimos un triple como vector columna \(t=(a,b,c)^T\). Las implementaciones aplican repetidamente las matrices
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
Si definimos \(G=\mathrm{diag}(-1,-1,1)\), entonces \(Q(t)=t^T G t\), y cada matriz satisface
$$M_i^T G M_i=G.$$
Por consiguiente, cada transformación preserva \(Q\):
$$Q(M_i t)=Q(t).$$
Como el triple raíz \((2,2,3)\) tiene \(Q=1\), todo descendiente cumple automáticamente \(c^2-a^2-b^2=1\), es decir, \(a^2+b^2=c^2-1\).
La búsqueda comienza en
$$(2,2,3),$$
el menor punto positivo sobre \(Q=1\). Estas tres matrices forman un árbol de tipo Berggren para esta forma cuadrática: manteniendo la orientación, las aplicaciones sucesivas generan las soluciones enteras positivas sin duplicados. Las implementaciones se apoyan en esa estructura, y la versión en C++ además la contrasta con enumeración directa para varios perímetros pequeños.
La ecuación es simétrica en \(a\) y \(b\), pero el árbol trabaja con triples ordenados. Para contar cada triángulo geométrico una sola vez, el algoritmo usa la orientación canónica
$$a\le b.$$
Esa condición se aplica solo al contar, no al recorrer el árbol, porque un estado intermedio con \(a\gt b\) puede producir después descendientes con \(a\le b\).
Si aplicamos las tres matrices a la raíz, obtenemos
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
Los tres cumplen
$$a^2+b^2+1=c^2.$$
El tercer hijo no se cuenta inmediatamente porque \(8\gt 4\), pero no puede descartarse. Si aplicamos una vez más \(M_1\), aparece
$$M_1(8,4,9)^T=(18,30,35)^T,$$
y ahora sí vale \(18\le 30\). Esa rama aporta un triángulo nuevo. Por eso el recorrido conserva ambas orientaciones aunque la cuenta final use solo una.
La tercera coordenada de cada hijo es
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
Como
$$c^2=a^2+b^2+1\gt (a-b)^2,$$
tenemos \(c\gt |a-b|\). Entonces
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
Así, el árbol siempre avanza hacia triples más grandes. En cuanto un nodo supera el límite \(P\) de perímetro, todos sus descendientes también serán demasiado grandes. Una búsqueda en profundidad con la poda \(a+b+c\le P\) visita exactamente la parte finita del árbol que interesa. En otras palabras, la respuesta es
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
donde \(\mathcal{T}\) es el árbol ternario generado desde \((2,2,3)\) por \(M_1,M_2,M_3\).
Las implementaciones en C++, Python y Java realizan una búsqueda en profundidad con una pila explícita. Empiezan con el triple raíz \((2,2,3)\), extraen un nodo cada vez, calculan su perímetro y lo descartan en cuanto supera el límite.
Si el nodo pasa ese filtro, se incrementa la cuenta cuando \(a\le b\) y \(a+b\gt c\). La segunda condición es redundante para soluciones positivas de esta ecuación, pero deja claro en el código que solo se cuentan triángulos genuinos.
Después se multiplica el nodo actual por las tres matrices fijas. Los hijos con alguna coordenada no positiva se rechazan, y los hijos cuyo perímetro ya excede el límite no se vuelven a insertar. Como el invariante \(c^2-a^2-b^2=1\) se conserva por construcción, la ruta rápida no necesita verificar raíces cuadradas.
La implementación en C++ incluye además comprobaciones directas para varios perímetros pequeños. Ese procedimiento lento enumera \(a\le b\), reconstruye \(c\) a partir de \(a^2+b^2+1\), decide si \(c\) es entero y compara el resultado con el conteo por árbol. La coincidencia en esos puntos de control es una evidencia concreta de que las fórmulas matriciales y la regla de conteo están bien ajustadas antes de usar el límite grande.
Sea \(N(P)\) el número de nodos generados por el árbol con perímetro a lo sumo \(P\). Cada nodo visitado requiere solo trabajo constante: un cálculo de perímetro, una prueba de conteo y tres transformaciones fijas de tamaño \(3\times 3\). Por tanto, el tiempo total es
$$O(N(P)).$$
El algoritmo es sensible a la salida: depende de cuántos triángulos casi rectángulos existen realmente bajo el límite, no del mucho mayor espacio \(1\le a,b,c\le P\). La pila DFS solo guarda la frontera activa de un árbol de ramificación constante, así que la memoria auxiliar es \(O(D(P))\), donde \(D(P)\) es la profundidad máxima alcanzada bajo la restricción de perímetro.
题目要求统计所有周长不超过 \(75{,}000{,}000\) 的整数边三角形 \((a,b,c)\)，满足
$$a^2+b^2=c^2-1.$$
也就是
$$c^2=a^2+b^2+1.$$
因此，最大边的平方只比直角三角形关系多了 \(1\)。用余弦定理写出 \(c\) 对应的角 \(C\)，有
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
所以这个角确实是钝角，但只比 \(90^\circ\) 大一点点，这正是 “Almost Right-angled” 的含义。
高效解法并不在 \((a,b,c)\) 空间里做暴力枚举，而是沿着一个整数三叉树生成所有需要的解。这个三叉树的核心是不变量
$$Q(a,b,c)=c^2-a^2-b^2.$$
只要 \(a,b\) 都是正整数，三角形不等式其实自动成立。因为
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
于是立刻得到 \(c \lt a+b\)。实现里仍然显式检查 \(a+b \gt c\)，但从数学上看，任何正整数解都已经是真正的三角形。
奇偶性也被完全限制住了。平方数模 \(4\) 只能是 \(0\) 或 \(1\)，因此
$$a^2+b^2+1\equiv c^2 \pmod 4$$
排除了 “只有一个是奇数” 以及 “两个都是奇数” 这两类情况。于是每个解都满足
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
这就说明最小的正整数解只能从很小的偶数边开始，实际最小解正是
$$(2,2,3).$$
把三元组写成列向量 \(t=(a,b,c)^T\)。程序反复应用下面三个固定矩阵：
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
令
$$G=\mathrm{diag}(-1,-1,1),$$
则 \(Q(t)=t^T G t\)。这三个矩阵都满足
$$M_i^T G M_i=G.$$
所以它们会保持二次型不变：
$$Q(M_i t)=Q(t).$$
由于根节点 \((2,2,3)\) 满足 \(Q=1\)，那么树上所有后代都会自动满足
$$c^2-a^2-b^2=1,$$
也就是题目要求的
$$a^2+b^2=c^2-1.$$
搜索从最小正解
$$(2,2,3)$$
开始。对这个二次型而言，上面三个矩阵构成了一个 Berggren 风格的解树：如果把 \((a,b,c)\) 看成有序三元组，那么不断施加这三个变换，可以无重复地生成所有正整数解。实现正是建立在这个结构之上，而 C++ 版本还会在若干较小周长上用直接枚举做交叉验证。
需要注意的是，方程本身对 \(a\) 和 \(b\) 是对称的，也就是说 \((a,b,c)\) 与 \((b,a,c)\) 表示同一个几何三角形。但这棵树是在有序三元组上展开的，因此程序在“遍历”时保留两种顺序，在“计数”时才使用规范方向
$$a\le b.$$
这样每个几何三角形最终只计一次，但不会错过那些需要经过镜像状态才能到达的后代。
把三个矩阵都作用在根节点上，可得到
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
这三个三元组都满足
$$a^2+b^2+1=c^2.$$
其中第三个孩子 \((8,4,9)\) 因为 \(8\gt 4\)，不会立即被计入答案。但它绝不是“无用节点”。如果再对它应用一次 \(M_1\)，就得到
$$M_1(8,4,9)^T=(18,30,35)^T,$$
此时已经有 \(18\le 30\)，因此这个分支会贡献一个新的合法三角形。也就是说，如果在遍历过程中一看到 \(a\gt b\) 就直接剪掉，那么后面本来应该出现的规范解也会被一起漏掉。
三个孩子的第三个坐标分别是
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
另一方面，由
$$c^2=a^2+b^2+1\gt (a-b)^2$$
可知
$$c\gt |a-b|.$$
因此
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
也就是说，每次向下扩展时，第三个坐标一定严格变大，整体规模也随之上升。一旦某个节点已经满足 \(a+b+c\gt P\)，更深层的所有后代都会更大，不可能重新回到范围内。所以深度优先搜索只需要保留
$$a+b+c\le P$$
的节点，就正好遍历到题目所需的那一块有限子树。于是答案可以写成
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
其中 \(\mathcal{T}\) 表示从 \((2,2,3)\) 出发、反复应用 \(M_1,M_2,M_3\) 得到的三叉树。
C++、Python 和 Java 实现都采用显式栈来做深度优先遍历。初始时把根三元组 \((2,2,3)\) 压栈；之后每次弹出一个节点，先算周长，若已经超出上界就直接丢弃。
若节点仍在范围内，则在 \(a\le b\) 且 \(a+b\gt c\) 时把答案加一。第二个条件对于本题的正整数解来说从理论上是冗余的，但它让代码层面的“只数真正三角形”这一点表达得更清楚。
接着，程序把当前节点分别乘以三个固定矩阵，得到三个候选孩子。任何坐标不再为正的孩子都会被舍弃；周长已经超界的孩子也不会再次入栈。由于矩阵本身就保证了 \(c^2-a^2-b^2=1\) 这个不变量，快速路径里不需要重复做平方根整除判断。
C++ 实现额外带有若干小周长检查点。慢速验证会直接枚举 \(a\le b\)，由 \(a^2+b^2+1\) 反推出候选 \(c\)，检查它是否为整数，并把这个朴素计数与树搜索结果进行比较。对于这些小范围，两者完全一致，就为矩阵生成树和计数条件的正确性提供了非常具体的支撑。
设 \(N(P)\) 为周长不超过 \(P\) 的生成节点总数。每访问一个节点，只做常数次工作：一次周长判断、一次计数判断，以及三次固定的 \(3\times 3\) 变换。因此总时间复杂度是
$$O(N(P)).$$
这是一种输出敏感算法：它依赖的是周长限制下实际存在多少个“几乎直角”的整数三角形，而不是更大的盒状搜索空间 \(1\le a,b,c\le P\)。显式 DFS 栈只需要保存一棵常分支树的当前前沿，所以额外空间为 \(O(D(P))\)，其中 \(D(P)\) 表示在周长上界内达到的最大深度。
Нужно посчитать количество целочисленных треугольников \((a,b,c)\) с периметром не больше \(75{,}000{,}000\), для которых выполняется
$$a^2+b^2=c^2-1.$$
То есть
$$c^2=a^2+b^2+1.$$
Квадрат наибольшей стороны лишь на \(1\) больше, чем в прямоугольном случае. По теореме косинусов для угла напротив стороны \(c\) получаем
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
поэтому этот угол тупой, но совсем немного.
Быстрое решение не перебирает все возможные длины сторон. Вместо этого оно проходит по тернарному дереву целочисленных преобразований, сохраняющих квадратичную форму
$$Q(a,b,c)=c^2-a^2-b^2.$$
Как только \(a\) и \(b\) положительны, неравенство треугольника выполняется автоматически. Действительно,
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
значит, \(c \lt a+b\). В коде проверка \(a+b \gt c\) все равно оставлена, но с математической точки зрения любой положительный целочисленный корень уже задает настоящий треугольник.
Четность тоже жестко фиксирована. Квадраты по модулю \(4\) дают только \(0\) или \(1\), поэтому
$$a^2+b^2+1\equiv c^2 \pmod 4$$
исключает случаи, когда ровно одна из сторон \(a,b\) нечетна, и когда они обе нечетны. Следовательно, любой корень удовлетворяет
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
Минимальное положительное решение поэтому равно \((2,2,3)\).
Представим тройку как столбец \(t=(a,b,c)^T\). Реализации многократно применяют три матрицы
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
Если положить \(G=\mathrm{diag}(-1,-1,1)\), то \(Q(t)=t^T G t\), и каждая из матриц удовлетворяет равенству
$$M_i^T G M_i=G.$$
Значит, квадратичная форма сохраняется:
$$Q(M_i t)=Q(t).$$
Поскольку корневая тройка \((2,2,3)\) имеет \(Q=1\), любой потомок автоматически удовлетворяет \(c^2-a^2-b^2=1\), то есть исходному условию \(a^2+b^2=c^2-1\).
Поиск начинается из
$$(2,2,3),$$
минимальной положительной точки на поверхности \(Q=1\). Для этой квадратичной формы указанные матрицы образуют дерево типа Берггрена: если сохранять ориентацию, последовательные применения порождают все положительные целочисленные решения без повторов. На этой структуре и основаны реализации; кроме того, версия на C++ сверяет результат с прямым перебором на нескольких малых ограничениях по периметру.
Само уравнение симметрично по \(a\) и \(b\), но дерево строится по упорядоченным тройкам. Чтобы каждую геометрическую фигуру посчитать один раз, алгоритм использует каноническую ориентацию
$$a\le b.$$
Однако эта проверка делается только в момент подсчета, а не при обходе: промежуточное состояние с \(a\gt b\) может привести к более глубоким потомкам, где уже будет \(a\le b\).
Применим три матрицы к корню:
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
Все три тройки удовлетворяют
$$a^2+b^2+1=c^2.$$
Третий потомок не считается сразу, потому что \(8\gt 4\). Но выбрасывать его нельзя. Если еще раз применить \(M_1\), получится
$$M_1(8,4,9)^T=(18,30,35)^T,$$
и теперь уже \(18\le 30\). Значит, эта ветвь действительно приводит к новому корректному треугольнику. Поэтому при обходе сохраняются обе ориентации, хотя в ответ идет только одна.
Третья координата у потомков имеет вид
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
Из неравенства
$$c^2=a^2+b^2+1\gt (a-b)^2$$
следует, что \(c\gt |a-b|\). Поэтому
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
То есть дерево всегда движется к более крупным тройкам. Если для некоторого узла уже выполнено \(a+b+c\gt P\), то все его потомки будут еще больше. Следовательно, поиск в глубину с отсечением по условию \(a+b+c\le P\) проходит ровно по той конечной части дерева, которая нужна для задачи. Искомое количество можно записать как
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
где \(\mathcal{T}\) обозначает тернарное дерево, порожденное из \((2,2,3)\) матрицами \(M_1,M_2,M_3\).
Реализации на C++, Python и Java используют явный стек и выполняют поиск в глубину. В стек сначала кладется корневая тройка \((2,2,3)\); далее на каждой итерации извлекается один узел, вычисляется его периметр и узел сразу отбрасывается, если лимит превышен.
Если узел проходит этот фильтр, ответ увеличивается при выполнении условий \(a\le b\) и \(a+b\gt c\). Второе условие для положительных решений данного уравнения математически избыточно, но в коде оно ясно показывает, что считаются именно треугольники.
После этого текущая тройка умножается на три фиксированные матрицы. Потомки с неположительными координатами отбрасываются, а потомки, уже вышедшие за пределы по периметру, в стек не добавляются. Поскольку инвариант \(c^2-a^2-b^2=1\) сохраняется конструктивно, в быстром алгоритме не требуется проверять целочисленность через квадратный корень.
В реализации на C++ есть и прямой проверяющий режим для нескольких небольших значений периметра. Медленная версия перебирает \(a\le b\), восстанавливает кандидат \(c\) из \(a^2+b^2+1\), проверяет, является ли он целым, и сравнивает итог с деревом. Совпадение на этих контрольных точках служит содержательной проверкой того, что матрическая генерация и правило подсчета согласованы правильно.
Пусть \(N(P)\) обозначает число сгенерированных узлов дерева с периметром не больше \(P\). Каждый посещенный узел требует лишь постоянного объема работы: один расчет периметра, одну проверку на подсчет и три фиксированных преобразования размера \(3\times 3\). Поэтому время работы равно
$$O(N(P)).$$
Алгоритм является выходно-чувствительным: стоимость определяется числом реально существующих почти прямоугольных треугольников под заданным пределом, а не гораздо большим объемом пространства \(1\le a,b,c\le P\). Явный стек DFS хранит только текущий фронт дерева с постоянным ветвлением, поэтому дополнительная память равна \(O(D(P))\), где \(D(P)\) — максимальная глубина, достигнутая при данном ограничении на периметр.
المطلوب هو عدّ المثلثات ذات الأضلاع الصحيحة \((a,b,c)\) التي لا يتجاوز محيطها \(75{,}000{,}000\) وتحقق
$$a^2+b^2=c^2-1.$$
وبصيغة مكافئة،
$$c^2=a^2+b^2+1.$$
أي إن مربع الضلع الأكبر يزيد بمقدار \(1\) فقط على علاقة المثلث القائم. ومن قانون جيب التمام نحصل على الزاوية المقابلة للضلع \(c\):
$$\cos C=\frac{a^2+b^2-c^2}{2ab}=-\frac{1}{2ab},$$
ولذلك فالمثلث منفرج الزاوية، لكنه قريب جدا من القائم.
الحل السريع لا يجرّب كل الأطوال الممكنة مباشرة، بل يتحرك داخل شجرة ثلاثية من التحويلات الصحيحة التي تحفظ الشكل التربيعي
$$Q(a,b,c)=c^2-a^2-b^2.$$
ما إن يكون \(a\) و\(b\) موجبين حتى تصبح متباينة المثلث تلقائية. فعلا،
$$c^2=a^2+b^2+1 \lt a^2+b^2+2ab=(a+b)^2,$$
ومن ثم \(c \lt a+b\). يبقي التنفيذ على اختبار \(a+b \gt c\)، لكن من الناحية الرياضية كل حل موجب يعطي مثلثا صحيحا فعلا.
كما أن الفردية والزوجية مقيدتان تماما. فمربعات الأعداد بترديد \(4\) لا تكون إلا \(0\) أو \(1\)، ولذلك فإن
$$a^2+b^2+1\equiv c^2 \pmod 4$$
يستبعد حالتي: كون أحد \(a,b\) فرديا والآخر زوجيا، أو كونهما فرديين معا. لذا فإن كل حل يحقق
$$a\equiv b\equiv 0 \pmod 2,\qquad c\equiv 1 \pmod 2.$$
وأصغر حل موجب هو إذن
$$(2,2,3).$$
لنكتب الثلاثي على صورة متجه عمودي \(t=(a,b,c)^T\). تقوم التطبيقات بتكرار استعمال المصفوفات الثلاث
$$M_1=\begin{pmatrix}1&-2&2\\2&-1&2\\2&-2&3\end{pmatrix},\qquad M_2=\begin{pmatrix}1&2&2\\2&1&2\\2&2&3\end{pmatrix},\qquad M_3=\begin{pmatrix}-1&2&2\\-2&1&2\\-2&2&3\end{pmatrix}.$$
إذا أخذنا
$$G=\mathrm{diag}(-1,-1,1),$$
فإن \(Q(t)=t^T G t\)، وكل مصفوفة من هذه المصفوفات تحقق
$$M_i^T G M_i=G.$$
وبالتالي فهي تحفظ الشكل التربيعي:
$$Q(M_i t)=Q(t).$$
وبما أن الجذر \((2,2,3)\) يحقق \(Q=1\)، فإن كل نسل له يحقق تلقائيا
$$c^2-a^2-b^2=1,$$
أي شرط المسألة نفسه
$$a^2+b^2=c^2-1.$$
يبدأ البحث من
$$(2,2,3),$$
وهو أصغر حل موجب على السطح \(Q=1\). هذه المصفوفات الثلاث تشكل شجرة من نمط Berggren لهذا الشكل التربيعي: إذا احتفظنا بترتيب \((a,b,c)\) بوصفه ثلاثيا مرتبا، فإن التكرار يولد جميع الحلول الصحيحة الموجبة من غير تكرار. تعتمد التطبيقات على هذه البنية، كما أن نسخة C++ تتحقق منها أيضا بمقارنة مباشرة عند حدود محيط صغيرة.
المعادلة نفسها متناظرة في \(a\) و\(b\)، لكن الشجرة مبنية على ثلاثيات مرتبة. ولكي يُحسب كل مثلث هندسي مرة واحدة فقط، تستخدم الخوارزمية الاتجاه القياسي
$$a\le b.$$
غير أن هذا الشرط يطبّق عند العد فقط، لا عند التوسيع داخل الشجرة، لأن حالة وسيطة فيها \(a\gt b\) قد تقود لاحقا إلى نسل جديد يحقق \(a\le b\).
إذا طبقنا المصفوفات الثلاث على الجذر حصلنا على
$$M_1(2,2,3)^T=(4,8,9)^T,\qquad M_2(2,2,3)^T=(12,12,17)^T,\qquad M_3(2,2,3)^T=(8,4,9)^T.$$
وجميعها تحقق
$$a^2+b^2+1=c^2.$$
الابن الثالث لا يُعد مباشرة لأن \(8\gt 4\)، لكنه ليس زائدا عن الحاجة. فإذا طبقنا \(M_1\) مرة أخرى نحصل على
$$M_1(8,4,9)^T=(18,30,35)^T,$$
والآن صار \(18\le 30\)، أي إن هذا الفرع ينتج مثلثا صحيحا جديدا يجب احتسابه. لهذا السبب تحتفظ عملية العبور بكلتا الجهتين، حتى لو كان العد النهائي يستخدم جهة واحدة فقط.
الإحداثي الثالث لكل ابن هو
$$c_1=2a-2b+3c,\qquad c_2=2a+2b+3c,\qquad c_3=-2a+2b+3c.$$
ومن
$$c^2=a^2+b^2+1\gt (a-b)^2$$
نستنتج أن
$$c\gt |a-b|.$$
إذن
$$c_1=c+2(a-b+c)\gt c,\qquad c_2\gt c,\qquad c_3=c+2(b-a+c)\gt c.$$
أي إن الشجرة تتجه دائما نحو ثلاثيات أكبر. وما إن يصبح محيط عقدة ما أكبر من \(P\)، فإن جميع نسلها سيكون أكبر أيضا. لذلك فإن البحث بالعمق مع شرط القطع
$$a+b+c\le P$$
يزور بالضبط الجزء المنتهي من الشجرة الذي نحتاجه. وبعبارة أخرى، العدد المطلوب هو
$$T(P)=\#\{(a,b,c)\in\mathcal{T}: a+b+c\le P,\ a\le b\},$$
حيث \(\mathcal{T}\) هي الشجرة الثلاثية المتولدة من \((2,2,3)\) باستعمال \(M_1,M_2,M_3\).
تنفذ نسخ C++ وPython وJava بحثا عمقيا باستعمال مكدس صريح. يبدأ التنفيذ بوضع الجذر \((2,2,3)\) في المكدس، ثم يسحب ثلاثيا واحدا في كل خطوة، ويحسِب محيطه، ويتجاهله فورا إذا تجاوز الحد.
إذا بقيت العقدة ضمن الحد، يزيد العداد عندما يتحقق الشرطان \(a\le b\) و\(a+b\gt c\). الشرط الثاني زائد رياضيا بالنسبة للحلول الموجبة لهذه المعادلة، لكنه يوضح في الكود أن ما يُعد فعلا هو المثلثات الصحيحة فقط.
بعد ذلك يُضرب الثلاثي الحالي في المصفوفات الثلاث الثابتة. أي ابن يحتوي على إحداثي غير موجب يُرفض، وأي ابن صار محيطه أعلى من الحد لا يُعاد إدخاله إلى المكدس. ولأن الثابت \(c^2-a^2-b^2=1\) محفوظ بنيويا، فلا حاجة في المسار السريع إلى اختبارات الجذر التربيعي.
تتضمن نسخة C++ أيضا نقاط تحقق مباشرة عند عدة قيم صغيرة للمحيط. في هذا المسار الأبطأ يتم تعداد \(a\le b\)، ثم إعادة بناء \(c\) من \(a^2+b^2+1\)، وفحص كونه عددا صحيحا، ثم مقارنة النتيجة مع العد الناتج من الشجرة. هذا التطابق عند الحدود الصغيرة يقدم دعما عمليا واضحا لصحة شجرة المصفوفات وقاعدة العد قبل الانتقال إلى الحد الكبير.
لنرمز بـ \(N(P)\) إلى عدد عقد الشجرة المتولدة ذات المحيط الذي لا يتجاوز \(P\). كل عقدة مزارة تحتاج إلى عمل ثابت فقط: حساب محيط، واختبار عد، وثلاثة تطبيقات لمصفوفات ثابتة من الحجم \(3\times 3\). لذلك فإن زمن التنفيذ هو
$$O(N(P)).$$
هذه خوارزمية حساسة للمخرجات؛ فهي تعتمد على عدد المثلثات الصحيحة شبه القائمة الموجودة فعلا تحت حد المحيط، لا على الصندوق الأكبر كثيرا \(1\le a,b,c\le P\). أما الذاكرة الإضافية فهي \(O(D(P))\)، حيث \(D(P)\) هو أقصى عمق تصل إليه عملية DFS تحت هذا الحد، لأن المكدس الصريح لا يخزن إلا الجبهة النشطة لشجرة ذات تفرع ثابت.