We want to count integer-sided triangles \((a,b,c)\) with \(a \le b \le c\), perimeter \(a+b+c \le P\), and
$$a^2+b^2=c^2+1.$$
For the Project Euler instance, \(P=25{,}000{,}000\). The equation says that the triangle is exactly one unit away from being right-angled, so a brute-force search over all triples is completely impractical.
The successful idea is to fix the smallest side \(a\), rewrite the equation as a factorization of \(a^2-1\), and count only the divisor pairs that can still satisfy the perimeter and ordering constraints.
The central observation is that once \(a\) is fixed, the other two sides can be recovered from a factor pair of \(a^2-1\). That turns the problem from a quadratic search in \((b,c)\) into a bounded divisor-counting problem.
Because \(a \le b \le c\), every valid triangle satisfies
$$3a \le a+b+c \le P.$$
Therefore
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
The implementations loop over this range of possible smallest sides and solve the rest of the triangle from there.
Start from
$$a^2+b^2=c^2+1,$$
which can be rearranged as
$$c^2-b^2=a^2-1.$$
Now define
$$u=b+c,\qquad v=c-b.$$
Then \(u>0\), \(v\ge 0\), and
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
Conversely, once a factor pair \((u,v)\) is known, the two larger sides are
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
So for a fixed \(a\), every admissible triangle corresponds to a divisor pair of \(a^2-1\) with the parity condition
$$u\equiv v \pmod 2,$$
because \(b\) and \(c\) must be integers.
For \(a \ge 2\), we have \(a^2-1>0\), so \(v>0\). Then each valid choice of the smaller factor \(v\) determines \(u=(a^2-1)/v\), and therefore determines \((b,c)\) uniquely.
The perimeter becomes especially simple in the new variables:
$$a+b+c=a+u.$$
Hence the perimeter bound is
$$u \le P-a.$$
Since \(u=(a^2-1)/v\), this gives the lower bound
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
Very small divisors make \(u\) too large, so they cannot contribute.
The ordering condition \(a \le b\) becomes
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
Substituting \(u=(a^2-1)/v\) yields
$$v^2+2av \le a^2-1.$$
Solving this quadratic inequality gives an upper bound for the smaller factor:
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
Therefore the search for \(v\) is completely localized:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
Only divisors of \(a^2-1\) inside this interval need to be tested.
Once this upper bound is enforced, the strict triangle inequality no longer needs a separate filter. Indeed,
$$a+b-c=a-v,$$
and the bound above implies \(v<a\). So every divisor that survives the bound and parity checks already yields a genuine triangle with \(a \le b \le c\).
When \(a=1\), the product \(a^2-1\) vanishes, so the divisor parameterization above is not the right tool. The original equation becomes
$$1+b^2=c^2+1,$$
which immediately simplifies to \(b=c\). So every triangle in this family has the form
$$ (1,b,b).$$
The perimeter condition is then
$$1+2b \le P,$$
so this case contributes exactly
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
solutions and is counted separately before the main divisor loop.
Take \(a=5\). Then
$$a^2-1=24.$$
The upper bound from \(a \le b\) is
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
So only the divisors \(v=1\) and \(v=2\) are even worth examining.
For \(v=1\), we get \(u=24\), but \(u-v=23\) is odd, so \(b\) and \(c\) would not be integers. For \(v=2\), we get \(u=12\), hence
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
This produces the valid almost-right triangle \((5,5,7)\), and indeed
$$5^2+5^2=7^2+1.$$
The full algorithm repeats exactly this bounded divisor test for every \(a \le P/3\).
The C++, Python, and Java implementations all follow the same mathematical plan. They first set \(a_{\max}=\lfloor P/3\rfloor\), add the separate contribution from \(a=1\), and build a smallest-prime-factor table up to \(a_{\max}+1\). That range is enough because the implementations never factor \(a^2-1\) directly. Instead they factor \(a-1\) and \(a+1\), then combine those prime exponents to recover the factorization of \((a-1)(a+1)=a^2-1\).
For each fixed \(a \ge 2\), the implementation computes \(v_{\min}\) from the perimeter bound and an initial floating-point estimate of \(v_{\max}\) from \(\sqrt{2a^2-1}-a\). Because floating-point rounding can miss the true floor by one, that estimate is corrected with exact integer inequalities before any counting starts. After that, the implementation generates only those divisors of \(a^2-1\) that do not exceed \(v_{\max}\), and each candidate \(v\) is checked against the four remaining conditions: \(v \ge v_{\min}\), correct parity, \(u \ge v+2a\), and \(a+u \le P\).
The work splits naturally across independent ranges of \(a\). The C++ and Java implementations distribute consecutive chunks of \(a\)-values to worker threads, while the Python implementation uses the same chunking idea with worker processes when that helps and falls back to a serial pass otherwise. Each worker needs only small temporary factor and divisor buffers, so the main shared structure is the prime-factor table.
The smallest-prime-factor table up to \(a_{\max}+1=\lfloor P/3\rfloor+1\) costs \(O(P)\) time and \(O(P)\) memory up to constant factors. After that, the work for one fixed \(a\) is dominated by factoring \(a-1\) and \(a+1\) and by generating the admissible divisors of \(a^2-1\).
A convenient summary of the total runtime is
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$$
where \(\tau(n)\) is the divisor-counting function. This matches the structure of the implementations: the sieve is linear-size preprocessing, and the main loop spends its time on the divisor structure of \(a^2-1\). Parallel execution improves wall-clock time but does not change the asymptotic bound. Extra memory beyond the sieve is only small thread-local or process-local working storage.
Gesucht ist die Anzahl ganzzahliger Dreiecke \((a,b,c)\) mit \(a \le b \le c\), Umfang \(a+b+c \le P\) und
$$a^2+b^2=c^2+1.$$
Im eigentlichen Project-Euler-Fall gilt \(P=25{,}000{,}000\). Die Gleichung beschreibt Dreiecke, die genau um 1 vom rechtwinkligen Fall abweichen, daher ist ein naiver Durchlauf über alle Tripel viel zu groß.
Die Lösung fixiert stattdessen zuerst die kleinste Seite \(a\), schreibt die Gleichung als Faktorisierung von \(a^2-1\) um und zählt nur noch diejenigen Teilerpaare, die überhaupt noch mit Umfang und Seitenordnung vereinbar sind.
Die entscheidende Beobachtung ist: Ist \(a\) fest, dann lassen sich \(b\) und \(c\) aus einem Faktorpärchen von \(a^2-1\) rekonstruieren. Damit wird aus einer quadratischen Suche in \((b,c)\) eine kontrollierte Teilerzählung.
Aus \(a \le b \le c\) folgt für jedes gültige Dreieck
$$3a \le a+b+c \le P.$$
Also gilt
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
Die Implementierungen laufen genau über diesen Bereich möglicher kleinster Seiten und leiten den Rest des Dreiecks daraus ab.
Aus
$$a^2+b^2=c^2+1$$
wird durch Umstellen
$$c^2-b^2=a^2-1.$$
Nun setzen wir
$$u=b+c,\qquad v=c-b.$$
Dann ist \(u>0\), \(v\ge 0\), und es gilt
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
Umgekehrt erhält man aus einem Faktorpärchen \((u,v)\) die beiden größeren Seiten durch
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
Für festes \(a\) entspricht also jedes zulässige Dreieck einem Teilerpärchen von \(a^2-1\) mit der Paritätsbedingung
$$u\equiv v \pmod 2,$$
denn \(b\) und \(c\) müssen ganzzahlig sein.
Für \(a \ge 2\) ist \(a^2-1>0\), also sogar \(v>0\). Dann bestimmt jede gültige Wahl des kleineren Faktors \(v\) eindeutig \(u=(a^2-1)/v\) und damit auch \((b,c)\).
Im neuen Koordinatensystem wird der Umfang besonders einfach:
$$a+b+c=a+u.$$
Daher ist die Umfangsbedingung
$$u \le P-a.$$
Mit \(u=(a^2-1)/v\) folgt daraus die untere Schranke
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
Zu kleine Teiler machen also \(u\) zu groß und scheiden sofort aus.
Die Ordnungsbedingung \(a \le b\) wird zu
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
Nach Einsetzen von \(u=(a^2-1)/v\) erhält man
$$v^2+2av \le a^2-1.$$
Diese quadratische Ungleichung liefert die obere Schranke
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
Damit ist die Suche nach \(v\) vollständig lokalisiert:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
Nur Teiler von \(a^2-1\) in diesem Intervall können überhaupt beitragen.
Ist diese Schranke einmal durchgesetzt, braucht die strikte Dreiecksungleichung keinen eigenen Test mehr. Denn
$$a+b-c=a-v,$$
und aus der oberen Schranke folgt \(v<a\). Jeder Teiler, der die Schranken- und Paritätsprüfungen besteht, erzeugt also automatisch ein echtes Dreieck mit \(a \le b \le c\).
Für \(a=1\) verschwindet das Produkt \(a^2-1\), daher ist die obige Teilerparametrisierung nicht passend. Die Ursprungsgleichung wird zu
$$1+b^2=c^2+1,$$
also unmittelbar zu \(b=c\). Alle Dreiecke dieser Familie haben die Form
$$ (1,b,b).$$
Die Umfangsbedingung lautet dann
$$1+2b \le P,$$
und diese Familie liefert genau
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
Lösungen. Deshalb wird sie vor der eigentlichen Teilerschleife separat addiert.
Nehmen wir \(a=5\). Dann ist
$$a^2-1=24.$$
Die obere Schranke aus \(a \le b\) ist
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
Also müssen nur noch die Teiler \(v=1\) und \(v=2\) betrachtet werden.
Für \(v=1\) gilt \(u=24\), aber \(u-v=23\) ist ungerade, also wären \(b\) und \(c\) nicht ganzzahlig. Für \(v=2\) erhält man \(u=12\) und damit
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
Das ergibt das gültige fast rechtwinklige Dreieck \((5,5,7)\), und tatsächlich gilt
$$5^2+5^2=7^2+1.$$
Genau diesen beschränkten Teilertest führt der Algorithmus für jedes \(a \le P/3\) aus.
Die C++-, Python- und Java-Implementierungen folgen derselben mathematischen Struktur. Zuerst setzen sie \(a_{\max}=\lfloor P/3\rfloor\), addieren den separaten Beitrag von \(a=1\) und bauen eine Tabelle des kleinsten Primteilers bis \(a_{\max}+1\) auf. Diese Reichweite genügt, weil nicht \(a^2-1\) direkt faktorisiert wird. Stattdessen werden \(a-1\) und \(a+1\) faktorisiert, und ihre Primexponenten werden anschließend zu der Faktorisierung von \((a-1)(a+1)=a^2-1\) zusammengeführt.
Für jedes feste \(a \ge 2\) berechnet die Implementierung \(v_{\min}\) aus der Umfangsbedingung und eine erste Gleitkomma-Näherung für \(v_{\max}\) aus \(\sqrt{2a^2-1}-a\). Da Rundungsfehler um eins danebenliegen können, wird diese Schätzung vor dem Zählen noch mit exakten ganzzahligen Ungleichungen korrigiert. Danach werden nur noch die Teiler von \(a^2-1\) erzeugt, die höchstens \(v_{\max}\) sind, und jeder Kandidat \(v\) wird gegen die vier verbleibenden Bedingungen geprüft: \(v \ge v_{\min}\), richtige Parität, \(u \ge v+2a\) und \(a+u \le P\).
Die Arbeit lässt sich natürlich parallelisieren, weil verschiedene Werte von \(a\) unabhängig sind. Die C++- und Java-Implementierungen verteilen zusammenhängende Blöcke von \(a\)-Werten auf Threads. Die Python-Implementierung verwendet dieselbe Blockidee mit Prozessen, wenn sich das lohnt, und fällt sonst auf einen seriellen Durchlauf zurück. Pro Worker werden nur kleine temporäre Puffer für Faktoren und Teiler benötigt; die große gemeinsame Struktur ist die Primteiler-Tabelle.
Die Tabelle des kleinsten Primteilers bis \(a_{\max}+1=\lfloor P/3\rfloor+1\) benötigt \(O(P)\) Zeit und \(O(P)\) Speicher bis auf konstante Faktoren. Danach wird die Arbeit für ein festes \(a\) von der Faktorisierung von \(a-1\) und \(a+1\) sowie von der Erzeugung der zulässigen Teiler von \(a^2-1\) dominiert.
Als kompakte Zusammenfassung der Gesamtlaufzeit bietet sich
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right)$$
an, wobei \(\tau(n)\) die Anzahl der positiven Teiler bezeichnet. Das passt exakt zur Struktur der Implementierungen: Das Sieb ist lineare Vorverarbeitung, und die Hauptschleife lebt von der Teilerstruktur von \(a^2-1\). Parallelisierung verbessert die reale Laufzeit, ändert aber nichts an der asymptotischen Schranke. Zusätzlicher Speicher über das Sieb hinaus besteht nur aus kleinen thread-lokalen oder prozess-lokalen Arbeitsbereichen.
Aranan şey, \(a \le b \le c\), \(a+b+c \le P\) ve
$$a^2+b^2=c^2+1$$
koşullarını sağlayan tam sayı kenarlı üçgenlerin sayısıdır. Project Euler sürümünde \(P=25{,}000{,}000\) alınır. Denklem, üçgenin dik üçgene tam 1 kadar uzak olduğunu söyler; bu yüzden bütün \((a,b,c)\) üçlülerini kaba kuvvetle dolaşmak pratik değildir.
Başarılı yaklaşım, önce en küçük kenar \(a\)'yı sabitlemek, sonra denklemi \(a^2-1\)'in bölenlerine dönüştürmek ve yalnızca çevre ile kenar sırası koşullarını geçebilecek bölen çiftlerini saymaktır.
Ana fikir şudur: \(a\) sabitlenince diğer iki kenar, \(a^2-1\)'in bir çarpan çiftinden geri elde edilebilir. Böylece \((b,c)\) üzerinde kuadratik bir arama yapmak yerine sınırlı bir bölen sayımı yapılır.
\(a \le b \le c\) olduğundan her geçerli üçgen için
$$3a \le a+b+c \le P$$
vardır. Dolayısıyla
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
Uygulamalar tam olarak bu aralıktaki en küçük kenar adaylarını dolaşır ve üçgenin geri kalanını bu seçimden üretir.
Başlangıç denklemi
$$a^2+b^2=c^2+1$$
şöyle yeniden yazılır:
$$c^2-b^2=a^2-1.$$
Şimdi
$$u=b+c,\qquad v=c-b$$
tanımlarını yapalım. O zaman \(u>0\), \(v\ge 0\) ve
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1$$
olur. Tersine, bir \((u,v)\) çarpan çifti biliniyorsa büyük iki kenar
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}$$
şeklinde bulunur. Demek ki sabit bir \(a\) için her geçerli üçgen, \(a^2-1\)'in bir bölen çiftiyle eşleşir; fakat \(b\) ve \(c\) tam sayı olacağı için şu parite koşulu gerekir:
$$u\equiv v \pmod 2.$$
\(a \ge 2\) olduğunda \(a^2-1>0\) olduğu için \(v>0\) da zorunludur. Böylece küçük çarpan \(v\) seçildiğinde \(u=(a^2-1)/v\) ve ardından \((b,c)\) tek biçimde belirlenir.
Yeni değişkenlerde çevre çok sadeleşir:
$$a+b+c=a+u.$$
Bu yüzden çevre koşulu
$$u \le P-a$$
olur. \(u=(a^2-1)/v\) yazınca alt sınır elde ederiz:
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
Yani çok küçük bölenler \(u\)'yu fazla büyüttüğü için hemen elenir.
Kenar sırası koşulu \(a \le b\) ise
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a$$
eşdeğerliğine dönüşür. Burada \(u=(a^2-1)/v\) yazılırsa
$$v^2+2av \le a^2-1$$
bulunur. Bu kuadratik eşitsizlik küçük çarpan için üst sınır verir:
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
Böylece arama aralığı tamamen belirlenmiş olur:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
Yalnızca bu aralıktaki bölenler denenmelidir.
Bu üst sınır uygulandıktan sonra sıkı üçgen eşitsizliği için ayrı bir denetime gerek kalmaz. Çünkü
$$a+b-c=a-v,$$
ve yukarıdaki sınır \(v<a\) sonucunu verir. Dolayısıyla sınır ve parite testlerinden geçen her bölen, otomatik olarak \(a \le b \le c\) sağlayan gerçek bir üçgen üretir.
\(a=1\) için \(a^2-1=0\) olur; bu yüzden yukarıdaki bölen parametreleştirmesi doğrudan kullanılmaz. Asıl denklem
$$1+b^2=c^2+1$$
haline gelir ve buradan hemen \(b=c\) çıkar. Demek ki bu ailedeki bütün üçgenler
$$ (1,b,b)$$
biçimindedir. Çevre şartı
$$1+2b \le P$$
olduğundan bu özel aile tam olarak
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
adet çözüm verir. Bu sayı ana döngü başlamadan önce ayrı eklenir.
\(a=5\) alalım. O zaman
$$a^2-1=24.$$
\(a \le b\) koşulundan gelen üst sınır
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2$$
olur. Yani yalnızca \(v=1\) ve \(v=2\) bölenlerine bakmak gerekir.
\(v=1\) için \(u=24\) bulunur; fakat \(u-v=23\) tek sayı olduğu için \(b\) ve \(c\) tam sayı olmaz. \(v=2\) için \(u=12\) elde edilir ve
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7$$
çıkar. Böylece \((5,5,7)\) üçgeni elde edilir ve gerçekten
$$5^2+5^2=7^2+1$$
eşitliği sağlanır. Tam algoritma, \(a \le P/3\) olan her değer için bu sınırlı bölen testini tekrarlar.
C++, Python ve Java uygulamaları aynı matematiksel planı uygular. Önce \(a_{\max}=\lfloor P/3\rfloor\) belirlenir, \(a=1\) için gelen ayrı katkı eklenir ve \(a_{\max}+1\)'e kadar en küçük asal bölen tablosu hazırlanır. Bu aralık yeterlidir; çünkü uygulamalar doğrudan \(a^2-1\)'i çarpanlara ayırmaz. Onun yerine \(a-1\) ve \(a+1\) ayrı ayrı ayrıştırılır, sonra bu iki listenin üsleri birleştirilerek \((a-1)(a+1)=a^2-1\)'in asal çarpan yapısı elde edilir.
Her sabit \(a \ge 2\) için önce çevre sınırından \(v_{\min}\) hesaplanır, sonra \(\sqrt{2a^2-1}-a\) ifadesinden \(v_{\max}\) için kayan noktalı bir ilk tahmin alınır. Kayan nokta hesabı gerçek tabandan bir yukarı ya da bir aşağı sapabileceği için, sayım başlamadan önce bu tahmin tam sayı eşitsizlikleriyle düzeltilir. Ardından yalnızca \(v_{\max}\)'i aşmayan bölenler üretilir ve her \(v\) adayı dört şarttan geçirilir: \(v \ge v_{\min}\), doğru parite, \(u \ge v+2a\) ve \(a+u \le P\).
Farklı \(a\) değerleri birbirinden bağımsız olduğundan iş doğal biçimde paralelleşir. C++ ve Java sürümleri ardışık \(a\) bloklarını iş parçacıklarına dağıtır. Python sürümü de aynı bloklama fikrini süreç havuzuyla kullanır; faydalı değilse seri çalışmaya döner. Her işçi yalnızca küçük geçici bölen ve çarpan tamponlarına ihtiyaç duyar; büyük ortak yapı asal bölen tablosudur.
\(a_{\max}+1=\lfloor P/3\rfloor+1\) noktasına kadar kurulan en küçük asal bölen tablosu, sabit çarpanlar göz ardı edildiğinde \(O(P)\) zaman ve \(O(P)\) bellek ister. Bundan sonra sabit bir \(a\) için maliyetin baskın kısmı, \(a-1\) ve \(a+1\)'i çarpanlara ayırmak ve \(a^2-1\)'in geçerli bölenlerini üretmektir.
Toplam çalışma süresi için uygun bir özet
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right)$$
şeklindedir; burada \(\tau(n)\) bölen sayısı fonksiyonudur. Bu ifade, uygulamaların gerçek yapısıyla uyuşur: elek doğrusal büyüklükte bir ön işlemdir ve ana döngü zamanı \(a^2-1\)'in bölen yapısında harcanır. Paralel çalışma duvar saati süresini azaltır ama asimptotik sınırı değiştirmez. Eleğin ötesindeki ek bellek, yalnızca işçi başına küçük çalışma alanlarından ibarettir.
Queremos contar los triángulos de lados enteros \((a,b,c)\) con \(a \le b \le c\), perímetro \(a+b+c \le P\) y
$$a^2+b^2=c^2+1.$$
En la instancia de Project Euler, \(P=25{,}000{,}000\). La ecuación dice que el triángulo está a una sola unidad del caso rectángulo, de modo que un recorrido directo sobre todos los ternas es inviable.
La idea eficaz es fijar primero el lado menor \(a\), reescribir la ecuación como una factorización de \(a^2-1\) y contar solo los pares de divisores que todavía pueden satisfacer el perímetro y el orden \(a \le b \le c\).
La observación central es que, una vez fijado \(a\), los otros dos lados pueden recuperarse a partir de un par de factores de \(a^2-1\). Así, el problema deja de ser una búsqueda cuadrática en \((b,c)\) y pasa a ser una enumeración acotada de divisores.
Como \(a \le b \le c\), cualquier triángulo válido cumple
$$3a \le a+b+c \le P.$$
Por tanto,
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
Las implementaciones recorren exactamente ese rango de posibles valores para el lado menor y deducen el resto del triángulo a partir de ahí.
Partimos de
$$a^2+b^2=c^2+1,$$
que se reordena como
$$c^2-b^2=a^2-1.$$
Ahora definimos
$$u=b+c,\qquad v=c-b.$$
Entonces \(u>0\), \(v\ge 0\), y
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
A la inversa, si conocemos un par de factores \((u,v)\), obtenemos los lados mayores mediante
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
Así, para un \(a\) fijo, cada triángulo admisible corresponde a un par de divisores de \(a^2-1\) con la condición de paridad
$$u\equiv v \pmod 2,$$
porque \(b\) y \(c\) deben ser enteros.
Cuando \(a \ge 2\), se tiene \(a^2-1>0\), luego \(v>0\). En ese caso, cada elección válida del factor pequeño \(v\) determina \(u=(a^2-1)/v\) y por tanto determina \((b,c)\) de forma única.
El perímetro se vuelve especialmente simple en las nuevas variables:
$$a+b+c=a+u.$$
Por eso la restricción de perímetro es
$$u \le P-a.$$
Como \(u=(a^2-1)/v\), esto se transforma en la cota inferior
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
Los divisores demasiado pequeños hacen que \(u\) sea demasiado grande y se descartan enseguida.
La condición de orden \(a \le b\) equivale a
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
Sustituyendo \(u=(a^2-1)/v\), obtenemos
$$v^2+2av \le a^2-1.$$
Resolver esta desigualdad cuadrática da una cota superior para el factor pequeño:
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
Por tanto, la búsqueda de \(v\) queda completamente localizada:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
Solo pueden contribuir los divisores de \(a^2-1\) que estén dentro de ese intervalo.
Una vez impuesta esa cota superior, la desigualdad estricta del triángulo ya no necesita una comprobación aparte. En efecto,
$$a+b-c=a-v,$$
y la cota anterior implica \(v<a\). Así, cualquier divisor que supera las pruebas de rango y paridad ya produce automáticamente un triángulo auténtico con \(a \le b \le c\).
Cuando \(a=1\), el producto \(a^2-1\) se anula, así que la parametrización por divisores deja de ser la herramienta adecuada. La ecuación original se convierte en
$$1+b^2=c^2+1,$$
y de ahí se obtiene inmediatamente \(b=c\). Todos los triángulos de esta familia tienen la forma
$$ (1,b,b).$$
La condición sobre el perímetro es
$$1+2b \le P,$$
de modo que este caso aporta exactamente
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
soluciones y se cuenta por separado antes del bucle principal.
Tomemos \(a=5\). Entonces
$$a^2-1=24.$$
La cota superior que sale de \(a \le b\) es
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
Por lo tanto, solo merece la pena revisar los divisores \(v=1\) y \(v=2\).
Para \(v=1\), obtenemos \(u=24\), pero \(u-v=23\) es impar, así que \(b\) y \(c\) no serían enteros. Para \(v=2\), resulta \(u=12\), y entonces
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
Eso produce el triángulo válido \((5,5,7)\), y en efecto
$$5^2+5^2=7^2+1.$$
El algoritmo completo repite exactamente esta prueba acotada de divisores para cada \(a \le P/3\).
Las implementaciones en C++, Python y Java siguen el mismo plan matemático. Primero fijan \(a_{\max}=\lfloor P/3\rfloor\), añaden la contribución separada del caso \(a=1\) y construyen una tabla del menor factor primo hasta \(a_{\max}+1\). Ese rango basta porque no se factoriza \(a^2-1\) de manera directa. En su lugar se factorizan \(a-1\) y \(a+1\), y luego se combinan sus exponentes primos para reconstruir la factorización de \((a-1)(a+1)=a^2-1\).
Para cada \(a \ge 2\), la implementación calcula \(v_{\min}\) a partir del límite de perímetro y obtiene una primera estimación en coma flotante de \(v_{\max}\) usando \(\sqrt{2a^2-1}-a\). Como esa estimación puede quedar desplazada en una unidad por redondeo, se corrige con desigualdades enteras exactas antes de empezar a contar. Después se generan solo los divisores de \(a^2-1\) que no exceden \(v_{\max}\), y cada candidato \(v\) se comprueba contra las cuatro condiciones restantes: \(v \ge v_{\min}\), paridad correcta, \(u \ge v+2a\) y \(a+u \le P\).
El trabajo se divide de forma natural porque distintos valores de \(a\) son independientes. Las implementaciones en C++ y Java reparten bloques consecutivos de valores de \(a\) entre hilos, mientras que la implementación en Python usa la misma idea de bloques con procesos cuando compensa y, si no, ejecuta el recorrido de forma serial. Cada trabajador solo necesita pequeños buffers temporales para factores y divisores; la estructura grande compartida es la tabla de factores primos.
La tabla del menor factor primo hasta \(a_{\max}+1=\lfloor P/3\rfloor+1\) cuesta \(O(P)\) tiempo y \(O(P)\) memoria, salvo factores constantes. Después, el coste para un valor fijo de \(a\) está dominado por factorizar \(a-1\) y \(a+1\) y por generar los divisores admisibles de \(a^2-1\).
Una forma cómoda de resumir el tiempo total es
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$$
donde \(\tau(n)\) es la función que cuenta divisores. Esta expresión encaja con la estructura real de las implementaciones: la criba es un preproceso lineal en tamaño, y el bucle principal dedica su esfuerzo a la estructura de divisores de \(a^2-1\). La paralelización reduce el tiempo de reloj, pero no cambia la cota asintótica. La memoria adicional, aparte de la criba, es solo almacenamiento de trabajo pequeño por hilo o por proceso.
要求统计满足 \(a \le b \le c\)、周长 \(a+b+c \le P\)，并且
$$a^2+b^2=c^2+1$$
的整数边三角形个数。对 Project Euler 这道题来说，\(P=25{,}000{,}000\)。这个方程表示三角形只比直角三角形偏离了 1，因此如果直接枚举所有三元组 \((a,b,c)\)，规模会大得无法接受。
可行的方法是先固定最短边 \(a\)，再把方程改写成 \(a^2-1\) 的因子分解问题，只统计那些仍然可能满足周长限制和边长顺序限制的因子对。
核心观察是：一旦 \(a\) 固定，另外两条边 \(b,c\) 就可以从 \(a^2-1\) 的一个因子对中恢复出来。这样问题就从对 \((b,c)\) 的二次搜索，变成了带上下界的约数枚举。
由于 \(a \le b \le c\)，任何合法三角形都满足
$$3a \le a+b+c \le P.$$
因此
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
实现就是在这个范围内枚举可能的最短边 \(a\)，然后由它推导出整组三边。
从
$$a^2+b^2=c^2+1$$
出发，可以整理为
$$c^2-b^2=a^2-1.$$
现在定义
$$u=b+c,\qquad v=c-b.$$
那么 \(u>0\)、\(v\ge 0\)，并且
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
反过来，如果知道一个因子对 \((u,v)\)，就能恢复出另外两条边：
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
所以对于固定的 \(a\)，每一个可行三角形都对应 \(a^2-1\) 的一个因子对，但还必须满足奇偶性条件
$$u\equiv v \pmod 2,$$
这样 \(b\) 和 \(c\) 才会是整数。
当 \(a \ge 2\) 时，\(a^2-1>0\)，因此 \(v>0\)。此时只要选定较小的因子 \(v\)，就能唯一确定 \(u=(a^2-1)/v\)，进而唯一确定 \((b,c)\)。
在新变量下，周长写成非常简单的形式：
$$a+b+c=a+u.$$
因此周长限制就是
$$u \le P-a.$$
再代入 \(u=(a^2-1)/v\)，得到 \(v\) 的下界
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
这意味着太小的约数会让 \(u\) 过大，因而不可能满足周长条件。
边长顺序条件 \(a \le b\) 等价于
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
把 \(u=(a^2-1)/v\) 代入后，得到
$$v^2+2av \le a^2-1.$$
解这个二次不等式，就得到较小因子 \(v\) 的上界：
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
于是 \(v\) 的搜索范围被完全限定为
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
只有落在这个区间里的约数才值得检查。
一旦施加了这个上界，严格三角形不等式就不需要再单独处理了。因为
$$a+b-c=a-v,$$
而上面的约束已经推出 \(v<a\)。所以只要约数通过了区间和奇偶性检查，它自动给出一个真正的三角形，并且满足 \(a \le b \le c\)。
当 \(a=1\) 时，\(a^2-1=0\)，上面的约数参数化就不再合适。原方程变成
$$1+b^2=c^2+1,$$
马上得到 \(b=c\)。因此这一族三角形全都形如
$$ (1,b,b).$$
周长条件变成
$$1+2b \le P,$$
所以这一部分恰好贡献
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
个解。实现会在主循环开始前把这部分单独加入答案。
取 \(a=5\)。此时
$$a^2-1=24.$$
由 \(a \le b\) 导出的上界是
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
因此只需要看 \(v=1\) 和 \(v=2\) 这两个约数。
当 \(v=1\) 时，\(u=24\)，但 \(u-v=23\) 是奇数，所以 \(b,c\) 不是整数。 当 \(v=2\) 时，\(u=12\)，于是
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
这就得到合法三角形 \((5,5,7)\)，并且确实满足
$$5^2+5^2=7^2+1.$$
完整算法就是对每个 \(a \le P/3\) 重复同样的有界约数测试。
C++、Python 和 Java 实现遵循完全相同的数学框架。它们先设定 \(a_{\max}=\lfloor P/3\rfloor\)，加入 \(a=1\) 这一特殊家族的贡献，然后建立一个到 \(a_{\max}+1\) 为止的最小质因子表。之所以只需要做到这个范围，是因为实现并不直接分解 \(a^2-1\)。它们先分别分解 \(a-1\) 和 \(a+1\)，再把这两部分的质因子指数合并起来，从而恢复 \((a-1)(a+1)=a^2-1\) 的质因子分解。
对于每个固定的 \(a \ge 2\)，实现先根据周长限制算出 \(v_{\min}\)，再用 \(\sqrt{2a^2-1}-a\) 得到 \(v_{\max}\) 的浮点初值。由于浮点误差可能让这个值偏离真实下取整一个单位，程序会先用精确的整数不等式把它修正到正确位置，再开始计数。之后只生成那些不超过 \(v_{\max}\) 的约数，并对每个候选 \(v\) 依次检查四个剩余条件：\(v \ge v_{\min}\)、奇偶性正确、\(u \ge v+2a\)、以及 \(a+u \le P\)。
不同的 \(a\) 之间彼此独立，因此这部分工作天然可以并行。C++ 和 Java 实现把连续的 \(a\) 区间分给多个线程；Python 实现也采用同样的分块思想，在合适时使用进程池，否则就顺序执行。每个工作单元只需要很小的临时因子和约数缓冲区，所以真正的大型共享数据结构只有那张最小质因子表。
建立到 \(a_{\max}+1=\lfloor P/3\rfloor+1\) 的最小质因子表，需要 \(O(P)\) 时间和 \(O(P)\) 空间，常数因子忽略不计。之后，对固定一个 \(a\) 来说，主要成本来自分解 \(a-1\) 与 \(a+1\)，以及生成 \(a^2-1\) 的可行约数。
总运行时间可以方便地概括为
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$$
其中 \(\tau(n)\) 表示约数个数函数。这个表达式与实现结构完全一致：筛法是线性规模的预处理，主循环的主要工作量则集中在 \(a^2-1\) 的约数结构上。并行化只会改善实际耗时，不会改变渐近复杂度。除筛表之外，额外内存只包括很小的线程局部或进程局部工作区。
Нужно посчитать треугольники с целыми сторонами \((a,b,c)\), для которых \(a \le b \le c\), периметр \(a+b+c \le P\), и выполняется
$$a^2+b^2=c^2+1.$$
В задаче Project Euler берется \(P=25{,}000{,}000\). Это семейство треугольников отличается от прямоугольных ровно на 1, поэтому прямой перебор всех троек \((a,b,c)\) слишком дорог.
Рабочая идея состоит в том, чтобы сначала зафиксировать наименьшую сторону \(a\), затем переписать уравнение как разложение числа \(a^2-1\) на множители и считать только те пары делителей, которые еще могут удовлетворить ограничению на периметр и условию порядка \(a \le b \le c\).
Главное наблюдение такое: после фиксации \(a\) стороны \(b\) и \(c\) восстанавливаются из одной пары множителей числа \(a^2-1\). Тем самым задача превращается не в квадратичный поиск по \((b,c)\), а в ограниченный перебор делителей.
Из условия \(a \le b \le c\) следует
$$3a \le a+b+c \le P.$$
Значит,
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
Именно по этому диапазону возможных значений наименьшей стороны и проходят реализации, а остальные стороны выводятся уже из выбранного \(a\).
Начинаем с
$$a^2+b^2=c^2+1,$$
что можно переписать как
$$c^2-b^2=a^2-1.$$
Теперь введем
$$u=b+c,\qquad v=c-b.$$
Тогда \(u>0\), \(v\ge 0\), и
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
Обратно, если известна пара множителей \((u,v)\), то две большие стороны равны
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
Следовательно, для фиксированного \(a\) каждый допустимый треугольник соответствует паре делителей числа \(a^2-1\), причем должна выполняться условие четности
$$u\equiv v \pmod 2,$$
иначе \(b\) и \(c\) не будут целыми.
Если \(a \ge 2\), то \(a^2-1>0\), а значит \(v>0\). Тогда каждый допустимый выбор меньшего множителя \(v\) однозначно задает \(u=(a^2-1)/v\), а вместе с ним и пару \((b,c)\).
В новых переменных периметр имеет особенно простой вид:
$$a+b+c=a+u.$$
Поэтому ограничение на периметр выглядит так:
$$u \le P-a.$$
Подставляя \(u=(a^2-1)/v\), получаем нижнюю границу
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
Слишком маленькие делители дают слишком большое \(u\), так что их можно сразу отбросить.
Условие порядка \(a \le b\) эквивалентно
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
Если теперь подставить \(u=(a^2-1)/v\), получится
$$v^2+2av \le a^2-1.$$
Решение этого квадратного неравенства дает верхнюю границу для меньшего множителя:
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
Значит, поиск по \(v\) полностью локализован:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
Проверять нужно только делители \(a^2-1\), лежащие в этом промежутке.
После введения этой верхней границы строгое неравенство треугольника уже не требует отдельной проверки. Действительно,
$$a+b-c=a-v,$$
а из полученной оценки следует \(v<a\). Поэтому любой делитель, прошедший проверки диапазона и четности, автоматически задает настоящий треугольник с \(a \le b \le c\).
При \(a=1\) произведение \(a^2-1\) равно нулю, поэтому описанная параметризация делителями здесь не подходит. Исходное уравнение превращается в
$$1+b^2=c^2+1,$$
откуда сразу следует \(b=c\). Значит, все треугольники этого семейства имеют вид
$$ (1,b,b).$$
Условие на периметр тогда равно
$$1+2b \le P,$$
и эта ветвь дает ровно
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
решений. Поэтому ее считают отдельно до основного цикла по делителям.
Возьмем \(a=5\). Тогда
$$a^2-1=24.$$
Верхняя граница, вытекающая из \(a \le b\), равна
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
Значит, достаточно проверить только делители \(v=1\) и \(v=2\).
Для \(v=1\) получаем \(u=24\), но \(u-v=23\) нечетно, поэтому \(b\) и \(c\) не будут целыми. Для \(v=2\) имеем \(u=12\), а значит
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
Получается допустимый треугольник \((5,5,7)\), и действительно
$$5^2+5^2=7^2+1.$$
Именно такую ограниченную проверку делителей алгоритм повторяет для каждого \(a \le P/3\).
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они устанавливают \(a_{\max}=\lfloor P/3\rfloor\), добавляют отдельный вклад случая \(a=1\) и строят таблицу наименьшего простого делителя до \(a_{\max}+1\). Этого диапазона достаточно, потому что число \(a^2-1\) не факторизуется напрямую. Вместо этого отдельно факторизуются \(a-1\) и \(a+1\), а затем их простые показатели объединяются, чтобы восстановить разложение \((a-1)(a+1)=a^2-1\).
Для каждого фиксированного \(a \ge 2\) вычисляется \(v_{\min}\) из ограничения на периметр и берется первоначальная вещественная оценка для \(v_{\max}\) по формуле \(\sqrt{2a^2-1}-a\). Поскольку округление с плавающей точкой может ошибиться на единицу, эта оценка затем поправляется точными целочисленными неравенствами. После этого генерируются только те делители числа \(a^2-1\), которые не превосходят \(v_{\max}\), и каждый кандидат \(v\) проходит четыре оставшиеся проверки: \(v \ge v_{\min}\), правильная четность, \(u \ge v+2a\) и \(a+u \le P\).
Работа естественно распараллеливается, потому что разные значения \(a\) независимы. Реализации на C++ и Java раздают последовательные блоки значений \(a\) рабочим потокам. Реализация на Python использует ту же идею блоков с рабочими процессами, когда это оправдано, и иначе выполняет проход последовательно. Каждому рабочему нужны только небольшие временные буферы для факторов и делителей; крупной общей структурой остается таблица простых делителей.
Построение таблицы наименьшего простого делителя до \(a_{\max}+1=\lfloor P/3\rfloor+1\) требует \(O(P)\) времени и \(O(P)\) памяти с точностью до постоянных множителей. После этого стоимость для одного фиксированного \(a\) определяется в основном факторизацией \(a-1\) и \(a+1\), а также генерацией допустимых делителей числа \(a^2-1\).
Удобная сводка общей трудоемкости такова:
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$$
где \(\tau(n)\) обозначает функцию числа делителей. Эта формула точно отражает структуру реализаций: решето является линейной по размеру предварительной обработкой, а основное время уходит на делительную структуру числа \(a^2-1\). Параллельное исполнение сокращает реальное время работы, но не меняет асимптотическую оценку. Дополнительная память сверх решета сводится к небольшим локальным рабочим буферам потоков или процессов.
نريد عدّ المثلثات ذات الأضلاع الصحيحة \((a,b,c)\) التي تحقق \(a \le b \le c\)، ومحيطها \(a+b+c \le P\)، وتلبي المعادلة
$$a^2+b^2=c^2+1.$$
في نسخة Project Euler تكون \(P=25{,}000{,}000\). هذه المعادلة تعني أن المثلث يبتعد عن المثلث القائم بمقدار 1 فقط، ولذلك فإن الفحص المباشر لجميع الثلاثيات \((a,b,c)\) غير عملي تمامًا.
الفكرة الفعالة هي تثبيت الضلع الأصغر \(a\) أولًا، ثم إعادة كتابة المعادلة على صورة تحليل للعدد \(a^2-1\)، وبعد ذلك نعدّ فقط أزواج القواسم التي ما زال يمكنها أن تحقق شرط المحيط وترتيب الأضلاع.
الملاحظة الأساسية هي أنه بعد تثبيت \(a\)، يمكن استرجاع الضلعين \(b\) و\(c\) من زوج عوامل للعدد \(a^2-1\). وهكذا تتحول المسألة من بحث تربيعي في \((b,c)\) إلى تعداد مقيد للقواسم.
بما أن \(a \le b \le c\)، فإن كل مثلث صالح يحقق
$$3a \le a+b+c \le P.$$
ومن ثم
$$1 \le a \le \left\lfloor \frac{P}{3}\right\rfloor.$$
لذلك تدور الخوارزمية على جميع القيم الممكنة للضلع الأصغر فقط، ثم تستنتج منها بقية أضلاع المثلث.
نبدأ من
$$a^2+b^2=c^2+1,$$
ثم نعيد ترتيبها إلى
$$c^2-b^2=a^2-1.$$
الآن نعرّف
$$u=b+c,\qquad v=c-b.$$
عندئذ يكون \(u>0\) و\(v\ge 0\)، كما أن
$$uv=(b+c)(c-b)=c^2-b^2=a^2-1.$$
وبالعكس، إذا عرفنا زوج العوامل \((u,v)\)، فإن الضلعين الأكبرين يساويان
$$b=\frac{u-v}{2},\qquad c=\frac{u+v}{2}.$$
إذن لكل \(a\) ثابت، يقابل كل مثلث مقبول زوج قواسم للعدد \(a^2-1\)، لكن يجب أيضًا أن يتحقق شرط الزوجية
$$u\equiv v \pmod 2,$$
حتى يكون \(b\) و\(c\) عددين صحيحين.
إذا كان \(a \ge 2\)، فإن \(a^2-1>0\)، وبالتالي \(v>0\). وعندها فإن اختيار العامل الأصغر \(v\) يحدد \(u=(a^2-1)/v\) ثم يحدد \((b,c)\) بصورة وحيدة.
في المتغيرات الجديدة يصبح المحيط بسيطًا جدًا:
$$a+b+c=a+u.$$
لذلك فإن شرط المحيط هو
$$u \le P-a.$$
ومع \(u=(a^2-1)/v\) نحصل على الحد الأدنى
$$v \ge v_{\min}=\left\lceil\frac{a^2-1}{P-a}\right\rceil.$$
أي أن القواسم الصغيرة جدًا تجعل \(u\) كبيرًا أكثر من اللازم، فتُستبعد فورًا.
أما شرط الترتيب \(a \le b\) فيكافئ
$$a \le \frac{u-v}{2}\qquad\Longleftrightarrow\qquad u \ge v+2a.$$
وبالتعويض عن \(u\) نحصل على
$$v^2+2av \le a^2-1.$$
وحل هذه المتباينة التربيعية يعطي حدًا أعلى للعامل الأصغر:
$$v \le v_{\max}=\left\lfloor \sqrt{2a^2-1}-a\right\rfloor.$$
وهكذا تصبح مساحة البحث عن \(v\) محددة تمامًا:
$$v_{\min} \le v \le v_{\max},\qquad v \mid (a^2-1).$$
فقط القواسم الواقعة داخل هذا المجال يمكن أن تنتج حلولًا.
وبعد فرض هذا الحد الأعلى، لا نحتاج إلى اختبار منفصل لمتباينة المثلث الصارمة. ذلك لأن
$$a+b-c=a-v,$$
ومن القيد السابق نستنتج \(v<a\). لذا فإن أي قاسم يمر باختباري المجال والزوجية يعطي تلقائيًا مثلثًا حقيقيًا يحقق \(a \le b \le c\).
عندما يكون \(a=1\)، فإن \(a^2-1=0\)، ولذلك لا تكون بارامترة القواسم السابقة هي الأداة المناسبة. تصبح المعادلة الأصلية
$$1+b^2=c^2+1,$$
ومنها مباشرة \(b=c\). إذن جميع مثلثات هذه العائلة تأخذ الشكل
$$ (1,b,b).$$
ويصبح شرط المحيط
$$1+2b \le P,$$
فتعطي هذه الحالة بالضبط
$$\left\lfloor \frac{P-1}{2}\right\rfloor$$
حلًا، ولذلك تُحسب منفصلة قبل بدء الحلقة الرئيسية.
لنأخذ \(a=5\). عندئذ
$$a^2-1=24.$$
والحد الأعلى الناتج من الشرط \(a \le b\) هو
$$v_{\max}=\left\lfloor \sqrt{49}-5\right\rfloor=2.$$
إذًا لا نحتاج إلى فحص إلا القاسمين \(v=1\) و\(v=2\).
إذا كان \(v=1\)، فإن \(u=24\)، لكن \(u-v=23\) فردي، ولذلك لن يكون \(b\) و\(c\) عددين صحيحين. أما إذا كان \(v=2\)، فنحصل على \(u=12\)، ومن ثم
$$b=\frac{12-2}{2}=5,\qquad c=\frac{12+2}{2}=7.$$
وهذا يعطي المثلث الصحيح \((5,5,7)\)، وبالفعل
$$5^2+5^2=7^2+1.$$
وتكرر الخوارزمية هذه التجربة نفسها، لكن بصورة منهجية، لكل \(a \le P/3\).
تتبع تطبيقات C++ وPython وJava الخطة الرياضية نفسها. فهي تبدأ بتحديد \(a_{\max}=\lfloor P/3\rfloor\)، ثم تضيف المساهمة الخاصة بحالة \(a=1\)، ثم تبني جدولًا لأصغر عامل أولي حتى \(a_{\max}+1\). ويكفي هذا الحد لأن التنفيذ لا يحلل \(a^2-1\) مباشرة. بدلًا من ذلك، يُحلَّل كل من \(a-1\) و\(a+1\) على حدة، ثم تُدمج أسس العوامل الأولية للحصول على تحليل \((a-1)(a+1)=a^2-1\).
لكل قيمة ثابتة \(a \ge 2\)، تحسب الشفرة \(v_{\min}\) من شرط المحيط، ثم تأخذ تقديرًا أوليًا عائمًا لـ \(v_{\max}\) من \(\sqrt{2a^2-1}-a\). وبما أن التقريب العائم قد يخطئ بمقدار واحد، فإن هذا التقدير يُصحَّح قبل العد باستعمال متباينات صحيحة دقيقة. بعد ذلك تُولَّد فقط قواسم \(a^2-1\) التي لا تتجاوز \(v_{\max}\)، ويُفحص كل مرشح \(v\) وفق الشروط الأربعة المتبقية: \(v \ge v_{\min}\)، والزوجية الصحيحة، و\(u \ge v+2a\)، و\(a+u \le P\).
هذا العمل يقبل التوازي بطبيعته لأن القيم المختلفة لـ \(a\) مستقلة عن بعضها. توزع تطبيقتا C++ وJava كتلًا متتالية من قيم \(a\) على الخيوط، بينما يستخدم تطبيق Python الفكرة نفسها مع العمليات عندما يكون ذلك مفيدًا، ويعود إلى التنفيذ التسلسلي عند الحاجة. كل عامل يحتاج فقط إلى مخازن مؤقتة صغيرة للعوامل والقواسم، لذا فإن البنية الكبيرة المشتركة فعليًا هي جدول العوامل الأولية.
بناء جدول أصغر عامل أولي حتى \(a_{\max}+1=\lfloor P/3\rfloor+1\) يكلف \(O(P)\) زمنًا و\(O(P)\) ذاكرة مع تجاهل الثوابت. وبعد ذلك تصبح كلفة القيمة الواحدة من \(a\) محكومة أساسًا بتحليل \(a-1\) و\(a+1\) وتوليد القواسم المقبولة للعدد \(a^2-1\).
ويمكن تلخيص زمن التنفيذ الكلي على الصورة
$$O\!\left(P+\sum_{a\le P/3}\tau(a^2-1)\right),$$
حيث \(\tau(n)\) هي دالة عدد القواسم. هذا يطابق بنية التنفيذ بدقة: فالسير هو مرحلة تمهيدية خطية الحجم، والحلقة الرئيسية تقضي وقتها في بنية قواسم \(a^2-1\). أما التوازي فيحسن زمن التنفيذ الفعلي فقط، ولا يغير الرتبة التقاربية. والذاكرة الإضافية بعد جدول السير تقتصر على مساحات عمل صغيرة محلية للخيوط أو للعمليات.