For a bound \(N\), define
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
The task is to evaluate \(S(10^9)\). The C++, Python, and Java implementations do not search directly in \((x,y,z)\)-space. Instead, they generate primitive solutions from a quadratic parametrization, divide out a small class factor, and keep only the parameter pairs that can satisfy the ordering and divisibility conditions.
The key observation is that the ordered primitive triples on this quadratic surface can be generated from coprime pairs \((u,v)\) lying in a narrow cone. The raw quadratic forms are
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
After dividing by a class factor \(g\in\{1,4,16,19,64,76,304,1216\}\), the counted triple is
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
The three raw forms are chosen so that substituting them into the symmetric Diophantine equation gives an identity:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
Dividing every coordinate by the same positive factor preserves the equation, so the same relation holds for \((x,y,z)\). The primitive condition is enforced by combining \(\gcd(u,v)=1\) with the systematic removal of the shared class factor \(g\).
Write \(t=u/v\). Then
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
To obtain positive solutions on the relevant branch we need \(t>5/3\). Next,
$$y_0-x_0=2v^2(45t^2-206t+229).$$
The smaller root of \(45t^2-206t+229=0\) is
$$h=\frac{103-4\sqrt{19}}{45}.$$
Therefore \(x_0\le y_0\) on the ordered branch when
$$\frac{5}{3}<t\le h.$$
On this same interval one also has \(y_0\le z_0\), so the search only needs the cone
$$\frac{5}{3}v<u\le hv.$$
Introduce the linear forms
$$a=5u-3v,\qquad b=3u-5v.$$
Then the raw coordinates can be rewritten as
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
These identities explain why only eight class factors occur. The \(2\)-power part is
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
so \(g_2\in\{1,4,16,64\}\). In addition, if \(19\mid a\), then all three raw coordinates are divisible by \(19\). Hence the full factor is one of
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
The class factor depends only on
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
That is enough because the \(2\)-power part only needs the powers of \(2\) in \(a\) and \(b\) up to \(2^3\), and the \(19\)-part only asks whether \(a\equiv 0\pmod{19}\). Combining modulus \(16\) and modulus \(19\) gives
$$16\cdot 19=304.$$
So for each class factor \(g\) and each residue of \(v\bmod 304\), the implementations precompute the admissible residues of \(u\bmod 304\). The main search can then skip every parameter pair whose residue class cannot possibly land in the desired primitive branch.
Still writing \(t=u/v\), we have
$$z_0=v^2(32t^2-176t+240).$$
On the interval \(\frac{5}{3}<t\le h\), this quadratic factor is minimized at the right endpoint, so
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
Because the counted triple satisfies \(z=z_0/g\le N\), every class obeys
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
This square-root bound is exactly what determines the per-class outer loop limits.
Take \((u,v)=(13,7)\). Then
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
which lies inside \(\frac{5}{3}<u/v\le h\). Now
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
Both \(a\) and \(b\) are divisible by \(4\), but not both by \(8\), so \(g_2=16\). Since \(19\nmid 44\), there is no extra factor \(19\), hence \(g=16\).
The raw forms are
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
and dividing by \(16\) gives
$$ (x,y,z)=\left(11,21,72\right). $$
This triple is primitive and ordered, and it satisfies
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
Its contribution to the sum is therefore
$$11+21+72=104.$$
The C++, Python, and Java implementations all follow the same pipeline. First they precompute, for each class factor and each residue of \(v\bmod 304\), the admissible residues of \(u\bmod 304\). Next they determine class-dependent upper bounds for \(v\) from the inequality \(z\le N\). For every \(v\), they scan only the integers \(u\) in the cone \(\frac{5}{3}v<u\le hv\) that match one of the allowed residue classes. They then apply three final filters: \(\gcd(u,v)=1\), the bound \(z_0\le Ng\), and division by the class factor \(g\). Every surviving candidate contributes
$$\frac{x_0+y_0+z_0}{g}$$
to the running total. The C++ and Java implementations optionally split the \(v\)-range across several threads for large \(N\); the Python implementation uses the same arithmetic in a single thread.
The residue precomputation is constant-size, because it only fills tables for \(8\) classes and \(304\) residues. For a fixed class, the outer variable \(v\) runs to \(O(\sqrt{N})\), while the raw width of the cone in \(u\) is \(O(v)\). Thus the unfiltered search region has \(O(N)\) area. The residue table removes most candidates before any gcd or bound test is attempted, so the practical constant factor is much smaller than a direct cone scan. Memory usage is \(O(1)\) apart from the small residue tables and, in the threaded implementations, one accumulator per worker.
Für eine Schranke \(N\) definieren wir
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
Gesucht ist also \(S(10^9)\). Die C++-, Python- und Java-Implementierungen durchsuchen den Raum \((x,y,z)\) nicht direkt. Stattdessen erzeugen sie primitive Lösungen aus einer quadratischen Parametrisierung, teilen einen kleinen Klassenfaktor heraus und behalten nur die Parameterpaare, die sowohl die Ordnungs- als auch die Teilbarkeitsbedingungen erfüllen können.
Die zentrale Beobachtung ist, dass die geordneten primitiven Tripel auf dieser quadratischen Fläche aus teilerfremden Paaren \((u,v)\) in einem schmalen Kegel erzeugt werden. Die rohen quadratischen Formen lauten
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
Nach Division durch einen Klassenfaktor \(g\in\{1,4,16,19,64,76,304,1216\}\) erhält man das gezählte Tripel
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
Die drei rohen Formen sind so gewählt, dass das Einsetzen in die symmetrische diophantische Gleichung eine Identität ergibt:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
Teilt man alle drei Koordinaten durch denselben positiven Faktor, bleibt die Gleichung erhalten; also gilt dieselbe Beziehung auch für \((x,y,z)\). Die Primitivitätsbedingung wird durch die Kombination aus \(\gcd(u,v)=1\) und dem systematischen Entfernen des gemeinsamen Klassenfaktors \(g\) erzwungen.
Schreibe \(t=u/v\). Dann gilt
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
Damit \(x_0\) auf dem relevanten positiven Zweig positiv ist, braucht man \(t>5/3\). Weiter ist
$$y_0-x_0=2v^2(45t^2-206t+229).$$
Die kleinere Nullstelle von \(45t^2-206t+229=0\) ist
$$h=\frac{103-4\sqrt{19}}{45}.$$
Daraus folgt \(x_0\le y_0\) auf dem geordneten Zweig für
$$\frac{5}{3}<t\le h.$$
Auf demselben Intervall gilt auch \(y_0\le z_0\). Daher genügt es, im Kegel
$$\frac{5}{3}v<u\le hv$$
zu suchen.
Führe die linearen Formen
$$a=5u-3v,\qquad b=3u-5v$$
ein. Dann lassen sich die rohen Koordinaten umschreiben zu
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
Diese Identitäten erklären, warum nur acht Klassenfaktoren auftreten. Der Zweierpotenz-Anteil ist
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
also \(g_2\in\{1,4,16,64\}\). Zusätzlich gilt: Falls \(19\mid a\), dann sind alle drei rohen Koordinaten durch \(19\) teilbar. Daher ist der volle Faktor eines der Elemente
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
Der Klassenfaktor hängt nur von
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19$$
ab. Das genügt, weil für den Zweierpotenz-Anteil nur die Anzahl der Zweierfaktoren in \(a\) und \(b\) bis \(2^3\) relevant ist und der \(19\)-Anteil nur prüft, ob \(a\equiv 0\pmod{19}\) gilt. Durch das Kombinieren von Modulus \(16\) und Modulus \(19\) erhält man
$$16\cdot 19=304.$$
Somit berechnen die Implementierungen für jeden Klassenfaktor \(g\) und jeden Rest von \(v\bmod 304\) vorab die zulässigen Reste von \(u\bmod 304\). Die Hauptsuche kann dadurch jedes Parameterpaar überspringen, dessen Restklasse den gewünschten primitiven Zweig gar nicht liefern kann.
Mit \(t=u/v\) gilt weiterhin
$$z_0=v^2(32t^2-176t+240).$$
Auf dem Intervall \(\frac{5}{3}<t\le h\) wird der quadratische Faktor am rechten Rand minimal, also
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
Da das gezählte Tripel \(z=z_0/g\le N\) erfüllen muss, folgt für jede Klasse
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
Genau diese Wurzelabschätzung bestimmt die äußeren Schleifengrenzen pro Klasse.
Nehmen wir \((u,v)=(13,7)\). Dann ist
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
also innerhalb von \(\frac{5}{3}<u/v\le h\). Außerdem
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
Sowohl \(a\) als auch \(b\) sind durch \(4\) teilbar, aber nicht beide durch \(8\), also ist \(g_2=16\). Da \(19\nmid 44\), kommt kein zusätzlicher Faktor \(19\) hinzu, also \(g=16\).
Die rohen Formen sind
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
und nach Division durch \(16\) erhält man
$$ (x,y,z)=\left(11,21,72\right). $$
Dieses Tripel ist primitiv, geordnet und erfüllt
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
Sein Beitrag zur Summe ist daher
$$11+21+72=104.$$
Die C++-, Python- und Java-Implementierungen folgen alle demselben Ablauf. Zuerst werden für jeden Klassenfaktor und jeden Rest von \(v\bmod 304\) die zulässigen Reste von \(u\bmod 304\) vorab berechnet. Danach werden klassenabhängige Obergrenzen für \(v\) aus der Ungleichung \(z\le N\) bestimmt. Für jedes \(v\) werden dann nur die ganzen \(u\)-Werte im Kegel \(\frac{5}{3}v<u\le hv\) untersucht, die zu einer erlaubten Restklasse gehören. Anschließend folgen drei letzte Filter: \(\gcd(u,v)=1\), die Schranke \(z_0\le Ng\) und die Division durch den Klassenfaktor \(g\). Jeder verbleibende Kandidat trägt
$$\frac{x_0+y_0+z_0}{g}$$
zur laufenden Summe bei. Die C++- und Java-Implementierungen teilen den \(v\)-Bereich bei großem \(N\) optional auf mehrere Threads auf; die Python-Implementierung verwendet dieselbe Arithmetik seriell.
Die Restklassenvorberechnung hat konstante Größe, weil nur Tabellen für \(8\) Klassen und \(304\) Reste gefüllt werden. Für eine feste Klasse läuft die äußere Variable \(v\) bis \(O(\sqrt{N})\), während die rohe Breite des Kegels in \(u\) gleich \(O(v)\) ist. Der ungefilterte Suchbereich hat also Fläche \(O(N)\). Die Restklassentabelle verwirft den Großteil aller Kandidaten, bevor überhaupt ein ggT- oder Schrankencheck erfolgt, daher ist der praktische Konstantenfaktor deutlich kleiner als bei einer direkten Kegelsuche. Der Speicherbedarf ist \(O(1)\), abgesehen von den kleinen Restklassentabellen und in den parallelen Implementierungen von je einem Akkumulator pro Worker.
Bir \(N\) üst sınırı için
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z)$$
tanımını yapalım. Amaç \(S(10^9)\) değerini hesaplamaktır. C++, Python ve Java implementasyonları \((x,y,z)\) uzayını doğrudan taramaz. Bunun yerine ilkel çözümleri kuadratik bir parametrizasyondan üretir, küçük bir sınıf çarpanını dışarı alır ve sadece sıralama ile bölünebilirlik koşullarını sağlayabilecek parametre çiftlerini tutar.
Temel gözlem şudur: Bu kuadratik yüzey üzerindeki sıralı ilkel üçlüler, dar bir koni içinde kalan aralarında asal \((u,v)\) çiftlerinden üretilebilir. Ham kuadratik biçimler
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2$$
şeklindedir. Bunları \(g\in\{1,4,16,19,64,76,304,1216\}\) sınıf çarpanına böldüğümüzde sayılan üçlü
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}$$
olur.
Bu üç ham biçim, simetrik diofant denkleme yerleştirildiğinde özdeşlik verecek şekilde seçilmiştir:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
Tüm koordinatları aynı pozitif sayıya bölmek denklemi bozmaz; dolayısıyla aynı ilişki \((x,y,z)\) için de geçerlidir. İlkel olma şartı, \(\gcd(u,v)=1\) koşulu ile ortak sınıf çarpanı \(g\)'nin sistematik olarak çıkarılmasının birleşiminden gelir.
\(t=u/v\) yazalım. O zaman
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
İlgili pozitif dalda \(x_0>0\) olması için \(t>5/3\) gerekir. Ayrıca
$$y_0-x_0=2v^2(45t^2-206t+229).$$
\(45t^2-206t+229=0\) denkleminin küçük kökü
$$h=\frac{103-4\sqrt{19}}{45}$$
olur. Bu nedenle sıralı dalda
$$\frac{5}{3}<t\le h$$
iken \(x_0\le y_0\) sağlanır. Aynı aralıkta \(y_0\le z_0\) da geçerlidir; dolayısıyla arama sadece
$$\frac{5}{3}v<u\le hv$$
konisi içinde yapılır.
Şu lineer biçimleri tanımlayalım:
$$a=5u-3v,\qquad b=3u-5v.$$
Ham koordinatlar o zaman
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}$$
şeklinde yazılır. Bu özdeşlikler neden sadece sekiz sınıf çarpanı çıktığını açıklar. \(2\)-üssü kısmı
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)}$$
olduğundan \(g_2\in\{1,4,16,64\}\) olur. Ek olarak \(19\mid a\) ise üç ham koordinatın tamamı \(19\)'a bölünür. Böylece tam çarpan
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}$$
kümesinden gelir.
Sınıf çarpanı yalnızca şu bilgilere bağlıdır:
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
Bu yeterlidir; çünkü \(2\)-üssü kısmı için sadece \(a\) ve \(b\)'deki \(2\) kuvvetlerini \(2^3\)'e kadar ayırt etmek gerekir, \(19\) kısmı içinse yalnızca \(a\equiv 0\pmod{19}\) olup olmadığına bakılır. Modül \(16\) ile modül \(19\) birleştirilince
$$16\cdot 19=304$$
elde edilir. Bu yüzden implementasyonlar her sınıf çarpanı \(g\) ve her \(v\bmod 304\) kalanı için izinli \(u\bmod 304\) kalıntılarını önceden çıkarır. Ana arama da böylece istenen ilkel dala düşmesi imkansız olan her parametre çiftini atlar.
Yine \(t=u/v\) iken
$$z_0=v^2(32t^2-176t+240)$$
olur. \(\frac{5}{3}<t\le h\) aralığında bu kuadratik katsayı sağ uçta minimum aldığı için
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240$$
yazılır. Sayılan üçlü \(z=z_0/g\le N\) sağlamalıdır; dolayısıyla her sınıf için
$$v\le \sqrt{\frac{Ng}{c_{\min}}}$$
üst sınırı elde edilir. Dış döngüde görülen kök ölçekli sınır tam olarak budur.
\((u,v)=(13,7)\) alalım. Bu durumda
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
yani \(\frac{5}{3}<u/v\le h\) aralığındadır. Ayrıca
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
Hem \(a\) hem \(b\) \(4\)'e bölünür, fakat ikisi birden \(8\)'e bölünmez; bu yüzden \(g_2=16\) olur. \(19\nmid 44\) olduğundan ek \(19\) çarpanı yoktur ve \(g=16\) elde edilir.
Ham biçimler
$$x_0=176,\qquad y_0=336,\qquad z_0=1152$$
olur; \(16\)'ya böldüğümüzde
$$ (x,y,z)=\left(11,21,72\right) $$
elde edilir. Bu üçlü hem ilkel hem sıralıdır ve
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11)$$
eşitliğini sağlar. Dolayısıyla toplama katkısı
$$11+21+72=104$$
olur.
C++, Python ve Java implementasyonlarının hepsi aynı akışı izler. Önce her sınıf çarpanı ve her \(v\bmod 304\) kalanı için izinli \(u\bmod 304\) kalıntıları önceden hesaplanır. Sonra \(z\le N\) eşitsizliğinden her sınıfa özel \(v\) üst sınırları bulunur. Her \(v\) için yalnızca \(\frac{5}{3}v<u\le hv\) konisi içinde olup izinli artık sınıfına düşen tamsayı \(u\) değerleri gezilir. Ardından üç son filtre uygulanır: \(\gcd(u,v)=1\), \(z_0\le Ng\) sınırı ve sınıf çarpanı \(g\)'ye bölme işlemi. Geriye kalan her aday
$$\frac{x_0+y_0+z_0}{g}$$
kadar katkı yapar. C++ ve Java implementasyonları büyük \(N\) için \(v\) aralığını isteğe bağlı olarak iş parçacıklarına böler; Python implementasyonu aynı aritmetiği tek iş parçacığında yürütür.
Artık tablosu ön hesabı sabit boyutludur; çünkü sadece \(8\) sınıf ve \(304\) kalıntı için tablo doldurulur. Sabit bir sınıf için dış değişken \(v\), \(O(\sqrt{N})\) mertebesine kadar gider; koninin \(u\) yönündeki ham genişliği ise \(O(v)\)'dir. Bu nedenle filtrelenmemiş arama bölgesinin alanı \(O(N)\) olur. Artık tablosu, EBOB ya da sınır kontrolü yapılmadan önce adayların büyük kısmını eler; bu yüzden pratik sabit katsayı doğrudan koni taramasından çok daha küçüktür. Bellek kullanımı, küçük artık tabloları ve paralel sürümlerdeki işçi başına tek bir biriktirici dışında \(O(1)\)'dir.
Para una cota \(N\), definimos
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
La meta es calcular \(S(10^9)\). Las implementaciones en C++, Python y Java no recorren directamente el espacio \((x,y,z)\). En su lugar, generan soluciones primitivas a partir de una parametrización cuadrática, extraen un pequeño factor de clase y conservan solo los pares de parámetros que pueden satisfacer tanto el orden \(x\le y\le z\) como las condiciones de divisibilidad.
La observación central es que las ternas primitivas ordenadas sobre esta superficie cuadrática pueden generarse a partir de pares coprimos \((u,v)\) dentro de un cono muy estrecho. Las formas cuadráticas brutas son
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
Después de dividir por un factor de clase \(g\in\{1,4,16,19,64,76,304,1216\}\), la terna contada es
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
Las tres formas brutas están escogidas para que al sustituirlas en la ecuación diofántica simétrica aparezca una identidad:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
Dividir las tres coordenadas por el mismo factor positivo conserva la ecuación, así que la misma relación vale para \((x,y,z)\). La condición de primitividad se impone combinando \(\gcd(u,v)=1\) con la eliminación sistemática del factor común \(g\).
Escribamos \(t=u/v\). Entonces
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
Para obtener la rama positiva relevante necesitamos \(t>5/3\). Además,
$$y_0-x_0=2v^2(45t^2-206t+229).$$
La raíz menor de \(45t^2-206t+229=0\) es
$$h=\frac{103-4\sqrt{19}}{45}.$$
Por tanto, en la rama ordenada se tiene \(x_0\le y_0\) cuando
$$\frac{5}{3}<t\le h.$$
En ese mismo intervalo también se cumple \(y_0\le z_0\), así que basta con explorar el cono
$$\frac{5}{3}v<u\le hv.$$
Introduzcamos las formas lineales
$$a=5u-3v,\qquad b=3u-5v.$$
Entonces las coordenadas brutas se reescriben como
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
Estas identidades explican por qué solo aparecen ocho factores de clase. La parte correspondiente a potencias de \(2\) es
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
de modo que \(g_2\in\{1,4,16,64\}\). Además, si \(19\mid a\), entonces las tres coordenadas brutas son divisibles por \(19\). Por lo tanto, el factor total pertenece a
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
El factor de clase depende solo de
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
Eso basta porque la parte \(2\)-ádica solo necesita distinguir las potencias de \(2\) en \(a\) y \(b\) hasta \(2^3\), y la parte de \(19\) solo pregunta si \(a\equiv 0\pmod{19}\). Al combinar módulo \(16\) y módulo \(19\) obtenemos
$$16\cdot 19=304.$$
Así, para cada factor de clase \(g\) y cada residuo de \(v\bmod 304\), las implementaciones precalculan los residuos admisibles de \(u\bmod 304\). La búsqueda principal puede entonces saltarse todos los pares de parámetros cuya clase residual no puede producir la rama primitiva deseada.
Siguiendo con \(t=u/v\), tenemos
$$z_0=v^2(32t^2-176t+240).$$
En el intervalo \(\frac{5}{3}<t\le h\), ese factor cuadrático alcanza su mínimo en el extremo derecho, de modo que
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
Como la terna contada cumple \(z=z_0/g\le N\), cada clase satisface
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
Ese límite de tipo raíz cuadrada es exactamente el que aparece en los bucles exteriores.
Tomemos \((u,v)=(13,7)\). Entonces
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
que cae dentro de \(\frac{5}{3}<u/v\le h\). Ahora
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
Tanto \(a\) como \(b\) son divisibles por \(4\), pero no ambos por \(8\), así que \(g_2=16\). Como \(19\nmid 44\), no aparece el factor extra \(19\), y por tanto \(g=16\).
Las formas brutas son
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
y al dividir por \(16\) obtenemos
$$ (x,y,z)=\left(11,21,72\right). $$
Esta terna es primitiva, está ordenada y satisface
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
Su contribución a la suma es entonces
$$11+21+72=104.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Primero precalculan, para cada factor de clase y cada residuo de \(v\bmod 304\), qué residuos de \(u\bmod 304\) son admisibles. Después calculan, clase por clase, hasta dónde puede llegar \(v\) usando la cota derivada de \(z\le N\). Para cada \(v\), solo recorren los enteros \(u\) dentro del cono \(\frac{5}{3}v<u\le hv\) que coinciden con un residuo permitido. Luego aplican tres filtros finales: \(\gcd(u,v)=1\), la restricción \(z_0\le Ng\) y la división por el factor de clase \(g\). Cada candidato que sobrevive aporta
$$\frac{x_0+y_0+z_0}{g}$$
al acumulado. Las versiones en C++ y Java pueden repartir el rango de \(v\) entre varios hilos cuando \(N\) es grande; la versión en Python usa la misma aritmética de forma secuencial.
La precalculación de residuos es de tamaño constante, porque solo llena tablas para \(8\) clases y \(304\) residuos. Para una clase fija, la variable exterior \(v\) llega hasta \(O(\sqrt{N})\), mientras que el ancho bruto del cono en \(u\) es \(O(v)\). Por tanto, la región de búsqueda sin filtrar tiene área \(O(N)\). La tabla de residuos elimina la mayoría de los candidatos antes de intentar cualquier cálculo de gcd o comprobación de cota, así que el factor constante práctico es mucho menor que en un barrido directo del cono. El uso de memoria es \(O(1)\), aparte de las pequeñas tablas de residuos y, en las implementaciones paralelas, un acumulador por trabajador.
对给定上界 \(N\)，定义
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
题目的目标是求 \(S(10^9)\)。C++、Python 和 Java 实现都不会在 \((x,y,z)\) 空间中直接暴力枚举，而是先用一个二次参数化生成原始候选，再除去一个很小的公共类别因子，最后只保留那些既可能满足整除条件、又位于有序分支 \(x\le y\le z\) 上的参数对。
核心事实是：这条二次曲面上的有序原始三元组，可以由一个很窄的参数锥体中的互素整数对 \((u,v)\) 生成。原始二次型为
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
再除以类别因子 \(g\in\{1,4,16,19,64,76,304,1216\}\)，就得到真正计入求和的三元组
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
这三个原始二次型被专门构造成满足如下恒等式：
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
也就是说，把它们代入对称丢番图方程时，恒等成立。把三个坐标同时除以同一个正因子不会破坏这个关系，因此 \((x,y,z)\) 也仍然满足原方程。所谓“原始”条件，则通过两层结构共同保证：一方面要求 \(\gcd(u,v)=1\)，另一方面把参数化中可预见的公共因子 \(g\) 统一除掉。
令 \(t=u/v\)。则
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
为了使所需的正分支上有 \(x_0>0\)，必须满足 \(t>5/3\)。接下来考虑
$$y_0-x_0=2v^2(45t^2-206t+229).$$
二次方程 \(45t^2-206t+229=0\) 的较小根为
$$h=\frac{103-4\sqrt{19}}{45}.$$
因此在我们关心的有序分支上，只要
$$\frac{5}{3}<t\le h,$$
就有 \(x_0\le y_0\)。而在同一个区间内，还可以验证 \(y_0\le z_0\)。所以实现只需要扫描狭窄锥体
$$\frac{5}{3}v<u\le hv$$
中的整点，而不必考虑其余参数区域。
定义两个线性形式
$$a=5u-3v,\qquad b=3u-5v.$$
这样原始坐标可以改写为
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
这组恒等式直接解释了为什么只会出现八种类别因子。先看 \(2\) 的部分：
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
因此 \(g_2\) 只能取 \(\{1,4,16,64\}\)。再看 \(19\) 的部分：如果 \(19\mid a\)，那么上面三个表达式都自动再带有一个因子 \(19\)。所以完整的类别因子只能来自
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
类别因子只依赖于下面这些同余信息：
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
原因是：对于 \(2\)-进部分，我们只需要知道 \(a\) 与 \(b\) 中 \(2\) 的幂次到 \(2^3\) 为止；而对于 \(19\) 的部分，只需要判断 \(a\equiv 0\pmod{19}\) 是否成立。把模 \(16\) 与模 \(19\) 合并，得到
$$16\cdot 19=304.$$
于是，对于每一个类别因子 \(g\) 和每一个 \(v\bmod 304\) 的取值，程序都会预先列出所有允许的 \(u\bmod 304\) 剩余类。主循环就只需访问这些剩余类对应的参数，大量不可能产生合法原始三元组的候选会在最早阶段被直接跳过。
继续记 \(t=u/v\)，有
$$z_0=v^2(32t^2-176t+240).$$
在区间 \(\frac{5}{3}<t\le h\) 上，这个二次因子在右端点取得最小值，因此
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
而真正计入的三元组满足 \(z=z_0/g\le N\)，所以对每一个类别因子都有
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
这就是实现里外层循环上界呈现平方根规模的原因。
取 \((u,v)=(13,7)\)。这时
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
确实落在 \(\frac{5}{3}<u/v\le h\) 之内。再计算
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
\(a\) 和 \(b\) 都能被 \(4\) 整除，但不能同时被 \(8\) 整除，所以 \(g_2=16\)。又因为 \(19\nmid 44\)，没有额外的 \(19\) 因子，于是 \(g=16\)。
对应的原始坐标为
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
除以 \(16\) 后得到
$$ (x,y,z)=\left(11,21,72\right). $$
这个三元组既是原始的，又满足 \(x\le y\le z\)，并且确实满足
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
因此它对总和的贡献是
$$11+21+72=104.$$
C++、Python 和 Java 实现遵循完全相同的流程。第一步，按类别因子和 \(v\bmod 304\) 的值，预计算所有允许的 \(u\bmod 304\) 剩余类。第二步，根据 \(z\le N\) 推出的不等式，分别给每个类别建立 \(v\) 的上界。第三步，对每个 \(v\)，只扫描锥体 \(\frac{5}{3}v<u\le hv\) 内、并且属于允许剩余类的那些整数 \(u\)。最后再做三重过滤：\(\gcd(u,v)=1\)、\(z_0\le Ng\)、以及按类别因子 \(g\) 做整除。所有保留下来的候选都会向总和增加
$$\frac{x_0+y_0+z_0}{g}$$
这一项。C++ 和 Java 版本在 \(N\) 很大时还会把 \(v\) 的区间拆分给多个线程；Python 版本则用相同算术顺序执行。
剩余表的预计算是常数规模的，因为只需要为 \(8\) 个类别和 \(304\) 个剩余值填表。对某个固定类别来说，外层变量 \(v\) 的上界是 \(O(\sqrt{N})\)，而锥体中 \(u\) 的原始宽度是 \(O(v)\)，所以未经筛选的参数区域面积是 \(O(N)\)。剩余类表会在进行 gcd 和边界检测之前先淘汰绝大多数不可能的候选，因此实际运行时的常数因子远小于直接扫描整个锥体。除去很小的剩余表以及并行版本中每个线程的累计器之外，空间复杂度是 \(O(1)\)。
Для заданной границы \(N\) определим
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
Нужно вычислить \(S(10^9)\). Реализации на C++, Python и Java не перебирают пространство \((x,y,z)\) напрямую. Вместо этого они порождают примитивные решения из квадратической параметризации, делят на небольшой классовый множитель и оставляют только те пары параметров, которые могут одновременно удовлетворять порядку \(x\le y\le z\) и нужным условиям делимости.
Главная идея состоит в том, что упорядоченные примитивные тройки на этой квадратической поверхности порождаются взаимно простыми парами \((u,v)\), лежащими в узком конусе. Сырые квадратические формы таковы:
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
После деления на классовый множитель \(g\in\{1,4,16,19,64,76,304,1216\}\) получаем учитываемую тройку
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
Эти три формы подобраны так, что подстановка в симметрическое диофантово уравнение дает тождество:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
Если разделить все три координаты на один и тот же положительный множитель, уравнение сохранится, поэтому та же связь верна и для \((x,y,z)\). Примитивность обеспечивается сочетанием условия \(\gcd(u,v)=1\) и систематического удаления общего классового множителя \(g\).
Положим \(t=u/v\). Тогда
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
Чтобы на нужной положительной ветви было \(x_0>0\), требуется \(t>5/3\). Далее,
$$y_0-x_0=2v^2(45t^2-206t+229).$$
Меньший корень уравнения \(45t^2-206t+229=0\) равен
$$h=\frac{103-4\sqrt{19}}{45}.$$
Следовательно, на упорядоченной ветви имеем \(x_0\le y_0\), если
$$\frac{5}{3}<t\le h.$$
На том же интервале выполняется и \(y_0\le z_0\), поэтому поиск сводится к конусу
$$\frac{5}{3}v<u\le hv.$$
Введем линейные формы
$$a=5u-3v,\qquad b=3u-5v.$$
Тогда сырые координаты переписываются так:
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
Именно эти тождества объясняют, почему возможны только восемь классовых множителей. Двухадическая часть имеет вид
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
то есть \(g_2\in\{1,4,16,64\}\). Кроме того, если \(19\mid a\), то все три сырые координаты делятся на \(19\). Значит, полный множитель принадлежит множеству
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
Классовый множитель зависит только от
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
Этого достаточно: для двухадической части нужно различать степени двойки в \(a\) и \(b\) лишь до уровня \(2^3\), а для части, связанной с \(19\), достаточно проверить условие \(a\equiv 0\pmod{19}\). Объединяя модули \(16\) и \(19\), получаем
$$16\cdot 19=304.$$
Поэтому для каждого классового множителя \(g\) и каждого остатка \(v\bmod 304\) реализации заранее вычисляют допустимые остатки \(u\bmod 304\). Основной цикл затем пропускает все пары параметров, чей класс вычетов заведомо не может попасть в нужную примитивную ветвь.
Продолжая писать \(t=u/v\), имеем
$$z_0=v^2(32t^2-176t+240).$$
На интервале \(\frac{5}{3}<t\le h\) этот квадратичный множитель минимален на правом конце, так что
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
Так как учитываемая тройка должна удовлетворять \(z=z_0/g\le N\), для каждого класса получается ограничение
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
Именно эта оценка корневого масштаба задает внешние пределы цикла.
Возьмем \((u,v)=(13,7)\). Тогда
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
то есть отношение лежит внутри \(\frac{5}{3}<u/v\le h\). Далее
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
И \(a\), и \(b\) делятся на \(4\), но не оба делятся на \(8\), значит \(g_2=16\). Поскольку \(19\nmid 44\), дополнительного множителя \(19\) нет, и поэтому \(g=16\).
Сырые формы равны
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
а после деления на \(16\) получаем
$$ (x,y,z)=\left(11,21,72\right). $$
Эта тройка примитивна, упорядочена и удовлетворяет равенству
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
Следовательно, ее вклад в сумму равен
$$11+21+72=104.$$
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала для каждого классового множителя и каждого остатка \(v\bmod 304\) заранее вычисляются допустимые остатки \(u\bmod 304\). Затем из неравенства \(z\le N\) выводятся зависящие от класса верхние границы для \(v\). Для каждого \(v\) перебираются только те целые \(u\), которые лежат в конусе \(\frac{5}{3}v<u\le hv\) и принадлежат разрешенному классу вычетов. После этого применяются три окончательных фильтра: \(\gcd(u,v)=1\), ограничение \(z_0\le Ng\) и деление на классовый множитель \(g\). Каждый прошедший кандидат добавляет к ответу
$$\frac{x_0+y_0+z_0}{g}$$
к сумме. В версиях на C++ и Java диапазон \(v\) при больших \(N\) при необходимости делится между несколькими потоками; Python-версия выполняет ту же арифметику последовательно.
Предварительное построение таблицы вычетов имеет постоянный размер, потому что заполняются только таблицы для \(8\) классов и \(304\) остатков. Для фиксированного класса внешняя переменная \(v\) идет до \(O(\sqrt{N})\), а грубая ширина конуса по \(u\) равна \(O(v)\). Значит, площадь нефильтрованной области поиска имеет порядок \(O(N)\). Таблица вычетов отсеивает большую часть кандидатов еще до проверки gcd и границы, поэтому практический множитель существенно меньше, чем у прямого сканирования всего конуса. Память составляет \(O(1)\), не считая маленьких таблиц вычетов и по одному накопителю на поток в параллельных реализациях.
لحد علوي \(N\) نعرّف
$$S(N)=\sum_{\substack{1\le x\le y\le z\le N\\ \gcd(x,y,z)=1\\ 15(x^2+y^2+z^2)=34(xy+yz+zx)}}(x+y+z).$$
المطلوب هو حساب \(S(10^9)\). لا تقوم تطبيقات C++ وPython وJava بفحص فضاء \((x,y,z)\) مباشرة، بل تولّد الحلول الأولية من تمثيل تربيعي بارامتري، ثم تقسم على عامل صنف صغير، ثم تحتفظ فقط بأزواج المعلمات القادرة على تحقيق الترتيب \(x\le y\le z\) وشروط القسمة معًا.
الفكرة الأساسية هي أن الثلاثيات الأولية المرتبة على هذا السطح التربيعي يمكن توليدها من أزواج متباينة أوليًا \((u,v)\) تقع داخل مخروط ضيق. الصيغ التربيعية الخام هي
$$x_0=15u^2-34uv+15v^2,\qquad y_0=105u^2-446uv+473v^2,\qquad z_0=32u^2-176uv+240v^2.$$
وبعد القسمة على عامل الصنف \(g\in\{1,4,16,19,64,76,304,1216\}\) نحصل على الثلاثية المحسوبة
$$x=\frac{x_0}{g},\qquad y=\frac{y_0}{g},\qquad z=\frac{z_0}{g}.$$
اختيرت هذه الصيغ الثلاث بحيث يعطي التعويض في المعادلة الديوفانتية المتماثلة متطابقة مباشرة:
$$15(x_0^2+y_0^2+z_0^2)=34(x_0y_0+y_0z_0+z_0x_0).$$
وقسمة الإحداثيات الثلاثة على العامل الموجب نفسه لا تغيّر صحة المعادلة، ولذلك تبقى العلاقة صحيحة أيضًا بعد الانتقال إلى \((x,y,z)\). أما شرط الأولية فيُفرض من خلال الجمع بين \(\gcd(u,v)=1\) وإزالة عامل الصنف المشترك \(g\) بطريقة منهجية.
لنكتب \(t=u/v\). عندئذ
$$x_0=v^2(15t^2-34t+15)=v^2(5t-3)(3t-5).$$
ولكي يكون \(x_0>0\) على الفرع الموجب المطلوب يجب أن يكون \(t>5/3\). ولدينا أيضًا
$$y_0-x_0=2v^2(45t^2-206t+229).$$
والجذر الأصغر للمعادلة \(45t^2-206t+229=0\) هو
$$h=\frac{103-4\sqrt{19}}{45}.$$
إذن على الفرع المرتب يتحقق \(x_0\le y_0\) عندما
$$\frac{5}{3}<t\le h.$$
وعلى الفترة نفسها يتحقق أيضًا \(y_0\le z_0\)، ولهذا يكفي أن يقتصر البحث على المخروط
$$\frac{5}{3}v<u\le hv.$$
لنعرّف الشكلين الخطيين
$$a=5u-3v,\qquad b=3u-5v.$$
فتصبح الإحداثيات الخام
$$x_0=ab,$$
$$y_0=\frac{(3a-19b)(a-5b)}{4},$$
$$z_0=\frac{(5a-19b)(a-3b)}{4}.$$
هذه المتطابقات تفسّر لماذا لا يظهر إلا ثمانية عوامل صنف. الجزء الخاص بقوى \(2\) يساوي
$$g_2=4^{\min(\nu_2(a),\nu_2(b),3)},$$
ومن ثم \(g_2\in\{1,4,16,64\}\). وإذا تحقق \(19\mid a\) فإن الإحداثيات الخام الثلاثة كلها تقبل القسمة على \(19\). لذلك يكون العامل الكامل واحدًا من
$$g\in\{1,4,16,64\}\times\{1,19\}=\{1,4,16,19,64,76,304,1216\}.$$
يعتمد عامل الصنف فقط على المعلومات التالية:
$$a\bmod 16,\qquad b\bmod 16,\qquad a\bmod 19.$$
وهذا يكفي لأن الجزء \(2\)-أدي يحتاج فقط إلى تمييز قوى \(2\) في \(a\) و\(b\) حتى \(2^3\)، أما جزء \(19\) فلا يسأل إلا عمّا إذا كان \(a\equiv 0\pmod{19}\). وعند جمع الترديدين \(16\) و\(19\) نحصل على
$$16\cdot 19=304.$$
لذلك تقوم التطبيقات، لكل عامل صنف \(g\) ولكل باقٍ من \(v\bmod 304\)، بحساب البواقي المسموح بها لـ \(u\bmod 304\) مسبقًا. وهكذا تتجاوز الحلقة الرئيسية كل زوج معلمات لا يمكن لفئته الباقية أصلًا أن تنتج الفرع الأولي المطلوب.
مع الاستمرار في كتابة \(t=u/v\) نحصل على
$$z_0=v^2(32t^2-176t+240).$$
وعلى الفترة \(\frac{5}{3}<t\le h\) يصل هذا العامل التربيعي إلى قيمته الدنيا عند الطرف الأيمن، ولذلك
$$z_0\ge c_{\min}v^2,\qquad c_{\min}=32h^2-176h+240.$$
وبما أن الثلاثية المقبولة تحقق \(z=z_0/g\le N\)، فإن كل صنف يحقق القيد
$$v\le \sqrt{\frac{Ng}{c_{\min}}}.$$
وهذا هو السبب في أن حدود الحلقة الخارجية تظهر بمقياس الجذر التربيعي.
خذ \((u,v)=(13,7)\). عندئذ
$$\frac{u}{v}=\frac{13}{7}\approx 1.857,$$
وهو يقع داخل المجال \(\frac{5}{3}<u/v\le h\). ثم نحسب
$$a=5u-3v=44,\qquad b=3u-5v=4.$$
كل من \(a\) و\(b\) قابل للقسمة على \(4\)، لكن ليس كلاهما قابلًا للقسمة على \(8\)، ومن ثم \(g_2=16\). وبما أن \(19\nmid 44\) فلا يوجد عامل إضافي \(19\)، وبالتالي \(g=16\).
الصيغ الخام تعطي
$$x_0=176,\qquad y_0=336,\qquad z_0=1152,$$
وبعد القسمة على \(16\) نحصل على
$$ (x,y,z)=\left(11,21,72\right). $$
هذه الثلاثية أولية ومرتبة وتحقق
$$15(11^2+21^2+72^2)=34(11\cdot21+21\cdot72+72\cdot11).$$
ولذلك تكون مساهمتها في المجموع
$$11+21+72=104.$$
تتبع تطبيقات C++ وPython وJava جميعها المسار نفسه. أولًا تُحسب مسبقًا، لكل عامل صنف ولكل باقٍ من \(v\bmod 304\)، البواقي المسموح بها لـ \(u\bmod 304\). ثم تُستخرج حدود عليا خاصة بكل صنف للقيمة \(v\) من المتباينة \(z\le N\). وبعد ذلك، ولكل \(v\)، لا يُفحص إلا القيم الصحيحة لـ \(u\) داخل المخروط \(\frac{5}{3}v<u\le hv\) والتي تنتمي إلى أحد البواقي المسموح بها. ثم تُطبَّق ثلاثة مرشحات نهائية: \(\gcd(u,v)=1\)، والقيد \(z_0\le Ng\)، ثم القسمة على عامل الصنف \(g\). وكل مرشح ينجو منه المرشح يضيف
$$\frac{x_0+y_0+z_0}{g}$$
إلى المجموع الجاري. وفي حال كان \(N\) كبيرًا يمكن لتطبيقي C++ وJava توزيع مجال \(v\) على عدة خيوط، بينما ينفذ تطبيق Python الحساب نفسه بصورة تسلسلية.
مرحلة بناء جدول البواقي ذات حجم ثابت، لأنها تملأ جداول لعدد \(8\) أصناف و\(304\) بواقي فقط. ولصنف ثابت يصل المتغير الخارجي \(v\) إلى \(O(\sqrt{N})\)، بينما يكون العرض الخام للمخروط في اتجاه \(u\) من رتبة \(O(v)\). لذلك فإن مساحة منطقة البحث غير المفلترة هي \(O(N)\). ويزيل جدول البواقي معظم المرشحين قبل أي فحص للقاسم المشترك الأكبر أو للحدود، ولهذا يكون الثابت العملي أصغر بكثير من المسح المباشر للمخروط كله. واستهلاك الذاكرة هو \(O(1)\) باستثناء جداول البواقي الصغيرة، وفي النسخ المتوازية يوجد مجمّع واحد لكل عامل تنفيذ.