We consider integer-sided triangles \(ABC\) whose perimeter \(p\) does not exceed a bound \(P\). Let \(I\) be the incenter, and define
$$L=p+IA+IB+IC.$$
The task is to sum \(L\) over exactly those triangles for which the three distances from the incenter to the vertices are integers. A brute-force scan over all side triples is far too expensive for the real limit, so the solution rewrites the triangle in coordinates that expose the arithmetic structure of the incenter directly.
The key observation is that the incenter conditions become much simpler after switching from side lengths to semiperimeter coordinates.
Let
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Then \(x,y,z>0\), and the original sides can be recovered from
$$a=y+z,\qquad b=x+z,\qquad c=x+y.$$
Because \(s=x+y+z\), the perimeter is
$$p=2s=2(x+y+z).$$
Using Heron's formula \(\Delta^2=s(s-a)(s-b)(s-c)\) together with \(\Delta=rs\), we obtain
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
So every admissible triangle corresponds to positive integers \(x,y,z,r\) satisfying that identity.
The tangency point on side \(BC\) forms a right triangle with legs \(r\) and \(x\), so
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
Therefore each of \(x,y,z\) must participate in a Pythagorean relation with the same inradius \(r\). For a fixed \(r\), write
$$t^2-x^2=r^2,$$
or equivalently
$$\left(t-x\right)\left(t+x\right)=r^2.$$
If we set \(d=t-x\) and \(e=t+x\), then \(de=r^2\), \(d\le e\), and \(d\) and \(e\) must have the same parity. This gives
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
So enumerating divisors \(d\mid r^2\) generates all possible integer pairs \((x,t)\) with \(x^2+r^2=t^2\). The same list serves for \(y\) and \(z\) as well.
Once two entries \(x\) and \(y\) are chosen from that list, the inradius formula determines \(z\). Starting from
$$r^2=\frac{xyz}{x+y+z},$$
we solve for \(z\):
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
This immediately explains the filters used by the implementation: the denominator must be positive, so
$$xy>r^2,$$
and the numerator must be divisible by that denominator so that \(z\) is an integer. Finally, \(z\) must itself belong to the previously generated Pythagorean list; otherwise \(IC\) would not be integral.
The variables \(x,y,z\) are symmetric, so we may impose
$$x\le y\le z$$
to count each triangle once. The perimeter condition becomes
$$2(x+y+z)\le P,$$
or equivalently
$$z\le \frac{P}{2}-x-y.$$
For each valid triple the contribution is
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
There is also a global bound on \(r\). Among triangles with fixed perimeter, the equilateral triangle maximizes the inradius, so
$$r\le \frac{P\sqrt{3}}{18}.$$
That turns the search into a finite loop over
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Take \(r=21\), so \(r^2=441\). Factor pairs of \(441\) with the same parity give several Pythagorean options. Two useful ones are
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
and
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
Now choose \(x=y=28\). Then
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
Because \(72\) is already in the same Pythagorean list, all three vertex distances are integral:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
The corresponding sides are
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
so the perimeter is \(256\) and the contribution is
$$L=256+35+35+75=401.$$
The C++, Python, and Java implementations all follow the same pipeline. First they compute the upper limit \(\left\lfloor P\sqrt{3}/18\right\rfloor\) for the inradius and build a smallest-prime-factor sieve up to that value. The sieve makes it cheap to factor each candidate \(r\).
For a fixed inradius, the implementation doubles the exponents in the factorization of \(r\) to enumerate every divisor of \(r^2\). Each divisor pair produces one candidate \((x,t)\) with \(x^2+r^2=t^2\), and these candidates are stored in sorted order by \(x\).
It then loops over ordered pairs \(x\le y\), computes the forced value of \(z\), and rejects the pair unless the divisibility condition, the positivity condition, and the perimeter bound all hold. A binary search checks whether that \(z\) already appears in the candidate list, which is equivalent to checking that \(z^2+r^2\) is a square. Every surviving triple contributes the perimeter plus the three already-determined vertex distances to the running total.
The larger implementations can split the inradius interval into chunks and sum those chunks independently. They also use small direct checks and the known checkpoint at \(P=1000\), namely \(3619\), before evaluating the full bound.
Let
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Building the smallest-prime-factor sieve costs \(O(R\log\log R)\) time and \(O(R)\) memory. For a fixed \(r\), suppose \(m(r)\) candidate values survive the divisor-to-leg conversion. Factoring \(r\) and generating divisors is essentially proportional to the number of divisors of \(r^2\), sorting costs \(O(m(r)\log m(r))\), and the pair search costs \(O(m(r)^2\log m(r))\) because each pair uses one binary search for \(z\).
Thus the total running time is
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
with \(O(R+m_{\max})\) memory. In practice \(m(r)\) is small, so this arithmetic reformulation is dramatically faster than scanning all integer side triples.
Betrachtet werden Dreiecke \(ABC\) mit ganzzahligen Seiten und Umfang \(p\le P\). Sei \(I\) der Inkreismittelpunkt und
$$L=p+IA+IB+IC.$$
Gesucht ist die Summe von \(L\) über genau diejenigen Dreiecke, bei denen die drei Abstände vom Inkreismittelpunkt zu den Ecken ganzzahlig sind. Eine direkte Suche über alle Seitentripel ist für die echte Schranke zu teuer, daher formt die Lösung das Problem in Koordinaten um, in denen die Arithmetik des Inkreismittelpunkts direkt sichtbar wird.
Die entscheidende Beobachtung ist, dass die Bedingungen an den Inkreismittelpunkt deutlich einfacher werden, wenn man statt der Seitenlängen die Abstände zum Halbumfang verwendet.
Setze
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Dann sind \(x,y,z>0\), und die ursprünglichen Seiten lassen sich aus
$$a=y+z,\qquad b=x+z,\qquad c=x+y$$
zurückgewinnen. Weil \(s=x+y+z\) gilt, ist der Umfang
$$p=2s=2(x+y+z).$$
Mit der Heron-Formel \(\Delta^2=s(s-a)(s-b)(s-c)\) und \(\Delta=rs\) folgt
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
Jedes zulässige Dreieck entspricht also positiven ganzen Zahlen \(x,y,z,r\), die diese Identität erfüllen.
Der Berührpunkt des Inkreises auf der Seite \(BC\) bildet mit \(A\) ein rechtwinkliges Dreieck mit Katheten \(r\) und \(x\). Daher gilt
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
Also müssen \(x,y,z\) jeweils zusammen mit demselben Inkreisradius \(r\) in einer pythagoreischen Beziehung stehen. Für festes \(r\) schreiben wir
$$t^2-x^2=r^2,$$
also
$$\left(t-x\right)\left(t+x\right)=r^2.$$
Mit \(d=t-x\) und \(e=t+x\) erhält man \(de=r^2\), \(d\le e\), und \(d\) sowie \(e\) müssen dieselbe Parität haben. Damit ergibt sich
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
Durch das Auflisten aller Teiler \(d\mid r^2\) bekommt man somit genau die ganzzahligen Paare \((x,t)\) mit \(x^2+r^2=t^2\). Dieselbe Liste kann ebenso für \(y\) und \(z\) benutzt werden.
Sobald zwei Werte \(x\) und \(y\) aus dieser Liste gewählt sind, ist \(z\) durch die Inkreisformel festgelegt. Aus
$$r^2=\frac{xyz}{x+y+z}$$
folgt durch Auflösen nach \(z\)
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
Damit werden die Filter des Programms sofort verständlich: Der Nenner muss positiv sein, also
$$xy>r^2,$$
und der Zähler muss durch diesen Nenner teilbar sein, damit \(z\) ganzzahlig ist. Außerdem muss auch \(z\) selbst in der zuvor erzeugten pythagoreischen Liste vorkommen; sonst wäre \(IC\) nicht ganzzahlig.
Die Variablen \(x,y,z\) sind symmetrisch, daher dürfen wir
$$x\le y\le z$$
fordern, um jedes Dreieck genau einmal zu zählen. Die Umfangsbedingung wird zu
$$2(x+y+z)\le P,$$
also äquivalent zu
$$z\le \frac{P}{2}-x-y.$$
Für jedes gültige Tripel ist der Beitrag
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
Zusätzlich gibt es eine globale Schranke für \(r\). Unter allen Dreiecken mit festem Umfang maximiert das gleichseitige Dreieck den Inkreisradius, also
$$r\le \frac{P\sqrt{3}}{18}.$$
Damit wird die Suche zu einer endlichen Schleife über
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Nehmen wir \(r=21\), also \(r^2=441\). Faktorpaare von \(441\) mit gleicher Parität liefern mehrere pythagoreische Möglichkeiten. Zwei nützliche sind
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
und
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
Wählen wir nun \(x=y=28\). Dann ergibt sich
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
Da \(72\) bereits in derselben pythagoreischen Liste vorkommt, sind alle drei Eckabstände ganzzahlig:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
Die zugehörigen Seiten sind
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
also hat das Dreieck Umfang \(256\), und der Beitrag ist
$$L=256+35+35+75=401.$$
Die C++-, Python- und Java-Implementierungen folgen alle derselben Pipeline. Zuerst berechnen sie die obere Grenze \(\left\lfloor P\sqrt{3}/18\right\rfloor\) für den Inkreisradius und bauen bis dorthin ein Sieb der kleinsten Primfaktoren auf. Damit lässt sich jedes Kandidaten-\(r\) schnell faktorisieren.
Für einen festen Inkreisradius verdoppelt die Implementierung die Exponenten in der Primfaktorzerlegung von \(r\), um alle Teiler von \(r^2\) zu erzeugen. Jedes Teilerpaar liefert ein Kandidatenpaar \((x,t)\) mit \(x^2+r^2=t^2\), und diese Kandidaten werden nach \(x\) sortiert gespeichert.
Danach läuft der Code über geordnete Paare \(x\le y\), berechnet den erzwungenen Wert von \(z\) und verwirft das Paar, falls Teilbarkeit, Positivität oder die Umfangsschranke nicht erfüllt sind. Eine binäre Suche prüft, ob dieses \(z\) bereits in der Kandidatenliste vorkommt; das ist gleichbedeutend damit, dass \(z^2+r^2\) ein Quadrat ist. Jedes überlebende Tripel trägt den Umfang plus die drei bereits bestimmten Eckabstände zur Summe bei.
Die größeren Implementierungen können das Inkreisintervall in Blöcke aufteilen und diese unabhängig aufsummieren. Zusätzlich werden kleine Direktprüfungen und der bekannte Kontrollwert \(3619\) für \(P=1000\) verwendet, bevor die volle Schranke ausgewertet wird.
Sei
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Das Sieb der kleinsten Primfaktoren kostet \(O(R\log\log R)\) Zeit und \(O(R)\) Speicher. Für festes \(r\) sei \(m(r)\) die Anzahl der Kandidatenwerte nach der Umwandlung von Teilern in Katheten. Das Faktorisieren von \(r\) und das Erzeugen der Teiler ist im Wesentlichen proportional zur Anzahl der Teiler von \(r^2\), das Sortieren kostet \(O(m(r)\log m(r))\), und die Paarsuche kostet \(O(m(r)^2\log m(r))\), weil jedes Paar genau eine binäre Suche für \(z\) ausführt.
Die gesamte Laufzeit ist damit
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
bei \(O(R+m_{\max})\) Speicher. In der Praxis ist \(m(r)\) klein, daher ist diese arithmetische Umformung drastisch schneller als das Durchmustern aller ganzzahligen Seitentripel.
\(ABC\) üçgeninin kenarları tam sayı ve çevresi \(p\le P\) olacak. \(I\) içmerkez olsun ve
$$L=p+IA+IB+IC$$
tanımını yapalım. İstenen şey, içmerkezden köşelere olan üç uzaklığın da tam sayı olduğu tüm üçgenler üzerinde bu \(L\) değerlerinin toplamıdır. Gerçek üst sınır için bütün kenar üçlülerini doğrudan taramak çok pahalı olduğundan çözüm, problemi içmerkezin aritmetik yapısını açıkça gösteren koordinatlara dönüştürür.
Temel fikir, kenar uzunlukları yerine yarı çevreye göre tanımlanan farkları kullanınca içmerkez koşullarının çok daha düzenli hale gelmesidir.
Şöyle tanımlayalım:
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Böylece \(x,y,z>0\) olur ve kenarlar
$$a=y+z,\qquad b=x+z,\qquad c=x+y$$
şeklinde geri elde edilir. Ayrıca \(s=x+y+z\) olduğundan çevre
$$p=2s=2(x+y+z)$$
olur. Heron formülü \(\Delta^2=s(s-a)(s-b)(s-c)\) ve \(\Delta=rs\) bağıntısı birlikte
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}$$
sonucunu verir. Yani uygun her üçgen, bu özdeşliği sağlayan pozitif tam sayılar \(x,y,z,r\) ile temsil edilir.
İçteğet çemberinin \(BC\) üzerindeki temas noktası ile \(A\) arasında oluşan dik üçgende dik kenarlar \(r\) ve \(x\) olduğundan
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
Demek ki \(x,y,z\) değerlerinin her biri aynı \(r\) ile bir Pisagor ilişkisine girmelidir. Sabit bir \(r\) için
$$t^2-x^2=r^2$$
ve dolayısıyla
$$\left(t-x\right)\left(t+x\right)=r^2$$
yazarız. \(d=t-x\) ve \(e=t+x\) dersek \(de=r^2\), \(d\le e\) olur ve \(d\) ile \(e\) aynı paritye sahip olmalıdır. Buradan
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}$$
elde edilir. Böylece \(r^2\)'nin bölenlerini dolaşmak, \(x^2+r^2=t^2\) sağlayan tüm tam sayı \((x,t)\) çiftlerini üretir. Aynı liste \(y\) ve \(z\) için de kullanılır.
Bu listeden iki değer \(x\) ve \(y\) seçildiğinde içyarıçap formülü \(z\)'yi zorunlu olarak belirler. Başlangıçta
$$r^2=\frac{xyz}{x+y+z}$$
vardır; buradan \(z\) için çözülürse
$$z=\frac{r^2(x+y)}{xy-r^2}$$
elde edilir. Böylece kodun filtreleri doğal hale gelir: payda pozitif olmalı, yani
$$xy>r^2,$$
ve \(z\)'nin tam sayı olması için payın bu paydaya tam bölünmesi gerekir. Son olarak \(z\) de önceden üretilen Pisagor listesinde bulunmalıdır; aksi halde \(IC\) tam sayı olmaz.
\(x,y,z\) değişkenleri simetrik olduğundan
$$x\le y\le z$$
şartını koyup her üçgeni yalnızca bir kez sayabiliriz. Çevre koşulu
$$2(x+y+z)\le P$$
ve eşdeğer olarak
$$z\le \frac{P}{2}-x-y$$
şeklindedir. Geçerli her üçlü için katkı
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}$$
Ayrıca \(r\) için küresel bir üst sınır vardır. Sabit çevrede içyarıçapı en büyük yapan üçgen eşkenardır; dolayısıyla
$$r\le \frac{P\sqrt{3}}{18}.$$
Böylece arama
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor$$
aralığında sonlu bir döngüye indirgenir.
\(r=21\) alalım; o halde \(r^2=441\). \(441\)'in aynı parityeye sahip çarpan çiftleri birkaç Pisagor seçeneği üretir. İki yararlı örnek şunlardır:
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
ve
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
Şimdi \(x=y=28\) seçelim. O zaman
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72$$
olur. \(72\) aynı Pisagor listesinde bulunduğu için üç köşe uzaklığının hepsi tam sayıdır:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
Buna karşılık gelen kenarlar
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56$$
olur; çevre \(256\)'dır ve katkı
$$L=256+35+35+75=401$$
çıkar.
C++, Python ve Java uygulamalarının akışı aynıdır. Önce içyarıçap için üst sınır \(\left\lfloor P\sqrt{3}/18\right\rfloor\) hesaplanır ve bu değere kadar en küçük asal çarpanları tutan bir elek hazırlanır. Bu sayede her aday \(r\) hızlıca çarpanlara ayrılır.
Sabit bir içyarıçap için uygulama, \(r\)'nin asal üslerini ikiyle çarparak \(r^2\)'nin bütün bölenlerini üretir. Her bölen çifti \(x^2+r^2=t^2\) sağlayan bir \((x,t)\) adayı verir ve adaylar \(x\)'e göre sıralı halde saklanır.
Daha sonra kod, sıralı \(x\le y\) çiftleri üzerinde dolaşır, zorunlu \(z\) değerini hesaplar ve bölünebilirlik, pozitiflik veya çevre sınırı sağlanmıyorsa çifti eler. İkili arama ile bu \(z\)'nin aday listesinde bulunup bulunmadığı kontrol edilir; bu, \(z^2+r^2\)'nin kare olmasıyla eşdeğerdir. Ayakta kalan her üçlü, çevreyi ve önceden belirlenmiş üç köşe uzaklığını toplam değere ekler.
Daha büyük uygulamalar içyarıçap aralığını parçalara bölüp bu parçaları bağımsız toplayabilir. Ayrıca tam aralığa geçmeden önce küçük doğrudan kontroller ve \(P=1000\) için bilinen \(3619\) kontrol değeri kullanılır.
Şunu tanımlayalım:
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
En küçük asal çarpan eleğini kurmak \(O(R\log\log R)\) zaman ve \(O(R)\) bellek ister. Sabit bir \(r\) için, bölenlerden bacak listesine dönüşümden sonra kalan aday sayısı \(m(r)\) olsun. \(r\)'yi çarpanlara ayırma ve bölen üretme işi esasen \(r^2\)'nin bölen sayısıyla orantılıdır; sıralama \(O(m(r)\log m(r))\), çift taraması ise her çift için bir ikili arama yapıldığı için \(O(m(r)^2\log m(r))\) maliyetindedir.
Toplam çalışma süresi böylece
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right)$$
olur; bellek kullanımı \(O(R+m_{\max})\) düzeyindedir. Uygulamada \(m(r)\) genellikle küçüktür; bu yüzden bu aritmetik yeniden yazım, bütün tam sayı kenar üçlülerini denemekten çok daha hızlıdır.
Consideramos triángulos \(ABC\) con lados enteros y perímetro \(p\le P\). Sea \(I\) el incentro y definamos
$$L=p+IA+IB+IC.$$
Hay que sumar \(L\) sobre todos los triángulos para los cuales las tres distancias desde el incentro hasta los vértices son enteras. Un barrido directo de todos los tríos de lados es demasiado costoso para el límite real, así que la solución reescribe el triángulo en coordenadas donde la estructura aritmética del incentro aparece de forma natural.
La observación central es que las condiciones sobre el incentro se simplifican mucho si cambiamos de longitudes de lado a coordenadas basadas en el semiperímetro.
Definimos
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Entonces \(x,y,z>0\), y los lados originales se recuperan mediante
$$a=y+z,\qquad b=x+z,\qquad c=x+y.$$
Como \(s=x+y+z\), el perímetro vale
$$p=2s=2(x+y+z).$$
Usando la fórmula de Herón \(\Delta^2=s(s-a)(s-b)(s-c)\) junto con \(\Delta=rs\), obtenemos
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
Así, cada triángulo admisible queda descrito por enteros positivos \(x,y,z,r\) que satisfacen esa identidad.
El punto de tangencia sobre el lado \(BC\) forma con \(A\) un triángulo rectángulo de catetos \(r\) y \(x\), por lo que
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
Por tanto, cada uno de \(x,y,z\) debe formar una relación pitagórica con el mismo inradio \(r\). Para un \(r\) fijo escribimos
$$t^2-x^2=r^2,$$
o de manera equivalente
$$\left(t-x\right)\left(t+x\right)=r^2.$$
Si ponemos \(d=t-x\) y \(e=t+x\), entonces \(de=r^2\), \(d\le e\), y \(d\) y \(e\) deben tener la misma paridad. De ahí sale
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
Recorrer los divisores \(d\mid r^2\) genera todos los pares enteros \((x,t)\) con \(x^2+r^2=t^2\). La misma lista sirve también para \(y\) y para \(z\).
Una vez elegidos \(x\) e \(y\) de esa lista, la fórmula del inradio determina \(z\). Partiendo de
$$r^2=\frac{xyz}{x+y+z},$$
despejamos \(z\):
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
Aquí aparecen exactamente los filtros del algoritmo: el denominador debe ser positivo, así que
$$xy>r^2,$$
y el numerador debe ser divisible por ese denominador para que \(z\) sea entero. Además, \(z\) también debe estar en la lista pitagórica generada antes; si no, \(IC\) no sería entero.
Las variables \(x,y,z\) son simétricas, así que podemos imponer
$$x\le y\le z$$
para contar cada triángulo una sola vez. La restricción sobre el perímetro se convierte en
$$2(x+y+z)\le P,$$
o, de forma equivalente, en
$$z\le \frac{P}{2}-x-y.$$
Para cada terna válida, la contribución es
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
También existe una cota global para \(r\). Entre todos los triángulos con perímetro fijo, el equilátero maximiza el inradio, de modo que
$$r\le \frac{P\sqrt{3}}{18}.$$
Eso reduce la búsqueda a un bucle finito sobre
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Tomemos \(r=21\), de modo que \(r^2=441\). Los pares de factores de \(441\) con la misma paridad producen varias opciones pitagóricas. Dos útiles son
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
y
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
Ahora elegimos \(x=y=28\). Entonces
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
Como \(72\) ya aparece en la misma lista pitagórica, las tres distancias a los vértices son enteras:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
Los lados correspondientes son
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
así que el perímetro es \(256\) y la contribución vale
$$L=256+35+35+75=401.$$
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero calculan la cota superior \(\left\lfloor P\sqrt{3}/18\right\rfloor\) para el inradio y construyen una criba de menor factor primo hasta ese valor. Esa criba permite factorizar cada \(r\) candidato de manera eficiente.
Para un inradio fijo, la implementación duplica los exponentes de la factorización de \(r\) para enumerar todos los divisores de \(r^2\). Cada par de divisores produce un candidato \((x,t)\) con \(x^2+r^2=t^2\), y esos candidatos se almacenan ordenados por \(x\).
Luego recorre todos los pares ordenados \(x\le y\), calcula el valor forzado de \(z\) y descarta el par si fallan la divisibilidad, la positividad o la cota de perímetro. Una búsqueda binaria comprueba si ese \(z\) ya está en la lista de candidatos, lo cual equivale a verificar que \(z^2+r^2\) es un cuadrado. Cada terna superviviente añade el perímetro y las tres distancias enteras ya determinadas al total acumulado.
Las versiones más grandes pueden partir el intervalo del inradio en bloques y sumar cada bloque por separado. Además, antes de evaluar el límite completo se usan comprobaciones directas pequeñas y el valor de control conocido \(3619\) cuando \(P=1000\).
Sea
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Construir la criba de menor factor primo cuesta \(O(R\log\log R)\) tiempo y \(O(R)\) memoria. Para un \(r\) fijo, sea \(m(r)\) el número de candidatos que sobreviven a la conversión de divisores en catetos. Factorizar \(r\) y generar divisores es esencialmente proporcional al número de divisores de \(r^2\), ordenar cuesta \(O(m(r)\log m(r))\), y la búsqueda por pares cuesta \(O(m(r)^2\log m(r))\) porque cada par realiza una búsqueda binaria para \(z\).
Por tanto, el tiempo total es
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
con memoria \(O(R+m_{\max})\). En la práctica \(m(r)\) es pequeño, así que esta reformulación aritmética es muchísimo más rápida que recorrer todos los tríos enteros de lados.
我们考虑边长均为整数且周长 \(p\le P\) 的三角形 \(ABC\)。设 \(I\) 为内心，并定义
$$L=p+IA+IB+IC.$$
目标是在所有满足“内心到三个顶点的距离都是整数”的三角形上，把 \(L\) 全部累加起来。若直接枚举所有边长三元组，真实范围下的代价会非常大，因此解法先把三角形改写成更适合数论处理的参数形式，让内心条件直接转化为整除与平方关系。
关键观察是：把边长改写成与半周长有关的三个偏移量后，内切圆半径、顶点距离和周长都会出现非常整齐的公式。
设
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
因为三角形非退化，所以 \(x,y,z>0\)。反过来，原来的三条边可以写成
$$a=y+z,\qquad b=x+z,\qquad c=x+y.$$
又由于 \(s=x+y+z\)，周长就是
$$p=2s=2(x+y+z).$$
把海伦公式 \(\Delta^2=s(s-a)(s-b)(s-c)\) 与面积公式 \(\Delta=rs\) 结合起来，就得到
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
也就是说，任何符合条件的三角形都对应一组正整数 \(x,y,z,r\)，并满足上面的恒等式。
内切圆与边 \(BC\) 的切点会和顶点 \(A\) 构成一个直角三角形，其两条直角边分别是 \(r\) 与 \(x\)，因此
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
所以 \(x,y,z\) 每一个都必须和同一个 \(r\) 组成勾股三元关系。固定一个 \(r\) 后，考虑方程
$$t^2-x^2=r^2,$$
等价地写成
$$\left(t-x\right)\left(t+x\right)=r^2.$$
令 \(d=t-x\)、\(e=t+x\)，则 \(de=r^2\)，并且 \(d\le e\)，同时 \(d\) 与 \(e\) 必须同奇偶。于是有
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
这说明：只要枚举 \(r^2\) 的所有约数 \(d\)，就能生成全部满足 \(x^2+r^2=t^2\) 的整数对 \((x,t)\)。同一份候选列表既可以用于 \(x\)，也可以用于 \(y\) 和 \(z\)。
一旦从上述列表中选定了 \(x\) 和 \(y\)，内切圆半径公式就会强制决定 \(z\)。从
$$r^2=\frac{xyz}{x+y+z}$$
出发，对 \(z\) 求解可得
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
这正是实现中所有筛选条件的来源。首先分母必须为正，因此需要
$$xy>r^2.$$
其次，为了让 \(z\) 是整数，分子必须被这个分母整除。最后，得到的 \(z\) 还必须出现在之前的勾股候选列表中；否则 \(z^2+r^2\) 不是完全平方数，\(IC\) 就不会是整数。
由于 \(x,y,z\) 在公式中是对称的，我们可以规定
$$x\le y\le z$$
从而保证每个三角形只被计算一次。周长限制
$$2(x+y+z)\le P$$
等价于
$$z\le \frac{P}{2}-x-y.$$
对于每个有效三元组，其贡献就是
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
此外，\(r\) 本身也有一个全局上界。固定周长时，内切圆半径最大的三角形是正三角形，因此
$$r\le \frac{P\sqrt{3}}{18}.$$
于是搜索范围被压缩为有限区间
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
取 \(r=21\)，于是 \(r^2=441\)。把 \(441\) 分解成同奇偶的因子对，可以得到若干勾股候选。两个最有用的是
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
以及
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
现在选择 \(x=y=28\)。代入公式得到
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
由于 \(72\) 本来就在同一个勾股候选列表里，所以三个顶点距离全部是整数：
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
对应的边长为
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
因此周长为 \(256\)，这一组三角形的贡献为
$$L=256+35+35+75=401.$$
C++、Python 和 Java 三个实现遵循同一条主线。首先计算内切圆半径的上界 \(\left\lfloor P\sqrt{3}/18\right\rfloor\)，然后在这个范围内建立最小质因子筛。这样每个候选 \(r\) 都能被快速分解。
对于固定的 \(r\)，实现会先把 \(r\) 的质因数分解中各个指数翻倍，从而枚举出 \(r^2\) 的全部约数。每一对约数都会产生一个满足 \(x^2+r^2=t^2\) 的候选 \((x,t)\)，并按 \(x\) 排序保存。
接着程序遍历所有有序对 \(x\le y\)，计算被公式强制决定的 \(z\)，如果不满足整除条件、正性条件或周长限制，就立刻丢弃。然后利用二分查找检查这个 \(z\) 是否已经在候选列表中；这等价于验证 \(z^2+r^2\) 是否为完全平方数。所有保留下来的三元组都会把周长和三个已经确定的整数顶点距离加入总和。
较大的实现还可以把内切圆半径区间切成多个块并分别求和。为了避免隐藏错误，程序在正式计算前还会使用小范围直接枚举，以及 \(P=1000\) 时已知的检查值 \(3619\) 进行校验。
记
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
建立最小质因子筛需要 \(O(R\log\log R)\) 时间和 \(O(R)\) 空间。对于固定的 \(r\)，设从约数转换成勾股候选后保留下来的数量为 \(m(r)\)。分解 \(r\) 并生成约数的成本基本与 \(r^2\) 的约数个数成正比；排序成本是 \(O(m(r)\log m(r))\)；而两两配对搜索的成本是 \(O(m(r)^2\log m(r))\)，因为每一对都需要一次关于 \(z\) 的二分查找。
因此总时间复杂度可以写成
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
空间复杂度为 \(O(R+m_{\max})\)。在实际数据中，\(m(r)\) 通常很小，所以这种数论化重写远快于直接枚举所有整数边长三元组。
Рассматриваются треугольники \(ABC\) с целыми сторонами и периметром \(p\le P\). Пусть \(I\) обозначает центр вписанной окружности, а
$$L=p+IA+IB+IC.$$
Нужно просуммировать \(L\) по всем тем треугольникам, у которых расстояния от центра вписанной окружности до всех трёх вершин являются целыми числами. Полный перебор всех троек сторон слишком дорог для реального ограничения, поэтому решение переводит задачу в координаты, где арифметика центра вписанной окружности становится прозрачной.
Главное наблюдение состоит в том, что условия на центр вписанной окружности резко упрощаются, если перейти от длин сторон к смещениям относительно полупериметра.
Положим
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
Тогда \(x,y,z>0\), а исходные стороны восстанавливаются по формулам
$$a=y+z,\qquad b=x+z,\qquad c=x+y.$$
Поскольку \(s=x+y+z\), периметр равен
$$p=2s=2(x+y+z).$$
Используя формулу Герона \(\Delta^2=s(s-a)(s-b)(s-c)\) вместе с \(\Delta=rs\), получаем
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
Следовательно, каждый допустимый треугольник задаётся положительными целыми \(x,y,z,r\), удовлетворяющими этому тождеству.
Точка касания вписанной окружности со стороной \(BC\) образует вместе с вершиной \(A\) прямоугольный треугольник с катетами \(r\) и \(x\), поэтому
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
Значит, каждое из чисел \(x,y,z\) должно входить в пифагорово соотношение с одним и тем же \(r\). Для фиксированного \(r\) рассмотрим
$$t^2-x^2=r^2,$$
то есть
$$\left(t-x\right)\left(t+x\right)=r^2.$$
Если обозначить \(d=t-x\) и \(e=t+x\), то \(de=r^2\), \(d\le e\), а \(d\) и \(e\) должны иметь одинаковую чётность. Отсюда
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
Итак, перебор делителей \(d\mid r^2\) порождает все целые пары \((x,t)\), для которых \(x^2+r^2=t^2\). Один и тот же список затем используется и для \(y\), и для \(z\).
После выбора \(x\) и \(y\) из этого списка формула для радиуса вписанной окружности однозначно определяет \(z\). Из равенства
$$r^2=\frac{xyz}{x+y+z}$$
получаем
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
Именно отсюда появляются проверки в алгоритме. Во-первых, знаменатель должен быть положительным, то есть
$$xy>r^2.$$
Во-вторых, числитель должен делиться на знаменатель, чтобы \(z\) было целым. Наконец, само \(z\) обязано встречаться в заранее построенном пифагоровом списке; иначе \(IC\) не будет целым.
Переменные \(x,y,z\) симметричны, поэтому можно потребовать
$$x\le y\le z,$$
чтобы каждый треугольник учитывался ровно один раз. Ограничение на периметр записывается как
$$2(x+y+z)\le P,$$
или эквивалентно как
$$z\le \frac{P}{2}-x-y.$$
Для каждой допустимой тройки вклад равен
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
Кроме того, для \(r\) существует глобальная верхняя граница. Среди треугольников фиксированного периметра максимальный радиус вписанной окружности имеет равносторонний треугольник, поэтому
$$r\le \frac{P\sqrt{3}}{18}.$$
Следовательно, поиск сводится к конечному циклу по
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Возьмём \(r=21\), тогда \(r^2=441\). Парные множители числа \(441\) с одинаковой чётностью дают несколько пифагоровых вариантов. Два полезных варианта таковы:
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
и
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
Теперь выберем \(x=y=28\). Тогда
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
Так как \(72\) уже присутствует в том же пифагоровом списке, все три расстояния до вершин являются целыми:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
Соответствующие стороны равны
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
поэтому периметр равен \(256\), а вклад составляет
$$L=256+35+35+75=401.$$
Реализации на C++, Python и Java используют одну и ту же схему. Сначала вычисляется верхняя граница \(\left\lfloor P\sqrt{3}/18\right\rfloor\) для радиуса вписанной окружности, а затем строится решето минимальных простых делителей до этого значения. Это позволяет быстро раскладывать каждое кандидатное \(r\) на простые множители.
Для фиксированного радиуса реализация удваивает показатели в разложении числа \(r\), чтобы перечислить все делители числа \(r^2\). Каждая пара делителей порождает кандидат \((x,t)\) с условием \(x^2+r^2=t^2\), после чего кандидаты сохраняются в отсортированном по \(x\) виде.
Далее код перебирает упорядоченные пары \(x\le y\), вычисляет вынужденное значение \(z\) и отбрасывает пару, если нарушаются делимость, положительность или ограничение на периметр. Двоичный поиск проверяет, встречается ли такое \(z\) среди кандидатов; это эквивалентно условию, что \(z^2+r^2\) является квадратом. Каждая прошедшая тройка добавляет к сумме периметр и три уже найденных целочисленных расстояния до вершин.
Более крупные реализации могут разбивать диапазон радиусов на независимые блоки и суммировать их отдельно. Перед полным запуском используются также небольшие прямые проверки и известное контрольное значение \(3619\) для случая \(P=1000\).
Обозначим
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
Построение решета минимальных простых делителей требует \(O(R\log\log R)\) времени и \(O(R)\) памяти. Для фиксированного \(r\) обозначим через \(m(r)\) число кандидатов, оставшихся после преобразования делителей в катеты. Разложение \(r\) и генерация делителей по сути пропорциональны числу делителей \(r^2\), сортировка стоит \(O(m(r)\log m(r))\), а поиск по парам стоит \(O(m(r)^2\log m(r))\), потому что для каждой пары выполняется один двоичный поиск по \(z\).
Итоговая асимптотика имеет вид
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
при памяти \(O(R+m_{\max})\). На практике \(m(r)\) обычно мало, поэтому такая арифметическая переформулировка намного быстрее полного перебора всех целочисленных троек сторон.
ننظر إلى مثلثات \(ABC\) ذات أضلاع صحيحة ومحيط \(p\le P\). وليكن \(I\) هو مركز الدائرة الداخلية، ونعرّف
$$L=p+IA+IB+IC.$$
المطلوب هو جمع \(L\) على جميع المثلثات التي تكون فيها المسافات الثلاث من المركز الداخلي إلى الرؤوس أعدادًا صحيحة. الفحص المباشر لكل ثلاثيات الأضلاع يصبح مكلفًا جدًا عند الحد الحقيقي للمسألة، لذلك تعيد الفكرة صياغة المثلث بإحداثيات تكشف البنية الحسابية المرتبطة بالمركز الداخلي مباشرة.
الفكرة الأساسية هي أن شروط المركز الداخلي تصبح أبسط كثيرًا إذا استبدلنا أطوال الأضلاع بإزاحات مقاسة من نصف المحيط.
لنضع
$$s=\frac{a+b+c}{2},\qquad x=s-a,\qquad y=s-b,\qquad z=s-c.$$
عندئذ يكون \(x,y,z>0\)، ويمكن استرجاع الأضلاع الأصلية من
$$a=y+z,\qquad b=x+z,\qquad c=x+y.$$
وبما أن \(s=x+y+z\)، فإن المحيط يساوي
$$p=2s=2(x+y+z).$$
وباستخدام صيغة هيرون \(\Delta^2=s(s-a)(s-b)(s-c)\) مع العلاقة \(\Delta=rs\) نحصل على
$$r^2=\frac{\Delta^2}{s^2}=\frac{xyz}{x+y+z}.$$
إذن كل مثلث مقبول يقابله أربع قيم صحيحة موجبة \(x,y,z,r\) تحقق هذه الهوية.
نقطة التماس على الضلع \(BC\) تكوّن مع الرأس \(A\) مثلثًا قائمًا ضلعا قائمته هما \(r\) و\(x\)، ولذلك
$$IA^2=r^2+x^2,\qquad IB^2=r^2+y^2,\qquad IC^2=r^2+z^2.$$
وهذا يعني أن كل واحد من \(x,y,z\) يجب أن يدخل في علاقة فيثاغورية مع نفس نصف القطر الداخلي \(r\). ولـ \(r\) ثابت نكتب
$$t^2-x^2=r^2,$$
أي
$$\left(t-x\right)\left(t+x\right)=r^2.$$
إذا أخذنا \(d=t-x\) و\(e=t+x\)، فإن \(de=r^2\) مع \(d\le e\)، ويجب أن يكون \(d\) و\(e\) من نفس الفردية. ومن ثم
$$x=\frac{e-d}{2},\qquad t=\frac{e+d}{2},\qquad e=\frac{r^2}{d}.$$
إذن تعداد القواسم \(d\mid r^2\) يولّد كل الأزواج الصحيحة \((x,t)\) التي تحقق \(x^2+r^2=t^2\). والقائمة نفسها تُستخدم أيضًا من أجل \(y\) و\(z\).
بعد اختيار \(x\) و\(y\) من تلك القائمة، تصبح قيمة \(z\) مفروضة من معادلة نصف القطر الداخلي. انطلاقًا من
$$r^2=\frac{xyz}{x+y+z}$$
نحل بالنسبة إلى \(z\) فنحصل على
$$z=\frac{r^2(x+y)}{xy-r^2}.$$
وهنا تظهر شروط الترشيح في الخوارزمية بصورة طبيعية. أولًا يجب أن يكون المقام موجبًا، أي
$$xy>r^2.$$
وثانيًا يجب أن يقسم هذا المقام البسط حتى تكون \(z\) عددًا صحيحًا. وأخيرًا يجب أن تظهر \(z\) نفسها داخل القائمة الفيثاغورية المولّدة سابقًا؛ وإلا فلن تكون \(IC\) عددًا صحيحًا.
بما أن \(x,y,z\) متناظرة في الصياغة، يمكن فرض الشرط
$$x\le y\le z$$
لكي يُحسب كل مثلث مرة واحدة فقط. ويصبح قيد المحيط
$$2(x+y+z)\le P,$$
أو بصورة مكافئة
$$z\le \frac{P}{2}-x-y.$$
ولكل ثلاثية صالحة تكون المساهمة
$$L=2(x+y+z)+\sqrt{x^2+r^2}+\sqrt{y^2+r^2}+\sqrt{z^2+r^2}.$$
هناك أيضًا حد علوي عام على \(r\). فبين جميع المثلثات ذات المحيط الثابت، يحقق المثلث المتساوي الأضلاع أكبر نصف قطر للدائرة الداخلية، ولذلك
$$r\le \frac{P\sqrt{3}}{18}.$$
وبهذا تتحول عملية البحث إلى حلقة منتهية على المجال
$$1\le r\le \left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
لنأخذ \(r=21\)، ومن ثم \(r^2=441\). أزواج عوامل \(441\) ذات الفردية نفسها تعطي عدة خيارات فيثاغورية. خياران مفيدان هما
$$d=7,\ e=63\quad\Rightarrow\quad x=\frac{63-7}{2}=28,\qquad \frac{63+7}{2}=35,$$
و
$$d=3,\ e=147\quad\Rightarrow\quad z=\frac{147-3}{2}=72,\qquad \frac{147+3}{2}=75.$$
والآن نختار \(x=y=28\). عندئذ
$$z=\frac{441(28+28)}{28\cdot 28-441}=\frac{441\cdot 56}{343}=72.$$
وبما أن \(72\) موجودة أصلًا في القائمة الفيثاغورية نفسها، فإن المسافات الثلاث إلى الرؤوس تكون كلها صحيحة:
$$\sqrt{21^2+28^2}=35,\qquad \sqrt{21^2+72^2}=75.$$
أما الأضلاع المقابلة فهي
$$a=y+z=100,\qquad b=x+z=100,\qquad c=x+y=56,$$
ولذلك يكون المحيط \(256\)، والمساهمة هي
$$L=256+35+35+75=401.$$
تتبع تنفيذات C++ وPython وJava المخطط نفسه. أولًا تُحسب القيمة العليا \(\left\lfloor P\sqrt{3}/18\right\rfloor\) لنصف القطر الداخلي، ثم يُبنى غربال لأصغر عامل أولي حتى ذلك الحد. هذا يجعل تحليل كل قيمة مرشحة لـ \(r\) سريعًا.
بعد تثبيت \(r\)، تضاعف الشيفرة أسس التحليل الأولي لـ \(r\) من أجل تعداد جميع قواسم \(r^2\). كل زوج من القواسم يولّد مرشحًا \((x,t)\) يحقق \(x^2+r^2=t^2\)، ثم تُخزَّن هذه المرشحات مرتبة بحسب \(x\).
بعد ذلك تدور الشيفرة على جميع الأزواج المرتبة \(x\le y\)، وتحسب القيمة المفروضة لـ \(z\)، وترفض الزوج إذا أخفق شرط القسمة أو شرط الإيجابية أو شرط المحيط. ثم يُستخدم بحث ثنائي للتأكد من أن \(z\) موجودة أصلًا في قائمة المرشحات، وهو ما يكافئ التحقق من أن \(z^2+r^2\) مربع كامل. وكل ثلاثية تبقى بعد هذه الفلاتر تضيف المحيط والمسافات الصحيحة الثلاث المحسوبة مسبقًا إلى المجموع.
في النسخ الأكبر يمكن تقسيم مجال \(r\) إلى كتل مستقلة وجمع كل كتلة على حدة. وقبل تشغيل المجال الكامل تُستخدم أيضًا فحوص مباشرة صغيرة والقيمة المرجعية المعروفة \(3619\) عند \(P=1000\) للتأكد من سلامة التنفيذ.
لنرمز إلى
$$R=\left\lfloor\frac{P\sqrt{3}}{18}\right\rfloor.$$
بناء غربال أصغر عامل أولي يكلف \(O(R\log\log R)\) زمنًا و\(O(R)\) ذاكرة. ولـ \(r\) ثابت، لنفرض أن \(m(r)\) هو عدد القيم المرشحة الباقية بعد تحويل القواسم إلى قوائم فيثاغورية. تحليل \(r\) وتوليد القواسم يتناسبان أساسًا مع عدد قواسم \(r^2\)، أما الفرز فيكلف \(O(m(r)\log m(r))\)، والبحث الثنائي داخل فحص الأزواج يكلف \(O(m(r)^2\log m(r))\) لأن كل زوج يحتاج إلى عملية بحث واحدة تخص \(z\).
وعليه فإن الزمن الكلي يساوي
$$O\left(R\log\log R+\sum_{r=1}^{R} m(r)^2\log m(r)\right),$$
مع ذاكرة قدرها \(O(R+m_{\max})\). عمليًا تكون \(m(r)\) صغيرة غالبًا، ولذلك فهذه الصياغة الحسابية أسرع بكثير من المسح المباشر لكل ثلاثيات الأضلاع الصحيحة.