For each positive integer \(N\), the problem considers the circle through \((0,0)\), \((N,0)\), \((0,N)\), and \((N,N)\), and defines \(f(N)\) as the number of lattice points on that circle. The goal is to compute
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
A direct scan up to \(10^{11}\) is impossible. The successful route is to convert the geometry into a sum-of-two-squares counting problem, extract an exact multiplicative formula for \(f(N)\), and then classify all admissible prime-exponent patterns.
The central observation is that the original circle can be rewritten so that its lattice points are counted by representations of \(N^2\) as a sum of two squares.
The circle through the four corners of the \(N\times N\) square has center \((N/2,N/2)\) and radius \(N/\sqrt2\), so its equation is
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
Introduce the linear change of variables
$$a=x+y-N,\qquad b=x-y.$$
Substituting and simplifying gives
$$a^2+b^2=N^2.$$
This transformation is bijective on lattice points: from \(a\) and \(b\) we recover
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
and the parity condition is automatically satisfied whenever \(a^2+b^2=N^2\). Therefore \(f(N)\) is exactly the number of integer pairs \((a,b)\) satisfying that equation. In standard notation,
$$f(N)=r_2(N^2),$$
where \(r_2(m)\) counts representations of \(m\) as a sum of two squares with order and sign included.
Write the factorization of \(N\) as
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
where every \(p_i\equiv 1\pmod 4\) and every \(q_j\equiv 3\pmod 4\). Then
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
The sum-of-two-squares theorem implies that primes \(q_j\equiv 3\pmod 4\) do not affect the count here, because they appear with even exponents in \(N^2\). Only the \(1\bmod 4\) primes contribute, and the count becomes
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
This is the exact arithmetic object computed by the implementations, and it is also why the geometry can be cross-checked by factoring \(N\) instead of drawing the circle.
The target condition is
$$4\prod_i(2e_i+1)=420,$$
so we must solve
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
Each factor \(2e_i+1\) is an odd integer at least \(3\). That leaves only five possible exponent patterns:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
So any valid \(N\) must have its \(1\bmod4\) prime exponents equal to one permutation of
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$$
Separate every valid \(N\) into
$$N=c\cdot m.$$
The core \(c\) contains all primes \(p\equiv1\pmod4\) with one of the admissible exponent patterns above. The multiplier \(m\) contains only the prime \(2\) and primes \(q\equiv3\pmod4\). This decomposition is unique because the two prime families are disjoint.
The crucial invariance is that
$$f(c\,m)=f(c)$$
whenever every prime factor of \(m\) is \(2\) or \(3\bmod4\). So once a core is fixed, all allowed multipliers below the remaining limit generate further valid values of \(N\).
If \(\mathcal M(X)\) denotes the set of allowed multipliers not exceeding \(X\), then
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
then the required sum is
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
where \(\mathcal C\) is the set of distinct core numbers generated from the five exponent patterns.
Consider
$$N=5^3\cdot13^2\cdot17=359125.$$
All three primes are \(1\bmod4\), and their exponents are \(3\), \(2\), and \(1\). Therefore
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
Now multiply by \(2^4\cdot3\cdot7\). The new number
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17$$
has the same exponents on its \(1\bmod4\) primes, so it still satisfies \(f(N')=420\). This is exactly the “core plus neutral multiplier” structure exploited by the algorithm.
The C++, Python, and Java implementations first sieve the primes \(p\equiv1\pmod4\) up to a safe bound, then generate every core number compatible with the five exponent patterns. Exponents are assigned to strictly increasing \(1\bmod4\) primes so that each factorization is produced once. If a partial product already exceeds the limit, or even the smallest possible completion would exceed the limit, that branch is pruned immediately.
Once the smallest core is known, the maximum useful multiplier is \(\lfloor 10^{11}/c_{\min}\rfloor\). The implementation builds a smallest-prime-factor table up to that bound and marks exactly those integers whose prime divisors are all \(2\) or \(3\bmod4\). A prefix array then stores \(A(X)\), the sum of all allowed multipliers up to \(X\), for every relevant \(X\).
For each core \(c\), the algorithm computes \(X=\lfloor 10^{11}/c\rfloor\) and adds \(c\cdot A(X)\). That single lookup accounts for every valid number of the form \(c\,m\) without iterating over all such multiples individually. The C++ and Java implementations split this final sweep across several worker threads, while the Python implementation performs the same summation either serially or with process-level parallel work.
The C++ implementation also includes three consistency checks: it verifies the sample value \(f(10000)=36\), compares the arithmetic formula against direct geometric counting for small \(N\), and confirms that the fast summation matches a brute-force summation on a smaller limit.
Let \(C\) be the number of distinct core numbers and let \(M=\lfloor 10^{11}/c_{\min}\rfloor\), where \(c_{\min}=5^3\cdot13^2\cdot17\) is the smallest valid core. Core generation is very small compared with the original search space, because only five exponent patterns exist and the recursive search is heavily pruned by monotonic growth of prime powers.
The sieve, validity table, and prefix sums over multipliers cost \(O(M)\) time and \(O(M)\) memory. The final accumulation over cores costs \(O(C)\). The method therefore replaces an impossible \(O(10^{11})\) search with a modest prime sieve, a compact enumeration of core numbers, and a linear preprocessing pass over the multiplier range.
Für jede positive ganze Zahl \(N\) betrachtet die Aufgabe den Kreis durch \((0,0)\), \((N,0)\), \((0,N)\) und \((N,N)\). Mit \(f(N)\) wird die Anzahl der Gitterpunkte auf diesem Kreis bezeichnet. Gesucht ist
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
Ein direktes Durchsuchen aller \(N\le 10^{11}\) ist ausgeschlossen. Der Lösungsweg besteht darin, die Geometrie auf ein Problem über Summen zweier Quadrate zurückzuführen, daraus eine exakte multiplikative Formel für \(f(N)\) zu gewinnen und anschließend alle zulässigen Primexponenten-Muster zu klassifizieren.
Der entscheidende Schritt ist, den ursprünglichen Kreis so umzuschreiben, dass seine Gitterpunkte durch Darstellungen von \(N^2\) als Summe zweier Quadrate gezählt werden.
Der Kreis durch die vier Ecken des \(N\times N\)-Quadrats hat das Zentrum \((N/2,N/2)\) und den Radius \(N/\sqrt2\). Seine Gleichung lautet also
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
Mit der linearen Substitution
$$a=x+y-N,\qquad b=x-y$$
wird daraus
$$a^2+b^2=N^2.$$
Diese Transformation ist auf Gitterpunkten bijektiv, denn aus \(a\) und \(b\) erhält man
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
und die Parität stimmt automatisch, sobald \(a^2+b^2=N^2\) gilt. Also ist \(f(N)\) genau die Anzahl ganzzahliger Paare \((a,b)\), die diese Gleichung erfüllen. In Standardnotation heißt das
$$f(N)=r_2(N^2).$$
Schreibe
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
wobei \(p_i\equiv 1\pmod 4\) und \(q_j\equiv 3\pmod 4\). Dann gilt
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
Nach dem Satz über Summen zweier Quadrate spielen die \(q_j\equiv 3\pmod4\) hier keine Rolle, weil sie in \(N^2\) nur mit geraden Exponenten auftreten. Relevant sind allein die Primzahlen \(1\bmod4\), und damit folgt
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
Genau diese Formel wird von den Implementierungen benutzt und für kleine Werte zusätzlich mit direktem geometrischem Zählen abgeglichen.
Gesucht sind also genau die \(N\), für die
$$4\prod_i(2e_i+1)=420$$
gilt, also äquivalent
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
Jeder Faktor \(2e_i+1\) ist eine ungerade Zahl mindestens \(3\). Deshalb bleiben nur fünf Exponentenmuster übrig:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
Damit müssen die Exponenten der Primzahlen \(1\bmod4\) in jedem gültigen \(N\) eine Permutation von
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1]$$
sein.
Jedes gültige \(N\) lässt sich eindeutig als
$$N=c\cdot m$$
schreiben. Der Kern \(c\) enthält alle Primzahlen \(p\equiv1\pmod4\) mit einem der zulässigen Exponentenmuster. Der Faktor \(m\) enthält nur die Primzahl \(2\) und Primzahlen \(q\equiv3\pmod4\).
Der entscheidende Invarianzsatz ist
$$f(c\,m)=f(c),$$
solange alle Primfaktoren von \(m\) gleich \(2\) oder \(3\bmod4\) sind. Ist also ein Kern \(c\) fest, dann liefert jeder zulässige Multiplikator \(m\le 10^{11}/c\) eine weitere gültige Zahl.
Bezeichnet \(\mathcal M(X)\) die Menge aller zulässigen Multiplikatoren bis \(X\), dann
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
dann wird die gesuchte Summe zu
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
wobei \(\mathcal C\) die Menge aller verschiedenen Kernzahlen ist.
Betrachte
$$N=5^3\cdot13^2\cdot17=359125.$$
Alle drei Primzahlen sind \(1\bmod4\), mit Exponenten \(3\), \(2\) und \(1\). Daher gilt
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
Multipliziert man zusätzlich mit \(2^4\cdot3\cdot7\), erhält man
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17.$$
Die Exponenten der \(1\bmod4\)-Primzahlen bleiben unverändert, also bleibt auch \(f(N')=420\). Genau diese Struktur aus Kern plus neutralem Multiplikator nutzt der Algorithmus aus.
Die C++-, Python- und Java-Implementierungen sieben zuerst die Primzahlen \(p\equiv1\pmod4\) bis zu einer sicheren Obergrenze und erzeugen dann alle Kernzahlen, die mit den fünf Exponentenmuster vereinbar sind. Die Exponenten werden streng wachsenden Primzahlen \(1\bmod4\) zugeordnet, damit jede Faktorisierung genau einmal erscheint. Überschreitet ein Teilprodukt bereits das Limit oder würde selbst die kleinste mögliche Fortsetzung das Limit sprengen, wird der entsprechende Suchzweig sofort abgeschnitten.
Sobald die kleinste Kernzahl bekannt ist, steht auch die größte relevante Schranke für Multiplikatoren fest. Bis dorthin baut die Implementierung eine Tabelle kleinster Primfaktoren auf und markiert genau diejenigen Zahlen, deren Primteiler ausschließlich \(2\) oder \(3\bmod4\) sind. Eine Präfixsumme speichert anschließend \(A(X)\), also die Summe aller zulässigen Multiplikatoren bis \(X\).
Für jede Kernzahl \(c\) wird \(X=\lfloor 10^{11}/c\rfloor\) bestimmt und dann \(c\cdot A(X)\) addiert. Damit werden sofort alle gültigen Zahlen der Form \(c\,m\) berücksichtigt, ohne sie einzeln durchlaufen zu müssen. Die C++- und Java-Implementierungen verteilen diese Endschleife auf mehrere Threads; die Python-Implementierung verwendet dieselbe Formel seriell oder mit Prozess-Parallelität.
Die C++-Implementierung enthält zusätzlich drei Plausibilitätsprüfungen: den bekannten Wert \(f(10000)=36\), einen Vergleich von Geometrie und Formel für kleine \(N\) sowie einen Abgleich der schnellen Summe mit einer Brute-Force-Summe auf kleinerem Suchraum.
Sei \(C\) die Anzahl verschiedener Kernzahlen und \(M=\lfloor 10^{11}/c_{\min}\rfloor\), wobei \(c_{\min}=5^3\cdot13^2\cdot17\) die kleinste gültige Kernzahl ist. Die Kernerzeugung ist im Vergleich zum ursprünglichen Suchraum winzig, weil nur fünf Exponentenmuster existieren und die rekursive Suche durch Monotonie der Primpotenzen stark beschnitten wird.
Das Sieb, die Gültigkeitstabelle und die Präfixsummen über die Multiplikatoren kosten \(O(M)\) Zeit und \(O(M)\) Speicher. Die Endakkumulation über alle Kerne kostet \(O(C)\). Damit ersetzt das Verfahren eine unmögliche \(O(10^{11})\)-Suche durch eine kleine strukturierte Enumeration und einen linearen Vorverarbeitungsschritt.
Her pozitif tam sayı \(N\) için problem, \((0,0)\), \((N,0)\), \((0,N)\) ve \((N,N)\) noktalarından geçen çemberi tanımlar ve bu çember üzerindeki kafes noktalarının sayısını \(f(N)\) ile gösterir. Hesaplanması istenen toplam
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N$$
şeklindedir. \(N\)'yi tek tek \(10^{11}\)'e kadar denemek mümkün değildir. Başarılı çözüm, geometrik tanımı iki karenin toplamı problemine dönüştürür, ardından \(f(N)\) için tam bir çarpımsal formül çıkarır ve geçerli üs desenlerini sınıflandırır.
Asıl fikir, çember üzerindeki kafes noktalarını \(N^2\)'nin iki karenin toplamı olarak yazılış sayısına bağlamaktır.
\(N\times N\) karesinin dört köşesinden geçen çemberin merkezi \((N/2,N/2)\), yarıçapı ise \(N/\sqrt2\)'dir. Bu yüzden denklemi
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}$$
olur. Şimdi
$$a=x+y-N,\qquad b=x-y$$
dönüşümünü yapalım. Denklem doğrudan
$$a^2+b^2=N^2$$
biçimine iner. Bu dönüşüm kafes noktaları üzerinde bire birdir; çünkü ters dönüşüm
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2}$$
şeklindedir ve \(a^2+b^2=N^2\) olduğunda gerekli parite koşulu otomatik sağlanır. Dolayısıyla \(f(N)\), bu denklemi sağlayan tamsayı \((a,b)\) çiftlerinin tam sayısıdır. Standart gösterimle
$$f(N)=r_2(N^2)$$
elde edilir.
\(N\)'yi
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j}$$
şeklinde yazalım; burada her \(p_i\equiv1\pmod4\), her \(q_j\equiv3\pmod4\) olsun. O zaman
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
İki karenin toplamı teoremine göre \(q_j\equiv3\pmod4\) asallar burada sayıyı etkilemez; çünkü \(N^2\) içinde hepsi çift üs ile görünür. Sayımı belirleyen tek şey \(1\bmod4\) asallarıdır ve sonuç
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1)$$
olur. Kodun kullandığı temel formül tam olarak budur.
Hedef koşul
$$4\prod_i(2e_i+1)=420$$
olduğundan eşdeğer denklem
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7$$
şeklindedir. Her \(2e_i+1\) çarpanı en az \(3\) olan tek bir sayıdır. Bu da yalnızca şu beş üs desenini bırakır:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
Yani geçerli bir \(N\)'de, \(1\bmod4\) asallarının üsleri mutlaka
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1]$$
listelerinden birinin permütasyonu olmalıdır.
Her geçerli \(N\) sayısını
$$N=c\cdot m$$
şeklinde ayırmak mümkündür. Burada çekirdek \(c\), tüm \(p\equiv1\pmod4\) asallarını ve yukarıdaki uygun üs desenlerinden birini taşır. \(m\) ise yalnızca \(2\) asalını ve \(q\equiv3\pmod4\) asallarını içerir. Bu ayrım tektir.
Kritik değişmezlik şudur:
$$f(c\,m)=f(c)$$
eğer \(m\)'nin bütün asal çarpanları \(2\) veya \(3\bmod4\) ise. Bu nedenle bir çekirdek \(c\) sabitlenince, \(m\le 10^{11}/c\) olan bütün uygun çarpanlar yeni geçerli değerler üretir.
Eğer \(\mathcal M(X)\), \(X\)'i aşmayan uygun çarpanların kümesi ise
$$A(X)=\sum_{m\in\mathcal M(X)} m$$
diye tanımlarsak, aranan toplam
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right)$$
haline gelir. Burada \(\mathcal C\), bütün farklı çekirdek sayıların kümesidir.
Şu sayıyı alalım:
$$N=5^3\cdot13^2\cdot17=359125.$$
\(5\), \(13\) ve \(17\) asallarının hepsi \(1\bmod4\)'tür; üsleri de sırasıyla \(3\), \(2\) ve \(1\)'dir. O halde
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
Şimdi buna \(2^4\cdot3\cdot7\) ile çarpalım. Yeni sayı
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17$$
aynı \(1\bmod4\) üslerini koruduğu için yine \(f(N')=420\) olur. Algoritmanın çekirdekleri bir kez üretip bütün uygun çarpanları prefix toplamlarla eklemesinin sebebi tam olarak budur.
C++, Python ve Java uygulamaları önce \(p\equiv1\pmod4\) asallarını güvenli bir sınıra kadar eler, sonra beş üs deseninin her biri için mümkün olan tüm çekirdekleri üretir. Üsler artan \(1\bmod4\) asallara atanır; böylece her asal çarpanlaşma tek kez oluşur. Kısmi çarpım limitten büyükse ya da en küçük olası devam bile limiti aşacaksa o dal hemen budanır.
En küçük çekirdek belli olduktan sonra ihtiyaç duyulabilecek en büyük çarpan sınırı da belirlenmiş olur. Uygulama bu sınıra kadar en küçük asal çarpan tablosu kurar ve asal bölenlerinin tamamı yalnızca \(2\) veya \(3\bmod4\) olan sayıları işaretler. Ardından bir prefix dizi, her \(X\) için \(A(X)\) değerini saklar.
Her çekirdek \(c\) için \(X=\lfloor 10^{11}/c\rfloor\) hesaplanır ve \(c\cdot A(X)\) sonuca eklenir. Böylece \(c\,m\) biçimindeki bütün geçerli sayılar tek tek dolaşılmadan hesaba katılmış olur. C++ ve Java uygulamaları bu son taramayı birden çok iş parçacığına böler; Python uygulaması aynı toplamı seri olarak ya da süreç tabanlı paralellik ile hesaplar.
C++ uygulaması ayrıca üç sağlamlık kontrolü içerir: \(f(10000)=36\) örnek değeri, küçük \(N\)'lerde geometri ile formülün karşılaştırılması ve hızlı toplamın küçük bir limitte brute-force toplamla eşleşmesi.
\(C\) farklı çekirdek sayısı, \(M\) ise \(c_{\min}=5^3\cdot13^2\cdot17\) olmak üzere \(\lfloor 10^{11}/c_{\min}\rfloor\) olsun. Çekirdek üretimi, asıl arama uzayına göre çok küçüktür; çünkü yalnızca beş üs deseni vardır ve asal kuvvetleri büyüdükçe arama kuvvetli biçimde budanır.
Çarpanlar için kurulan asal çarpan tablosu, geçerlilik tablosu ve prefix toplamlar \(O(M)\) zaman ve \(O(M)\) bellek kullanır. Çekirdekler üzerindeki son toplama ise \(O(C)\) sürer. Böylece yöntem, imkansız bir \(O(10^{11})\) taramasını küçük bir yapılandırılmış üretim ve doğrusal bir ön işlem adımıyla değiştirir.
Para cada entero positivo \(N\), el problema considera la circunferencia que pasa por \((0,0)\), \((N,0)\), \((0,N)\) y \((N,N)\), y define \(f(N)\) como el número de puntos de la retícula sobre esa circunferencia. Hay que calcular
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
Recorrer todos los \(N\le 10^{11}\) es inviable. La solución consiste en transformar la geometría en un problema de suma de dos cuadrados, obtener una fórmula multiplicativa exacta para \(f(N)\) y clasificar los patrones posibles de exponentes primos.
La observación clave es que los puntos de la circunferencia se pueden contar a través de las representaciones de \(N^2\) como suma de dos cuadrados.
La circunferencia que pasa por las cuatro esquinas del cuadrado \(N\times N\) tiene centro \((N/2,N/2)\) y radio \(N/\sqrt2\). Por tanto, su ecuación es
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
Introducimos el cambio lineal
$$a=x+y-N,\qquad b=x-y.$$
Entonces la ecuación se convierte en
$$a^2+b^2=N^2.$$
La transformación es biyectiva sobre los puntos de la retícula, porque
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
y la paridad necesaria se satisface automáticamente cuando \(a^2+b^2=N^2\). Así, \(f(N)\) es exactamente el número de pares enteros \((a,b)\) que resuelven esa ecuación. En notación estándar,
$$f(N)=r_2(N^2).$$
Escribamos
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
donde \(p_i\equiv1\pmod4\) y \(q_j\equiv3\pmod4\). Entonces
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
El teorema de la suma de dos cuadrados implica que los primos \(q_j\equiv3\pmod4\) no aportan ningún factor aquí, porque en \(N^2\) aparecen con exponente par. Solo importan los primos \(1\bmod4\), y por eso
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
Esta es la cantidad aritmética real que calculan las implementaciones.
Debemos imponer
$$4\prod_i(2e_i+1)=420,$$
es decir,
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
Cada factor \(2e_i+1\) es impar y al menos igual a \(3\). Eso deja solo cinco patrones posibles:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
Por tanto, los exponentes de los primos \(1\bmod4\) en cualquier \(N\) válido deben ser una permutación de
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$$
Todo \(N\) válido se descompone de forma única como
$$N=c\cdot m.$$
El núcleo \(c\) contiene todos los primos \(p\equiv1\pmod4\) con uno de los patrones válidos de exponentes. El multiplicador \(m\) contiene solo el primo \(2\) y primos \(q\equiv3\pmod4\).
La invariancia fundamental es
$$f(c\,m)=f(c),$$
si todos los factores primos de \(m\) son \(2\) o \(3\bmod4\). Así, fijado un núcleo \(c\), cualquier multiplicador permitido con \(m\le 10^{11}/c\) produce otro valor válido.
Si \(\mathcal M(X)\) denota el conjunto de multiplicadores permitidos no mayores que \(X\), entonces
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
entonces la suma buscada es
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
donde \(\mathcal C\) es el conjunto de todos los núcleos distintos.
Tomemos
$$N=5^3\cdot13^2\cdot17=359125.$$
Los tres primos son \(1\bmod4\), con exponentes \(3\), \(2\) y \(1\). Entonces
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
Si además multiplicamos por \(2^4\cdot3\cdot7\), obtenemos
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17,$$
y \(f(N')\) no cambia, porque los exponentes sobre los primos \(1\bmod4\) siguen siendo exactamente los mismos. Esa es la razón por la que el algoritmo enumera los núcleos una sola vez y luego incorpora todos los multiplicadores permitidos mediante sumas prefijas.
Las implementaciones en C++, Python y Java criban primero los primos \(p\equiv1\pmod4\) hasta una cota segura y después generan todos los núcleos compatibles con los cinco patrones de exponentes. Los exponentes se asignan a primos \(1\bmod4\) estrictamente crecientes para no repetir factorizaciones. Cuando un producto parcial ya supera el límite, o incluso la finalización más pequeña posible lo superaría, esa rama se poda al instante.
Una vez conocido el núcleo mínimo, queda fijado el multiplicador máximo relevante. Hasta ese valor, la implementación construye una tabla de menor factor primo y marca exactamente los enteros cuyos divisores primos son todos \(2\) o \(3\bmod4\). Luego una tabla de prefijos almacena \(A(X)\), la suma de todos los multiplicadores permitidos hasta \(X\).
Para cada núcleo \(c\), el algoritmo calcula \(X=\lfloor 10^{11}/c\rfloor\) y añade \(c\cdot A(X)\). Con un solo acceso quedan contabilizados todos los números válidos de la forma \(c\,m\). Las versiones en C++ y Java reparten este último barrido entre varios hilos, mientras que la versión en Python aplica la misma fórmula en serie o con paralelismo por procesos.
La implementación de C++ también realiza tres verificaciones: comprueba el valor de muestra \(f(10000)=36\), compara la fórmula aritmética con el conteo geométrico directo para \(N\) pequeños y valida la suma rápida frente a una suma por fuerza bruta en un límite menor.
Sea \(C\) el número de núcleos distintos y \(M=\lfloor 10^{11}/c_{\min}\rfloor\), donde \(c_{\min}=5^3\cdot13^2\cdot17\) es el menor núcleo válido. La enumeración de núcleos es muy pequeña frente al espacio de búsqueda original, porque solo existen cinco patrones y el crecimiento monótono de las potencias primas permite podar con mucha eficacia.
La criba, la tabla de validez y las sumas prefijas sobre multiplicadores cuestan \(O(M)\) tiempo y \(O(M)\) memoria. La acumulación final sobre los núcleos cuesta \(O(C)\). En conjunto, el método reemplaza una exploración imposible de tamaño \(10^{11}\) por una enumeración estructurada muy compacta y un único preprocesamiento lineal.
对每个正整数 \(N\)，题目考虑经过 \((0,0)\)、\((N,0)\)、\((0,N)\)、\((N,N)\) 的圆，并把该圆上的整点个数记为 \(f(N)\)。目标是计算
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
显然不能把所有 \(N\le 10^{11}\) 都直接枚举一遍。真正可行的办法，是先把几何问题化成“\(N^2\) 能表示为两个平方和多少次”的算术问题，再从素因子分解中直接读出 \(f(N)\) 的值，最后只枚举满足 \(f(N)=420\) 的那几类指数结构。
整道题的核心，是把原来的圆转换成一个标准的平方和方程，然后利用它的乘法性结构。
经过正方形四个顶点的圆，圆心是 \((N/2,N/2)\)，半径是 \(N/\sqrt2\)，所以圆方程为
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
作线性代换
$$a=x+y-N,\qquad b=x-y.$$
代入后恰好得到
$$a^2+b^2=N^2.$$
这个变换对整点是双射，因为反解为
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
而当 \(a^2+b^2=N^2\) 时，所需的奇偶性条件会自动满足。因此，原题中的 \(f(N)\) 实际上就是整数解 \((a,b)\) 的个数。用标准记号表示，就是
$$f(N)=r_2(N^2),$$
其中 \(r_2(m)\) 表示把 \(m\) 写成两个平方和时，连同顺序和符号一起计数的表示数。
把 \(N\) 写成
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
其中所有 \(p_i\equiv1\pmod4\)，所有 \(q_j\equiv3\pmod4\)。于是
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
两个平方和定理告诉我们：在这里，\(q_j\equiv3\pmod4\) 的素数不会给表示数带来额外因子，因为它们在 \(N^2\) 中全部以偶次幂出现。真正起作用的只有 \(1\bmod4\) 的素数，因此有
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
这正是三份实现代码共同使用的核心公式，也是它们能够用分解而不是直接作几何计数的原因。
现在要求
$$4\prod_i(2e_i+1)=420,$$
也就是
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
每个因子 \(2e_i+1\) 都是不小于 \(3\) 的奇数，所以可能性非常有限。逐一拆分 \(105\) 后，只剩下五种指数模式：
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
因此，任何满足条件的 \(N\)，其所有 \(1\bmod4\) 素数的指数，必定是下面某个列表的一个排列：
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$$
每个合法的 \(N\) 都可以唯一地写成
$$N=c\cdot m.$$
这里的核心数 \(c\) 收集了全部 \(p\equiv1\pmod4\) 的素数，并给它们赋予上述五种模式之一的指数；而 \(m\) 只允许包含素数 \(2\) 以及所有 \(q\equiv3\pmod4\) 的素数。
关键不变量是
$$f(c\,m)=f(c),$$
只要 \(m\) 的所有素因子都来自 \(2\) 或 \(3\bmod4\) 这一类。换句话说，一旦核心数 \(c\) 固定，所有满足 \(m\le 10^{11}/c\) 的合法乘子都会给出新的可行 \(N\)。
如果把不超过 \(X\) 的全部合法乘子组成的集合记为 \(\mathcal M(X)\)，那么
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
那么原题就化成
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
其中 \(\mathcal C\) 是全部不同核心数的集合。
考虑
$$N=5^3\cdot13^2\cdot17=359125.$$
\(5\)、\(13\)、\(17\) 都是 \(1\bmod4\) 素数，其指数分别为 \(3\)、\(2\)、\(1\)。因此
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
如果再乘上 \(2^4\cdot3\cdot7\)，得到
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17,$$
由于 \(1\bmod4\) 素数部分的指数完全没有变化，所以 \(f(N')\) 仍然等于 \(420\)。这就是算法为什么只枚举核心数，然后用前缀和一次性吸收所有合法乘子的根本原因。
C++、Python 和 Java 实现都会先筛出足够范围内所有 \(p\equiv1\pmod4\) 的素数，再根据那五种指数模式生成全部可能的核心数。指数总是分配给严格递增的 \(1\bmod4\) 素数，因此不会重复产生同一个素因子分解。如果当前部分乘积已经超过上界，或者即便接上最小可能的后续部分也会超界，那么这一分支就立刻剪掉。
核心数枚举完成后，最小核心数决定了真正需要考虑的最大乘子范围。实现会在这个范围内建立最小素因子表，并据此标记出所有素因子都只来自 \(2\) 或 \(3\bmod4\) 的整数。接着再做一遍前缀累加，得到每个 \(X\) 对应的 \(A(X)\)。
对于每个核心数 \(c\)，算法只需计算 \(X=\lfloor 10^{11}/c\rfloor\)，再把 \(c\cdot A(X)\) 加入答案。这样就一次性统计了所有形如 \(c\,m\) 的合法数，而不需要逐个枚举这些乘积。C++ 与 Java 实现把这一步分配到多个工作线程上；Python 实现则使用同一条公式串行求和，或者通过进程并行处理。
C++ 实现还做了三类校验：验证样例值 \(f(10000)=36\)，对小 \(N\) 比较几何直接计数与算术公式，以及在较小上界下把快速求和与暴力求和进行对照。
设不同核心数的个数为 \(C\)，并令 \(M=\lfloor 10^{11}/c_{\min}\rfloor\)，其中 \(c_{\min}=5^3\cdot13^2\cdot17\) 是最小的合法核心数。核心数枚举相对原问题的搜索空间极小，因为只有五种指数模式，而且素数幂单调增大，使得剪枝非常有效。
乘子部分的最小素因子表、合法性标记和前缀和都需要 \(O(M)\) 时间与 \(O(M)\) 内存。最后对全部核心数做累加需要 \(O(C)\) 时间。也就是说，这个方法把一个不可能的 \(O(10^{11})\) 枚举，替换成了一个很小的结构化生成过程和一次线性预处理。
Для каждого положительного целого \(N\) задача рассматривает окружность, проходящую через точки \((0,0)\), \((N,0)\), \((0,N)\) и \((N,N)\), и обозначает через \(f(N)\) число узловых точек на этой окружности. Требуется вычислить
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
Перебирать все \(N\le 10^{11}\) напрямую нельзя. Рабочее решение сводит геометрию к задаче о представлении числа в виде суммы двух квадратов, получает точную мультипликативную формулу для \(f(N)\), а затем перечисляет только те шаблоны показателей, которые действительно могут дать значение \(420\).
Ключевая идея состоит в том, чтобы заменить исходную геометрию стандартным арифметическим объектом: числом представлений \(N^2\) в виде суммы двух квадратов.
Окружность через четыре вершины квадрата \(N\times N\) имеет центр \((N/2,N/2)\) и радиус \(N/\sqrt2\), поэтому ее уравнение равно
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
Введем линейную замену
$$a=x+y-N,\qquad b=x-y.$$
Тогда уравнение превращается в
$$a^2+b^2=N^2.$$
Это биекция на целочисленных точках, потому что обратное преобразование имеет вид
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
а нужная четность автоматически выполняется, если \(a^2+b^2=N^2\). Следовательно, \(f(N)\) есть в точности число целых пар \((a,b)\), удовлетворяющих этому уравнению. В стандартном обозначении
$$f(N)=r_2(N^2).$$
Пусть
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
где \(p_i\equiv1\pmod4\), а \(q_j\equiv3\pmod4\). Тогда
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
Теорема о сумме двух квадратов говорит, что простые \(q_j\equiv3\pmod4\) в этой задаче не дают дополнительных множителей, потому что в \(N^2\) они стоят только в четных степенях. Поэтому счет определяется лишь простыми \(1\bmod4\), и получается формула
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
Именно эта формула используется во всех трех реализациях.
Нужно решить уравнение
$$4\prod_i(2e_i+1)=420,$$
то есть
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
Каждый множитель \(2e_i+1\) нечетен и не меньше \(3\). Поэтому остаются только пять вариантов:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
Значит, показатели простых \(1\bmod4\) в любом подходящем \(N\) должны образовывать одну из перестановок списка
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$$
Каждое подходящее \(N\) единственным образом раскладывается в виде
$$N=c\cdot m.$$
Здесь ядро \(c\) содержит все простые \(p\equiv1\pmod4\) с одним из допустимых шаблонов показателей, а множитель \(m\) состоит только из простого \(2\) и простых \(q\equiv3\pmod4\).
Главный инвариант состоит в том, что
$$f(c\,m)=f(c),$$
если все простые делители \(m\) принадлежат классам \(2\) или \(3\bmod4\). Поэтому после выбора ядра \(c\) любой допустимый множитель \(m\le 10^{11}/c\) дает еще одно корректное значение.
Если обозначить через \(\mathcal M(X)\) множество всех допустимых множителей, не превосходящих \(X\), то
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
то искомая сумма принимает вид
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
где \(\mathcal C\) — множество всех различных ядер.
Рассмотрим число
$$N=5^3\cdot13^2\cdot17=359125.$$
Все три простых числа равны \(1\bmod4\), а их показатели равны \(3\), \(2\) и \(1\). Следовательно,
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
Если теперь домножить на \(2^4\cdot3\cdot7\), получится
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17,$$
и значение \(f(N')\) останется тем же, потому что показатели при простых \(1\bmod4\) не изменились. Именно поэтому алгоритм сначала перечисляет ядра, а затем добавляет все допустимые множители с помощью префиксных сумм.
Реализации на C++, Python и Java сначала просеивают простые \(p\equiv1\pmod4\) до безопасной границы, а затем строят все ядра, совместимые с пятью шаблонами показателей. Показатели назначаются строго возрастающим простым \(1\bmod4\), чтобы каждое разложение возникало ровно один раз. Если частичное произведение уже превысило предел или даже минимальное возможное продолжение его превысит, соответствующая ветвь немедленно отсекается.
После нахождения минимального ядра сразу известна максимальная величина множителя, которая вообще может понадобиться. До этой границы строится таблица наименьших простых делителей, по которой отмечаются все числа, состоящие только из простого \(2\) и простых \(3\bmod4\). Затем один проход формирует префиксный массив для значений \(A(X)\).
Для каждого ядра \(c\) алгоритм вычисляет \(X=\lfloor 10^{11}/c\rfloor\) и прибавляет \(c\cdot A(X)\). Одним таким действием учитываются сразу все числа вида \(c\,m\). Реализации на C++ и Java распараллеливают этот последний проход по списку ядер; реализация на Python использует ту же формулу последовательно или с параллельной обработкой по процессам.
Реализация на C++ дополнительно выполняет три проверки корректности: подтверждает образец \(f(10000)=36\), сравнивает арифметическую формулу с прямым геометрическим подсчетом для малых \(N\) и сверяет быстрый метод суммирования с лобовым методом на меньшем ограничении.
Пусть \(C\) — число различных ядер, а \(M=\lfloor 10^{11}/c_{\min}\rfloor\), где \(c_{\min}=5^3\cdot13^2\cdot17\) — минимальное допустимое ядро. Перечисление ядер очень мало по сравнению с исходным пространством поиска: шаблонов всего пять, а монотонный рост степеней простых позволяет эффективно отсекать бесперспективные ветви.
Построение решета, таблицы допустимости и префиксных сумм по множителям требует \(O(M)\) времени и \(O(M)\) памяти. Финальное суммирование по ядрам занимает \(O(C)\). Тем самым невозможный перебор масштаба \(10^{11}\) заменяется компактной структурированной генерацией и одной линейной фазой предварительной обработки.
لكل عدد صحيح موجب \(N\)، تنظر المسألة إلى الدائرة المارة بالنقاط \((0,0)\) و\((N,0)\) و\((0,N)\) و\((N,N)\)، وتعرّف \(f(N)\) بأنه عدد نقاط الشبكة الواقعة على تلك الدائرة. المطلوب هو حساب
$$S(10^{11})=\sum_{\substack{N\le 10^{11}\\f(N)=420}} N.$$
من المستحيل فحص جميع القيم حتى \(10^{11}\) مباشرة. الطريق الصحيح هو تحويل الوصف الهندسي إلى مسألة عددية عن تمثيلات \(N^2\) كمجموع مربعين، ثم استخراج صيغة ضربية دقيقة لـ \(f(N)\)، وبعد ذلك حصر جميع أنماط الأسس الأولية التي يمكن أن تعطي القيمة \(420\).
الفكرة الأساسية هي أن نقاط الشبكة على الدائرة الأصلية يمكن عدّها بعد تحويل بسيط إلى معادلة قياسية من نوع مجموع مربعين.
الدائرة المارة برؤوس المربع \(N\times N\) مركزها \((N/2,N/2)\) ونصف قطرها \(N/\sqrt2\)، ولذلك معادلتها
$$\left(x-\frac N2\right)^2+\left(y-\frac N2\right)^2=\frac{N^2}{2}.$$
نأخذ التحويل الخطي
$$a=x+y-N,\qquad b=x-y.$$
فتصبح المعادلة
$$a^2+b^2=N^2.$$
وهذا التحويل تبادلي على نقاط الشبكة، لأننا نسترجع
$$x=\frac{N+a+b}{2},\qquad y=\frac{N+a-b}{2},$$
كما أن شرط الزوجية المطلوب يتحقق تلقائيا عندما يكون \(a^2+b^2=N^2\). إذن \(f(N)\) هو بالضبط عدد الأزواج الصحيحة \((a,b)\) التي تحقق هذه المعادلة، أي
$$f(N)=r_2(N^2),$$
حيث \(r_2(m)\) يعد جميع تمثيلات \(m\) كمجموع مربعين مع احتساب الترتيب والإشارات.
لنكتب
$$N=2^\alpha\prod_i p_i^{e_i}\prod_j q_j^{f_j},$$
بحيث \(p_i\equiv1\pmod4\) و\(q_j\equiv3\pmod4\). عندئذ
$$N^2=2^{2\alpha}\prod_i p_i^{2e_i}\prod_j q_j^{2f_j}.$$
تعطي مبرهنة مجموع مربعين هنا تبسيطا مهما: الأوليات \(q_j\equiv3\pmod4\) لا تساهم في عدد التمثيلات لأن أسسها في \(N^2\) زوجية دائما. لذلك فإن العد يعتمد فقط على أوليات \(1\bmod4\)، ونحصل على
$$f(N)=r_2(N^2)=4\prod_i(2e_i+1).$$
وهذه هي الصيغة الحسابية الدقيقة التي تبني عليها جميع التطبيقات.
نحتاج إلى
$$4\prod_i(2e_i+1)=420,$$
أي بصورة مكافئة
$$\prod_i(2e_i+1)=105=3\cdot5\cdot7.$$
كل عامل من الصورة \(2e_i+1\) هو عدد فردي لا يقل عن \(3\)، ولذلك لا يبقى إلا خمس حالات ممكنة:
$$105 \Rightarrow e=52,$$
$$35\cdot3 \Rightarrow (e_1,e_2)=(17,1),$$
$$21\cdot5 \Rightarrow (e_1,e_2)=(10,2),$$
$$15\cdot7 \Rightarrow (e_1,e_2)=(7,3),$$
$$3\cdot5\cdot7 \Rightarrow (e_1,e_2,e_3)=(1,2,3).$$
إذن أسس الأوليات الموافقة لـ \(1\bmod4\) في أي \(N\) صالح يجب أن تكون ترتيبا لأحد الأنماط
$$[52],\ [17,1],\ [10,2],\ [7,3],\ [3,2,1].$$
يمكن كتابة كل \(N\) صالح على نحو وحيد بالشكل
$$N=c\cdot m.$$
الجزء الأساسي \(c\) يحتوي جميع الأوليات \(p\equiv1\pmod4\) مع أحد أنماط الأسس المسموح بها. أما \(m\) فيتكون فقط من الأولي \(2\) ومن الأوليات \(q\equiv3\pmod4\).
الثابت المهم هنا هو أن
$$f(c\,m)=f(c),$$
ما دامت جميع العوامل الأولية لـ \(m\) من النوع \(2\) أو \(3\bmod4\). لذلك، بعد تثبيت عدد أساسي \(c\)، فإن كل مضاعف مسموح \(m\le 10^{11}/c\) يولد قيمة جديدة صالحة.
إذا رمزنا بمجموعة جميع المضاعفات المسموح بها التي لا تتجاوز \(X\) إلى \(\mathcal M(X)\)، فإن
$$A(X)=\sum_{m\in\mathcal M(X)} m.$$
فإن المجموع المطلوب يصبح
$$S(10^{11})=\sum_{c\in\mathcal C} c\cdot A\!\left(\left\lfloor\frac{10^{11}}{c}\right\rfloor\right),$$
حيث \(\mathcal C\) هي مجموعة جميع الأعداد الأساسية المختلفة.
لنأخذ
$$N=5^3\cdot13^2\cdot17=359125.$$
الأوليات الثلاثة كلها من النوع \(1\bmod4\)، وأسها هي \(3\) و\(2\) و\(1\). ومن ثم
$$f(N)=4(2\cdot3+1)(2\cdot2+1)(2\cdot1+1)=4\cdot7\cdot5\cdot3=420.$$
إذا ضربنا بعد ذلك في \(2^4\cdot3\cdot7\)، نحصل على
$$N'=2^4\cdot3\cdot7\cdot5^3\cdot13^2\cdot17,$$
ولا تتغير قيمة \(f\)، لأن أسس أوليات \(1\bmod4\) لم تتغير. ولهذا السبب تعدّ الخوارزمية الأجزاء الأساسية أولا، ثم تدمج جميع المضاعفات المحايدة باستعمال المجاميع البادئة.
تبدأ تطبيقات C++ وPython وJava بغربلة الأوليات \(p\equiv1\pmod4\) حتى حد آمن، ثم تولد جميع الأعداد الأساسية الموافقة لأنماط الأسس الخمسة. وتسنَد الأسس إلى أوليات متزايدة من الفئة \(1\bmod4\) بحيث يظهر كل تحليل أولي مرة واحدة فقط. فإذا تجاوز حاصل الضرب الجزئي الحد، أو كان أصغر إكمال ممكن سيتجاوزه حتما، تُقصى تلك الشعبة فورا.
بعد معرفة أصغر عدد أساسي، يصبح الحد الأقصى لأي مضاعف مهم معروفا. عندئذ تبني الشيفرة جدولا لأصغر عامل أولي حتى ذلك الحد، وتعلّم كل عدد لا تحتوي عوامله الأولية إلا على \(2\) أو أوليات \(3\bmod4\). ثم تُبنى مصفوفة بادئة تخزن \(A(X)\) لكل قيمة مطلوبة من \(X\).
لكل عدد أساسي \(c\)، تحسب الخوارزمية \(X=\lfloor 10^{11}/c\rfloor\) ثم تضيف \(c\cdot A(X)\). بهذه العملية الواحدة تُحتسب جميع القيم الصالحة من الشكل \(c\,m\) دون المرور على كل حاصل ضرب منفردا. تطبقا C++ وJava هذه المرحلة الأخيرة على عدة خيوط عمل، بينما تستخدم Python الصيغة نفسها تسلسليا أو عبر توازٍ على مستوى العمليات.
وتتضمن نسخة C++ أيضا ثلاث وسائل تحقق: فحص القيمة النموذجية \(f(10000)=36\)، ومقارنة الصيغة الحسابية مع العد الهندسي المباشر للقيم الصغيرة من \(N\)، ومطابقة المجموع السريع مع مجموع brute-force على حد أصغر.
لنفرض أن \(C\) هو عدد الأجزاء الأساسية المختلفة، وأن \(M=\lfloor 10^{11}/c_{\min}\rfloor\) حيث \(c_{\min}=5^3\cdot13^2\cdot17\) هو أصغر جزء أساسي صالح. تعداد الأجزاء الأساسية صغير جدا مقارنة بفضاء البحث الأصلي، لأن عدد الأنماط الممكنة خمسة فقط، ونمو قوى الأوليات بشكل رتيب يجعل التقليم فعالا للغاية.
الغربال، وجدول الصلاحية، والمجاميع البادئة على المضاعفات تكلف \(O(M)\) زمنا و\(O(M)\) ذاكرة. أما المرور النهائي على جميع الأجزاء الأساسية فيكلف \(O(C)\). وهكذا تستبدل الطريقة مسحا مستحيلا بحجم \(10^{11}\) بتعداد منظم صغير وبمرحلة تمهيد خطية واحدة.