We must count integers \(n \le 2\times 10^9\) that can all be written in the four forms
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2,$$
with positive integers \(a\) and \(b\) in each representation.
The implementations do not search directly over all pairs \((a,b)\). Instead they first count a slightly larger set in which zero is temporarily allowed, classify those integers by their squarefree kernel, and then repair the overcount caused by perfect squares.
Let \(L=2\times 10^9\) and let \(D=\{1,2,3,7\}\). For the main counting argument it is convenient to relax the condition and first consider integers \(n\) such that for every \(d\in D\) there exist \(a_d,b_d\ge 0\) with
$$n=a_d^2+d\,b_d^2.$$
The strict positivity condition will be restored afterward.
Every positive integer has a unique decomposition
$$n=q\,m^2,$$
where \(q\) is squarefree. The implementations take as their number-theoretic starting point the characterization that simultaneous representability in all four relaxed forms depends only on this squarefree kernel. More precisely, the relaxed condition holds exactly when every prime factor of \(q\) lies in the residue classes
$$p\equiv 1,\ 25,\ 121 \pmod{168}.$$
So the admissible kernels are precisely
$$q=\prod_{i=1}^{r} p_i,$$
where the \(p_i\) are distinct primes from those three classes; \(q=1\) is the empty product. Once such a kernel is fixed, every number of the form \(q\,m^2\) belongs to the relaxed set, and once the kernel contains any other prime, the number can be discarded immediately.
For a fixed admissible kernel \(q\), the valid integers are exactly the numbers \(q\,m^2\le L\). Their count is therefore
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
If \(R(L)\) denotes the relaxed count, then
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
The implementations split this sum into three disjoint cases.
The kernel \(q=1\) contributes \(\lfloor\sqrt{L}\rfloor\). A singleton kernel \(q=p\) contributes \(\lfloor\sqrt{L/p}\rfloor\) for each good prime \(p\). All remaining kernels contain at least two distinct good primes, so the implementations enumerate their products by depth-first search and add the same floor term for each feasible product.
An important pruning rule comes from the smallest good prime. Since the first prime with residue \(1\), \(25\), or \(121\) modulo \(168\) is \(193\), any admissible kernel with at least two prime factors is at least \(193^2\). That is why the multi-prime stage can stop very early for small partial products.
The relaxed count is not yet the answer, because the original problem requires positive \(a\) and \(b\), not merely nonnegative ones. The only systematic overcount comes from perfect squares.
Indeed, every square \(m^2\) is automatically included in the relaxed set via the trivial identities
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D).$$
For a nonsquare, the degenerate case \(b=0\) cannot occur. And if \(a=0\) for \(d=2\), \(3\), or \(7\), then the squarefree kernel would contain \(2\), \(3\), or \(7\), which is impossible for an admissible kernel. So the positivity repair can be written as
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
where \(G(L)\) counts the squares \(m^2\le L\) that really do admit positive representations for all four coefficients.
To compute \(G(L)\), fix \(d\in D\) and ask when a square satisfies
$$m^2=a^2+d\,b^2$$
with \(a,b>0\). Rearranging gives
$$(m-a)(m+a)=d\,b^2.$$
If we set
$$u=m-a,\qquad v=m+a,$$
then we obtain
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
and conversely any factor pair \((u,v)\) satisfying these conditions yields
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
That turns the search for positive square representations into a divisor enumeration problem. For each fixed \(d\) and each positive \(b\), factor \(d\,b^2\), generate all divisors \(u\), define \(v=(d\,b^2)/u\), keep only pairs with the same parity and \(v>u\), and mark the resulting \(m\). Doing this separately for \(d=1,2,3,7\) produces four boolean tables over \(m\le \sqrt{L}\), and their intersection is exactly the set counted by \(G(L)\).
The number \(3600=60^2\) illustrates why the correction term is necessary. Its squarefree kernel is \(q=1\), so it is counted automatically in the relaxed total \(R(L)\).
It also survives the positivity correction, because it genuinely has positive representations in all four forms:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
So \(3600\) is first counted among all squares through the kernel \(q=1\), then removed by the blanket subtraction of \(\lfloor\sqrt{L}\rfloor\), and finally added back because it belongs to \(G(L)\).
The C++, Python, and Java implementations follow exactly the split described above. First they compute the relaxed quantity \(R(L)\). The singleton-kernel contribution is obtained by scanning primes up to \(L\) with a segmented sieve and keeping only primes in the three admissible residue classes modulo \(168\). Each such prime \(p\) contributes \(\left\lfloor \sqrt{L/p} \right\rfloor\).
The multi-prime part uses the ordered list of good primes up to \(L/193\). A depth-first search grows products of distinct good primes in increasing order, stops as soon as the next multiplication would exceed \(L\), and adds \(\left\lfloor \sqrt{L/q} \right\rfloor\) whenever the current product \(q\) already contains at least two primes. In this way every admissible multi-prime kernel is visited exactly once.
The square correction then builds a smallest-prime-factor table up to \(\sqrt{L}\). For each \(d\in\{1,2,3,7\}\) and each positive \(b\le \sqrt{L/d}\), the implementation factors \(d\,b^2\), generates all divisors, reconstructs every valid \(m\) from the factor pairs \((u,v)\), and marks it. The final answer is the relaxed kernel count minus all squares plus the number of \(m\) marked in every one of the four tables.
The language-specific execution strategy differs slightly, but the mathematics is the same. The C++ and Java implementations parallelize the segmented prime sweep across workers, while the Python implementation uses multiple processes for that same stage.
The dominant large-scale cost is the singleton-kernel stage, which performs a segmented prime sweep over the interval up to \(L\) while sieving with the base primes up to \(\sqrt{L}\). In asymptotic terms this is standard segmented-sieve work over a range of length \(L\), while memory stays bounded by the segment size and the small base-prime list.
The multi-prime DFS is much smaller in practice, because admissible kernels grow quickly once distinct good primes are multiplied together, and the recursion prunes immediately when the running product would exceed \(L\). The square-correction phase only works up to \(\sqrt{L}\), using a smallest-prime-factor table and divisor generation for numbers of the form \(d\,b^2\).
Memory usage is modest throughout: one segment buffer for the sieve, prime-factor data up to \(\sqrt{L}\), and four mark arrays of length \(\lfloor\sqrt{L}\rfloor\). The whole algorithm is efficient because it replaces a huge search in the \((a,b)\)-plane by kernel counting plus a focused correction on squares.
Gesucht ist die Anzahl der ganzen Zahlen \(n \le 2\times 10^9\), die sich gleichzeitig in den vier Formen
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2$$
mit positiven ganzen Zahlen \(a\) und \(b\) darstellen lassen.
Die Implementierungen durchsuchen nicht direkt alle möglichen Paare \((a,b)\). Stattdessen zählen sie zuerst eine etwas größere Menge, in der Null vorübergehend erlaubt ist, klassifizieren diese Zahlen über ihren quadratfreien Kern und korrigieren anschließend den Überhang, der durch Quadratzahlen entsteht.
Setze \(L=2\times 10^9\) und \(D=\{1,2,3,7\}\). Für das eigentliche Zählargument ist es zweckmäßig, zunächst die abgeschwächte Bedingung zu betrachten, dass es zu jedem \(d\in D\) nichtnegative ganze Zahlen \(a_d,b_d\) mit
$$n=a_d^2+d\,b_d^2$$
gibt. Die Forderung \(a_d,b_d>0\) wird danach wiederhergestellt.
Jede positive ganze Zahl besitzt eine eindeutige Zerlegung
$$n=q\,m^2,$$
wobei \(q\) quadratfrei ist. Die Implementierungen verwenden als Zahlentheorie-Grundlage die Charakterisierung, dass die gleichzeitige Darstellbarkeit in allen vier abgeschwächten Formen nur vom quadratfreien Kern abhängt. Genauer gesagt gilt die Bedingung genau dann, wenn alle Primteiler von \(q\) in den Restklassen
$$p\equiv 1,\ 25,\ 121 \pmod{168}$$
liegen.
Die zulässigen Kerne sind also genau die Produkte
$$q=\prod_{i=1}^{r} p_i,$$
wobei die \(p_i\) paarweise verschiedene Primzahlen aus diesen drei Restklassen sind; \(q=1\) ist das leere Produkt. Sobald ein solcher Kern feststeht, gehört jede Zahl der Form \(q\,m^2\) zur abgeschwächten Menge. Enthält der Kern dagegen irgendeinen anderen Primfaktor, kann die Zahl sofort verworfen werden.
Für einen festen zulässigen Kern \(q\) sind genau die Zahlen \(q\,m^2\le L\) gültig. Ihre Anzahl ist daher
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
Bezeichnet \(R(L)\) die abgeschwächte Anzahl, so gilt
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
Die Implementierungen zerlegen diese Summe in drei disjunkte Fälle.
Der Kern \(q=1\) liefert \(\lfloor\sqrt{L}\rfloor\). Ein Einzelkern \(q=p\) liefert für jede gute Primzahl \(p\) den Beitrag \(\lfloor\sqrt{L/p}\rfloor\). Alle übrigen Kerne enthalten mindestens zwei verschiedene gute Primzahlen; ihre Produkte werden deshalb per Tiefensuche erzeugt, und für jedes zulässige Produkt wird derselbe Wurzelausdruck addiert.
Eine wichtige Schranke folgt direkt aus der kleinsten guten Primzahl. Da die erste Primzahl mit Rest \(1\), \(25\) oder \(121\) modulo \(168\) gleich \(193\) ist, ist jeder zulässige Kern mit mindestens zwei Primfaktoren mindestens \(193^2\). Genau diese Beobachtung liefert das Abschneiden in der Mehr-Prim-Zählung.
Die abgeschwächte Anzahl ist noch nicht die gesuchte Antwort, weil das Originalproblem positive \(a\) und \(b\) verlangt und nicht nur nichtnegative. Der systematische Überhang kommt genau von den Quadratzahlen.
Jede Quadratzahl \(m^2\) liegt nämlich automatisch in der abgeschwächten Menge, denn es gelten die trivialen Identitäten
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D).$$
Für eine Nicht-Quadratzahl kann der degenerierte Fall \(b=0\) nicht auftreten. Und falls für \(d=2\), \(3\) oder \(7\) einmal \(a=0\) wäre, dann würde der quadratfreie Kern \(2\), \(3\) oder \(7\) enthalten, was bei einem zulässigen Kern unmöglich ist. Deshalb lässt sich die Positivitätskorrektur sauber schreiben als
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
wobei \(G(L)\) die Anzahl der Quadratzahlen \(m^2\le L\) bezeichnet, die tatsächlich für alle vier Koeffizienten positive Darstellungen besitzen.
Um \(G(L)\) zu berechnen, fixiert man ein \(d\in D\) und fragt, wann eine Quadratzahl
$$m^2=a^2+d\,b^2$$
mit \(a,b>0\) lösbar ist. Umformen liefert
$$(m-a)(m+a)=d\,b^2.$$
Setzt man
$$u=m-a,\qquad v=m+a,$$
so erhält man
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
und umgekehrt erzeugt jedes Faktorenpaar \((u,v)\) mit diesen Eigenschaften
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
Damit wird die Suche nach positiven Quadratdarstellungen zu einer Divisoraufgabe. Für jedes feste \(d\) und jedes positive \(b\) wird \(d\,b^2\) faktorisiert, es werden alle Teiler \(u\) erzeugt, \(v=(d\,b^2)/u\) gesetzt, dieselbe Parität geprüft und die Bedingung \(v>u\) erzwungen; anschließend wird das entstehende \(m\) markiert. Für \(d=1,2,3,7\) entstehen so vier Boolesche Tabellen über \(m\le \sqrt{L}\), und ihr Schnitt ist genau die durch \(G(L)\) gezählte Menge.
Die Zahl \(3600=60^2\) zeigt, warum der Korrekturterm nötig ist. Ihr quadratfreier Kern ist \(q=1\), also wird sie automatisch in der abgeschwächten Summe \(R(L)\) mitgezählt.
Sie bleibt aber auch nach der Positivitätskorrektur erhalten, weil sie echte positive Darstellungen in allen vier Formen besitzt:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
Die Zahl wird also zuerst unter allen Quadraten über den Kern \(q=1\) gezählt, dann durch die pauschale Subtraktion von \(\lfloor\sqrt{L}\rfloor\) entfernt und schließlich wieder hinzugefügt, weil sie zu \(G(L)\) gehört.
Die C++-, Python- und Java-Implementierungen folgen genau dieser Zweiteilung. Zuerst berechnen sie die abgeschwächte Größe \(R(L)\). Der Beitrag der Einzelkerne entsteht durch ein segmentiertes Primzahlsieb bis \(L\), aus dem nur die Primzahlen in den drei zulässigen Restklassen modulo \(168\) übernommen werden. Jede solche Primzahl \(p\) liefert den Beitrag \(\left\lfloor \sqrt{L/p} \right\rfloor\).
Der Mehr-Prim-Teil benutzt die geordnete Liste guter Primzahlen bis \(L/193\). Eine Tiefensuche baut Produkte verschiedener guter Primzahlen in aufsteigender Reihenfolge auf, bricht ab, sobald die nächste Multiplikation \(L\) überschreiten würde, und addiert \(\left\lfloor \sqrt{L/q} \right\rfloor\), sobald das aktuelle Produkt \(q\) bereits mindestens zwei Primfaktoren enthält. Auf diese Weise wird jeder zulässige Mehr-Prim-Kern genau einmal besucht.
Die Quadratkorrektur baut danach eine Tabelle kleinster Primfaktoren bis \(\sqrt{L}\) auf. Für jedes \(d\in\{1,2,3,7\}\) und jedes positive \(b\le \sqrt{L/d}\) faktorisiert die Implementierung \(d\,b^2\), erzeugt alle Teiler, rekonstruiert aus den Faktorenpaaren \((u,v)\) alle gültigen \(m\) und markiert sie. Die Endantwort ist dann die abgeschwächte Kernanzahl minus die Anzahl aller Quadratzahlen plus der Anzahl der \(m\), die in allen vier Tabellen markiert wurden.
Nur die Ausführungsstrategie unterscheidet sich leicht zwischen den Sprachen. Die C++- und Java-Versionen parallelisieren den segmentierten Primteildurchlauf über mehrere Worker, während die Python-Version für denselben Abschnitt mehrere Prozesse verwendet.
Der dominierende großskalige Aufwand steckt im Einzelkern-Teil, also im segmentierten Primzahldurchlauf über den Bereich bis \(L\) unter Verwendung der Basisprimzahlen bis \(\sqrt{L}\). Asymptotisch ist das die übliche Arbeit eines segmentierten Siebs über ein Intervall der Länge \(L\), während der Speicher nur von der Segmentgröße und der kleinen Basisprimliste abhängt.
Die Tiefensuche über Mehr-Prim-Kerne ist in der Praxis deutlich kleiner, weil zulässige Kerne rasch anwachsen, sobald verschiedene gute Primzahlen multipliziert werden, und weil die Rekursion sofort abschneidet, wenn das laufende Produkt \(L\) überschreiten würde. Die Quadratkorrektur arbeitet nur bis \(\sqrt{L}\) und benutzt dort eine Tabelle kleinster Primfaktoren sowie Divisor-Erzeugung für Zahlen der Form \(d\,b^2\).
Der Speicherbedarf bleibt moderat: ein Segmentpuffer für das Sieb, Primfaktor-Daten bis \(\sqrt{L}\) und vier Markierungsfelder der Länge \(\lfloor\sqrt{L}\rfloor\). Effizient wird das Verfahren dadurch, dass eine große Suche in der \((a,b)\)-Ebene durch Kernzählung plus eine gezielte Quadratkorrektur ersetzt wird.
Aranan şey, \(n \le 2\times 10^9\) koşulunu sağlayan ve aynı anda şu dört biçimde de yazılabilen tam sayıların sayısıdır:
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2.$$
Her eşitlikte \(a\) ve \(b\) pozitif tam sayı olmalıdır.
Uygulamalar tüm \((a,b)\) çiftlerini doğrudan taramıyor. Bunun yerine önce sıfırın geçici olarak izinli olduğu biraz daha geniş bir kümeyi sayıyor, bu sayıları kare-serbest çekirdeklerine göre sınıflandırıyor ve sonra tam karelerden gelen fazla sayımı düzeltiyor.
\(L=2\times 10^9\) ve \(D=\{1,2,3,7\}\) olsun. Ana sayım için önce gevşetilmiş koşulu ele almak uygundur: her \(d\in D\) için
$$n=a_d^2+d\,b_d^2$$
eşitliğini sağlayan \(a_d,b_d\ge 0\) tam sayıları bulunsun. Sıkı pozitiflik koşulu daha sonra geri getirilecektir.
Her pozitif tam sayı tek biçimde
$$n=q\,m^2$$
şeklinde yazılır; burada \(q\) kare-serbesttir. Uygulamaların dayandığı sayı kuramsal başlangıç noktası şudur: dört gevşetilmiş biçimin hepsinde aynı anda temsil edilebilir olma durumu yalnızca bu kare-serbest çekirdeğe bağlıdır. Daha açık söylersek, bu durum tam olarak \(q\)'nun tüm asal çarpanları
$$p\equiv 1,\ 25,\ 121 \pmod{168}$$
artık sınıflarında olduğunda gerçekleşir.
Dolayısıyla izinli çekirdekler tam olarak
$$q=\prod_{i=1}^{r} p_i$$
şeklindeki çarpımlardır; burada \(p_i\)'ler bu üç sınıftan gelen birbirinden farklı asal sayılardır. \(q=1\) boş çarpımdır. Böyle bir çekirdek bir kez seçildiğinde, \(q\,m^2\) biçimindeki her sayı gevşetilmiş kümeye girer. Çekirdek başka herhangi bir asal içeriyorsa sayı hemen elenir.
Sabit bir izinli çekirdek \(q\) için geçerli sayılar tam olarak \(q\,m^2\le L\) koşulunu sağlayan sayılardır. Bunların sayısı
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor$$
olur. Gevşetilmiş sayımı \(R(L)\) ile gösterirsek
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor$$
yazılır.
Uygulamalar bu toplamı üç ayrık parçaya böler. \(q=1\) çekirdeği \(\lfloor\sqrt{L}\rfloor\) katkısı yapar. Tek asal içeren bir çekirdek \(q=p\), her iyi asal \(p\) için \(\lfloor\sqrt{L/p}\rfloor\) katkısı verir. Geriye kalan bütün çekirdekler en az iki farklı iyi asal içerir; bu yüzden bu çarpımlar derinlik öncelikli arama ile üretilir ve uygun olan her çarpım için aynı kök terimi eklenir.
Burada önemli bir budama değişmezi vardır. İyi artık sınıflarından gelen en küçük asal \(193\) olduğundan, en az iki asal çarpanlı her izinli çekirdek en az \(193^2\) büyüklüğündedir. Çok asallı sayımın erken kesilmesini sağlayan fikir tam olarak budur.
Gevşetilmiş sayım henüz nihai cevap değildir; çünkü asıl problem yalnızca \(a,b\ge 0\) değil, \(a,b>0\) ister. Sistematik fazla sayım tam karelerden gelir.
Gerçekten de her \(m^2\) tam karesi,
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D)$$
özdeşlikleri sayesinde gevşetilmiş kümeye otomatik olarak girer. Kare olmayan bir sayıda \(b=0\) olamaz. Ayrıca \(d=2\), \(3\) veya \(7\) için \(a=0\) olsaydı, kare-serbest çekirdek \(2\), \(3\) ya da \(7\) içerirdi; bu da izinli çekirdek yapısıyla çelişir. Bu yüzden pozitiflik düzeltmesi temiz biçimde
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L)$$
şeklinde yazılır. Burada \(G(L)\), gerçekten dört katsayının hepsinde de pozitif temsile sahip olan \(m^2\le L\) karelerinin sayısıdır.
\(G(L)\)'yi hesaplamak için bir \(d\in D\) sabitleyelim ve
$$m^2=a^2+d\,b^2$$
eşitliğinin \(a,b>0\) ile ne zaman çözülebileceğini soralım. Düzenlersek
$$(m-a)(m+a)=d\,b^2$$
elde edilir. Şimdi
$$u=m-a,\qquad v=m+a$$
yazarsak
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2$$
olur; tersine, bu koşulları sağlayan her çarpan çifti \((u,v)\)
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}$$
değerlerini verir. Böylece pozitif kare temsilleri, bölen üretme problemine dönüşür. Her sabit \(d\) ve her pozitif \(b\) için \(d\,b^2\) asal çarpanlarına ayrılır, tüm bölenler \(u\) üretilir, \(v=(d\,b^2)/u\) alınır, aynı parity ve \(v>u\) koşulları denetlenir ve çıkan \(m\) işaretlenir. Bu işlem \(d=1,2,3,7\) için ayrı ayrı yapıldığında, \(m\le \sqrt{L}\) üzerinde dört Boole tablosu oluşur; bunların kesişimi tam olarak \(G(L)\)'dir.
\(3600=60^2\) sayısı, düzeltme teriminin neden gerekli olduğunu iyi gösterir. Kare-serbest çekirdeği \(q=1\) olduğu için bu sayı gevşetilmiş toplam \(R(L)\) içinde otomatik olarak sayılır.
Ama pozitiflik düzeltmesinden sonra da kalır; çünkü dört biçimin hepsinde gerçekten pozitif temsilleri vardır:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
Dolayısıyla \(3600\) önce \(q=1\) çekirdeği üzerinden tüm kareler arasında sayılır, sonra \(\lfloor\sqrt{L}\rfloor\) toplu çıkarımıyla silinir, sonra da \(G(L)\)'ye ait olduğu için yeniden eklenir.
C++, Python ve Java uygulamaları tam olarak bu ayrımı izler. Önce gevşetilmiş büyüklük \(R(L)\) hesaplanır. Tek asal çekirdek katkısı, \(L\)'ye kadar segmentli asal taraması yapılarak ve yalnızca \(168\) modunda üç izinli artık sınıfta kalan asallar tutularak bulunur. Her böyle asal \(p\), \(\left\lfloor \sqrt{L/p} \right\rfloor\) katkısı yapar.
Çok asallı bölüm, \(L/193\)'e kadar olan iyi asalların sıralı listesiyle çalışır. Derinlik öncelikli arama, artan sırada farklı iyi asalların çarpımlarını büyütür, sıradaki çarpma \(L\)'yi aşacaksa durur ve güncel çarpım \(q\) en az iki asal içerdiğinde \(\left\lfloor \sqrt{L/q} \right\rfloor\) terimini ekler. Böylece her izinli çok asallı çekirdek tam bir kez ziyaret edilir.
Kare düzeltmesi daha sonra \(\sqrt{L}\)'ye kadar en küçük asal çarpan tablosu kurar. Her \(d\in\{1,2,3,7\}\) ve her pozitif \(b\le \sqrt{L/d}\) için uygulama \(d\,b^2\)'yi çarpanlara ayırır, tüm bölenleri üretir, \((u,v)\) çarpan çiftlerinden geçerli \(m\) değerlerini yeniden kurar ve bunları işaretler. Son cevap, gevşetilmiş çekirdek sayımından bütün karelerin çıkarılıp dört tablonun hepsinde işaretlenen \(m\) sayısının eklenmesiyle elde edilir.
Diller arasındaki fark daha çok yürütme biçimindedir. C++ ve Java sürümleri segmentli asal taramasını işçilere bölerek paralelleştirir; Python sürümü ise aynı aşamada çoklu süreç kullanır.
Büyük ölçekte baskın maliyet, \(L\)'ye kadar yapılan segmentli asal taramasıdır. Bu aşama, \(\sqrt{L}\)'ye kadarki taban asalları kullanarak uzunluğu \(L\) olan bir aralık üzerinde standart segmentli sieve işi yapar; bellek tüketimi ise segment boyutu ile küçük taban asal listesiyle sınırlı kalır.
Çok asallı DFS pratikte çok daha küçüktür; çünkü farklı iyi asallar çarpıldıkça çekirdek hızla büyür ve kısmi çarpım \(L\)'yi aşar aşmaz dallanma hemen budanır. Kare düzeltmesi ise yalnızca \(\sqrt{L}\) ölçeğinde çalışır ve burada hem en küçük asal çarpan tablosunu hem de \(d\,b^2\) biçimindeki sayılar için bölen üretimini kullanır.
Bellek gereksinimi düşüktür: sieve için tek bir segment tamponu, \(\sqrt{L}\)'ye kadar asal çarpan verileri ve uzunluğu \(\lfloor\sqrt{L}\rfloor\) olan dört işaret dizisi. Yöntem, \((a,b)\) düzleminde kaba kuvvet arama yapmak yerine çekirdek sayımı ve kareler üzerinde odaklı bir düzeltme uyguladığı için verimlidir.
Hay que contar los enteros \(n \le 2\times 10^9\) que pueden escribirse simultáneamente en las cuatro formas
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2,$$
con \(a\) y \(b\) enteros positivos en cada caso.
Las implementaciones no recorren directamente todos los pares \((a,b)\). Primero cuentan un conjunto un poco más amplio en el que temporalmente se permite el cero, clasifican esos enteros por su núcleo libre de cuadrados y después corrigen el exceso que producen los cuadrados perfectos.
Tomemos \(L=2\times 10^9\) y \(D=\{1,2,3,7\}\). Para el argumento principal conviene empezar con la condición relajada: para cada \(d\in D\) deben existir enteros no negativos \(a_d,b_d\) tales que
$$n=a_d^2+d\,b_d^2.$$
La positividad estricta se recupera al final.
Todo entero positivo admite una descomposición única
$$n=q\,m^2,$$
donde \(q\) es libre de cuadrados. El punto de partida aritmético de las implementaciones es que la representabilidad simultánea en las cuatro formas relajadas depende solamente de ese núcleo. Más concretamente, la condición se cumple exactamente cuando todos los factores primos de \(q\) pertenecen a las clases de residuos
$$p\equiv 1,\ 25,\ 121 \pmod{168}.$$
Por tanto, los núcleos admisibles son precisamente los productos
$$q=\prod_{i=1}^{r} p_i,$$
donde los \(p_i\) son primos distintos tomados de esas tres clases; \(q=1\) es el producto vacío. Una vez fijado un núcleo de ese tipo, cualquier número \(q\,m^2\) pertenece al conjunto relajado. Si el núcleo contiene algún otro primo, el entero queda descartado de inmediato.
Para un núcleo admisible fijo \(q\), los valores válidos son exactamente los enteros \(q\,m^2\le L\). Su cantidad es
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
Si \(R(L)\) denota el conteo relajado, entonces
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
Las implementaciones descomponen esta suma en tres casos disjuntos.
El núcleo \(q=1\) aporta \(\lfloor\sqrt{L}\rfloor\). Un núcleo unitario \(q=p\) aporta \(\lfloor\sqrt{L/p}\rfloor\) para cada primo bueno \(p\). Todos los demás núcleos contienen al menos dos primos buenos distintos, así que sus productos se generan mediante una búsqueda en profundidad y se añade el mismo término de raíz para cada producto factible.
Aparece además una poda muy útil. El menor primo bueno es \(193\), de modo que cualquier núcleo admisible con al menos dos factores primos tiene tamaño al menos \(193^2\). Esa observación es justamente la que hace pequeña la exploración de núcleos múltiples.
El conteo relajado todavía no es la respuesta final, porque el problema original exige \(a,b>0\), no solo \(a,b\ge 0\). El exceso sistemático proviene exactamente de los cuadrados perfectos.
En efecto, todo cuadrado \(m^2\) entra automáticamente en el conjunto relajado gracias a las identidades triviales
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D).$$
Si \(n\) no es cuadrado, el caso degenerado \(b=0\) no puede ocurrir. Y si \(a=0\) para \(d=2\), \(3\) o \(7\), entonces el núcleo libre de cuadrados contendría \(2\), \(3\) o \(7\), algo incompatible con la condición de admisibilidad. Por eso la reparación de la positividad se escribe limpiamente como
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
donde \(G(L)\) cuenta los cuadrados \(m^2\le L\) que sí poseen representaciones positivas para los cuatro coeficientes.
Para calcular \(G(L)\), fijemos \(d\in D\) y preguntemos cuándo un cuadrado cumple
$$m^2=a^2+d\,b^2$$
con \(a,b>0\). Al reorganizar aparece
$$(m-a)(m+a)=d\,b^2.$$
Si escribimos
$$u=m-a,\qquad v=m+a,$$
obtenemos
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
y, a la inversa, cualquier par de factores \((u,v)\) con esas propiedades produce
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
Así, el problema de las representaciones cuadradas positivas pasa a ser una enumeración de divisores. Para cada \(d\) fijo y cada \(b\) positivo, el código factoriza \(d\,b^2\), genera todos los divisores \(u\), define \(v=(d\,b^2)/u\), comprueba la paridad y la desigualdad estricta \(v>u\), y marca el valor resultante de \(m\). Hacer esto por separado para \(d=1,2,3,7\) genera cuatro tablas booleanas sobre \(m\le \sqrt{L}\), y su intersección es exactamente el conjunto contado por \(G(L)\).
El número \(3600=60^2\) muestra bien por qué hace falta la corrección. Su núcleo libre de cuadrados es \(q=1\), así que queda incluido automáticamente en el total relajado \(R(L)\).
Además sobrevive a la corrección de positividad, porque realmente tiene representaciones positivas en las cuatro formas:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
En otras palabras, primero se cuenta entre todos los cuadrados a través del núcleo \(q=1\), luego se elimina con la sustracción global de \(\lfloor\sqrt{L}\rfloor\), y al final se vuelve a añadir porque pertenece a \(G(L)\).
Las implementaciones en C++, Python y Java siguen exactamente esta separación. Primero calculan la cantidad relajada \(R(L)\). La contribución de los núcleos unitarios se obtiene con un cribado segmentado de primos hasta \(L\), conservando solo los primos que caen en las tres clases de residuos admisibles módulo \(168\). Cada primo de ese tipo \(p\) aporta \(\left\lfloor \sqrt{L/p} \right\rfloor\).
La parte de varios primos usa la lista ordenada de primos buenos hasta \(L/193\). Una búsqueda en profundidad va creciendo productos de primos buenos distintos en orden creciente, se detiene en cuanto la siguiente multiplicación superaría \(L\), y suma \(\left\lfloor \sqrt{L/q} \right\rfloor\) siempre que el producto actual \(q\) ya contenga al menos dos primos. Así se enumera cada núcleo admisible con varios primos exactamente una vez.
La corrección de cuadrados construye después una tabla de menores factores primos hasta \(\sqrt{L}\). Para cada \(d\in\{1,2,3,7\}\) y cada \(b\) positivo con \(b\le \sqrt{L/d}\), la implementación factoriza \(d\,b^2\), genera todos sus divisores, reconstruye todos los \(m\) válidos a partir de los pares \((u,v)\) y los marca. La respuesta final es el conteo por núcleos relajados menos todos los cuadrados, más el número de valores \(m\) marcados en las cuatro tablas.
La estrategia de ejecución cambia ligeramente según el lenguaje, pero la matemática es la misma. Las versiones en C++ y Java paralelizan el barrido segmentado de primos; la versión en Python usa varios procesos en esa misma fase.
El coste dominante a gran escala está en la etapa de núcleos unitarios, que realiza un barrido segmentado de primos sobre el intervalo hasta \(L\) usando los primos base hasta \(\sqrt{L}\). Asintóticamente es el trabajo habitual de una criba segmentada sobre un rango de longitud \(L\), mientras que la memoria queda acotada por el tamaño del bloque y la pequeña lista de primos base.
La DFS de núcleos con varios primos es mucho más pequeña en la práctica, porque los núcleos admisibles crecen deprisa al multiplicar primos buenos distintos y la recursión se poda en cuanto el producto parcial superaría \(L\). La fase de corrección de cuadrados trabaja solo hasta \(\sqrt{L}\), con una tabla de menor factor primo y generación de divisores para números de la forma \(d\,b^2\).
El uso de memoria es moderado: un bloque del cribado segmentado, datos de factorización hasta \(\sqrt{L}\) y cuatro arreglos de marcas de longitud \(\lfloor\sqrt{L}\rfloor\). El método es eficaz porque sustituye una búsqueda enorme en el plano \((a,b)\) por conteo de núcleos más una corrección focalizada sobre los cuadrados.
目标是统计所有满足 \(n \le 2\times 10^9\) 的整数，并且它们能够同时写成下面四种形式：
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2,$$
而且每一种表示中的 \(a\) 与 \(b\) 都必须是正整数。
实现并没有直接暴力枚举所有 \((a,b)\) 对。它先统计一个稍微放宽的集合，在那个集合里暂时允许零出现；然后按照平方自由核来分类这些整数；最后再把由完全平方数带来的多算部分修正掉。
记 \(L=2\times 10^9\)，并设 \(D=\{1,2,3,7\}\)。为了建立计数公式，先考虑放宽后的条件：对于每个 \(d\in D\)，都存在非负整数 \(a_d,b_d\) 使得
$$n=a_d^2+d\,b_d^2.$$
真正的正整数条件稍后再恢复。
每个正整数都可以唯一写成
$$n=q\,m^2,$$
其中 \(q\) 是平方自由数。三个实现所依赖的数论事实是：能否同时在这四个放宽后的二次型中表示，只取决于这个平方自由核。更具体地说，放宽后的条件成立，当且仅当 \(q\) 的每一个素因子都落在下面三个模 \(168\) 的剩余类里：
$$p\equiv 1,\ 25,\ 121 \pmod{168}.$$
因此，允许的核恰好是
$$q=\prod_{i=1}^{r} p_i,$$
其中各个 \(p_i\) 是来自这三类的互不相同的素数；\(q=1\) 对应空乘积。一旦 \(q\) 是这样的核，那么所有形如 \(q\,m^2\) 的数都会进入放宽后的集合；反过来，只要核里出现了别的素数，就可以立刻排除。
对固定的允许核 \(q\)，所有满足条件的整数正好是
$$q\,m^2\le L,$$
所以它们的个数是
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
如果把放宽后的计数记成 \(R(L)\)，那么
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
实现把这件事拆成三个互不重叠的部分。
当 \(q=1\) 时，贡献是 \(\lfloor\sqrt{L}\rfloor\)。当 \(q=p\) 是单个好素数时，贡献是 \(\lfloor\sqrt{L/p}\rfloor\)。剩下的核都至少含有两个不同的好素数，因此程序用深度优先搜索枚举这些素数乘积，并对每一个可行乘积累加同样的平方根项。
这里有一个很重要的剪枝事实：最小的好素数是 \(193\)。因此，只要一个允许核已经包含至少两个素因子，它就至少有大小 \(193^2\)。这也是多素数部分能被迅速截断的原因。
放宽后的计数并不是最终答案，因为原题要求的是 \(a,b>0\)，而不是仅仅 \(a,b\ge 0\)。系统性多算的部分恰好来自完全平方数。
原因很直接：每个平方 \(m^2\) 都会通过平凡表示
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D)$$
自动进入放宽后的集合。若 \(n\) 不是平方数，则不可能出现 \(b=0\)。而如果对 \(d=2\)、\(3\) 或 \(7\) 出现 \(a=0\)，那么平方自由核就会含有 \(2\)、\(3\) 或 \(7\)，这与允许核的结构矛盾。所以，正性修正可以写成非常整齐的形式：
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
其中 \(G(L)\) 表示那些平方数 \(m^2\le L\) 中，真正对四个系数都拥有正表示的个数。
为了计算 \(G(L)\)，固定一个 \(d\in D\)，研究什么时候
$$m^2=a^2+d\,b^2$$
存在 \(a,b>0\) 的解。整理后得到
$$(m-a)(m+a)=d\,b^2.$$
如果记
$$u=m-a,\qquad v=m+a,$$
那么就有
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
反过来，任何满足这些条件的因子对 \((u,v)\) 都会给出
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
于是，正平方表示问题被转成了一个枚举因子的静态问题。对每个固定的 \(d\) 和每个正整数 \(b\)，程序分解 \(d\,b^2\) 的质因数，生成全部因子 \(u\)，取 \(v=(d\,b^2)/u\)，检查奇偶性是否一致以及是否满足 \(v>u\)，然后把对应的 \(m\) 标记出来。分别对 \(d=1,2,3,7\) 做完之后，会得到四张定义在 \(m\le \sqrt{L}\) 上的布尔表，它们的交集正是 \(G(L)\)。
\(3600=60^2\) 很适合说明这个修正为什么必要。它的平方自由核是 \(q=1\)，所以在放宽后的总数 \(R(L)\) 里会被自动计入。
同时它也会在修正之后保留下来，因为它确实在四种形式里都有正表示：
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
因此，\(3600\) 先通过核 \(q=1\) 在“所有平方数”这一批里被计算一次，然后随着整体减去 \(\lfloor\sqrt{L}\rfloor\) 而被拿掉，最后又因为它属于 \(G(L)\) 而重新加回来。
C++、Python 和 Java 三个实现完全按照上面的分解来做。首先计算放宽后的数量 \(R(L)\)。单素数核部分通过分段筛扫描到 \(L\) 的素数，只保留模 \(168\) 落在那三个允许剩余类中的素数。每个这样的素数 \(p\) 贡献 \(\left\lfloor \sqrt{L/p} \right\rfloor\)。
多素数核部分使用不超过 \(L/193\) 的好素数有序表。深度优先搜索按递增顺序扩展互不相同的好素数乘积，一旦下一次乘法会超过 \(L\) 就立刻停止；当当前乘积 \(q\) 已经包含至少两个素数时，就把 \(\left\lfloor \sqrt{L/q} \right\rfloor\) 加入总和。这样每个允许的多素数核都会恰好访问一次。
平方修正阶段则先建立到 \(\sqrt{L}\) 为止的最小质因子表。对每个 \(d\in\{1,2,3,7\}\) 和每个满足 \(b\le \sqrt{L/d}\) 的正整数 \(b\)，程序分解 \(d\,b^2\)，枚举其全部因子，并从满足条件的因子对 \((u,v)\) 重建所有可行的 \(m\)。最终答案等于放宽后的核计数减去全部平方数，再加上在四张标记表中都出现的 \(m\) 的个数。
不同语言之间只有执行策略略有差别。C++ 与 Java 版本把分段筛这一步并行化，Python 版本则在同一阶段使用多进程；但数学内容完全相同。
大尺度上的主导成本来自单素数核阶段，也就是对区间 \([1,L]\) 的分段筛扫描，并使用到 \(\sqrt{L}\) 为止的基素数。按渐近复杂度看，这就是长度为 \(L\) 的区间上的标准分段筛工作，而内存主要受块大小和基素数表控制。
多素数 DFS 在实践中要小得多，因为只要开始乘入互不相同的好素数，允许核就会迅速变大，而一旦部分乘积即将超过 \(L\)，递归就会立刻剪枝。平方修正阶段只在 \(\sqrt{L}\) 的范围内工作，配合最小质因子表以及对 \(d\,b^2\) 的因子生成。
整体内存占用并不高：一个分段筛缓冲区、到 \(\sqrt{L}\) 的质因子数据，以及四个长度为 \(\lfloor\sqrt{L}\rfloor\) 的标记数组。这个算法高效的原因在于，它把原本庞大的 \((a,b)\) 搜索，压缩成了“核计数 + 平方修正”两部分。
Нужно посчитать все целые числа \(n \le 2\times 10^9\), которые одновременно допускают представления
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2,$$
причем в каждом случае \(a\) и \(b\) должны быть положительными целыми числами.
Реализации не перебирают напрямую все пары \((a,b)\). Сначала они считают немного более широкое множество, где нуль временно разрешен, затем классифицируют числа по их квадратсвободному ядру и после этого исправляют переучет, возникающий из-за полных квадратов.
Положим \(L=2\times 10^9\) и \(D=\{1,2,3,7\}\). Для основного подсчета удобно сначала рассмотреть ослабленное условие: для каждого \(d\in D\) существуют неотрицательные целые \(a_d,b_d\), такие что
$$n=a_d^2+d\,b_d^2.$$
Требование строгой положительности будет восстановлено позже.
Каждое положительное целое однозначно раскладывается в виде
$$n=q\,m^2,$$
где \(q\) квадратсвободно. Числовой факт, на котором построены реализации, состоит в том, что одновременная представимость во всех четырех ослабленных формах зависит только от этого ядра. А именно, условие выполняется тогда и только тогда, когда все простые делители \(q\) лежат в классах вычетов
$$p\equiv 1,\ 25,\ 121 \pmod{168}.$$
Следовательно, допустимые ядра имеют вид
$$q=\prod_{i=1}^{r} p_i,$$
где \(p_i\) — попарно различные простые числа из этих трех классов; \(q=1\) соответствует пустому произведению. Как только ядро имеет такой вид, все числа \(q\,m^2\) принадлежат ослабленному множеству. Если же в ядре присутствует любой другой простой множитель, число можно сразу отбросить.
Для фиксированного допустимого ядра \(q\) подходящие числа — это ровно \(q\,m^2\le L\). Их количество равно
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
Если обозначить ослабленный подсчет через \(R(L)\), то
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
В коде эта сумма разбивается на три непересекающихся случая.
Ядро \(q=1\) дает вклад \(\lfloor\sqrt{L}\rfloor\). Однопростое ядро \(q=p\) дает вклад \(\lfloor\sqrt{L/p}\rfloor\) для каждого хорошего простого \(p\). Все остальные ядра содержат как минимум два различных хороших простых, поэтому их произведения перечисляются поиском в глубину, и для каждого допустимого произведения добавляется тот же самый корневой член.
Здесь есть важное ограничение. Наименьший хороший простой равен \(193\), поэтому любое допустимое ядро хотя бы с двумя простыми множителями имеет размер не меньше \(193^2\). Именно это наблюдение делает перебор многопростых ядер компактным.
Ослабленный подсчет еще не является окончательным ответом, потому что исходная задача требует \(a,b>0\), а не просто \(a,b\ge 0\). Систематический переучет возникает именно из-за полных квадратов.
Действительно, каждый квадрат \(m^2\) автоматически попадает в ослабленное множество благодаря тождествам
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D).$$
Для неквадрата вырожденный случай \(b=0\) невозможен. А если бы при \(d=2\), \(3\) или \(7\) оказалось \(a=0\), то квадратсвободное ядро содержало бы \(2\), \(3\) или \(7\), что несовместимо с допустимостью. Поэтому поправка на положительность записывается в виде
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
где \(G(L)\) — число квадратов \(m^2\le L\), которые действительно имеют положительные представления для всех четырех коэффициентов.
Чтобы вычислить \(G(L)\), зафиксируем \(d\in D\) и спросим, когда квадрат удовлетворяет равенству
$$m^2=a^2+d\,b^2$$
при \(a,b>0\). После преобразования получаем
$$(m-a)(m+a)=d\,b^2.$$
Если положить
$$u=m-a,\qquad v=m+a,$$
то имеем
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
и наоборот, любая пара делителей \((u,v)\) с этими свойствами задает
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
Тем самым задача о положительных квадратных представлениях превращается в перечисление делителей. Для каждого фиксированного \(d\) и каждого положительного \(b\) программа раскладывает \(d\,b^2\) на простые множители, генерирует все делители \(u\), берет \(v=(d\,b^2)/u\), проверяет одинаковую четность и условие \(v>u\), а затем отмечает полученное \(m\). Отдельное выполнение этого процесса для \(d=1,2,3,7\) дает четыре булевы таблицы на \(m\le \sqrt{L}\), и их пересечение в точности равно множеству, считаемому функцией \(G(L)\).
Число \(3600=60^2\) хорошо показывает, зачем нужна поправка. Его квадратсвободное ядро равно \(q=1\), поэтому оно автоматически входит в ослабленную сумму \(R(L)\).
Но после поправки оно остается, потому что действительно имеет положительные представления во всех четырех формах:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
Итак, сначала \(3600\) учитывается среди всех квадратов через ядро \(q=1\), затем убирается общей вычитательной поправкой \(\lfloor\sqrt{L}\rfloor\), а потом снова добавляется, потому что принадлежит \(G(L)\).
Реализации на C++, Python и Java буквально повторяют описанное разбиение. Сначала вычисляется ослабленная величина \(R(L)\). Вклад однопростых ядер получается с помощью сегментированного решета простых до \(L\), после чего остаются только простые числа из трех допустимых классов вычетов по модулю \(168\). Каждый такой простой \(p\) дает вклад \(\left\lfloor \sqrt{L/p} \right\rfloor\).
Многопростая часть использует упорядоченный список хороших простых до \(L/193\). Поиск в глубину наращивает произведения различных хороших простых в возрастающем порядке, останавливается, как только следующая операция умножения превысила бы \(L\), и прибавляет \(\left\lfloor \sqrt{L/q} \right\rfloor\), когда текущее произведение \(q\) уже содержит по меньшей мере два простых множителя. Благодаря этому каждое допустимое многопростое ядро перечисляется ровно один раз.
Далее этап квадратной поправки строит таблицу наименьших простых множителей до \(\sqrt{L}\). Для каждого \(d\in\{1,2,3,7\}\) и каждого положительного \(b\le \sqrt{L/d}\) реализация раскладывает \(d\,b^2\), генерирует все делители, восстанавливает из пар \((u,v)\) все допустимые значения \(m\) и помечает их. Окончательный ответ равен ослабленному ядровому подсчету минус все квадраты плюс число тех \(m\), которые отмечены во всех четырех таблицах.
Различие между языками в основном техническое. Версии на C++ и Java распараллеливают сегментированный проход по простым, а версия на Python использует на этом же этапе несколько процессов.
Главная крупномасштабная стоимость приходится на этап однопростых ядер, то есть на сегментированное просеивание диапазона до \(L\) с использованием базовых простых до \(\sqrt{L}\). Асимптотически это стандартная стоимость сегментированного решета на отрезке длины \(L\), тогда как память ограничивается размером сегмента и небольшой таблицей базовых простых.
DFS по многопростым ядрам на практике значительно меньше, потому что допустимые ядра быстро растут при умножении различных хороших простых, и рекурсия сразу отсекается, как только текущий продукт грозит превысить \(L\). Этап квадратной поправки работает только до \(\sqrt{L}\), используя таблицу наименьших простых множителей и генерацию делителей для чисел вида \(d\,b^2\).
Память остается умеренной: один сегментный буфер решета, данные факторизации до \(\sqrt{L}\) и четыре массива отметок длины \(\lfloor\sqrt{L}\rfloor\). Алгоритм эффективен потому, что заменяет огромный поиск в плоскости \((a,b)\) подсчетом ядер и локальной поправкой на квадраты.
المطلوب هو عدّ جميع الأعداد الصحيحة \(n \le 2\times 10^9\) التي يمكن كتابتها في الصور الأربع التالية مع كون \(a\) و\(b\) عددين صحيحين موجبين في كل مرة:
$$n=a^2+b^2=a^2+2b^2=a^2+3b^2=a^2+7b^2.$$
لا تعتمد التطبيقات على استعراض مباشر لكل الأزواج \((a,b)\). بل تبدأ أولًا بعدّ مجموعة أوسع قليلًا يُسمح فيها مؤقتًا بالقيمة الصفرية، ثم تصنّف الأعداد بحسب نواتها الخالية من المربعات، وبعد ذلك تصلح الزيادة الناتجة عن إدخال المربعات الكاملة.
لنضع \(L=2\times 10^9\) و\(D=\{1,2,3,7\}\). من الأنسب في برهان العد أن نبدأ بالشرط المخفف: لكل \(d\in D\) توجد أعداد صحيحة غير سالبة \(a_d,b_d\) تحقق
$$n=a_d^2+d\,b_d^2.$$
ثم نعيد شرط الإيجابية الصارمة في النهاية.
كل عدد صحيح موجب يملك كتابة وحيدة على الصورة
$$n=q\,m^2,$$
حيث إن \(q\) خالٍ من المربعات. الحقيقة العددية التي تعتمد عليها التطبيقات هي أن قابلية التمثيل المتزامن في الصور الأربع المخففة تعتمد فقط على هذه النواة. وبشكل أدق، يتحقق الشرط إذا وفقط إذا كانت جميع العوامل الأولية لـ \(q\) تقع في فئات البواقي
$$p\equiv 1,\ 25,\ 121 \pmod{168}.$$
ومن ثم فإن النوى المسموح بها هي بالضبط
$$q=\prod_{i=1}^{r} p_i,$$
حيث إن \(p_i\) أوليات متميزة مأخوذة من هذه الفئات الثلاث، و\(q=1\) يمثل الجداء الفارغ. متى ما كانت النواة من هذا النوع فإن كل عدد من الشكل \(q\,m^2\) ينتمي إلى المجموعة المخففة، أما إذا احتوت النواة على أي أولي آخر فيمكن استبعاد العدد فورًا.
إذا ثبتت نواة مسموح بها \(q\)، فإن الأعداد الصالحة هي تمامًا الأعداد التي تحقق \(q\,m^2\le L\). وعددها يساوي
$$\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
وإذا رمزنا إلى العد المخفف بـ \(R(L)\)، فإن
$$R(L)=\sum_{\substack{q\le L\\ q\text{ admissible}}}\left\lfloor \sqrt{\frac{L}{q}} \right\rfloor.$$
تقوم التطبيقات بتقسيم هذا المجموع إلى ثلاث حالات منفصلة.
الحالة \(q=1\) تعطي الإسهام \(\lfloor\sqrt{L}\rfloor\). أما النواة الأحادية \(q=p\) فتعطي \(\lfloor\sqrt{L/p}\rfloor\) لكل أولي جيد \(p\). وكل النوى الأخرى تحتوي على أوليين جيدين مختلفين على الأقل، لذلك تُولَّد جداءات هذه الأوليات ببحث عمقي، ويُضاف نفس الحد الجذري لكل جداء ممكن.
وهنا تظهر قاعدة قطع مهمة. أصغر أولي جيد هو \(193\)، ولذلك فإن أي نواة مسموح بها تحتوي على عاملين أوليين على الأقل لا يمكن أن تكون أصغر من \(193^2\). وهذه هي الفكرة التي تجعل تعداد النوى متعددة الأوليات محدودًا جدًا.
العد المخفف ليس هو الجواب النهائي، لأن المسألة الأصلية تشترط \(a,b>0\) لا مجرد \(a,b\ge 0\). والزيادة المنتظمة في العد تأتي تحديدًا من المربعات الكاملة.
فكل مربع \(m^2\) يدخل تلقائيًا في المجموعة المخففة بفضل الهويات البديهية
$$m^2=m^2+d\cdot 0^2 \qquad (d\in D).$$
إذا لم يكن \(n\) مربعًا فلا يمكن أن يحدث \(b=0\). وإذا حدث \(a=0\) عند \(d=2\) أو \(3\) أو \(7\)، فإن النواة الخالية من المربعات ستحتوي على \(2\) أو \(3\) أو \(7\)، وهذا مستحيل مع بنية النوى المسموح بها. لذلك يمكن كتابة تصحيح الإيجابية على الصورة
$$A(L)=R(L)-\lfloor\sqrt{L}\rfloor+G(L),$$
حيث إن \(G(L)\) هو عدد المربعات \(m^2\le L\) التي تملك بالفعل تمثيلات موجبة لجميع المعاملات الأربعة.
لحساب \(G(L)\)، نثبت \(d\in D\) ونسأل: متى يحقق مربع ما
$$m^2=a^2+d\,b^2$$
مع \(a,b>0\)؟ بإعادة الترتيب نحصل على
$$(m-a)(m+a)=d\,b^2.$$
إذا وضعنا
$$u=m-a,\qquad v=m+a,$$
فإننا نحصل على
$$uv=d\,b^2,\qquad u<v,\qquad u\equiv v\pmod 2,$$
وبالعكس فإن أي زوج قواسم \((u,v)\) يحقق هذه الشروط يعطي
$$m=\frac{u+v}{2},\qquad a=\frac{v-u}{2}.$$
وهكذا تتحول مسألة التمثيلات الموجبة للمربعات إلى تعداد قواسم. فلكل \(d\) ثابت ولكل \(b\) موجب، تفكك الشيفرة العدد \(d\,b^2\)، وتولد جميع القواسم \(u\)، ثم تأخذ \(v=(d\,b^2)/u\)، وتتحقق من تساوي الفردية ومن الشرط \(v>u\)، ثم تضع علامة على \(m\) الناتج. وعند تنفيذ هذا مستقلاً من أجل \(d=1,2,3,7\) نحصل على أربع جداول منطقية على المجال \(m\le \sqrt{L}\)، وتقاطع هذه الجداول هو بالضبط المجموعة التي يعدها \(G(L)\).
العدد \(3600=60^2\) يوضح جيدًا لماذا نحتاج إلى هذا التصحيح. نواته الخالية من المربعات هي \(q=1\)، ولذلك يُحسب تلقائيًا داخل المجموع المخفف \(R(L)\).
لكنه يبقى أيضًا بعد تصحيح الإيجابية، لأنه يملك تمثيلات موجبة حقيقية في الصور الأربع:
$$3600=48^2+36^2=20^2+2\cdot 40^2=30^2+3\cdot 30^2=45^2+7\cdot 15^2.$$
أي إن \(3600\) يُحسب أولًا ضمن جميع المربعات عبر النواة \(q=1\)، ثم يُزال مع الطرح الكلي لـ \(\lfloor\sqrt{L}\rfloor\)، ثم يُعاد إضافته لأنه ينتمي إلى \(G(L)\).
تتبع تطبيقات C++ وPython وJava هذا التقسيم نفسه حرفيًا. أولًا تحسب الكمية المخففة \(R(L)\). ويُستخرج إسهام النوى الأحادية بواسطة غربال أوليات مقسّم حتى \(L\)، ثم تُحتفظ فقط بالأوليات الواقعة في فئات البواقي الثلاث المسموح بها modulo \(168\). وكل أولي من هذا النوع \(p\) يضيف \(\left\lfloor \sqrt{L/p} \right\rfloor\).
أما جزء النوى متعددة الأوليات فيستعمل القائمة المرتبة للأوليات الجيدة حتى \(L/193\). ويقوم بحث عمقي بتوسيع جداءات أوليات جيدة متميزة بترتيب تصاعدي، ويتوقف بمجرد أن تتجاوز الضربة التالية الحد \(L\)، ويضيف \(\left\lfloor \sqrt{L/q} \right\rfloor\) كلما أصبح الجداء الحالي \(q\) محتويًا على أوليين على الأقل. وبهذه الطريقة يُزار كل جداء مسموح به مرة واحدة فقط.
بعد ذلك تبني مرحلة تصحيح المربعات جدولًا لأصغر عامل أولي حتى \(\sqrt{L}\). ولكل \(d\in\{1,2,3,7\}\) ولكل \(b\) موجب يحقق \(b\le \sqrt{L/d}\)، تفكك الشيفرة \(d\,b^2\)، وتولد جميع قواسمه، وتعيد بناء كل قيم \(m\) الصالحة من أزواج العوامل \((u,v)\)، ثم تضع علامة عليها. والجواب النهائي هو عدّ النوى المخففة ناقص جميع المربعات زائد عدد قيم \(m\) التي وُسمت في الجداول الأربع جميعًا.
الاختلاف بين اللغات تقني أكثر منه رياضي. فإصدارا C++ وJava يوازيان خطوة الغربال المقسّم، بينما يستخدم إصدار Python عدة عمليات في المرحلة نفسها.
التكلفة المهيمنة على النطاق الكبير تأتي من مرحلة النوى الأحادية، أي من المرور المقسّم على الأوليات حتى \(L\) باستخدام أوليات الأساس حتى \(\sqrt{L}\). ومن حيث التحليل التقاربي فهذه هي كلفة الغربال المقسّم المعتادة على مجال طوله \(L\)، بينما تبقى الذاكرة محدودة بحجم القطعة وقائمة أوليات الأساس الصغيرة.
أما البحث العمقي في النوى متعددة الأوليات فهو أصغر بكثير عمليًا، لأن النوى المسموح بها تنمو بسرعة عندما نضرب أوليات جيدة مختلفة، وتُقطع الشجرة مباشرة عندما يصبح الجداء الجزئي أكبر من \(L\). ومرحلة تصحيح المربعات تعمل فقط حتى \(\sqrt{L}\)، مستخدمةً جدول أصغر عامل أولي وتوليد القواسم للأعداد من الشكل \(d\,b^2\).
استهلاك الذاكرة يبقى معتدلًا: قطعة واحدة للغربال، وبيانات عوامل أولية حتى \(\sqrt{L}\)، وأربع مصفوفات تعليم طول كل منها \(\lfloor\sqrt{L}\rfloor\). وتكمن فعالية الخوارزمية في أنها تستبدل بحثًا ضخمًا في مستوى \((a,b)\) بعدّ النوى ثم تطبيق تصحيح مركز على المربعات.