For each shift \(k\) with \(0\le k\le m\), let \(P_k(n)\) be the number of unordered primitive positive integer triples \((p,q,r)\) such that
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
The required quantity is
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
A brute-force scan over all triples up to the perimeter bound would be far too slow, so the implementation organizes the search through a finite set of roots and a tree of shift-preserving linear transformations.
Fix one value of \(k\), and define the quadratic form
$$Q(p,q,r)=r^2-p^2-q^2.$$
Then the triples relevant to this shift are exactly the primitive positive integer points on the level set \(Q(p,q,r)=k\).
The search is built from three linear maps:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
A direct expansion shows that each map preserves the quadratic form:
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
So if one triple satisfies \(p^2+q^2+k=r^2\), then all of its descendants under these maps satisfy the same equation with the same shift \(k\). The maps are also invertible over the integers, so primitiveness is preserved: any common divisor of a child would also divide its parent.
The inverse transformations are
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
A primitive triple is called a root if none of these inverse images has all coordinates positive. Equivalently, a root is a solution with no parent inside the same search forest.
The implementations first enumerate primitive candidates with
$$1\le p\le q\le \max(4m,10),$$
test whether \(p^2+q^2+k\) is a square, and then discard every candidate that has a positive inverse parent. The underlying solver states that for \(k>0\), every root satisfies \(p,q\le 4k\), so scanning up to \(\max(4m,10)\) covers every shift \(0\le k\le m\).
Once the roots for a fixed \(k\) are known, each root generates one component under repeated application of \(A\), \(B\), and \(C\). The implementations explore that component with an explicit depth-first stack.
The perimeter function
$$\pi(p,q,r)=p+q+r$$
provides the pruning rule: if \(\pi(p,q,r)>n\), that node contributes nothing and its branch is discarded. Therefore only triples that can affect \(P_k(n)\) are ever visited.
Because non-roots were removed in the previous step, every admissible triple belongs to exactly one rooted component, so starting DFS from all roots visits each relevant ordered triple exactly once.
The equation and the primitiveness condition are unchanged by the swap
$$\sigma(p,q,r)=(q,p,r).$$
The root search only seeds triples with \(p\le q\), so the component structure already avoids double-starting symmetric families. Inside a component, the implementation records two values:
$$T=\text{number of visited triples},\qquad D=\text{number of visited triples with }p=q.$$
If the component contains diagonal states \(p=q\), then \(\sigma\) keeps that component, fixes exactly the diagonal states, and pairs all off-diagonal states. The unordered contribution is therefore
$$U=\frac{T+D}{2}.$$
If no diagonal state appears, the selected rooted component already contributes the correct unordered count, so the implementation simply uses \(U=T\).
The triple \((1,1,3)\) is primitive and satisfies
$$1^2+1^2+7=9=3^2,$$
so it belongs to the shift \(k=7\). Applying the three transformations gives
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
All three children still satisfy
$$r^2-p^2-q^2=7.$$
With perimeter bound \(n=31\), exactly four states from this component are counted:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
Here \(T=4\), and the diagonal states are \((1,1,3)\) and \((9,9,13)\), so \(D=2\). Hence the unordered contribution is
$$U=\frac{4+2}{2}=3,$$
corresponding to the three unordered triples \((1,1,3)\), \((5,7,9)\), and \((9,9,13)\).
After computing the unordered count \(P_k(n)\) for each fixed \(k\), the final result is simply
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
So the full problem is reduced to a finite root search for every shift and a pruned tree traversal from each root.
The C++, Python, and Java implementations all follow the same counting strategy. For every \(k\), they enumerate candidate primitive triples in the bounded root window, keep only those whose inverse images are not positive, and store those survivors as roots. Then each root is explored with an explicit stack, repeatedly applying the three forward maps and pruning as soon as the perimeter exceeds \(n\).
For every rooted component, the implementation accumulates the total number of visited triples and, separately, the number with \(p=q\). That pair is converted into an unordered contribution using the formula from the previous section. Summing these component contributions yields \(P_k(n)\), and summing \(P_k(n)\) over \(k=0,\dots,m\) gives the final answer. The C++ and Java implementations additionally distribute independent root tasks across worker threads, while the Python implementation delegates to the same underlying search strategy rather than re-deriving different mathematics.
Let \(R_k\) be the number of roots for shift \(k\), and let \(T_k(n)\) be the total number of triples visited across all rooted components after perimeter pruning. The preliminary root scan uses the bounded box
$$1\le p\le q\le \max(4m,10),$$
so its cost depends only on \(m\), not on the large perimeter bound \(n\). The dominant work is the traversal itself, which gives total running time
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
Memory usage is linear in the stored roots plus the explicit DFS stack for the currently explored component. Parallel execution reduces wall-clock time, but it does not change the underlying combinatorial work measured by the same sum of visited states.
Für jede Verschiebung \(k\) mit \(0\le k\le m\) sei \(P_k(n)\) die Anzahl ungeordneter primitiver positiver ganzzahliger Tripel \((p,q,r)\) mit
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
Gesucht ist dann
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Ein roher Vollscan über alle Tripel bis zur Perimetergrenze wäre viel zu teuer. Deshalb organisiert die Implementierung die Suche über eine endliche Wurzelmenge und einen Baum aus linearen Transformationen, die die Verschiebung erhalten.
Fixiere ein \(k\) und definiere die quadratische Form
$$Q(p,q,r)=r^2-p^2-q^2.$$
Die für diese Verschiebung relevanten Tripel sind also genau die primitiven positiven ganzzahligen Punkte der Niveaumenge \(Q(p,q,r)=k\).
Die Suche basiert auf drei linearen Abbildungen:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
Direktes Ausmultiplizieren zeigt, dass jede dieser Abbildungen \(Q\) invariant lässt:
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
Wenn also ein Tripel \(p^2+q^2+k=r^2\) erfüllt, dann tun dies auch alle seine Nachkommen unter diesen Abbildungen mit demselben \(k\). Da die Abbildungen über den ganzen Zahlen invertierbar sind, bleibt auch die Primitivität erhalten: Ein gemeinsamer Teiler eines Kindknotens würde auf den Elternknoten zurückgezogen.
Die inversen Transformationen lauten
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
Ein primitives Tripel heißt Wurzel, wenn keines dieser inversen Bilder nur positive Koordinaten besitzt. Dann hat es innerhalb des Suchwaldes keinen Elternknoten.
Die Implementierungen enumerieren zunächst primitive Kandidaten mit
$$1\le p\le q\le \max(4m,10),$$
prüfen, ob \(p^2+q^2+k\) ein Quadrat ist, und verwerfen danach alle Kandidaten mit positivem inversen Elternknoten. Der zugrunde liegende Solver hält fest, dass für \(k>0\) jede Wurzel \(p,q\le 4k\) erfüllt; damit deckt \(\max(4m,10)\) alle Verschiebungen \(0\le k\le m\) ab.
Sobald die Wurzeln für ein festes \(k\) bekannt sind, erzeugt jede Wurzel unter wiederholter Anwendung von \(A\), \(B\) und \(C\) genau eine Komponente. Die Implementierungen durchlaufen diese Komponente mit einem expliziten Tiefensuch-Stack.
Die Perimeterfunktion
$$\pi(p,q,r)=p+q+r$$
liefert die Abbruchregel: Gilt \(\pi(p,q,r)>n\), dann trägt dieser Knoten nichts mehr bei und der ganze Teilbaum wird abgeschnitten. Dadurch werden nur Tripel besucht, die \(P_k(n)\) tatsächlich beeinflussen können.
Weil Nicht-Wurzeln im vorherigen Schritt entfernt wurden, gehört jedes zulässige Tripel zu genau einer Wurzelkomponente. Der Start der DFS an allen Wurzeln besucht daher jedes relevante geordnete Tripel genau einmal.
Die Gleichung und die Primitivität bleiben unter dem Tausch
$$\sigma(p,q,r)=(q,p,r)$$
unverändert. Die Wurzelsuche startet nur mit \(p\le q\), sodass symmetrische Familien nicht doppelt gestartet werden. Innerhalb einer Komponente speichert die Implementierung zwei Werte:
$$T=\text{Anzahl besuchter Tripel},\qquad D=\text{Anzahl besuchter Tripel mit }p=q.$$
Wenn die Komponente Diagonalzustände \(p=q\) enthält, dann wirkt \(\sigma\) innerhalb derselben Komponente, fixiert genau diese Diagonalzustände und paart alle übrigen Zustände. Der ungeordnete Beitrag lautet dann
$$U=\frac{T+D}{2}.$$
Tritt kein Diagonalzustand auf, dann liefert die gewählte Wurzelkomponente bereits den korrekten ungeordneten Beitrag, also verwendet die Implementierung schlicht \(U=T\).
Das Tripel \((1,1,3)\) ist primitiv und erfüllt
$$1^2+1^2+7=9=3^2,$$
gehört also zur Verschiebung \(k=7\). Die drei Transformationen liefern
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
Alle drei Kinder erfüllen weiterhin
$$r^2-p^2-q^2=7.$$
Bei der Perimetergrenze \(n=31\) werden aus dieser Komponente genau vier Zustände gezählt:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
Hier ist \(T=4\), und die Diagonalzustände sind \((1,1,3)\) sowie \((9,9,13)\), also \(D=2\). Damit erhält man den ungeordneten Beitrag
$$U=\frac{4+2}{2}=3,$$
entsprechend den drei ungeordneten Tripeln \((1,1,3)\), \((5,7,9)\) und \((9,9,13)\).
Nachdem für jedes feste \(k\) der ungeordnete Wert \(P_k(n)\) berechnet wurde, ist das Endergebnis einfach
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Das Gesamtproblem reduziert sich also auf eine endliche Wurzelsuche für jede Verschiebung und eine beschnittene Baumdurchquerung von jeder Wurzel aus.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Zählidee. Für jedes \(k\) werden primitive Kandidaten im beschränkten Wurzelfenster erzeugt, danach bleiben nur diejenigen übrig, deren inverse Bilder nicht vollständig positiv sind. Diese überlebenden Kandidaten bilden die Wurzeln. Von jeder Wurzel aus wird dann mit einem expliziten Stack traversiert; nach jedem Schritt werden die drei Vorwärtsabbildungen angewandt, und sobald der Perimeter größer als \(n\) wird, wird der entsprechende Ast abgeschnitten.
Für jede Wurzelkomponente sammelt die Implementierung die Gesamtzahl der besuchten Tripel und separat die Zahl der Fälle mit \(p=q\). Aus diesem Paar wird per Formel aus dem vorigen Abschnitt der ungeordnete Beitrag berechnet. Die Summe dieser Beiträge ergibt \(P_k(n)\), und die Summation über \(k=0,\dots,m\) liefert den gesuchten Gesamtwert. Die C++- und Java-Implementierungen verteilen unabhängige Wurzelaufgaben zusätzlich auf mehrere Threads, während die Python-Implementierung dieselbe zugrunde liegende Suchstrategie nutzt, statt eine andere Mathematik nachzubauen.
Sei \(R_k\) die Zahl der Wurzeln zur Verschiebung \(k\), und sei \(T_k(n)\) die Gesamtzahl der nach dem Perimeter-Pruning besuchten Tripel über alle Wurzelkomponenten hinweg. Der vorbereitende Wurzelscan benutzt die beschränkte Box
$$1\le p\le q\le \max(4m,10),$$
sodass seine Kosten nur von \(m\), nicht aber von der großen Perimetergrenze \(n\), abhängen. Die dominierende Arbeit ist die eigentliche Traversierung, also insgesamt
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
Der Speicherverbrauch ist linear in den gespeicherten Wurzeln und im expliziten DFS-Stack für die aktuell bearbeitete Komponente. Parallele Ausführung verkürzt die Laufzeit an der Wanduhr, ändert aber nichts an der zugrunde liegenden kombinatorischen Arbeitsmenge.
Her \(0\le k\le m\) kaydırması için,
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1$$
koşullarını sağlayan sırasız ilkel pozitif tamsayı üçlülerinin sayısına \(P_k(n)\) diyelim. Aranan büyüklük
$$S(m,n)=\sum_{k=0}^{m} P_k(n)$$
olur. Çevre sınırına kadar tüm üçlüleri kaba kuvvetle taramak çok pahalı olduğundan, uygulama aramayı sonlu bir kök kümesi ve kaydırmayı koruyan lineer dönüşümler ağacı üzerinden yapar.
Sabit bir \(k\) seçelim ve
$$Q(p,q,r)=r^2-p^2-q^2$$
kuadratik formunu tanımlayalım. Bu durumda ilgili üçlüler, \(Q(p,q,r)=k\) düzey kümesindeki ilkel pozitif tamsayı noktalarıdır.
Arama şu üç lineer dönüşüme dayanır:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
Doğrudan açılım yapıldığında her birinin \(Q\)'yu koruduğu görülür:
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
Dolayısıyla bir üçlü \(p^2+q^2+k=r^2\) denklemini sağlıyorsa, bu dönüşümler altındaki bütün torunları da aynı \(k\) için aynı denklemi sağlar. Dönüşümler tamsayılarda terslenebilir olduğu için primitiftik de korunur; bir çocuk düğümün ortak böleni olsaydı, aynı bölen ebeveyni de bölerdi.
Ters dönüşümler şunlardır:
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
İlkel bir üçlü, bu ters görüntülerden hiçbirinin tüm koordinatları pozitif değilse kök kabul edilir. Başka bir deyişle, aynı arama ormanında ebeveyni olmayan çözümdür.
Uygulamalar önce
$$1\le p\le q\le \max(4m,10)$$
kutusunda ilkel adayları tarar, \(p^2+q^2+k\) değerinin kare olup olmadığını kontrol eder ve ardından pozitif ters ebeveyni olanları çıkarır. Çözücüde yer alan nota göre \(k>0\) için her kök \(p,q\le 4k\) sınırını sağlar; bu yüzden \(\max(4m,10)\) aralığı \(0\le k\le m\) için gereken bütün kökleri kapsar.
Sabit bir \(k\) için kökler belirlendikten sonra, her kök \(A\), \(B\) ve \(C\)'nin tekrar tekrar uygulanmasıyla tek bir bileşen üretir. Uygulamalar bu bileşeni açık bir derinlik-öncelikli yığın ile gezer.
Budama kuralını çevre fonksiyonu verir:
$$\pi(p,q,r)=p+q+r.$$
Eğer \(\pi(p,q,r)>n\) ise bu düğüm katkı vermez ve o dal tamamen kesilir. Böylece yalnızca \(P_k(n)\) değerini etkileyebilecek üçlüler ziyaret edilir.
Bir önceki adımda kök olmayanlar elendiği için, her uygun üçlü tam olarak bir kök bileşene aittir. Bu nedenle tüm köklerden başlatılan DFS, ilgili sıralı üçlülerin her birini tam bir kez ziyaret eder.
Denklem ve ilkel olma koşulu,
$$\sigma(p,q,r)=(q,p,r)$$
değiş tokuşu altında değişmez. Kök araması yalnızca \(p\le q\) olan tohumları kullandığı için simetrik aileler iki kez başlatılmaz. Bir bileşen içinde uygulama şu iki değeri tutar:
$$T=\text{ziyaret edilen üçlü sayısı},\qquad D=\text{ziyaret edilen ve }p=q\text{ olan üçlü sayısı}.$$
Eğer bileşen \(p=q\) diagonal durumlarını içeriyorsa, \(\sigma\) aynı bileşen içinde kalır, tam olarak diagonal düğümleri sabit bırakır ve diagonal dışındakileri ikili eşler. Bu durumda sırasız katkı
$$U=\frac{T+D}{2}$$
olur. Hiç diagonal durum yoksa, seçilmiş kök bileşeni zaten doğru sırasız katkıyı verdiğinden uygulama doğrudan \(U=T\) kullanır.
\((1,1,3)\) üçlüsü ilkeldir ve
$$1^2+1^2+7=9=3^2$$
eşitliğini sağladığı için \(k=7\) kaydırmasına aittir. Üç dönüşüm uygulanınca
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9)$$
elde edilir. Bu çocukların hepsi hâlâ
$$r^2-p^2-q^2=7$$
ilişkisini sağlar. Çevre sınırı \(n=31\) olduğunda bu bileşenden tam olarak dört durum sayılır:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
Burada \(T=4\) ve diagonal düğümler \((1,1,3)\) ile \((9,9,13)\) olduğundan \(D=2\) bulunur. Dolayısıyla sırasız katkı
$$U=\frac{4+2}{2}=3$$
olur; bu da \((1,1,3)\), \((5,7,9)\) ve \((9,9,13)\) sırasız üçlülerine karşılık gelir.
Her sabit \(k\) için sırasız sayı \(P_k(n)\) bulunduktan sonra nihai sonuç
$$S(m,n)=\sum_{k=0}^{m} P_k(n)$$
olur. Böylece tüm problem, her kaydırma için sonlu bir kök aramasına ve her kökten başlatılan budanmış ağaç dolaşımına indirgenir.
C++, Python ve Java uygulamaları aynı sayım planını izler. Her \(k\) için önce sınırlı kök penceresinde ilkel adaylar üretilir, sonra ters görüntüleri tamamen pozitif olmayanlar bırakılarak kök listesi oluşturulur. Her kök, açık bir yığınla gezilir; her adımda üç ileri dönüşüm uygulanır ve çevre \(n\)'yi aşar aşmaz ilgili dal budanır.
Her kök bileşeni için uygulama, ziyaret edilen toplam üçlü sayısını ve bunlardan kaç tanesinin \(p=q\) olduğunu ayrı ayrı toplar. Bu ikili, önceki bölümdeki formülle sırasız katkıya çevrilir. Bütün bileşen katkıları toplanınca \(P_k(n)\), bütün \(k=0,\dots,m\) değerleri toplanınca da nihai sonuç elde edilir. C++ ve Java uygulamaları ayrıca bağımsız kök görevlerini iş parçacıklarına dağıtır; Python uygulaması ise aynı temel arama stratejisini kullanır, farklı bir sayı kuramı yaklaşımı kurmaz.
\(R_k\), \(k\) kaydırmasının kök sayısı; \(T_k(n)\) ise çevre budamasından sonra tüm kök bileşenlerinde ziyaret edilen üçlülerin toplamı olsun. Hazırlık aşamasındaki kök taraması
$$1\le p\le q\le \max(4m,10)$$
kutusunu kullandığı için maliyeti büyük çevre sınırı \(n\)'den değil yalnızca \(m\)'den etkilenir. Baskın maliyet DFS dolaşımıdır ve toplam süre
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right)$$
olur. Bellek kullanımı, saklanan kökler ile o anda işlenen bileşenin açık DFS yığını kadar lineerdir. Paralel çalışma duvar saati süresini düşürür; ancak temel birleşimsel iş yükü yine aynı ziyaret edilen durumlar toplamıyla ölçülür.
Para cada desplazamiento \(k\) con \(0\le k\le m\), sea \(P_k(n)\) el número de triples primitivos positivos no ordenados \((p,q,r)\) que satisfacen
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
La cantidad pedida es
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Un barrido bruto sobre todos los triples hasta la cota de perímetro sería demasiado costoso, así que la implementación organiza la búsqueda mediante un conjunto finito de raíces y un árbol de transformaciones lineales que preservan el desplazamiento.
Fijemos un valor de \(k\) y definamos la forma cuadrática
$$Q(p,q,r)=r^2-p^2-q^2.$$
Entonces los triples relevantes para ese desplazamiento son exactamente los puntos enteros positivos primitivos del nivel \(Q(p,q,r)=k\).
La búsqueda se apoya en tres aplicaciones lineales:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
Al expandir directamente se comprueba que cada una conserva \(Q\):
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
Por tanto, si un triple satisface \(p^2+q^2+k=r^2\), todos sus descendientes bajo estas transformaciones satisfacen la misma ecuación con el mismo \(k\). Además, las transformaciones son invertibles sobre los enteros, así que la primitividad también se conserva: un divisor común de un hijo también dividiría al padre.
Las transformaciones inversas son
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
Un triple primitivo se llama raíz cuando ninguna de estas imágenes inversas tiene todas sus coordenadas positivas. Dicho de otro modo, es una solución que no tiene padre dentro del mismo bosque de búsqueda.
Las implementaciones enumeran primero candidatos primitivos con
$$1\le p\le q\le \max(4m,10),$$
comprueban si \(p^2+q^2+k\) es un cuadrado y luego eliminan todos los candidatos que poseen un padre inverso positivo. El solucionador de referencia indica que, para \(k>0\), toda raíz satisface \(p,q\le 4k\); por eso escanear hasta \(\max(4m,10)\) cubre todos los desplazamientos \(0\le k\le m\).
Una vez conocidas las raíces para un \(k\) fijo, cada raíz genera una componente al aplicar repetidamente \(A\), \(B\) y \(C\). Las implementaciones recorren esa componente con una pila explícita de búsqueda en profundidad.
La función perímetro
$$\pi(p,q,r)=p+q+r$$
da la regla de poda: si \(\pi(p,q,r)>n\), ese nodo ya no aporta nada y toda esa rama se descarta. De este modo solo se visitan triples que todavía pueden contribuir a \(P_k(n)\).
Como los no-raíces se eliminan en el paso anterior, cada triple admisible pertenece a una única componente enraizada. Por ello, iniciar el DFS desde todas las raíces visita cada triple ordenado relevante exactamente una vez.
La ecuación y la condición de primitividad no cambian bajo el intercambio
$$\sigma(p,q,r)=(q,p,r).$$
La búsqueda de raíces solo arranca con \(p\le q\), así que las familias simétricas no se inician dos veces. Dentro de una componente, la implementación guarda dos cantidades:
$$T=\text{número de triples visitados},\qquad D=\text{número de triples visitados con }p=q.$$
Si la componente contiene estados diagonales \(p=q\), entonces \(\sigma\) permanece dentro de esa misma componente, fija exactamente esos estados diagonales y empareja todos los estados fuera de la diagonal. La contribución no ordenada es entonces
$$U=\frac{T+D}{2}.$$
Si no aparece ningún estado diagonal, la componente enraizada elegida ya aporta la cuenta no ordenada correcta, de modo que la implementación usa simplemente \(U=T\).
El triple \((1,1,3)\) es primitivo y cumple
$$1^2+1^2+7=9=3^2,$$
así que pertenece al desplazamiento \(k=7\). Al aplicar las tres transformaciones se obtiene
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
Los tres hijos siguen satisfaciendo
$$r^2-p^2-q^2=7.$$
Con cota de perímetro \(n=31\), de esta componente se cuentan exactamente cuatro estados:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
Aquí \(T=4\), y los estados diagonales son \((1,1,3)\) y \((9,9,13)\), así que \(D=2\). Por tanto, la contribución no ordenada vale
$$U=\frac{4+2}{2}=3,$$
que corresponde a los tres triples no ordenados \((1,1,3)\), \((5,7,9)\) y \((9,9,13)\).
Después de calcular la cantidad no ordenada \(P_k(n)\) para cada \(k\) fijo, el resultado final es simplemente
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Así, todo el problema se reduce a una búsqueda finita de raíces para cada desplazamiento y a un recorrido podado del árbol a partir de cada raíz.
Las implementaciones en C++, Python y Java siguen la misma estrategia de conteo. Para cada \(k\), generan candidatos primitivos en la ventana acotada de raíces, conservan solo aquellos cuyas imágenes inversas no son completamente positivas y almacenan esos supervivientes como raíces. Después exploran cada raíz con una pila explícita, aplicando repetidamente las tres transformaciones directas y podando en cuanto el perímetro supera \(n\).
En cada componente enraizada, la implementación acumula el número total de triples visitados y, por separado, cuántos de ellos cumplen \(p=q\). Ese par se transforma en una contribución no ordenada mediante la fórmula de la sección anterior. La suma de las contribuciones de las componentes produce \(P_k(n)\), y al sumar \(P_k(n)\) sobre \(k=0,\dots,m\) se obtiene la respuesta final. Las implementaciones en C++ y Java además reparten raíces independientes entre trabajadores paralelos, mientras que la implementación en Python delega en la misma estrategia de búsqueda subyacente en lugar de reinventar otra matemática.
Sea \(R_k\) el número de raíces para el desplazamiento \(k\), y sea \(T_k(n)\) el número total de triples visitados en todas sus componentes una vez aplicada la poda por perímetro. El barrido previo de raíces usa la caja acotada
$$1\le p\le q\le \max(4m,10),$$
así que su coste depende solo de \(m\), no del gran valor de \(n\). El trabajo dominante es el recorrido DFS, lo que da un tiempo total
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
La memoria es lineal en las raíces almacenadas y en la pila explícita usada para la componente activa. La paralelización reduce el tiempo de pared, pero no altera el trabajo combinatorio subyacente medido por la misma suma de estados visitados.
对每个满足 \(0\le k\le m\) 的位移 \(k\)，记 \(P_k(n)\) 为满足下列条件的无序原始正整数三元组 \((p,q,r)\) 的个数：
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
题目真正要求的是
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
如果直接在周长上界以内枚举全部三元组，代价会非常高。实现采用的办法是：先找出有限个“根”三元组，再用一组保持位移不变的线性变换生成整棵搜索树。
固定一个 \(k\)，定义二次型
$$Q(p,q,r)=r^2-p^2-q^2.$$
于是与这个位移对应的目标三元组，正好就是满足 \(Q(p,q,r)=k\) 的原始正整数点。
实现使用的三个线性变换是
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
把它们直接展开后可以验证，每个变换都保持二次型 \(Q\) 不变：
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
因此，只要一个三元组满足 \(p^2+q^2+k=r^2\)，那么经过这些变换得到的所有后代仍然满足同一个位移 \(k\) 的方程。又因为这些变换在整数范围内可逆，所以“原始性”也会被保留：如果某个子节点有公共因子，那么把逆变换施回去，父节点也会有同样的公共因子。
对应的逆变换为
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
如果一个原始三元组在这三个逆变换下都得不到“所有坐标都为正”的前驱，那么它就被称为根。换句话说，它在同一片搜索森林中没有父节点。
实现先在
$$1\le p\le q\le \max(4m,10)$$
这个有界窗口里枚举原始候选，检查 \(p^2+q^2+k\) 是否为完全平方数，然后去掉所有拥有正逆父节点的候选。求解器中明确说明：当 \(k>0\) 时，每个根都满足 \(p,q\le 4k\)。因此，当需要处理全部 \(0\le k\le m\) 时，扫描到 \(\max(4m,10)\) 就足够覆盖所有根。
对固定的 \(k\) 找到所有根之后，每个根在不断应用 \(A\)、\(B\)、\(C\) 的过程中会生成一个连通组件。实现使用显式栈来进行深度优先遍历。
剪枝依据是周长函数
$$\pi(p,q,r)=p+q+r.$$
如果 \(\pi(p,q,r)>n\)，那么这个节点本身不可能对 \(P_k(n)\) 有贡献，它的后续分支也直接丢弃。于是程序只访问那些仍有机会计入答案的三元组。
由于上一步已经排除了所有非根节点，每个合法三元组都只属于一个根组件。因此，从全部根出发做 DFS，就会把每个相关的有序三元组恰好访问一次。
交换两条直角边
$$\sigma(p,q,r)=(q,p,r)$$
不会改变方程，也不会改变原始性。根搜索只从 \(p\le q\) 的状态启动，所以对称家族不会在根层面被重复启动。在一个组件内部，实现记录两个量：
$$T=\text{访问到的三元组总数},\qquad D=\text{其中满足 }p=q\text{ 的个数}.$$
如果某个组件含有对角状态 \(p=q\)，那么交换映射 \(\sigma\) 会留在同一个组件里，恰好固定这些对角状态，并把所有非对角状态两两配对。因此该组件的无序贡献是
$$U=\frac{T+D}{2}.$$
如果组件中根本没有对角状态，那么实现认为当前被选中的根组件本身就已经代表了正确的无序计数，于是直接取 \(U=T\)。
三元组 \((1,1,3)\) 是原始的，而且满足
$$1^2+1^2+7=9=3^2,$$
所以它属于位移 \(k=7\)。对它应用三个变换可得
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
这三个子节点仍然都满足
$$r^2-p^2-q^2=7.$$
当周长上界取 \(n=31\) 时，这个组件中恰好会计入四个状态：
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
此时 \(T=4\)，对角状态是 \((1,1,3)\) 和 \((9,9,13)\)，所以 \(D=2\)。于是无序贡献为
$$U=\frac{4+2}{2}=3,$$
对应的三个无序三元组就是 \((1,1,3)\)、\((5,7,9)\) 和 \((9,9,13)\)。这个例子同时展示了“位移保持”和“对角修正”两件事是如何一起工作的。
一旦对每个固定的 \(k\) 计算出无序计数 \(P_k(n)\)，最终答案就是
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
因此整道题被分解成两层：外层是对每个位移做有限根搜索，内层是从这些根出发做带周长剪枝的树遍历。
C++、Python 和 Java 实现都遵循同一套计数逻辑。对每个 \(k\)，它们先在有界根窗口中枚举原始候选三元组，保留那些没有正逆父节点的候选作为根。然后对每个根使用显式栈执行深度优先遍历，不断应用三个前向变换；一旦某个节点的周长超过 \(n\)，对应分支立即停止扩展。
对每个根组件，实现都会分别统计访问到的三元组总数以及其中满足 \(p=q\) 的个数，再按照上一节的公式把这两个数转换为无序贡献。所有组件贡献之和给出 \(P_k(n)\)，再对 \(k=0,\dots,m\) 求和得到最终结果。C++ 和 Java 实现还会把相互独立的根任务分配给并行工作线程；Python 实现则复用同样的底层搜索策略，而不是重新设计另一套不同的数论过程。
记 \(R_k\) 为位移 \(k\) 的根数量，记 \(T_k(n)\) 为在周长剪枝后该位移全部根组件中访问到的三元组总数。预处理阶段的根扫描只使用有界盒子
$$1\le p\le q\le \max(4m,10),$$
所以这一部分的代价只依赖于 \(m\)，与很大的周长上界 \(n\) 无关。真正占主导的是 DFS 遍历，总时间可以写成
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
空间复杂度对已保存的根列表和当前活动组件的显式 DFS 栈都是线性的。并行化能够降低实际运行时间，但不会改变由同一批被访问状态决定的组合工作量。
Для каждого сдвига \(k\), где \(0\le k\le m\), обозначим через \(P_k(n)\) число неупорядоченных примитивных положительных целочисленных троек \((p,q,r)\), удовлетворяющих условиям
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
Тогда искомая величина равна
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Полный перебор всех троек до ограничения на периметр слишком дорог, поэтому реализация организует поиск через конечное множество корней и дерево линейных преобразований, сохраняющих величину сдвига.
Зафиксируем одно значение \(k\) и введем квадратичную форму
$$Q(p,q,r)=r^2-p^2-q^2.$$
Тогда нужные для этого сдвига тройки - это в точности примитивные положительные целые точки на уровне \(Q(p,q,r)=k\).
Поиск строится на трех линейных отображениях:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
Прямое раскрытие скобок показывает, что каждое из них сохраняет форму \(Q\):
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
Следовательно, если тройка удовлетворяет уравнению \(p^2+q^2+k=r^2\), то все ее потомки под действием этих преобразований удовлетворяют тому же уравнению с тем же \(k\). Поскольку преобразования обратимы над целыми числами, примитивность тоже сохраняется: общий делитель потомка автоматически был бы общим делителем родителя.
Обратные преобразования имеют вид
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
Примитивная тройка называется корнем, если ни одно из этих обратных изображений не имеет всех координат положительными. Иными словами, это решение без родителя в том же лесу поиска.
Сначала реализации перебирают примитивные кандидаты в области
$$1\le p\le q\le \max(4m,10),$$
проверяют, является ли \(p^2+q^2+k\) полным квадратом, а затем отбрасывают все тройки с положительным обратным родителем. В решателе явно отмечено, что при \(k>0\) любой корень удовлетворяет неравенству \(p,q\le 4k\); значит, сканирование до \(\max(4m,10)\) покрывает все сдвиги \(0\le k\le m\).
Когда корни для фиксированного \(k\) найдены, каждый корень порождает одну компоненту при повторном применении \(A\), \(B\) и \(C\). Реализации обходят эту компоненту с помощью явного стека поиска в глубину.
Правило отсечения задает функция периметра
$$\pi(p,q,r)=p+q+r.$$
Если \(\pi(p,q,r)>n\), то данный узел уже ничего не дает в \(P_k(n)\), и вся ветвь отбрасывается. Поэтому посещаются только те тройки, которые еще могут повлиять на ответ.
Так как на предыдущем шаге все не-корни были исключены, каждая допустимая тройка принадлежит ровно одной корневой компоненте. Следовательно, старт DFS из всех корней посещает каждую релевантную упорядоченную тройку ровно один раз.
Уравнение и условие примитивности не меняются при перестановке
$$\sigma(p,q,r)=(q,p,r).$$
Поиск корней запускается только из состояний с \(p\le q\), поэтому симметричные семейства не стартуют дважды. Внутри каждой компоненты реализация хранит две величины:
$$T=\text{число посещенных троек},\qquad D=\text{число посещенных троек с }p=q.$$
Если компонента содержит диагональные состояния \(p=q\), то отображение \(\sigma\) действует внутри той же компоненты, фиксирует ровно диагональные состояния и попарно связывает все остальные. Поэтому неупорядоченный вклад равен
$$U=\frac{T+D}{2}.$$
Если диагональных состояний нет, выбранная корневая компонента уже дает правильный неупорядоченный вклад, и реализация просто берет \(U=T\).
Тройка \((1,1,3)\) примитивна и удовлетворяет равенству
$$1^2+1^2+7=9=3^2,$$
поэтому относится к сдвигу \(k=7\). Три преобразования дают
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
Все три потомка по-прежнему удовлетворяют
$$r^2-p^2-q^2=7.$$
При ограничении \(n=31\) из этой компоненты учитываются ровно четыре состояния:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
Здесь \(T=4\), а диагональные состояния - это \((1,1,3)\) и \((9,9,13)\), то есть \(D=2\). Следовательно, неупорядоченный вклад равен
$$U=\frac{4+2}{2}=3,$$
что соответствует трем неупорядоченным тройкам \((1,1,3)\), \((5,7,9)\) и \((9,9,13)\).
После вычисления неупорядоченного числа \(P_k(n)\) для каждого фиксированного \(k\) окончательный ответ равен
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
Тем самым вся задача сводится к конечному поиску корней для каждого сдвига и к обходу дерева с отсечением по периметру от каждой найденной корневой вершины.
Реализации на C++, Python и Java следуют одной и той же схеме подсчета. Для каждого \(k\) они перечисляют примитивные кандидатные тройки в ограниченном окне корней, оставляют только те, у которых нет положительного обратного родителя, и используют оставшиеся тройки как корни. Затем каждая корневая компонента обходится явным стеком: к текущей тройке применяются три прямых преобразования, а ветвь обрывается, как только периметр превышает \(n\).
Для каждой компоненты реализация отдельно накапливает общее число посещенных троек и число состояний с \(p=q\). По формуле из предыдущего раздела эта пара превращается в неупорядоченный вклад. Сумма вкладов по всем компонентам дает \(P_k(n)\), а суммирование по \(k=0,\dots,m\) дает итоговый ответ. Реализации на C++ и Java дополнительно распределяют независимые корни между параллельными рабочими потоками, тогда как реализация на Python использует ту же базовую стратегию поиска, не вводя отдельной альтернативной математики.
Пусть \(R_k\) - число корней для сдвига \(k\), а \(T_k(n)\) - суммарное число троек, посещенных во всех корневых компонентах после отсечения по периметру. Предварительное сканирование корней использует ограниченную область
$$1\le p\le q\le \max(4m,10),$$
поэтому стоимость этого этапа зависит только от \(m\), а не от большого ограничения \(n\). Основную работу составляет сам обход, так что общее время равно
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
Память линейна по числу сохраненных корней и по размеру явного DFS-стека для текущей активной компоненты. Параллелизм уменьшает реальное время выполнения, но не меняет основную комбинаторную трудоемкость, измеряемую той же суммой посещенных состояний.
لكل إزاحة \(k\) حيث \(0\le k\le m\)، نرمز بـ \(P_k(n)\) إلى عدد الثلاثيات الصحيحة الموجبة الأولية غير المرتبة \((p,q,r)\) التي تحقق
$$p^2+q^2+k=r^2,\qquad p+q+r\le n,\qquad \gcd(p,q,r)=1.$$
والكمية المطلوبة هي
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
العد المباشر لكل الثلاثيات حتى حد المحيط سيكون مكلفًا جدًا، لذلك ينظم التنفيذ البحث عبر مجموعة من الجذور المنتهية وشجرة من التحويلات الخطية التي تحفظ قيمة الإزاحة.
ثبّت قيمة واحدة لـ \(k\)، وعرّف الصورة التربيعية
$$Q(p,q,r)=r^2-p^2-q^2.$$
وعندئذ تكون الثلاثيات المطلوبة لهذا \(k\) هي بالضبط النقاط الصحيحة الموجبة الأولية على المستوى \(Q(p,q,r)=k\).
يبنى البحث على ثلاثة تحويلات خطية:
$$A(p,q,r)=\bigl(p-2q+2r,\ 2p-q+2r,\ 2p-2q+3r\bigr),$$
$$B(p,q,r)=\bigl(p+2q+2r,\ 2p+q+2r,\ 2p+2q+3r\bigr),$$
$$C(p,q,r)=\bigl(-p+2q+2r,\ -2p+q+2r,\ -2p+2q+3r\bigr).$$
وبالتوسيع المباشر يتبين أن كل تحويل منها يحفظ \(Q\):
$$Q(A(p,q,r))=Q(B(p,q,r))=Q(C(p,q,r))=Q(p,q,r).$$
إذن إذا حققت ثلاثية ما المعادلة \(p^2+q^2+k=r^2\)، فإن جميع أحفادها تحت هذه التحويلات يحققون المعادلة نفسها مع الإزاحة نفسها \(k\). ولأن هذه التحويلات قابلة للعكس على الأعداد الصحيحة، فإن الأولية تبقى محفوظة أيضًا: فأي قاسم مشترك لولد ما سيكون قاسمًا مشتركًا للأب عند تطبيق التحويل العكسي.
التحويلات العكسية هي
$$A^{-1}(p,q,r)=\bigl(p+2q-2r,\ -2p-q+2r,\ -2p-2q+3r\bigr),$$
$$B^{-1}(p,q,r)=\bigl(p+2q-2r,\ 2p+q-2r,\ -2p-2q+3r\bigr),$$
$$C^{-1}(p,q,r)=\bigl(-p-2q+2r,\ 2p+q-2r,\ -2p-2q+3r\bigr).$$
تسمى الثلاثية الأولية جذرًا إذا لم تعط أي من هذه الصور العكسية ثلاثية ذات إحداثيات موجبة كلها. وبصياغة أخرى: الجذر هو حل لا يملك أبًا داخل غابة البحث نفسها.
تبدأ التنفيذات بحصر المرشحين الأوليين داخل الصندوق
$$1\le p\le q\le \max(4m,10),$$
ثم تفحص هل \(p^2+q^2+k\) مربع كامل، وبعد ذلك تستبعد كل مرشح يملك أبًا عكسيًا موجبًا. ويذكر الحل المعتمد أن كل جذر عند \(k>0\) يحقق \(p,q\le 4k\)، ولذلك فإن المسح حتى \(\max(4m,10)\) يكفي لتغطية جميع الإزاحات \(0\le k\le m\).
بعد معرفة الجذور لقيمة ثابتة من \(k\)، يولد كل جذر مكوّنًا واحدًا تحت التطبيق المتكرر لـ \(A\) و\(B\) و\(C\). وتستخدم التنفيذات مكدسًا صريحًا لتنفيذ بحث عمق أولًا.
وقاعدة القطع تأتي من دالة المحيط
$$\pi(p,q,r)=p+q+r.$$
فإذا كان \(\pi(p,q,r)>n\)، فإن هذه العقدة لا يمكن أن تسهم في \(P_k(n)\)، وتُهمل معها الشعبة كلها. وبهذا لا تُزار إلا الثلاثيات التي ما زالت قادرة على التأثير في العد.
وبما أن العقد غير الجذرية استُبعدت في الخطوة السابقة، فإن كل ثلاثية صالحة تنتمي إلى مكوّن جذري واحد فقط. لذلك فإن بدء البحث من جميع الجذور يزور كل ثلاثية مرتبة ذات صلة مرة واحدة بالضبط.
المعادلة وشرط الأولية لا يتغيران تحت التبديل
$$\sigma(p,q,r)=(q,p,r).$$
وبما أن البحث عن الجذور يبدأ فقط من الحالات التي تحقق \(p\le q\)، فلا يتم بدء العائلات المتناظرة مرتين. داخل كل مكوّن يسجل التنفيذ قيمتين:
ولنرمز بعدد الثلاثيات المزارة بالرمز \(T\)، وبعدد الثلاثيات المزارة التي تحقق \(p=q\) بالرمز \(D\).
إذا احتوى المكوّن على حالات قطرية \(p=q\)، فإن التحويل \(\sigma\) يبقى داخل المكوّن نفسه، ويثبت هذه الحالات القطرية تحديدًا، ويزاوج كل حالة خارج القطر مع صورتها المتبادلة. عندئذ يكون الإسهام غير المرتب
$$U=\frac{T+D}{2}.$$
أما إذا لم تظهر أي حالة قطرية، فإن المكوّن الجذري المختار يعطي أصلًا العد غير المرتب الصحيح، ولذلك يستخدم التنفيذ ببساطة \(U=T\).
الثلاثية \((1,1,3)\) أولية وتحقق
$$1^2+1^2+7=9=3^2,$$
ولذلك فهي تنتمي إلى الإزاحة \(k=7\). وعند تطبيق التحويلات الثلاثة نحصل على
$$A(1,1,3)=(5,7,9),\qquad B(1,1,3)=(9,9,13),\qquad C(1,1,3)=(7,5,9).$$
وجميع هذه الأبناء ما زالوا يحققون
$$r^2-p^2-q^2=7.$$
ومع حد محيط \(n=31\)، فإن هذا المكوّن يساهم بأربع حالات مضبوطة:
$$ (1,1,3),\ (5,7,9),\ (7,5,9),\ (9,9,13). $$
وهنا \(T=4\)، أما الحالات القطرية فهي \((1,1,3)\) و\((9,9,13)\)، أي إن \(D=2\). ومن ثم يكون الإسهام غير المرتب
$$U=\frac{4+2}{2}=3,$$
ويقابل ذلك الثلاثيات غير المرتبة \((1,1,3)\) و\((5,7,9)\) و\((9,9,13)\).
بعد حساب العدد غير المرتب \(P_k(n)\) لكل \(k\) ثابت، يكون الجواب النهائي ببساطة
$$S(m,n)=\sum_{k=0}^{m} P_k(n).$$
وهكذا تختزل المسألة كلها إلى بحث منتهٍ عن الجذور لكل إزاحة، ثم إلى اجتياز شجري مقطوع بالمحيط انطلاقًا من كل جذر.
تتبع تنفيذات C++ وPython وJava الخطة الحسابية نفسها. فهي، لكل \(k\)، تولد مرشحين أوليين داخل نافذة الجذور المحدودة، ثم تحتفظ فقط بالمرشحين الذين لا يملكون أبًا عكسيًا موجبًا، وتتعامل مع هؤلاء بوصفهم جذورًا. بعد ذلك يُستكشف كل جذر بواسطة مكدس صريح، مع تطبيق التحويلات الأمامية الثلاثة مرارًا، وقطع الفرع فور تجاوز المحيط للقيمة \(n\).
وفي كل مكوّن جذري، يجمع التنفيذ عدد الحالات المزارة كله، ويجمع على نحو منفصل عدد الحالات التي تحقق \(p=q\). ثم تُحوَّل هذه الثنائية إلى إسهام غير مرتب باستعمال الصيغة المذكورة في القسم السابق. ومجموع إسهامات المكوّنات يعطي \(P_k(n)\)، ثم يعطي مجموع \(P_k(n)\) على \(k=0,\dots,m\) النتيجة النهائية. وتقوم تنفيذات C++ وJava أيضًا بتوزيع الجذور المستقلة على عمال متوازيين، بينما يعتمد تنفيذ Python على استراتيجية البحث الأساسية نفسها بدل بناء رياضيات مختلفة.
لنرمز بـ \(R_k\) إلى عدد الجذور للإزاحة \(k\)، وبـ \(T_k(n)\) إلى العدد الكلي للثلاثيات المزارة عبر جميع المكوّنات بعد قطع المحيط. إن المسح التمهيدي للجذور يستخدم الصندوق المحدود
$$1\le p\le q\le \max(4m,10),$$
ولذلك فإن كلفته تعتمد على \(m\) فقط، لا على حد المحيط الكبير \(n\). أما العمل الغالب فهو اجتياز DFS نفسه، ولذلك يكون الزمن الكلي
$$O\!\left(\sum_{k=0}^{m} T_k(n)\right).$$
واستهلاك الذاكرة خطي في عدد الجذور المخزنة وفي حجم مكدس DFS للمكوّن النشط. وتقلل الموازاة الزمن الفعلي، لكنها لا تغير مقدار العمل التوافقي الأصلي المقاس بالمجموع نفسه لعدد الحالات المزارة.