The target quantity is a summatory arithmetic function \(G(n)\), evaluated modulo \(10^9+7\), with the Project Euler input at \(n=10^{12}\). The native implementations show that the summand is multiplicative and that its local behavior depends on whether an odd prime is congruent to \(1\) or \(3\) modulo \(4\).
The relevant Dirichlet character is
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
Reading the prime and prime-power contributions from the implementations gives the multiplicative term
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
Therefore the problem is to compute
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
A direct loop to \(10^{12}\) is not viable, so the implementation uses a compressed prime-prefix sieve together with a DFS over admissible prime-power products.
The entire method can be reconstructed from two facts visible in the implementations: a prime first appears with weight \(p^3-\chi_4(p)\), and every extra copy of the same prime multiplies the contribution by another factor \(p^3\).
For a prime \(p\), the first occurrence contributes
$$w(p)=p^3-\chi_4(p).$$
So the three residue classes behave as follows:
$$w(2)=8,\qquad w(p)=p^3-1\ \text{if }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{if }p\equiv 3\pmod 4.$$
This is the arithmetic signature of the problem: primes \(1\bmod 4\) and \(3\bmod 4\) are treated differently, exactly through the character \(\chi_4\).
Once a branch already contains \(p\), increasing the exponent by \(1\) multiplies the current local contribution by \(p^3\). Therefore
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
In particular, the factor for \(p=2\) is simply \(2^{3e}\), because \(\chi_4(2)=0\). For odd primes the correction term is exactly one unit of \(p^{3e-3}\), with sign determined by \(p\bmod 4\).
Independent prime branches multiply, so for
$$n=\prod_{p^e\parallel n} p^e$$
we get
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
This is the closed form encoded by the DFS. An equivalent divisor-sum identity is
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3,$$
because only squarefree divisors survive the Möbius factor. That identity is not used directly in the code, but it confirms the prime-power formula and makes the multiplicativity transparent.
The summatory function can be decomposed into the contribution of \(1\), the contribution of primes, and the remaining composite branches. The prime part is
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
For that reason the implementation builds two prime-prefix tables:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
Then the prime contribution is their difference
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Both tables start from easy full-integer prefixes and then sieve away composite contributions prime by prime. For cubes, the starting formula is
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
For the mod-\(4\) character, the full-integer prefix is periodic:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
The values \(\left\lfloor n/i\right\rfloor\) repeat heavily, so the implementation stores prime-prefix information only on the compressed domain
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
This reduces the table size from \(O(n)\) to \(O(\sqrt n)\). After the prime-only prefixes are available on that domain, a DFS enumerates multiplicative branches in increasing prime order. Ordering the primes this way prevents double-counting. At each branch:
$$\text{first copy of }p \Rightarrow p^3-\chi_4(p),\qquad \text{each extra copy of }p \Rightarrow \times p^3.$$
The prime-prefix tables instantly add the cases where a branch is extended by one larger prime, while recursion handles products containing several larger primes.
The local formula gives
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
Summing these values yields
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
which matches the checkpoint used by the native implementations.
The C++ and Java implementations first generate all primes up to \(\lfloor\sqrt n\rfloor\). They then build two compressed prime-prefix tables: one for \(\sum_{p\le x} p^3\), and one for \(\sum_{p\le x}\chi_4(p)\). Each table starts from the corresponding prefix over all integers and applies a prime-sieving transform so that only prime contributions remain.
After subtracting those tables, the implementation has fast access to \(\sum_{p\le x}(p^3-\chi_4(p))\) for every needed compressed argument \(x\). A DFS then enumerates composite multiplicative branches in increasing prime order. When a new prime enters a branch, the factor is \(p^3-\chi_4(p)\); when the same prime is repeated, the factor gains another multiplier \(p^3\). The prefix tables let the implementation add all one-more-prime extensions in bulk, while recursion handles deeper products.
The final answer is
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{composite DFS contribution}\pmod{10^9+7}.$$
The Python implementation is intentionally thin: it compiles and launches the native solver when needed, then returns the parsed numeric result.
The compressed floor-division domain has size \(O(\sqrt n)\), so the memory usage is \(O(\sqrt n)\). The two prime-prefix transforms run on that compressed domain rather than on all integers up to \(n\); in standard Min_25-style analysis this is roughly \(O(n^{3/4}/\log n)\) work. The DFS over admissible prime-power products is much smaller than a direct scan to \(n\) and is practical for the required input size. Overall the method is decisively sublinear in \(n\) and is designed specifically for \(n=10^{12}\).
Gesucht ist ein Summenwert \(G(n)\) modulo \(10^9+7\); für das eigentliche Project-Euler-Ziel ist \(n=10^{12}\). Aus den nativen Implementierungen liest man ab, dass der Summand multiplikativ ist und dass sein lokales Verhalten davon abhängt, ob eine ungerade Primzahl zu \(1\) oder zu \(3\) modulo \(4\) kongruent ist.
Die relevante Dirichlet-Charakterfunktion lautet
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
Aus den Beiträgen von Primzahlen und Primzahlpotenzen folgt damit
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
Somit ist die Zielgröße
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
Ein direkter Lauf bis \(10^{12}\) wäre zu langsam, daher kombiniert die Lösung ein komprimiertes Primzahl-Präfixsieb mit einer DFS über zulässige Primzahlpotenz-Produkte.
Die gesamte Methode lässt sich aus zwei sichtbaren Eigenschaften rekonstruieren: Beim ersten Auftreten einer Primzahl ist ihr Gewicht \(p^3-\chi_4(p)\), und jede weitere Kopie derselben Primzahl multipliziert den Beitrag noch einmal mit \(p^3\).
Für eine Primzahl \(p\) ist der erste Beitrag
$$w(p)=p^3-\chi_4(p).$$
Damit ergeben sich die drei Fälle
$$w(2)=8,\qquad w(p)=p^3-1\ \text{für }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{für }p\equiv 3\pmod 4.$$
Genau hierin steckt die arithmetische Struktur des Problems: Primzahlen \(1\bmod 4\) und \(3\bmod 4\) werden über den Charakter \(\chi_4\) unterschiedlich gewichtet.
Ist \(p\) bereits in einem Zweig enthalten, dann erhöht ein zusätzlicher Exponent den lokalen Beitrag um einen weiteren Faktor \(p^3\). Also gilt
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
Für \(p=2\) vereinfacht sich das zu \(2^{3e}\), weil \(\chi_4(2)=0\). Bei ungeraden Primzahlen ist der Korrekturterm genau eine Einheit von \(p^{3e-3}\), mit Vorzeichen je nach Restklasse modulo \(4\).
Verschiedene Primzahlzweige sind unabhängig. Für
$$n=\prod_{p^e\parallel n} p^e$$
erhält man deshalb
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
Das ist genau die geschlossene Form, die von der DFS implementiert wird. Äquivalent dazu gilt die Teilerdarstellung
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3,$$
denn wegen der Möbius-Funktion tragen nur quadratfreie Teiler bei. Diese Formel wird im Code nicht direkt benutzt, bestätigt aber die Primzahlpotenz-Regel und macht die Multiplikativität klar sichtbar.
Die Summenfunktion zerfällt in den Beitrag von \(1\), den Beitrag der Primzahlen und die übrigen zusammengesetzten Zweige. Für Primzahlen ist
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Darum baut die Implementierung zwei Primzahl-Präfixtabellen:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
Ihre Differenz ist
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Beide Tabellen starten aus einfachen Präfixsummen über alle ganzen Zahlen und sieben anschließend Kompositzahlen primzahlweise heraus. Für die Kubiksumme gilt
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
Für den mod-\(4\)-Charakter ist die Ganzzahl-Präfixsumme periodisch:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
Die Werte \(\left\lfloor n/i\right\rfloor\) wiederholen sich stark. Deshalb speichert die Implementierung Primzahl-Präfixinformationen nur auf der komprimierten Menge
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
So schrumpft die Tabellengröße von \(O(n)\) auf \(O(\sqrt n)\). Sobald die Primzahlpräfixe auf dieser Menge vorliegen, durchläuft eine DFS die multiplikativen Zweige in aufsteigender Primzahlreihenfolge. Diese Ordnung verhindert Doppeltzählungen. In jedem Zweig gilt:
$$\text{erste Kopie von }p \Rightarrow p^3-\chi_4(p),\qquad \text{jede weitere Kopie von }p \Rightarrow \times p^3.$$
Die Präfixtabellen addieren sofort alle Erweiterungen um genau eine größere Primzahl; die Rekursion übernimmt Produkte mit mehreren größeren Primzahlen.
Aus der lokalen Formel folgt
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
Daraus ergibt sich
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
genau der Kontrollwert der nativen Implementierungen.
Die C++- und Java-Implementierungen erzeugen zuerst alle Primzahlen bis \(\lfloor\sqrt n\rfloor\). Danach konstruieren sie zwei komprimierte Primzahl-Präfixtabellen: eine für \(\sum_{p\le x} p^3\) und eine für \(\sum_{p\le x}\chi_4(p)\). Beide beginnen als Präfixsummen über alle ganzen Zahlen und werden dann mit einer Primzahl-Transformation so bereinigt, dass nur Primzahlbeiträge übrig bleiben.
Nach der Subtraktion dieser beiden Tabellen steht \(\sum_{p\le x}(p^3-\chi_4(p))\) für jeden benötigten komprimierten Wert \(x\) schnell zur Verfügung. Anschließend zählt eine DFS die zusammengesetzten multiplikativen Zweige in aufsteigender Primzahlreihenfolge. Beim ersten Auftreten einer neuen Primzahl ist der Faktor \(p^3-\chi_4(p)\); bei Wiederholung derselben Primzahl kommt jeweils ein weiterer Faktor \(p^3\) hinzu. Mit den Präfixtabellen kann der Code alle Erweiterungen um genau eine größere Primzahl gesammelt hinzufügen, während die Rekursion tiefere Produkte behandelt.
Die Endform ist
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{DFS-Beitrag der Komposita}\pmod{10^9+7}.$$
Die Python-Implementierung ist bewusst schlank: Sie kompiliert den nativen Solver bei Bedarf, startet ihn und liefert das geparste numerische Ergebnis zurück.
Die komprimierte Quotientenmenge hat Größe \(O(\sqrt n)\), also beträgt auch der Speicherbedarf \(O(\sqrt n)\). Die beiden Primzahl-Präfixtransformationen arbeiten auf dieser komprimierten Menge statt auf allen Zahlen bis \(n\); in der üblichen Min_25-Analyse entspricht das grob \(O(n^{3/4}/\log n)\) Arbeit. Die DFS über zulässige Primzahlpotenz-Produkte ist wesentlich kleiner als eine direkte Summation bis \(n\) und für die Zielgröße \(10^{12}\) praktikabel. Insgesamt ist das Verfahren klar sublinear in \(n\).
Hedef nicelik, \(10^9+7\) modunda hesaplanan bir toplamsal aritmetik fonksiyon \(G(n)\)'dir; Project Euler girdisinde \(n=10^{12}\) alınır. Yerel davranıştan görüldüğü üzere toplanan terim çarpımsaldır ve tek asalın \(4\) moduna göre \(1\) mi yoksa \(3\) mü olduğuna bağlı olarak değişir.
Kullanılan Dirichlet karakteri şudur:
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
Uygulamaların asal ve asal kuvvet katkılarından çıkan çarpımsal terim
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}$$
şeklindedir. Dolayısıyla istenen toplam
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}$$
olur. \(10^{12}\)'ye kadar doğrudan dolaşmak mümkün olmadığından çözüm, sıkıştırılmış asal önek tablolarını asal kuvvetler üzerinde çalışan bir DFS ile birleştirir.
Bütün yöntem iki gözleme dayanır: bir asal ilk kez göründüğünde ağırlığı \(p^3-\chi_4(p)\) olur; aynı asalın üssü arttıkça katkı her defasında bir kez daha \(p^3\) ile çarpılır.
Bir asal \(p\) için ilk katkı
$$w(p)=p^3-\chi_4(p)$$
olur. Buna göre üç durum vardır:
$$w(2)=8,\qquad w(p)=p^3-1\ \text{eğer }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{eğer }p\equiv 3\pmod 4.$$
Problemin karakteristik aritmetik imzası budur: \(1\bmod 4\) ve \(3\bmod 4\) asalları \(\chi_4\) üzerinden farklı davranır.
Bir dalda \(p\) zaten varsa, üssü \(1\) artırmak yerel katkıya bir tane daha \(p^3\) çarpanı ekler. Bu yüzden
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}$$
elde edilir. \(p=2\) için bu doğrudan \(2^{3e}\)'ye iner; çünkü \(\chi_4(2)=0\). Tek asallarda düzeltme terimi \(p^{3e-3}\)'ün tam bir kopyasıdır ve işareti kalıntı sınıfına göre değişir.
Farklı asallar bağımsız çoğaldığı için
$$n=\prod_{p^e\parallel n} p^e$$
yazıldığında
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right)$$
olur. DFS'in kodladığı kapalı form tam olarak budur. Eşdeğer bir bölen toplamı ifadesi de vardır:
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3.$$
Möbius çarpanı yüzünden sadece karesiz bölenler kaldığından bu özdeşlik asal kuvvet formülünü doğrular ve çarpımsallığı netleştirir. Kod bu eşitliği doğrudan kullanmaz, fakat matematiksel yapıyı açık eder.
Toplam, \(1\)'in katkısı, asal katkısı ve geri kalan bileşik dallar olarak ayrılabilir. Asallar için
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr)$$
olduğundan uygulama iki ayrı asal önek tablosu kurar:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
Farkları
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr)$$
olur. Her iki tablo da önce tüm tamsayılar üzerindeki kolay öneklerden başlar, sonra bileşik terimler asal asal ayıklanır. Küpler için başlangıç formülü
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1$$
şeklindedir. Mod \(4\) karakteri için tam sayı öneki ise periyodiktir:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
\(\left\lfloor n/i\right\rfloor\) değerleri çok tekrar ettiği için asal önek bilgisi sadece şu sıkıştırılmış kümede tutulur:
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
Böylece tablo boyutu \(O(n)\)'den \(O(\sqrt n)\)'ye iner. Bu kümede asal önekleri hazır olduktan sonra DFS, çarpımsal dalları artan asal sırasıyla gezer; bu düzen aynı sayının iki kez sayılmasını engeller. Her dal için kural şudur:
$$\text{\(p\)'nin ilk kopyası } \Rightarrow p^3-\chi_4(p),\qquad \text{\(p\)'nin her ek kopyası } \Rightarrow \times p^3.$$
Önek tabloları, dala tam bir daha büyük asal eklenmesiyle oluşan tüm durumları topluca ekler; daha derin çarpımlar için özyineleme devreye girer.
Yerel formül kullanılırsa
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
Bunların toplamı
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053$$
olur ve bu, yerel doğrulama değerini tam olarak verir.
C++ ve Java uygulamaları önce \(\lfloor\sqrt n\rfloor\)'ye kadar bütün asalları üretir. Ardından iki sıkıştırılmış asal önek tablosu kurulur: biri \(\sum_{p\le x} p^3\) için, diğeri \(\sum_{p\le x}\chi_4(p)\) için. Her tablo önce tüm tamsayılar üzerindeki ilgili önek toplamından başlar ve ardından asal tabanlı bir eleme dönüşümüyle yalnızca asal katkıları bırakır.
Bu iki tablo çıkarıldığında, gereken her sıkıştırılmış \(x\) değeri için \(\sum_{p\le x}(p^3-\chi_4(p))\) hazır hale gelir. Sonra DFS, bileşik çarpımsal dalları artan asal sırasıyla dolaşır. Dala yeni giren bir asal için katsayı \(p^3-\chi_4(p)\)'dir; aynı asalı tekrar etmek bir tane daha \(p^3\) çarpanı ekler. Önek tabloları tek ek asal ile genişleyen bütün durumları topluca sayar, özyineleme ise daha derin ürünleri toplar.
Son ifade
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{bileşik DFS katkısı}\pmod{10^9+7}$$
şeklindedir. Python uygulaması ise bilinçli olarak ince tutulmuştur: gerektiğinde yerel derlemeyi yapar, yerel ikiliyi çalıştırır ve sayısal sonucu ayıklayıp döndürür.
Sıkıştırılmış taban bölmesi kümesinin boyutu \(O(\sqrt n)\) olduğundan bellek kullanımı da \(O(\sqrt n)\)'dir. İki asal önek dönüşümü tüm \(1,\dots,n\) aralığında değil, bu sıkıştırılmış uzayda çalışır; standart Min_25 analizinde bu yaklaşık \(O(n^{3/4}/\log n)\) iş demektir. Asal kuvvet ürünleri üzerindeki DFS, \(n\)'ye kadar doğrudan toplamaktan çok daha küçüktür ve hedef büyüklük olan \(10^{12}\) için pratiktir. Sonuç olarak yöntem belirgin biçimde altdoğrusaldır.
La cantidad objetivo es una función sumatoria \(G(n)\) calculada módulo \(10^9+7\); en el caso de Project Euler se toma \(n=10^{12}\). A partir de las implementaciones nativas se ve que el término sumado es multiplicativo y que su comportamiento local depende de si un primo impar es congruente con \(1\) o con \(3\) módulo \(4\).
El carácter de Dirichlet relevante es
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
De las contribuciones de primos y potencias primas se obtiene
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
Por tanto, el problema consiste en calcular
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
Un recorrido directo hasta \(10^{12}\) sería inviable, así que la solución combina una criba de prefijos sobre primos en dominio comprimido con un DFS sobre productos admisibles de potencias primas.
Todo el método se reconstruye a partir de dos observaciones visibles en las implementaciones: la primera aparición de un primo aporta \(p^3-\chi_4(p)\), y cada copia adicional del mismo primo multiplica la contribución por otro factor \(p^3\).
Para un primo \(p\), la primera contribución es
$$w(p)=p^3-\chi_4(p).$$
Eso da los tres casos
$$w(2)=8,\qquad w(p)=p^3-1\ \text{si }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{si }p\equiv 3\pmod 4.$$
Aquí está la firma aritmética del problema: los primos \(1\bmod 4\) y \(3\bmod 4\) se distinguen exactamente mediante \(\chi_4\).
Una vez que \(p\) ya pertenece a una rama, aumentar su exponente en \(1\) multiplica el aporte local por \(p^3\). Por eso
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
En particular, para \(p=2\) esto se reduce a \(2^{3e}\), porque \(\chi_4(2)=0\). Para primos impares, el término correctivo es exactamente una unidad de \(p^{3e-3}\), con signo fijado por la clase módulo \(4\).
Como las ramas asociadas a primos distintos son independientes, si
$$n=\prod_{p^e\parallel n} p^e$$
entonces
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
Esa es la forma cerrada que implementa el DFS. Una identidad equivalente mediante divisores es
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3,$$
ya que el factor de Möbius elimina todos los divisores no libres de cuadrados. El código no usa esta fórmula de manera literal, pero sirve para verificar la regla de potencias primas y para hacer explícita la multiplicatividad.
La suma total se descompone en la contribución de \(1\), la de los primos y la del resto de ramas compuestas. Para los primos,
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Por eso la implementación construye dos tablas de prefijos sobre primos:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
Su diferencia es
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Ambas tablas parten de prefijos fáciles sobre todos los enteros y luego eliminan las contribuciones compuestas primo por primo. Para los cubos se usa
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
Para el carácter módulo \(4\), el prefijo entero es periódico:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
Los valores \(\left\lfloor n/i\right\rfloor\) se repiten mucho, así que la información de prefijos sobre primos sólo se guarda en el dominio comprimido
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
Con ello el tamaño de las tablas baja de \(O(n)\) a \(O(\sqrt n)\). Una vez disponibles los prefijos de primos en ese dominio, el DFS enumera ramas multiplicativas en orden creciente de primo, lo que evita el doble conteo. En cada rama vale la regla
$$\text{primera copia de }p \Rightarrow p^3-\chi_4(p),\qquad \text{cada copia adicional de }p \Rightarrow \times p^3.$$
Las tablas de prefijos permiten sumar de golpe todos los casos en los que la rama se prolonga con exactamente un primo mayor, mientras que la recursión cubre productos con varios primos mayores.
La fórmula local produce
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
Por tanto,
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
que coincide con el valor de control usado por las implementaciones nativas.
Las implementaciones en C++ y Java primero generan todos los primos hasta \(\lfloor\sqrt n\rfloor\). Después construyen dos tablas comprimidas de prefijos sobre primos: una para \(\sum_{p\le x} p^3\) y otra para \(\sum_{p\le x}\chi_4(p)\). Cada tabla empieza como un prefijo sobre todos los enteros y luego aplica una transformación tipo criba para que sólo permanezcan las contribuciones primas.
Al restar ambas tablas, la implementación obtiene acceso rápido a \(\sum_{p\le x}(p^3-\chi_4(p))\) para cada argumento comprimido necesario. A continuación, un DFS recorre las ramas multiplicativas compuestas en orden creciente de primos. Cuando entra un primo nuevo en una rama, el factor es \(p^3-\chi_4(p)\); cuando se repite el mismo primo, el factor gana otro multiplicador \(p^3\). Las tablas de prefijos permiten añadir en bloque todas las extensiones con un primo mayor adicional, mientras que la recursión se encarga de los productos más profundos.
La forma final es
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{contribución compuesta del DFS}\pmod{10^9+7}.$$
La implementación en Python es deliberadamente ligera: compila y ejecuta el solucionador nativo cuando hace falta y luego devuelve el resultado numérico ya interpretado.
El dominio comprimido de cocientes tiene tamaño \(O(\sqrt n)\), así que la memoria también es \(O(\sqrt n)\). Las dos transformaciones de prefijos sobre primos trabajan en ese dominio comprimido en vez de recorrer todos los enteros hasta \(n\); con el análisis estándar de Min_25, eso equivale aproximadamente a \(O(n^{3/4}/\log n)\) operaciones. El DFS sobre productos admisibles de potencias primas es mucho menor que una suma directa hasta \(n\) y resulta práctico para \(10^{12}\). En conjunto, el método es claramente sublineal.
目标量是一个求和函数 \(G(n)\)，结果按 \(10^9+7\) 取模；在 Project Euler 的正式输入中，\(n=10^{12}\)。从原生实现可以直接看出，被求和的项是一个乘法函数，而且它的局部行为取决于奇素数在模 \(4\) 下是 \(1\) 还是 \(3\)。
这里出现的 Dirichlet 特征是
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
从素数与素数幂的贡献规则可以恢复出被求和的乘法函数：
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
因此题目实际上要求计算
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
如果直接从 \(1\) 累加到 \(10^{12}\)，时间显然不可接受，所以实现采用了“压缩后的素数前缀筛 + 枚举素数幂乘积分支的 DFS”这一组合方案。
整个算法可以从两个直接可见的事实推出：一个素数第一次进入乘积时的权重是 \(p^3-\chi_4(p)\)，而同一个素数每额外增加一次幂次，贡献都会再乘一个 \(p^3\)。
对任意素数 \(p\)，第一次出现时的局部贡献为
$$w(p)=p^3-\chi_4(p).$$
于是三种情况分别是
$$w(2)=8,\qquad w(p)=p^3-1\ \text{当 }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{当 }p\equiv 3\pmod 4.$$
这正是题目的算术特征：模 \(4\) 为 \(1\) 的素数与模 \(4\) 为 \(3\) 的素数被不同对待，而差异完全由 \(\chi_4\) 控制。
一旦某个分支里已经含有 \(p\)，把指数再提高 \(1\) 就会让局部贡献多乘一个 \(p^3\)。因此
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
特别地，\(p=2\) 时因为 \(\chi_4(2)=0\)，所以只是简单的 \(2^{3e}\)。对奇素数而言，修正项正好是一份 \(p^{3e-3}\)，符号由 \(p\bmod 4\) 决定。
不同素数的分支彼此独立，相乘即可。若
$$n=\prod_{p^e\parallel n} p^e,$$
那么
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
这就是 DFS 实际编码的闭式。还可以把它改写成除数和：
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3.$$
因为 Möbius 因子会消去所有非平方自由除数，所以这个恒等式与素数幂公式完全一致。实现并不直接按这个除数和来算，但它非常适合用来验证乘法性和局部因子的正确性。
总和可以拆成 \(1\) 的贡献、所有素数的贡献，以及其余合数分支的贡献。素数部分满足
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
因此实现构造了两个素数前缀表：
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
它们的差就是
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
这两个表都不是从零开始硬筛到 \(x\)，而是先利用“所有整数”的简单前缀公式，再逐个素数剔除合数贡献。立方和的初始前缀是
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
模 \(4\) 特征在所有整数上的前缀则具有长度为 \(4\) 的周期：
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
也就是说，代码先掌握“整数前缀”，再通过筛法把它们变成“素数前缀”。
\(\left\lfloor n/i\right\rfloor\) 的取值会大量重复，因此没有必要为所有 \(1\le x\le n\) 都存表。实现只在压缩域
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}$$
上保存这些前缀信息，从而把表规模从 \(O(n)\) 降到 \(O(\sqrt n)\)。有了压缩域上的素数前缀和以后，DFS 就按素数递增顺序枚举所有乘法分支。这种顺序非常关键，因为它天然避免了重复计数。每个分支遵守的规则很简单：
$$\text{素数 }p\text{ 第一次出现 } \Rightarrow p^3-\chi_4(p),\qquad \text{同一素数每多出现一次 } \Rightarrow \times p^3.$$
借助前缀表，程序可以一次性加上“当前分支再乘一个更大素数”的全部贡献；若还要继续附加更多更大的素数，就交给递归继续展开。
按局部公式逐项计算可得
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
因此
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
这与原生实现中的校验值完全一致。
C++ 和 Java 实现首先生成所有不超过 \(\lfloor\sqrt n\rfloor\) 的素数。随后它们构造两个压缩的素数前缀表：一个保存 \(\sum_{p\le x} p^3\)，另一个保存 \(\sum_{p\le x}\chi_4(p)\)。每张表都从“所有整数上的前缀和”出发，再通过一次素数筛式变换，逐步去掉合数部分，最终留下纯粹的素数贡献。
把这两张表相减之后，程序就能快速得到任意所需压缩参数 \(x\) 上的 \(\sum_{p\le x}(p^3-\chi_4(p))\)。接下来，DFS 按照素数递增顺序枚举所有合数分支。一个新素数进入分支时，乘上的因子是 \(p^3-\chi_4(p)\)；同一个素数再次出现时，再额外乘一个 \(p^3\)。前缀表负责批量处理“再接一个更大素数”的全部情况，而递归负责处理包含多个更大素数的更深层乘积。
最终结果可写成
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{DFS 统计出的合数部分}\pmod{10^9+7}.$$
Python 实现则是一个很薄的桥接层：需要时编译原生求解器，执行它，然后把输出解析成最终的数值答案。
压缩后的整除分块域大小为 \(O(\sqrt n)\)，所以内存使用也是 \(O(\sqrt n)\)。两张素数前缀表都在这个压缩域上工作，而不是在 \(1\) 到 \(n\) 的整个区间上工作；按照标准的 Min_25 风格分析，主导时间大约是 \(O(n^{3/4}/\log n)\)。枚举可行素数幂乘积的 DFS 远小于直接遍历到 \(n\) 的代价，因此对于 \(n=10^{12}\) 这样的输入规模是可行的。整体上，这是一种明显优于线性扫描的次线性算法。
Искомая величина — суммирующая функция \(G(n)\) по модулю \(10^9+7\); в задаче Project Euler используется \(n=10^{12}\). Из нативных реализаций видно, что суммируемый член является мультипликативной функцией, а его локальное поведение зависит от того, сравним ли нечётный простой с \(1\) или с \(3\) по модулю \(4\).
Здесь появляется характер Дирихле
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
Из вкладов простых и их степеней следует формула
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
Следовательно, нужно вычислить
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
Прямой проход до \(10^{12}\) слишком дорог, поэтому используется сочетание сжатых префиксных сумм по простым и DFS по допустимым произведениям простых степеней.
Вся схема восстанавливается из двух наблюдений, которые прямо видны в реализациях: первое появление простого числа даёт вес \(p^3-\chi_4(p)\), а каждое дальнейшее увеличение его степени добавляет ещё один множитель \(p^3\).
Для простого \(p\) первый вклад равен
$$w(p)=p^3-\chi_4(p).$$
Значит, имеются три случая:
$$w(2)=8,\qquad w(p)=p^3-1\ \text{при }p\equiv 1\pmod 4,\qquad w(p)=p^3+1\ \text{при }p\equiv 3\pmod 4.$$
Именно здесь проявляется арифметическая природа задачи: простые \(1\bmod 4\) и \(3\bmod 4\) различаются ровно через характер \(\chi_4\).
Если \(p\) уже вошёл в ветвь, то увеличение показателя степени на \(1\) умножает локальный вклад ещё на \(p^3\). Поэтому
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
Для \(p=2\) это просто \(2^{3e}\), так как \(\chi_4(2)=0\). Для нечётных простых корректирующий член равен одной копии \(p^{3e-3}\), а знак определяется классом по модулю \(4\).
Разные простые ветви независимы. Если
$$n=\prod_{p^e\parallel n} p^e,$$
то
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
Это и есть замкнутая форма, которую фактически кодирует DFS. Ей эквивалентно тождество по делителям
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3,$$
потому что множитель Мёбиуса оставляет только свободные от квадратов делители. Код не вычисляет сумму по делителям напрямую, но это равенство удобно для проверки формулы для простых степеней и мультипликативности.
Сумма раскладывается на вклад числа \(1\), вклад простых и вклад остальных составных ветвей. Для простых имеем
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Поэтому реализация строит две префиксные таблицы по простым:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
Их разность равна
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
Обе таблицы стартуют с простых префиксов по всем целым числам, а затем составные вклады вычитаются простое за простым. Для кубов используется формула
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
Для характера по модулю \(4\) целочисленный префикс периодичен:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
Значения \(\left\lfloor n/i\right\rfloor\) сильно повторяются, поэтому нет смысла хранить таблицы для всех \(1\le x\le n\). Реализация держит префиксную информацию только на сжатом множестве
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
Тем самым размер таблиц уменьшается с \(O(n)\) до \(O(\sqrt n)\). После построения префиксов на этом множестве DFS перечисляет мультипликативные ветви в порядке возрастания простых, что автоматически устраняет двойной счёт. Правило каждой ветви таково:
$$\text{первое появление }p \Rightarrow p^3-\chi_4(p),\qquad \text{каждое дополнительное появление }p \Rightarrow \times p^3.$$
Префиксные таблицы позволяют сразу добавить все случаи, когда к текущей ветви присоединяется ровно один больший простой, а рекурсия отвечает за произведения с несколькими большими простыми.
Локальная формула даёт
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
Следовательно,
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
что совпадает с контрольным значением, используемым в нативных реализациях.
Сначала реализации на C++ и Java строят все простые числа до \(\lfloor\sqrt n\rfloor\). Затем они формируют две сжатые префиксные таблицы по простым: одну для \(\sum_{p\le x} p^3\), другую для \(\sum_{p\le x}\chi_4(p)\). Каждая таблица начинает с соответствующего префикса по всем целым числам, после чего применяется преобразование в духе решета, убирающее составные вклады и оставляющее только простые.
После вычитания одной таблицы из другой реализация получает быстрый доступ к \(\sum_{p\le x}(p^3-\chi_4(p))\) для каждого нужного сжатого аргумента \(x\). Далее DFS перечисляет составные мультипликативные ветви в порядке возрастания простых. Когда в ветвь входит новый простой, используется фактор \(p^3-\chi_4(p)\); когда тот же простой повторяется, добавляется ещё один множитель \(p^3\). Префиксные таблицы позволяют пакетно учесть все продолжения ветви одним большим простым, а рекурсия обрабатывает более глубокие произведения.
Итоговая формула имеет вид
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+\text{составной вклад DFS}\pmod{10^9+7}.$$
Python-реализация намеренно минимальна: при необходимости она компилирует и запускает нативный решатель, а затем возвращает разобранный числовой результат.
Размер сжатого множества значений \(\lfloor n/i\rfloor\) равен \(O(\sqrt n)\), следовательно, память также равна \(O(\sqrt n)\). Две префиксные трансформации по простым работают на этом сжатом домене, а не на всём отрезке \(1,\dots,n\); в стандартном анализе Min_25 это даёт примерно \(O(n^{3/4}/\log n)\) операций. DFS по допустимым произведениям простых степеней существенно меньше прямого перебора до \(n\) и практичен для \(n=10^{12}\). В целом метод строго сублинеен по \(n\).
الكمية المطلوبة هي دالة جمع \(G(n)\) محسوبة بترديد \(10^9+7\)، وفي إدخال Project Euler الفعلي يكون \(n=10^{12}\). من تنفيذات C++ وJava يتضح أن الحد الذي يُجمع هو دالة ضربية، وأن سلوكه المحلي يعتمد على ما إذا كان العدد الأولي الفردي يحقق \(p\equiv 1\pmod 4\) أو \(p\equiv 3\pmod 4\).
الحرف الديريشليه المستعمل هنا هو
$$\chi_4(m)=\begin{cases} 0,& 2\mid m,\\ 1,& m\equiv 1\pmod 4,\\ -1,& m\equiv 3\pmod 4. \end{cases}$$
ومن مساهمات الأعداد الأولية وقواها نحصل على الحد الضربي
$$a(1)=1,\qquad a(p^e)=p^{3e}\left(1-\frac{\chi_4(p)}{p^3}\right)=p^{3e}-\chi_4(p)p^{3e-3}.$$
إذن الكمية المطلوب حسابها هي
$$G(n)=\sum_{m\le n} a(m)\pmod{10^9+7}.$$
المرور المباشر حتى \(10^{12}\) غير عملي، لذلك يعتمد الحل على جمع بين جداول بادئات أولية مضغوطة وDFS يعدد جداءات قوى الأعداد الأولية المسموح بها.
يمكن إعادة بناء الطريقة كلها من حقيقتين واضحتين في التنفيذات: الظهور الأول للعدد الأولي يعطي الوزن \(p^3-\chi_4(p)\)، وكل نسخة إضافية من العدد الأولي نفسه تضرب المساهمة بعامل جديد هو \(p^3\).
بالنسبة إلى عدد أولي \(p\)، تكون المساهمة الأولى
$$w(p)=p^3-\chi_4(p).$$
ومن ثم تصبح الحالات الثلاث
$$w(2)=8,\qquad w(p)=p^3-1\ (p\equiv 1\pmod 4),\qquad w(p)=p^3+1\ (p\equiv 3\pmod 4).$$
هذه هي البصمة الحسابية للمسألة: الأعداد الأولية من النمط \(1\bmod 4\) و\(3\bmod 4\) تُعاملان بشكل مختلف تماماً عبر الحرف \(\chi_4\).
إذا كان \(p\) موجوداً بالفعل في أحد الفروع، فإن زيادة الأس بمقدار \(1\) تضرب المساهمة المحلية في \(p^3\). لذلك
$$a(p^e)=w(p)\,p^{3(e-1)}=(p^3-\chi_4(p))p^{3(e-1)}=p^{3e}-\chi_4(p)p^{3e-3}.$$
وعلى وجه الخصوص، عندما \(p=2\) نحصل ببساطة على \(2^{3e}\) لأن \(\chi_4(2)=0\). أما في حالة الأوليات الفردية، فحد التصحيح يساوي نسخة واحدة من \(p^{3e-3}\) وتحدد إشارته بقاعدة \(p\bmod 4\).
بما أن الفروع المرتبطة بأوليات مختلفة مستقلة عن بعضها، فإذا كتبنا
$$n=\prod_{p^e\parallel n} p^e,$$
فإننا نحصل على
$$a(n)=\prod_{p^e\parallel n} a(p^e)=n^3\prod_{p\mid n}\left(1-\frac{\chi_4(p)}{p^3}\right).$$
وهذه هي الصيغة المغلقة التي يحققها DFS فعلياً. وهناك صيغة مكافئة على صورة مجموع على القواسم:
$$a(n)=\sum_{d\mid n}\mu(d)\chi_4(d)\left(\frac{n}{d}\right)^3.$$
وبسبب عامل Möbius لا تبقى إلا القواسم الخالية من المربعات. لا تستخدم الشيفرة هذه الصيغة بشكل مباشر، لكنها تؤكد صحة قاعدة قوى الأوليات وتوضح الضربية بصورة صريحة.
يمكن تفكيك المجموع الكلي إلى مساهمة \(1\)، ثم مساهمة الأعداد الأولية، ثم بقية الفروع المركبة. بالنسبة إلى الأوليات:
$$\sum_{p\le x} a(p)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
لهذا السبب تبني التنفيذات جدولين لبادئات الأعداد الأولية:
$$S_3(x)=\sum_{p\le x} p^3,\qquad C_4(x)=\sum_{p\le x}\chi_4(p).$$
والفرق بينهما هو
$$S(x)=S_3(x)-C_4(x)=\sum_{p\le x}\bigl(p^3-\chi_4(p)\bigr).$$
كلا الجدولين يبدأ من بادئات سهلة على جميع الأعداد الصحيحة، ثم تُزال مساهمات المركبات عدداً أولياً بعد آخر. بالنسبة إلى مجموع المكعبات نستخدم
$$\sum_{m=2}^{x} m^3=\left(\frac{x(x+1)}{2}\right)^2-1.$$
أما بادئة الحرف modulo \(4\) على جميع الأعداد الصحيحة فهي دورية:
$$\sum_{m=2}^{x}\chi_4(m)=\begin{cases} 0,& x\equiv 1,2\pmod 4,\\ -1,& x\equiv 0,3\pmod 4. \end{cases}$$
قيم \(\left\lfloor n/i\right\rfloor\) تتكرر كثيراً، ولذلك لا حاجة لتخزين جدول لكل \(x\) حتى \(n\). تحتفظ التنفيذات بالمعلومات فقط على المجال المضغوط
$$\mathcal{D}(n)=\left\{1,2,\dots,\left\lfloor\frac{n}{\lfloor\sqrt n\rfloor}\right\rfloor\right\}\cup\left\{\left\lfloor\frac{n}{i}\right\rfloor:1\le i\le \lfloor\sqrt n\rfloor\right\}.$$
وبذلك ينخفض حجم الجداول من \(O(n)\) إلى \(O(\sqrt n)\). بعد تجهيز بادئات الأوليات على هذا المجال، يقوم DFS بتعداد الفروع الضربية بترتيب أولي متزايد، وهذا الترتيب يمنع العد المكرر تلقائياً. القاعدة داخل كل فرع هي
$$a(p)=p^3-\chi_4(p),\qquad a(p^{e+1})=p^3\,a(p^e)\quad (e\ge 1).$$
وتسمح جداول البادئات بإضافة جميع الحالات التي يُمدَّد فيها الفرع بعدد أولي أكبر واحد دفعة واحدة، بينما تتولى العودية معالجة الجداءات الأعمق التي تحتوي على عدة أوليات أكبر.
تعطي الصيغة المحلية القيم
$$\begin{aligned} a(1)&=1,\\ a(2)&=2^3=8,\\ a(3)&=3^3\left(1+\frac{1}{3^3}\right)=28,\\ a(4)&=4^3=64,\\ a(5)&=5^3\left(1-\frac{1}{5^3}\right)=124,\\ a(6)&=a(2)a(3)=224,\\ a(7)&=7^3\left(1+\frac{1}{7^3}\right)=344,\\ a(8)&=8^3=512,\\ a(9)&=9^3\left(1+\frac{1}{3^3}\right)=756,\\ a(10)&=a(2)a(5)=992. \end{aligned}$$
ومن ثم
$$G(10)=1+8+28+64+124+224+344+512+756+992=3053,$$
وهو تماماً مقدار التحقق الذي تستخدمه التنفيذات الأصلية.
تبدأ تنفيذات C++ وJava بتوليد جميع الأعداد الأولية حتى \(\lfloor\sqrt n\rfloor\). بعد ذلك تُبنى جدولان مضغوطان لبادئات الأوليات: أحدهما لـ \(\sum_{p\le x} p^3\)، والآخر لـ \(\sum_{p\le x}\chi_4(p)\). يبدأ كل جدول من بادئة مقابلة على جميع الأعداد الصحيحة، ثم تُطبَّق عليه عملية غربلة تزيل مساهمات المركبات وتترك مساهمات الأوليات فقط.
بعد طرح أحد الجدولين من الآخر تصبح الشيفرة قادرة على الوصول سريعاً إلى \(\sum_{p\le x}(p^3-\chi_4(p))\) لكل وسيط مضغوط مطلوب \(x\). بعد ذلك يعدِّد DFS الفروع المركبة بالترتيب التصاعدي للأوليات. عند دخول أولي جديد إلى الفرع يكون العامل \(p^3-\chi_4(p)\)، وعند تكرار الأولي نفسه يضاف عامل آخر \(p^3\). تسمح جداول البادئات بحساب جميع التمديدات التي تضيف أولياً أكبر واحداً دفعة واحدة، بينما تتكفل العودية بالجداءات الأعمق.
والصيغة النهائية هي
$$G(n)=1+\sum_{p\le n}\bigl(p^3-\chi_4(p)\bigr)+R(n)\pmod{10^9+7}.$$
وهنا تمثل \(R(n)\) جميع المساهمات المركبة التي يجمعها DFS.
أما تنفيذ Python فهو طبقة ربط خفيفة: يترجم الحل الأصلي عند الحاجة، يشغله، ثم يعيد القيمة العددية بعد تحليل المخرجات.
حجم المجال المضغوط لقيم \(\lfloor n/i\rfloor\) هو \(O(\sqrt n)\)، ولذلك يكون استهلاك الذاكرة أيضاً \(O(\sqrt n)\). جدولا بادئات الأوليات يعملان على هذا المجال المضغوط بدلاً من جميع الأعداد حتى \(n\)، ووفق التحليل المعتاد لأسلوب Min_25 فإن العمل الغالب يقارب \(O(n^{3/4}/\log n)\). أما DFS الخاص بجداءات قوى الأوليات فهو أصغر بكثير من مسح مباشر حتى \(n\)، ولذلك فهو عملي عند \(n=10^{12}\). باختصار، الخوارزمية دون خطية بوضوح.