For each odd prime \(p\), the computation associates an integer \(g(p)\) obtained from a modular expression involving powers of \(2\), and then sums these values:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ prime}}} g(p).$$
The difficulty is that the exponent \(2^p\) is already enormous, and the quantity for each prime is not taken merely modulo \(p\) but depends on how a congruence lifts from modulo \(p\) to modulo \(p^2\). The implemented method therefore combines exponent reduction, modular inversion, a controlled lift to \(p^2\), and a prime sieve.
Fix an odd prime \(p\). The implementation computes \(g(p)\) by first finding a residue modulo \(p\), then lifting it to a compatible residue modulo \(p^2\), and finally extracting the multiple of \(p\) that measures the difference between the two levels.
We begin with the residue
$$b_p \equiv 2^{2^p}\pmod{p}.$$
Computing \(2^{2^p}\) directly is hopeless, but Fermat's little theorem gives \(2^{p-1}\equiv 1 \pmod p\), so exponents can be reduced modulo \(p-1\). Therefore
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
If we define
$$a_p = 2^p \bmod (p-1),$$
then the needed residue becomes
$$b_p \equiv 2^{a_p}\pmod p.$$
This reduces a gigantic exponent tower to two ordinary modular exponentiations.
Because \(p\) is odd, the number \(2\) is invertible modulo \(p\). Its inverse is
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
since \(2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p\).
Now choose the unique residue \(h_p\in\{0,1,\dots,p-1\}\) satisfying
$$2h_p\equiv b_p\pmod p.$$
Equivalently,
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
This is the modular analogue of dividing the residue \(b_p\) by \(2\).
Next form the residue
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
The key observation is that \(w_p\) has the same value as \(b_p\) modulo \(p\). Indeed, by Fermat's little theorem,
$$2^p \equiv 2 \pmod p,$$
so
$$w_p \equiv h_p\,2 \equiv b_p \pmod p.$$
Therefore the difference \(w_p-b_p\) is divisible by \(p\). If \(w_p\ge b_p\), we can divide that difference directly by \(p\). If \(w_p<b_p\), we add one full modulus \(p^2\) first, which preserves the congruence class modulo \(p^2\) while making the representative nonnegative.
Thus \(g(p)\) is defined by
$$g(p)=\frac{\delta_p}{p},$$
where \(\delta_p\) is the unique integer with
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2.$$
Because \(w_p\equiv b_p\pmod p\), the numerator is automatically a multiple of \(p\).
The residue \(b_p\) captures the value of the large power modulo \(p\). The residue \(w_p\) is a compatible lift modulo \(p^2\). Since the two agree modulo \(p\), their difference must be of the form \(p\cdot q\). The number \(g(p)\) is exactly this quotient:
$$w_p=b_p+p\,g(p)\quad\text{inside } \mathbb{Z}/p^2\mathbb{Z}.$$
So \(g(p)\) measures the first correction term that appears when passing from arithmetic modulo \(p\) to arithmetic modulo \(p^2\).
Once \(g(p)\) is available for one prime, the target quantity is just
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ prime}}} g(p).$$
The remaining algorithmic task is therefore to enumerate every odd prime below \(n\) and apply the same modular procedure to each one.
This prime is large enough to show every ingredient while still fitting on paper.
First reduce the tower exponent:
$$a_{31}=2^{31}\bmod 30=8.$$
Hence
$$b_{31}\equiv 2^8\equiv 256\equiv 8 \pmod{31}.$$
Now solve the halving congruence:
$$2h_{31}\equiv 8\pmod{31},$$
so the least nonnegative solution is
$$h_{31}=4.$$
Next compute the lifted power modulo \(31^2=961\):
$$2^{31}\equiv 374\pmod{961}.$$
Therefore
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
Now subtract the modulo-\(31\) residue:
$$535-8=527=31\cdot 17.$$
So
$$g(31)=17.$$
This is one of the checkpoints used by the implementations. Another small aggregate checkpoint is
$$G(100)=474.$$
The C++, Python, and Java implementations all follow the same structure. They first generate a primality table up to \(n\) with the classical sieve of Eratosthenes, then iterate only over odd primes. For each such prime, they perform three modular exponentiations: one modulo \(p-1\) to compress the exponent, one modulo \(p\) to recover the residue \(2^{2^p}\bmod p\), and one modulo \(p^2\) to build the lifted quantity.
After that, the implementation multiplies by the modular inverse of \(2\) modulo \(p\) in order to solve \(2x\equiv b_p\pmod p\). The lifted residue is compared with the modulo-\(p\) residue, and if the subtraction would be negative, one copy of \(p^2\) is added before dividing by \(p\). That guarantees an integer quotient in the canonical range. The resulting \(g(p)\) is then accumulated into the final sum.
The C++ and Java versions include dedicated modular multiplication routines to keep intermediate products safe under 64-bit arithmetic, while the Python version relies on built-in arbitrary-precision integers and modular exponentiation.
The sieve up to \(n\) costs \(O(n\log\log n)\) time and \(O(n)\) memory. For each prime \(p<n\), the algorithm performs a constant number of fast modular exponentiations, each taking \(O(\log p)\) modular multiplications. Summed over all primes, the arithmetic work is
$$O\!\left(\sum_{p \lt n,\ p\text{ prime}}\log p\right)=O(\pi(n)\log n),$$
which is smaller than the sieve term for large \(n\). Thus the full method runs in \(O(n\log\log n+\pi(n)\log n)\) time and uses \(O(n)\) memory.
Zu jeder ungeraden Primzahl \(p\) wird eine ganze Zahl \(g(p)\) aus einem modularen Ausdruck mit Potenzen von \(2\) bestimmt und anschließend aufsummiert:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ prim}}} g(p).$$
Die Schwierigkeit besteht darin, dass schon der Exponent \(2^p\) riesig ist und die gesuchte Größe nicht nur von einer Rechnung modulo \(p\), sondern vom Übergang von modulo \(p\) zu modulo \(p^2\) abhängt. Die Lösung verbindet deshalb Exponentenreduktion, modulares Invertieren, einen kontrollierten Lift auf \(p^2\) und ein Primzahlsieb.
Fixiere eine ungerade Primzahl \(p\). Die Implementierung berechnet \(g(p)\), indem sie zuerst einen Rest modulo \(p\) bestimmt, diesen zu einem kompatiblen Rest modulo \(p^2\) anhebt und dann den dabei entstehenden Faktor vor \(p\) isoliert.
Zunächst betrachten wir
$$b_p \equiv 2^{2^p}\pmod{p}.$$
Direkt ist diese Potenz unbrauchbar groß. Nach dem kleinen Satz von Fermat gilt jedoch \(2^{p-1}\equiv 1\pmod p\), daher dürfen Exponenten modulo \(p-1\) reduziert werden. Somit
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
Setzt man
$$a_p = 2^p \bmod (p-1),$$
so genügt
$$b_p \equiv 2^{a_p}\pmod p.$$
Aus einem riesigen Exponenten wird also eine normale modulare Potenzierung.
Da \(p\) ungerade ist, besitzt \(2\) ein Inverses modulo \(p\), nämlich
$$2^{-1}\equiv \frac{p+1}{2}\pmod p.$$
Nun wählen wir den eindeutigen Rest \(h_p\in\{0,1,\dots,p-1\}\) mit
$$2h_p\equiv b_p\pmod p.$$
Äquivalent dazu gilt
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
Damit wird der Rest \(b_p\) modular durch \(2\) geteilt.
Als Nächstes definieren wir den Rest
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
Wichtig ist, dass \(w_p\) modulo \(p\) denselben Wert wie \(b_p\) hat. Wegen
$$2^p \equiv 2\pmod p$$
folgt nämlich
$$w_p \equiv h_p\,2 \equiv b_p \pmod p.$$
Also ist \(w_p-b_p\) durch \(p\) teilbar. Falls \(w_p\ge b_p\), können wir direkt subtrahieren. Falls \(w_p<b_p\), addieren wir einmal \(p^2\), damit der Repräsentant nichtnegativ wird, ohne die Restklasse modulo \(p^2\) zu ändern.
Dann definieren wir
$$g(p)=\frac{\delta_p}{p},$$
wobei \(\delta_p\) die eindeutige Zahl mit
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2$$
ist. Die Teilbarkeit durch \(p\) ist automatisch gesichert.
Der Rest \(b_p\) ist die Information auf der Ebene modulo \(p\). Der Rest \(w_p\) ist dazu ein kompatibler Lift modulo \(p^2\). Weil beide modulo \(p\) übereinstimmen, muss ihre Differenz die Form \(p\cdot q\) besitzen. Genau dieser Quotient ist
$$w_p=b_p+p\,g(p)\quad\text{in } \mathbb{Z}/p^2\mathbb{Z}.$$
Man kann \(g(p)\) daher als erste Korrektur verstehen, die sichtbar wird, sobald man von modulo \(p\) zu modulo \(p^2\) übergeht.
Ist \(g(p)\) für ein festes \(p\) bekannt, lautet die Zielgröße schlicht
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ prim}}} g(p).$$
Algorithmisch bleibt also nur, alle ungeraden Primzahlen unterhalb von \(n\) zu finden und auf jede dieselbe modulare Prozedur anzuwenden.
Zuerst reduzieren wir den Exponenten:
$$a_{31}=2^{31}\bmod 30=8.$$
Damit erhält man
$$b_{31}\equiv 2^8\equiv 256\equiv 8 \pmod{31}.$$
Nun lösen wir
$$2h_{31}\equiv 8\pmod{31},$$
also ist der kleinste nichtnegative Rest
$$h_{31}=4.$$
Außerdem gilt modulo \(31^2=961\)
$$2^{31}\equiv 374\pmod{961}.$$
Daraus folgt
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
Die Differenz ist
$$535-8=527=31\cdot 17,$$
also
$$g(31)=17.$$
Ein weiterer Kontrollwert der Implementierungen lautet
$$G(100)=474.$$
Die C++-, Python- und Java-Implementierungen folgen derselben Struktur. Zuerst erzeugen sie mit dem Sieb des Eratosthenes eine Primtabelle bis \(n\). Danach iterieren sie nur über ungerade Primzahlen. Für jede davon werden drei modulare Potenzierungen ausgeführt: einmal modulo \(p-1\) zur Exponentenreduktion, einmal modulo \(p\) für den Rest \(2^{2^p}\bmod p\) und einmal modulo \(p^2\) für den Lift.
Anschließend löst die Implementierung die Kongruenz \(2x\equiv b_p\pmod p\) durch Multiplikation mit dem inversen Element von \(2\). Danach wird der modulo-\(p^2\)-Rest mit dem modulo-\(p\)-Rest verglichen. Falls die Subtraktion negativ wäre, wird einmal \(p^2\) addiert; erst dann erfolgt die Division durch \(p\). So entsteht ein wohldefinierter ganzzahliger Beitrag \(g(p)\), der in die Gesamtsumme eingeht.
Die C++- und Java-Fassungen verwenden eigene Routinen für sichere modulare Multiplikation unter 64-Bit-Arithmetik. Python kann dafür seine eingebauten Ganzzahlen beliebiger Größe und die eingebaute modulare Potenzfunktion nutzen.
Das Sieb bis \(n\) benötigt \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Für jede Primzahl \(p<n\) werden konstant viele schnelle modulare Potenzierungen ausgeführt, jeweils in \(O(\log p)\) modularen Multiplikationen. Insgesamt ergibt das für den arithmetischen Teil
$$O\!\left(\sum_{p \lt n,\ p\text{ prim}}\log p\right)=O(\pi(n)\log n).$$
Damit läuft das Gesamtverfahren in \(O(n\log\log n+\pi(n)\log n)\) Zeit bei \(O(n)\) Speicherbedarf.
Her tek asal \(p\) için, \(2\) kuvvetleriyle kurulan modüler bir ifadeden bir \(g(p)\) tamsayısı üretilir ve sonra bu değerler toplanır:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ asal}}} g(p).$$
Zorluk şuradadır: \(2^p\) üssü bile çok büyüktür ve aranan katkı sadece \(\bmod p\) seviyesinden değil, aynı kalıntının \(\bmod p^2\) seviyesine nasıl kaldırıldığından da etkilenir. Bu yüzden çözüm; üs indirgeme, modüler ters alma, \(p^2\)'ye kontrollü kaldırma ve asal eleğini birlikte kullanır.
Sabit bir tek asal \(p\) alalım. Uygulama \(g(p)\) değerini, önce \(\bmod p\) altında bir kalıntı bularak, sonra bunu \(\bmod p^2\) altında uyumlu bir kalıntıya kaldırarak ve son olarak aradaki \(p\) katsayısını ayırarak hesaplar.
Önce şu kalıntıya bakıyoruz:
$$b_p \equiv 2^{2^p}\pmod{p}.$$
Bu sayıyı doğrudan hesaplamak mümkün değildir. Ama Fermat'nın küçük teoremine göre \(2^{p-1}\equiv 1\pmod p\) olduğundan, üsler \(p-1\) moduna indirilebilir. Dolayısıyla
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
Eğer
$$a_p = 2^p \bmod (p-1)$$
dersek, ihtiyaç duyulan kalıntı
$$b_p \equiv 2^{a_p}\pmod p$$
olur. Böylece devasa bir üs kulesi yerine iki normal modüler üs alma işlemi yeterli hale gelir.
\(p\) tek asal olduğu için \(2\)'nin mod \(p\) altında tersi vardır. Bu ters
$$2^{-1}\equiv \frac{p+1}{2}\pmod p$$
şeklindedir; çünkü \(2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p\).
Şimdi \(\{0,1,\dots,p-1\}\) aralığında bulunan ve
$$2h_p\equiv b_p\pmod p$$
koşulunu sağlayan tek kalıntıyı seçelim. Eşdeğer biçimde
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p$$
olur. Bu adım, \(b_p\) kalıntısını modüler anlamda \(2\)'ye bölmektedir.
Ardından
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2$$
kalıntısını oluştururuz. Kritik nokta, \(w_p\)'nin mod \(p\) altında yine \(b_p\) ile aynı değere sahip olmasıdır. Gerçekten, Fermat'nın küçük teoremi ile
$$2^p\equiv 2\pmod p$$
olduğundan
$$w_p \equiv h_p\cdot 2 \equiv b_p \pmod p$$
elde edilir. Demek ki \(w_p-b_p\) mutlaka \(p\)'ye bölünür. Eğer \(w_p\ge b_p\) ise doğrudan çıkarırız. Eğer \(w_p<b_p\) ise bir kez \(p^2\) ekleriz; böylece aynı \(\bmod p^2\) sınıfında kalıp negatif olmayan temsilciyi seçmiş oluruz.
Böylece
$$g(p)=\frac{\delta_p}{p}$$
tanımlanır; burada \(\delta_p\) şu koşulları sağlayan tek sayıdır:
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2.$$
\(w_p\equiv b_p\pmod p\) olduğu için pay zaten \(p\)'nin katıdır.
\(b_p\), büyük kuvvetin mod \(p\) altındaki bilgisidir. \(w_p\) ise bunun mod \(p^2\) altında uyumlu bir kaldırımıdır. İkisi mod \(p\) altında eşit olduğundan farkları mutlaka \(p\cdot q\) biçimindedir. Aranan sayı tam olarak bu katsayıdır:
$$w_p=b_p+p\,g(p)\quad\text{ifadesi } \mathbb{Z}/p^2\mathbb{Z}\text{ içinde geçerlidir.}$$
Başka bir deyişle \(g(p)\), mod \(p\) düzeyinden mod \(p^2\) düzeyine geçerken ortaya çıkan ilk düzeltme terimidir.
Tek bir asal için katkı hesaplandıktan sonra hedef nicelik
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ asal}}} g(p)$$
olur. Bu yüzden geriye kalan iş, \(n\)'den küçük tüm tek asalları bulmak ve aynı modüler prosedürü her biri için uygulamaktır.
Bu örnek, yöntemin tüm parçalarını açıkça gösterir.
Önce üssü indirgeriz:
$$a_{31}=2^{31}\bmod 30=8.$$
Dolayısıyla
$$b_{31}\equiv 2^8\equiv 256\equiv 8\pmod{31}.$$
Şimdi
$$2h_{31}\equiv 8\pmod{31}$$
denkliğini çözeriz ve en küçük negatif olmayan çözüm
$$h_{31}=4$$
olur. Ayrıca \(31^2=961\) için
$$2^{31}\equiv 374\pmod{961}.$$
Buradan
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}$$
elde edilir. Son fark
$$535-8=527=31\cdot 17$$
olduğundan
$$g(31)=17$$
sonucuna ulaşılır. Uygulamadaki bir diğer küçük doğrulama değeri de
$$G(100)=474$$
eşitliğidir.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce Eratosthenes eleği ile \(n\)'e kadar bir asallık tablosu oluşturulur. Daha sonra yalnızca tek asallar dolaşılır. Her asal için üç modüler üs alma işlemi yapılır: biri \(p-1\) modunda üs sıkıştırmak için, biri \(p\) modunda \(2^{2^p}\bmod p\) kalıntısını bulmak için, biri de \(p^2\) modunda kaldırılmış kalıntıyı üretmek için.
Bunun ardından uygulama, \(2x\equiv b_p\pmod p\) denkliğini çözmek amacıyla \(2\)'nin modüler tersini kullanır. Sonra \(p^2\) modundaki kalıntı ile \(p\) modundaki kalıntı karşılaştırılır. Çıkarma işlemi negatif olacaksa bir kez \(p^2\) eklenir ve ancak ondan sonra \(p\)'ye bölünür. Böylece tam sayılı ve kanonik bir \(g(p)\) katkısı elde edilir. Son adımda tüm bu katkılar toplanır.
C++ ve Java sürümleri, 64 bit sınırları içinde ara çarpımları güvenli tutmak için özel modüler çarpma yordamları kullanır. Python sürümü ise yerleşik büyük tamsayı desteğine ve yerleşik modüler üs alma işlevine dayanır.
\(n\)'e kadar elek kurmanın maliyeti \(O(n\log\log n)\) zaman ve \(O(n)\) bellektir. Her \(p<n\) asalı için sabit sayıda hızlı modüler üs alma yapılır; bunların her biri \(O(\log p)\) modüler çarpım gerektirir. Dolayısıyla aritmetik kısım toplamda
$$O\!\left(\sum_{p \lt n,\ p\text{ asal}}\log p\right)=O(\pi(n)\log n)$$
mertebesindedir. Sonuç olarak tüm yöntem \(O(n\log\log n+\pi(n)\log n)\) zamanda çalışır ve \(O(n)\) bellek kullanır.
Para cada primo impar \(p\), el cálculo asocia un entero \(g(p)\) obtenido a partir de una expresión modular con potencias de \(2\), y después suma todos esos aportes:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ primo}}} g(p).$$
La dificultad es doble: el exponente \(2^p\) ya es gigantesco, y además la cantidad buscada no depende solo del residuo módulo \(p\), sino de cómo ese residuo se eleva de módulo \(p\) a módulo \(p^2\). Por eso la solución mezcla reducción de exponentes, inversión modular, elevación controlada a \(p^2\) y una criba de primos.
Fijemos un primo impar \(p\). La implementación calcula \(g(p)\) obteniendo primero un residuo módulo \(p\), luego construyendo un residuo compatible módulo \(p^2\) y finalmente extrayendo el múltiplo de \(p\) que separa ambos niveles.
El primer residuo relevante es
$$b_p \equiv 2^{2^p}\pmod{p}.$$
No se puede calcular directamente, pero el pequeño teorema de Fermat da \(2^{p-1}\equiv 1\pmod p\), así que los exponentes pueden reducirse módulo \(p-1\). En consecuencia,
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
Si definimos
$$a_p = 2^p \bmod (p-1),$$
entonces basta calcular
$$b_p \equiv 2^{a_p}\pmod p.$$
La torre enorme queda reducida a dos exponenciaciones modulares normales.
Como \(p\) es impar, \(2\) es invertible módulo \(p\). Su inverso es
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
porque \(2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p\).
Elegimos ahora el único residuo \(h_p\in\{0,1,\dots,p-1\}\) que satisface
$$2h_p\equiv b_p\pmod p.$$
De forma equivalente,
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
Esta es la versión modular de dividir por \(2\).
Después formamos
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
La observación central es que \(w_p\) coincide con \(b_p\) al reducir módulo \(p\). En efecto, como
$$2^p \equiv 2\pmod p,$$
se obtiene
$$w_p \equiv h_p\,2 \equiv b_p \pmod p.$$
Por tanto, \(w_p-b_p\) es divisible por \(p\). Si \(w_p\ge b_p\), se resta directamente. Si \(w_p<b_p\), se añade una copia de \(p^2\) antes de restar para mantener un representante no negativo de la misma clase módulo \(p^2\).
Así se define
$$g(p)=\frac{\delta_p}{p},$$
donde \(\delta_p\) es el único entero tal que
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2.$$
La divisibilidad por \(p\) es automática porque \(w_p\equiv b_p\pmod p\).
El residuo \(b_p\) describe el valor de la gran potencia a nivel módulo \(p\). El residuo \(w_p\) es una elevación compatible a nivel módulo \(p^2\). Como ambos coinciden módulo \(p\), su diferencia debe ser de la forma \(p\cdot q\). Ese cociente es precisamente
$$w_p=b_p+p\,g(p)\quad\text{en } \mathbb{Z}/p^2\mathbb{Z}.$$
En otras palabras, \(g(p)\) mide la primera corrección visible al pasar de módulo \(p\) a módulo \(p^2\).
Una vez calculado \(g(p)\) para un primo, la cantidad buscada es
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ primo}}} g(p).$$
Por eso el resto del trabajo consiste en enumerar todos los primos impares menores que \(n\) y aplicar el mismo procedimiento modular a cada uno.
Este caso muestra todas las piezas del método sin que las cuentas sean demasiado largas.
Primero reducimos el exponente:
$$a_{31}=2^{31}\bmod 30=8.$$
Luego
$$b_{31}\equiv 2^8\equiv 256\equiv 8 \pmod{31}.$$
Ahora resolvemos
$$2h_{31}\equiv 8\pmod{31},$$
y el menor residuo no negativo es
$$h_{31}=4.$$
Además, módulo \(31^2=961\),
$$2^{31}\equiv 374\pmod{961}.$$
Por tanto,
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
La diferencia es
$$535-8=527=31\cdot 17,$$
de donde
$$g(31)=17.$$
Otro punto de control útil que aparece en las implementaciones es
$$G(100)=474.$$
Las implementaciones en C++, Python y Java siguen la misma estructura. Primero construyen una tabla de primalidad hasta \(n\) con la criba de Eratóstenes. Después recorren solo los primos impares. Para cada primo realizan tres exponenciaciones modulares: una módulo \(p-1\) para comprimir el exponente, una módulo \(p\) para obtener el residuo \(2^{2^p}\bmod p\), y una módulo \(p^2\) para construir la elevación.
Luego la implementación multiplica por el inverso modular de \(2\) para resolver \(2x\equiv b_p\pmod p\). El residuo elevado se compara con el residuo módulo \(p\); si la resta sería negativa, se suma una vez \(p^2\) antes de dividir por \(p\). Así se obtiene un cociente entero bien definido, que es la contribución \(g(p)\). Finalmente se acumulan todas las contribuciones.
Las versiones en C++ y Java usan multiplicación modular segura para no desbordar los productos intermedios en 64 bits. La versión en Python aprovecha enteros de precisión arbitraria y la exponenciación modular incorporada.
La criba hasta \(n\) cuesta \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. Para cada primo \(p<n\), el algoritmo hace un número constante de exponenciaciones modulares rápidas, cada una en \(O(\log p)\) multiplicaciones modulares. Sumando sobre todos los primos, el trabajo aritmético es
$$O\!\left(\sum_{p \lt n,\ p\text{ primo}}\log p\right)=O(\pi(n)\log n).$$
En conjunto, el método completo corre en \(O(n\log\log n+\pi(n)\log n)\) tiempo y usa \(O(n)\) memoria.
对每个奇素数 \(p\)，都定义一个由 \(2\) 的幂所构成的模表达式对应的整数 \(g(p)\)，然后把这些值加总起来：
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ 为素数}}} g(p).$$
难点有两层。第一层是指数 \(2^p\) 已经极大，不能直接构造；第二层是所求量并不只依赖模 \(p\) 下的结果，而是依赖这个结果如何从模 \(p\) 提升到模 \(p^2\)。因此实现采用了指数降维、模逆元、从 \(p\) 到 \(p^2\) 的提升，以及素数筛这几部分共同完成计算。
固定一个奇素数 \(p\)。实现对 \(g(p)\) 的计算思路是：先求出一个模 \(p\) 的剩余类，再构造与之兼容的模 \(p^2\) 的剩余类，最后把两者相差的那一份 \(p\) 倍系数提取出来。
首先关注下面这个模 \(p\) 的值：
$$b_p \equiv 2^{2^p}\pmod{p}.$$
直接计算 \(2^{2^p}\) 显然不现实。但由于 \(p\) 是奇素数，费马小定理告诉我们
$$2^{p-1}\equiv 1\pmod p.$$
这意味着指数可以按 \(p-1\) 取模来缩减，所以
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
若记
$$a_p = 2^p \bmod (p-1),$$
那么真正需要计算的就只是
$$b_p \equiv 2^{a_p}\pmod p.$$
原本看起来像指数塔的问题，就被压缩成了两次普通的快速模幂。
因为 \(p\) 是奇数，\(2\) 在模 \(p\) 意义下可逆，其逆元为
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
因为
$$2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p.$$
于是我们选择唯一的 \(h_p\in\{0,1,\dots,p-1\}\)，使得
$$2h_p\equiv b_p\pmod p.$$
等价地也可以写成
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
这一步的意义就是在模 \(p\) 下把 \(b_p\) “除以 \(2\)”。
接下来定义
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
这里最关键的观察是：\(w_p\) 在模 \(p\) 下与 \(b_p\) 完全一致。原因是
$$2^p\equiv 2\pmod p,$$
于是
$$w_p \equiv h_p\cdot 2 \equiv b_p\pmod p.$$
因此 \(w_p-b_p\) 一定可以被 \(p\) 整除。如果 \(w_p\ge b_p\)，那么直接作差即可；如果 \(w_p<b_p\)，就先加上一个完整的模数 \(p^2\)，这样既不改变模 \(p^2\) 的同余类，又能保证得到非负代表元。
于是定义
$$g(p)=\frac{\delta_p}{p},$$
其中 \(\delta_p\) 是满足
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2$$
的唯一整数。因为 \(w_p\equiv b_p\pmod p\)，所以这个分子天然是 \(p\) 的倍数。
\(b_p\) 记录的是大幂在模 \(p\) 层面的信息，\(w_p\) 则是与之兼容的模 \(p^2\) 层面的提升。既然两者在模 \(p\) 下相同，它们的差就必定具有形式 \(p\cdot q\)。这个商正是题目所需要的局部贡献：
$$w_p=b_p+p\,g(p)\quad\text{在 } \mathbb{Z}/p^2\mathbb{Z}\text{ 中成立。}$$
可以把 \(g(p)\) 理解为从模 \(p\) 过渡到模 \(p^2\) 时出现的第一阶修正项。
当单个素数的贡献 \(g(p)\) 得到以后，目标量就是
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ 为素数}}} g(p).$$
于是剩下的算法任务就很直接了：枚举所有小于 \(n\) 的奇素数，对每个素数重复同样的模运算流程，然后把结果加起来。
这个例子足够具体，能够把全部步骤都展示出来。
先压缩指数：
$$a_{31}=2^{31}\bmod 30=8.$$
因此
$$b_{31}\equiv 2^8\equiv 256\equiv 8\pmod{31}.$$
接着解同余方程
$$2h_{31}\equiv 8\pmod{31},$$
得到最小非负解
$$h_{31}=4.$$
再计算模 \(31^2=961\) 下的幂：
$$2^{31}\equiv 374\pmod{961}.$$
所以
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
此时作差：
$$535-8=527=31\cdot 17.$$
于是得到
$$g(31)=17.$$
实现中还使用了一个较小的汇总校验值：
$$G(100)=474.$$
C++、Python 和 Java 实现采用的是同一条算法路线。首先用埃拉托斯特尼筛建立到 \(n\) 为止的素数表，然后只遍历奇素数。对于每个素数，程序都会进行三次模幂运算：第一次在模 \(p-1\) 下压缩指数，第二次在模 \(p\) 下得到 \(2^{2^p}\bmod p\) 的剩余类，第三次在模 \(p^2\) 下构造提升后的剩余类。
接下来，程序利用 \(2\) 在模 \(p\) 下的逆元来解方程 \(2x\equiv b_p\pmod p\)。得到提升后的剩余类后，再与模 \(p\) 的剩余类比较；如果直接相减会得到负数，就先补上一份 \(p^2\)，再除以 \(p\)。这样就能保证最终商是一个定义明确的整数，也就是该素数对应的 \(g(p)\)。所有素数的贡献最终累加成答案。
C++ 与 Java 版本额外实现了安全的模乘步骤，以避免 64 位整数中间乘积溢出。Python 版本则依赖语言自带的大整数和内建模幂运算。
筛法到 \(n\) 的时间复杂度是 \(O(n\log\log n)\)，空间复杂度是 \(O(n)\)。对于每个 \(p<n\) 的素数，算法执行常数次快速模幂，每次需要 \(O(\log p)\) 次模乘。因此全部算术部分的总代价为
$$O\!\left(\sum_{p \lt n,\ p\text{ 为素数}}\log p\right)=O(\pi(n)\log n).$$
综合起来，总复杂度为 \(O(n\log\log n+\pi(n)\log n)\)，空间复杂度为 \(O(n)\)。
Для каждого нечётного простого числа \(p\) вычисляется целое значение \(g(p)\), построенное из модульного выражения с степенями двойки, после чего все такие значения суммируются:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ простое}}} g(p).$$
Сложность состоит в том, что показатель \(2^p\) уже огромен, а искомый вклад определяется не только вычислением по модулю \(p\), но и тем, как соответствующий остаток поднимается с уровня \(p\) на уровень \(p^2\). Поэтому решение сочетает редукцию показателя, обращение по модулю, контролируемый подъём к модулю \(p^2\) и решето простых чисел.
Зафиксируем нечётное простое \(p\). Реализация получает \(g(p)\) в три этапа: сначала находит остаток по модулю \(p\), затем строит совместимый остаток по модулю \(p^2\), а потом выделяет коэффициент при \(p\), который отделяет один уровень от другого.
Сначала рассматривается величина
$$b_p \equiv 2^{2^p}\pmod{p}.$$
Вычислять такую степень напрямую бессмысленно. Но по малой теореме Ферма
$$2^{p-1}\equiv 1\pmod p,$$
поэтому показатель можно сократить по модулю \(p-1\). Значит,
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
Если ввести обозначение
$$a_p = 2^p \bmod (p-1),$$
то достаточно вычислить
$$b_p \equiv 2^{a_p}\pmod p.$$
Таким образом, гигантская степень заменяется двумя обычными быстрыми модульными возведениями в степень.
Поскольку \(p\) нечётно, число \(2\) обратимо по модулю \(p\). Его обратный элемент равен
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
так как \(2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p\).
Выберем единственный остаток \(h_p\in\{0,1,\dots,p-1\}\), для которого
$$2h_p\equiv b_p\pmod p.$$
То же самое можно записать как
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
Это и есть модульный аналог деления остатка \(b_p\) на \(2\).
Теперь строится число
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
Ключевой факт состоит в том, что \(w_p\) совпадает с \(b_p\) по модулю \(p\). Действительно,
$$2^p\equiv 2\pmod p,$$
следовательно,
$$w_p \equiv h_p\,2 \equiv b_p\pmod p.$$
Значит, разность \(w_p-b_p\) делится на \(p\). Если \(w_p\ge b_p\), разность можно брать напрямую. Если же \(w_p<b_p\), сначала добавляется один полный модуль \(p^2\), что сохраняет тот же класс по модулю \(p^2\), но делает представителя неотрицательным.
После этого определяется
$$g(p)=\frac{\delta_p}{p},$$
где \(\delta_p\) - единственное число, удовлетворяющее условиям
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2.$$
Поскольку \(w_p\equiv b_p\pmod p\), числитель автоматически кратен \(p\).
Остаток \(b_p\) описывает значение большой степени на уровне модуля \(p\). Остаток \(w_p\) - это совместимый подъём на уровень модуля \(p^2\). Так как они совпадают по модулю \(p\), их разность обязана иметь вид \(p\cdot q\). Именно этот коэффициент и является искомой величиной:
$$w_p=b_p+p\,g(p)\quad\text{в кольце } \mathbb{Z}/p^2\mathbb{Z}.$$
Иными словами, \(g(p)\) измеряет первую поправку, возникающую при переходе от арифметики по модулю \(p\) к арифметике по модулю \(p^2\).
Когда вклад одного простого найден, искомая функция равна
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ простое}}} g(p).$$
Следовательно, остаётся перечислить все нечётные простые меньше \(n\) и применить к каждому тот же модульный алгоритм.
Этот пример достаточно нагляден и при этом остаётся вычислимым вручную.
Сначала сокращаем показатель:
$$a_{31}=2^{31}\bmod 30=8.$$
Затем
$$b_{31}\equiv 2^8\equiv 256\equiv 8\pmod{31}.$$
Теперь решаем сравнение
$$2h_{31}\equiv 8\pmod{31},$$
и получаем минимальный неотрицательный остаток
$$h_{31}=4.$$
Далее, по модулю \(31^2=961\),
$$2^{31}\equiv 374\pmod{961}.$$
Следовательно,
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
Разность равна
$$535-8=527=31\cdot 17,$$
откуда
$$g(31)=17.$$
Ещё один малый контрольный результат, используемый в реализациях:
$$G(100)=474.$$
Реализации на C++, Python и Java устроены одинаково. Сначала с помощью решета Эратосфена строится таблица простоты до \(n\). Затем перебираются только нечётные простые числа. Для каждого простого выполняются три модульных возведения в степень: одно по модулю \(p-1\) для сокращения показателя, одно по модулю \(p\) для получения остатка \(2^{2^p}\bmod p\), и одно по модулю \(p^2\) для построения подъёма.
После этого реализация умножает на обратный к \(2\) элемент по модулю \(p\), чтобы решить сравнение \(2x\equiv b_p\pmod p\). Поднятый остаток сравнивается с остатком по модулю \(p\); если прямое вычитание было бы отрицательным, добавляется одна копия \(p^2\), и только затем выполняется деление на \(p\). Так получается корректный целый вклад \(g(p)\), который добавляется к общей сумме.
Версии на C++ и Java дополнительно используют безопасное модульное умножение, чтобы не переполнять 64-битные промежуточные произведения. В Python это перекладывается на встроенные длинные целые числа и встроенную модульную степень.
Решето до \(n\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Для каждого простого \(p<n\) выполняется постоянное число быстрых модульных возведений в степень, каждое за \(O(\log p)\) модульных умножений. В сумме арифметическая часть имеет сложность
$$O\!\left(\sum_{p \lt n,\ p\text{ простое}}\log p\right)=O(\pi(n)\log n).$$
Итак, полная сложность равна \(O(n\log\log n+\pi(n)\log n)\), а объём памяти равен \(O(n)\).
لكل عدد أولي فردي \(p\)، تُعرَّف قيمة صحيحة \(g(p)\) انطلاقًا من تعبير معياري يعتمد على قوى العدد \(2\)، ثم تُجمَع هذه القيم جميعًا:
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ أولي}}} g(p).$$
تكمن الصعوبة في أمرين: الأس \(2^p\) نفسه ضخم جدًا، كما أن القيمة المطلوبة لا تعتمد فقط على الحساب بترديد \(p\)، بل على كيفية رفع الباقي نفسه من ترديد \(p\) إلى ترديد \(p^2\). لذلك يجمع الحل بين اختزال الأس، والمعكوس الضربي بترديد \(p\)، والرفع المنضبط إلى \(p^2\)، وغربال للأعداد الأولية.
لنثبت عددًا أوليًا فرديًا \(p\). تحسب الخوارزمية \(g(p)\) عبر ثلاث أفكار متتابعة: إيجاد باقٍ بترديد \(p\)، ثم بناء باقٍ منسجم معه بترديد \(p^2\)، ثم استخراج معامل \(p\) الذي يفصل بين المستويين.
نبدأ بالباقي
$$b_p \equiv 2^{2^p}\pmod{p}.$$
لا يمكن حساب هذه القوة مباشرة، لكن مبرهنة فيرما الصغرى تعطينا
$$2^{p-1}\equiv 1\pmod p,$$
وبالتالي يمكن اختزال الأس modulo \(p-1\). لذا
$$2^{2^p}\equiv 2^{\,2^p\bmod (p-1)}\pmod p.$$
إذا عرّفنا
$$a_p = 2^p \bmod (p-1),$$
فإن المطلوب يصبح ببساطة
$$b_p \equiv 2^{a_p}\pmod p.$$
وهكذا تتحول بنية أسية هائلة إلى عمليتي أس معياري عاديتين.
بما أن \(p\) عدد فردي، فإن \(2\) قابل للعكس بترديد \(p\). ومعكوسه هو
$$2^{-1}\equiv \frac{p+1}{2}\pmod p,$$
لأن
$$2\cdot \frac{p+1}{2}=p+1\equiv 1\pmod p.$$
نختار الآن الباقي الوحيد \(h_p\in\{0,1,\dots,p-1\}\) الذي يحقق
$$2h_p\equiv b_p\pmod p.$$
وبصورة مكافئة يمكن كتابة
$$h_p \equiv b_p\cdot \frac{p+1}{2}\pmod p.$$
هذه الخطوة تمثل القسمة المعيارية على \(2\).
بعد ذلك نكوّن
$$w_p \equiv h_p\,2^p \pmod{p^2},\qquad 0\le w_p \lt p^2.$$
الملاحظة الأساسية هي أن \(w_p\) يطابق \(b_p\) عند الاختزال بترديد \(p\). فبما أن
$$2^p\equiv 2\pmod p,$$
فإن
$$w_p \equiv h_p\,2 \equiv b_p\pmod p.$$
إذن الفرق \(w_p-b_p\) من مضاعفات \(p\) حتمًا. إذا كان \(w_p\ge b_p\) نطرح مباشرة. وإذا كان \(w_p<b_p\) نضيف نسخة واحدة من \(p^2\) قبل الطرح حتى نحصل على ممثل غير سالب من نفس الفئة بترديد \(p^2\).
بعد ذلك نعرّف
$$g(p)=\frac{\delta_p}{p},$$
حيث \(\delta_p\) هو العدد الوحيد الذي يحقق
$$\delta_p \equiv w_p-b_p \pmod{p^2},\qquad 0\le \delta_p \lt p^2.$$
وبما أن \(w_p\equiv b_p\pmod p\)، فإن البسط قابل للقسمة على \(p\) تلقائيًا.
يمثل \(b_p\) المعلومة الموجودة على مستوى الحساب بترديد \(p\)، بينما يمثل \(w_p\) رفعًا منسجمًا لها على مستوى \(p^2\). ولأنهما متساويان بترديد \(p\)، فلا بد أن يكون الفرق بينهما على صورة \(p\cdot q\). هذا المعامل هو بالضبط القيمة المطلوبة:
$$w_p=b_p+p\,g(p)\quad\text{داخل } \mathbb{Z}/p^2\mathbb{Z}.$$
أي أن \(g(p)\) يقيس أول حد تصحيحي يظهر عند الانتقال من الحساب بترديد \(p\) إلى الحساب بترديد \(p^2\).
بعد حساب مساهمة أولية واحدة، تصبح الكمية النهائية
$$G(n)=\sum_{\substack{3\le p \lt n\\ p\text{ أولي}}} g(p).$$
ومن ثم فالمهمة الخوارزمية المتبقية هي تعداد جميع الأوليات الفردية الأصغر من \(n\)، ثم تطبيق الإجراء المعياري نفسه على كل واحد منها.
هذا المثال يكفي لإظهار جميع مكونات الطريقة بوضوح.
أولًا نختزل الأس:
$$a_{31}=2^{31}\bmod 30=8.$$
ومن ثم
$$b_{31}\equiv 2^8\equiv 256\equiv 8\pmod{31}.$$
نحل الآن
$$2h_{31}\equiv 8\pmod{31},$$
فنحصل على أصغر حل غير سالب
$$h_{31}=4.$$
كذلك لدينا، بترديد \(31^2=961\)،
$$2^{31}\equiv 374\pmod{961}.$$
لذلك
$$w_{31}\equiv 4\cdot 374=1496\equiv 535\pmod{961}.$$
وبالتالي
$$535-8=527=31\cdot 17,$$
ومنها
$$g(31)=17.$$
كما أن قيمة تحقق صغيرة مستخدمة في التطبيقات هي
$$G(100)=474.$$
تتبع تطبيقات C++ وPython وJava البنية نفسها. تبدأ أولًا ببناء جدول أولية حتى \(n\) باستخدام غربال إراتوستينس، ثم تمر فقط على الأوليات الفردية. ولكل عدد أولي تُجرى ثلاث عمليات أس معياري: واحدة بترديد \(p-1\) لضغط الأس، وواحدة بترديد \(p\) للحصول على الباقي \(2^{2^p}\bmod p\)، وواحدة بترديد \(p^2\) لبناء الرفع.
بعد ذلك تستخدم الخوارزمية المعكوس المعياري للعدد \(2\) لحل المقارنة \(2x\equiv b_p\pmod p\). ثم يُقارن الباقي المرفوع بالباقي الأصلي بترديد \(p\). فإذا كان الطرح سيعطي قيمة سالبة، تُضاف نسخة واحدة من \(p^2\) قبل القسمة على \(p\). بهذه الطريقة نحصل على قيمة صحيحة ومحددة جيدًا لـ \(g(p)\)، ثم تُجمع جميع هذه القيم لإنتاج الناتج النهائي.
في نسختي C++ وJava توجد معالجة خاصة للضرب المعياري حتى تبقى النواتج الوسيطة آمنة ضمن حدود 64 بت. أما Python فيعتمد على الأعداد الصحيحة ذات الدقة غير المحدودة وعلى عملية الأس المعياري المدمجة.
بناء الغربال حتى \(n\) يكلف \(O(n\log\log n)\) زمنًا و\(O(n)\) ذاكرة. ولكل عدد أولي \(p<n\)، تنفذ الخوارزمية عددًا ثابتًا من عمليات الأس المعياري السريع، وكل واحدة منها تحتاج إلى \(O(\log p)\) من الضربات المعيارية. لذلك يكون مجموع الجزء الحسابي
$$O\!\left(\sum_{p \lt n,\ p\text{ أولي}}\log p\right)=O(\pi(n)\log n).$$
إذًا يعمل الحل كاملًا بزمن \(O(n\log\log n+\pi(n)\log n)\) ويستخدم ذاكرة \(O(n)\).