For a prime \(p\), define
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}.$$
So \(F(p)\) counts ordered triples of nonzero residues modulo \(p\) that satisfy the Fermat-type congruence \(a^3+b^3=c^3\). The goal is to compute
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
A direct \(O(p^3)\) count for every prime would be far too slow, so the solution uses the structure of the cube map on \(\mathbb F_p^\times\) and a closed formula for the difficult congruence class \(p\equiv 1\pmod 3\).
The key observation is that the number of cube roots of a nonzero residue depends entirely on the residue class of \(p\) modulo \(3\). That turns the whole problem into a clean case split.
Because \(a,b,c\) are chosen from \(\{1,\dots,p-1\}\), all three variables live in the multiplicative group \(\mathbb F_p^\times\), which has size \(p-1\).
For a nonzero residue \(s\), let \(N_p(s)\) be the number of nonzero solutions of \(x^3=s\). Then
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3).$$
So the job is to understand how many cube roots a residue has and how often \(a^3+b^3\) lands in each class.
The group \(\mathbb F_p^\times\) is cyclic of size \(p-1\). If \(p\equiv 2\pmod 3\), then \(\gcd(3,p-1)=1\), so the map
$$x\longmapsto x^3$$
is a permutation of \(\mathbb F_p^\times\). Therefore every nonzero residue has exactly one nonzero cube root.
There are \((p-1)^2\) ordered pairs \((a,b)\). Among them, exactly \(p-1\) satisfy \(a^3+b^3\equiv 0\pmod p\), because for each nonzero \(a\) there is exactly one choice of \(b\), namely \(b\equiv -a\), that cancels the sum.
Those pairs contribute nothing, since \(c\) is required to be nonzero. Every other pair contributes exactly one value of \(c\). Hence
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
The small primes fit naturally into this picture: \(F(2)=0\), while \(F(3)=2\) can be checked directly.
If \(p\equiv 1\pmod 3\), then \(3\mid (p-1)\). The cube map is no longer bijective: its kernel has size \(3\), so every nonzero cubic residue has exactly three cube roots, and non-cubic residues have none.
What remains is to measure how often \(a^3+b^3\) lands in the cubic-residue set. That is the nontrivial part of the problem, and the implementations use the classical closed form
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3),$$
where the integer \(t\) comes from a quadratic representation of \(p\). This formula is the cubic-character/Jacobi-sum evaluation encoded by the program.
For every prime \(p\equiv 1\pmod 3\), there exist integers \(u\) and \(t\) such that
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3.$$
Up to signs, this representation is unique. The sign of \(t\) matters in the formula, so once \(|t|\) is found the correct sign is chosen by the congruence condition \(t\equiv 1\pmod 3\).
Substituting that value into the closed form immediately gives \(F(p)\).
The complete evaluation is therefore
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
After applying this formula prime by prime, the required answer is obtained by summing over all primes below \(6\cdot 10^6\).
Two small primes show both branches.
For \(p=5\), we are in the easy branch \(p\equiv 2\pmod 3\), so
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
For \(p=19\), we are in the hard branch \(p\equiv 1\pmod 3\). We have
$$4p=76=27\cdot 1^2+7^2,$$
and \(7\equiv 1\pmod 3\), so \(t=7\). Therefore
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
These values agree with the formula used by the implementations.
The C++, Python, and Java implementations all follow the same plan. First they build a prime sieve up to \(6\cdot 10^6\), so each prime can be processed exactly once.
Next they precompute the monotone list
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
up to \(4\cdot 6\cdot 10^6\). This turns the search for the representation \(4p=27u^2+t^2\) into a scan over candidate values of \(27u^2\).
For each prime \(p\):
If \(p=3\), the contribution is \(2\).
If \(p\equiv 2\pmod 3\), the implementation adds \((p-1)(p-2)\).
If \(p\equiv 1\pmod 3\), it loops through the precomputed \(27u^2\) values not exceeding \(4p\), computes
$$4p-27u^2,$$
tests whether that remainder is a perfect square, and when a square is found uses its root as \(|t|\). The sign is then fixed so that \(t\equiv 1\pmod 3\), and the closed formula \((p-1)(p-8+t)\) is added to the total.
All three implementations accumulate the final sum in 64-bit arithmetic. One implementation also checks the formula against direct enumeration for small primes before printing the final total.
Let \(L=6\cdot 10^6\). The prime sieve costs \(O(L\log\log L)\) time and \(O(L)\) memory. Precomputing the values \(27u^2\) takes \(O(\sqrt L)\) time and memory.
For primes with \(p\equiv 1\pmod 3\), the representation search scans \(u\) while \(27u^2\le 4p\), so a conservative upper bound is \(O(\sqrt p)\) work per such prime. Summed over all primes, this gives the practical estimate
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
with \(O(L)\) total memory. In practice it is faster than this bound suggests, because the search stops as soon as the first valid representation is found.
Für eine Primzahl \(p\) sei
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}.$$
Damit zählt \(F(p)\) geordnete Tripel nichtverschwindender Restklassen modulo \(p\), die die fermatsche Kongruenz \(a^3+b^3=c^3\) erfüllen. Gesucht ist
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
Eine direkte Zählung wäre viel zu langsam. Deshalb nutzt die Lösung die Struktur der Abbildung \(x\mapsto x^3\) auf \(\mathbb F_p^\times\) und für den schwierigen Fall \(p\equiv 1\pmod 3\) eine geschlossene Formel.
Der zentrale Punkt ist, dass die Anzahl der Kubikwurzeln einer von null verschiedenen Restklasse allein von \(p\bmod 3\) abhängt. Genau daraus entsteht die natürliche Fallunterscheidung.
Da \(a,b,c\) aus \(\{1,\dots,p-1\}\) stammen, liegen alle drei Variablen in der multiplikativen Gruppe \(\mathbb F_p^\times\) mit \(p-1\) Elementen.
Für eine von null verschiedene Restklasse \(s\) sei \(N_p(s)\) die Anzahl der nichtnull Lösungen von \(x^3=s\). Dann gilt
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3).$$
Wir müssen also verstehen, wie viele Kubikwurzeln ein Rest besitzt und wie oft \(a^3+b^3\) in die verschiedenen Klassen fällt.
Die Gruppe \(\mathbb F_p^\times\) ist zyklisch von Ordnung \(p-1\). Ist \(p\equiv 2\pmod 3\), so gilt \(\gcd(3,p-1)=1\). Daher ist
$$x\longmapsto x^3$$
eine Permutation von \(\mathbb F_p^\times\). Jede von null verschiedene Restklasse besitzt also genau eine nichtnull Kubikwurzel.
Es gibt \((p-1)^2\) geordnete Paare \((a,b)\). Genau \(p-1\) davon erfüllen \(a^3+b^3\equiv 0\pmod p\), denn zu jedem nichtnull \(a\) gibt es genau ein \(b\equiv -a\), das die Summe aufhebt.
Diese Paare tragen nichts bei, weil \(c\) nichtnull sein muss. Alle übrigen Paare liefern genau ein \(c\). Also
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
Die kleinen Primzahlen passen dazu: \(F(2)=0\), und \(F(3)=2\) lässt sich direkt nachrechnen.
Gilt \(p\equiv 1\pmod 3\), dann teilt \(3\) die Zahl \(p-1\). Die Kubikabbildung ist jetzt nicht mehr bijektiv: Ihr Kern hat Größe \(3\), also besitzt jeder nichtnull kubische Rest genau drei Kubikwurzeln, während nichtkubische Reste keine besitzen.
Nun muss gezählt werden, wie häufig \(a^3+b^3\) selbst ein kubischer Rest ist. Genau hier steckt die tiefe Zahlentheorie, und die Implementierungen benutzen die klassische geschlossene Formel
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3),$$
wobei \(t\) aus einer quadratischen Darstellung von \(p\) stammt. Diese Formel ist die ausgewertete kubische Charakter- beziehungsweise Jacobi-Summen-Identität, auf die der Code aufgebaut ist.
Für jede Primzahl \(p\equiv 1\pmod 3\) existieren ganze Zahlen \(u\) und \(t\) mit
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3.$$
Bis auf Vorzeichen ist diese Darstellung eindeutig. Im Endresultat ist das Vorzeichen von \(t\) relevant. Deshalb wird nach dem Finden von \(|t|\) das Vorzeichen so gewählt, dass die Kongruenz \(t\equiv 1\pmod 3\) erfüllt ist.
Mit diesem \(t\) ergibt sich \(F(p)\) sofort aus der geschlossenen Formel.
Damit lautet die vollständige Auswertung
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
Die gesuchte Antwort erhält man, indem man diese Werte über alle Primzahlen unter \(6\cdot 10^6\) aufsummiert.
Zwei kleine Primzahlen zeigen beide Zweige.
Für \(p=5\) gilt \(p\equiv 2\pmod 3\), also
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
Für \(p=19\) liegt der schwierige Fall \(p\equiv 1\pmod 3\) vor. Man erhält
$$4p=76=27\cdot 1^2+7^2,$$
und \(7\equiv 1\pmod 3\), also \(t=7\). Damit folgt
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
Diese Werte stimmen mit der von den Implementierungen verwendeten Formel überein.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst bauen sie ein Primzahlsieb bis \(6\cdot 10^6\), damit jede Primzahl genau einmal verarbeitet wird.
Danach berechnen sie die monotone Liste
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
bis zur Schranke \(4\cdot 6\cdot 10^6\) vor. So wird die Suche nach Darstellungen der Form \(4p=27u^2+t^2\) zu einem linearen Durchlauf über Kandidaten für \(27u^2\).
Für jede Primzahl \(p\):
Bei \(p=3\) wird \(2\) addiert.
Bei \(p\equiv 2\pmod 3\) wird direkt \((p-1)(p-2)\) addiert.
Bei \(p\equiv 1\pmod 3\) durchläuft die Implementierung alle vorberechneten Werte \(27u^2\le 4p\), berechnet
$$4p-27u^2,$$
prüft, ob dieser Rest ein perfektes Quadrat ist, und verwendet dessen Wurzel als \(|t|\). Danach wird das Vorzeichen so festgelegt, dass \(t\equiv 1\pmod 3\), und der Term \((p-1)(p-8+t)\) zum Gesamtergebnis addiert.
Alle drei Implementierungen akkumulieren die Summe mit 64-Bit-Arithmetik. Eine Implementierung vergleicht die Formel für kleine Primzahlen zusätzlich mit direkter Enumeration.
Mit \(L=6\cdot 10^6\) kostet das Primzahlsieb \(O(L\log\log L)\) Zeit und \(O(L)\) Speicher. Die Vorberechnung der Werte \(27u^2\) benötigt \(O(\sqrt L)\) Zeit und Speicher.
Für Primzahlen mit \(p\equiv 1\pmod 3\) läuft die Darstellungssuche über alle \(u\) mit \(27u^2\le 4p\), also in einer konservativen Schranke \(O(\sqrt p)\) pro solcher Primzahl. Insgesamt ergibt sich damit die praktische Abschätzung
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
bei \(O(L)\) Gesamtspeicher. In der Praxis ist die Laufzeit geringer, weil die Suche stoppt, sobald die erste gültige Darstellung gefunden wurde.
Bir asal \(p\) için
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}$$
olsun. Yani \(F(p)\), modulo \(p\) altında \(a^3+b^3=c^3\) kongrüansını sağlayan sıralı ve sıfır olmayan kalıntı üçlülerinin sayısını verir. İstenen toplam
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
Her asal için kübik sayım yapmak çok pahalı olduğu için çözüm, \(\mathbb F_p^\times\) üzerindeki küp alma dönüşümünü inceler ve özellikle \(p\equiv 1\pmod 3\) durumunda kapalı bir formül kullanır.
Ana fikir şudur: sıfır olmayan bir kalıntının kaç farklı küp kökü olduğu, yalnızca \(p\)'nin \(3\)'e göre kalanına bağlıdır. Böylece problem doğal biçimde iki ana dala ayrılır.
\(a,b,c\) değerleri \(\{1,\dots,p-1\}\) kümesinden geldiği için hepsi \(p-1\) elemanlı çarpımsal grup \(\mathbb F_p^\times\) içinde yaşar.
Sıfır olmayan bir \(s\) kalıntısı için, \(N_p(s)\) değerini \(x^3=s\) denkleminin sıfır olmayan çözüm sayısı olarak tanımlayalım. O zaman
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3)$$
olur. Demek ki asıl mesele, hangi kalıntının kaç küp kökü olduğunu ve \(a^3+b^3\) toplamının hangi sınıflara ne sıklıkta düştüğünü anlamaktır.
\(\mathbb F_p^\times\) grubu çevrimseldir ve mertebesi \(p-1\)'dir. Eğer \(p\equiv 2\pmod 3\) ise \(\gcd(3,p-1)=1\) olur. Bu yüzden
$$x\longmapsto x^3$$
dönüşümü \(\mathbb F_p^\times\) üzerinde bir permütasyondur. Sonuç olarak sıfır olmayan her kalıntının tam bir tane sıfır olmayan küp kökü vardır.
Sıralı \((a,b)\) çiftlerinin sayısı \((p-1)^2\)'dir. Bunların tam \(p-1\) tanesinde \(a^3+b^3\equiv 0\pmod p\) olur; çünkü her sıfır olmayan \(a\) için toplamı sıfırlayan tek seçim \(b\equiv -a\)'dır.
Bu çiftler katkı vermez, çünkü \(c\) sıfır olamaz. Kalan her çift ise tam bir \(c\) üretir. Dolayısıyla
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
Küçük asallar da buna uyumludur: \(F(2)=0\) ve \(F(3)=2\) doğrudan doğrulanabilir.
\(p\equiv 1\pmod 3\) olduğunda \(3\mid (p-1)\) olur. Bu kez küp alma dönüşümü birebir değildir; çekirdeğinin boyutu \(3\)'tür. Yani sıfır olmayan bir kübik kalıntının tam üç küp kökü vardır, kübik olmayan kalıntıların ise hiç yoktur.
Asıl zor soru, \(a^3+b^3\) toplamının ne kadar sık kübik kalıntı verdiğidir. Burada devreye klasik sonuç girer ve uygulama şu kapalı formülü kullanır:
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3).$$
Buradaki \(t\), \(p\)'nin belirli bir kuadratik gösteriminden gelir. Programın kullandığı matematik, kübik karakterler ve Jacobi toplamlarının bu formüle indirgenmiş halidir.
Her \(p\equiv 1\pmod 3\) asalı için
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3$$
şeklinde tamsayılar vardır. İşaretler dışında bu temsil tektir. Formülde işaret önemli olduğu için \(|t|\) bulunduktan sonra \(t\equiv 1\pmod 3\) koşulunu sağlayan işaret seçilir.
Böylece \(t\) bulunduğunda \(F(p)\) anında hesaplanır.
Sonuç olarak tam parçalı formül şudur:
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
Aranan değer de bu katkıların \(6\cdot 10^6\)'dan küçük tüm asallar boyunca toplanmasıyla elde edilir.
İki küçük asal iki ana dalı da gösterir.
\(p=5\) için kolay daldanız, çünkü \(5\equiv 2\pmod 3\). O halde
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
\(p=19\) için ise zor dal geçerlidir, çünkü \(19\equiv 1\pmod 3\). Burada
$$4p=76=27\cdot 1^2+7^2$$
olur ve \(7\equiv 1\pmod 3\), yani \(t=7\). Böylece
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
Bu sonuçlar, uygulamanın kullandığı formülle birebir örtüşür.
C++, Python ve Java uygulamalarının üçü de aynı mantığı izler. Önce \(6\cdot 10^6\)'ya kadar bir asal eleği kurulur; böylece her asal tam bir kez işlenir.
Ardından
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
listesi \(4\cdot 6\cdot 10^6\) sınırına kadar önceden hesaplanır. Böylece \(4p=27u^2+t^2\) temsili için arama, artan bir aday listesi üzerinde yapılır.
Her asal \(p\) için:
Eğer \(p=3\) ise toplamaya \(2\) eklenir.
Eğer \(p\equiv 2\pmod 3\) ise doğrudan \((p-1)(p-2)\) eklenir.
Eğer \(p\equiv 1\pmod 3\) ise \(27u^2\le 4p\) olan önceden hesaplanmış değerler gezilir,
$$4p-27u^2$$
hesaplanır, bunun tam kare olup olmadığı sınanır ve bulunduğunda karekök \(|t|\) olarak alınır. Sonra işaret \(t\equiv 1\pmod 3\) olacak biçimde seçilir ve \((p-1)(p-8+t)\) toplam sonuca eklenir.
Üç uygulama da nihai toplamı 64 bit tamsayı aritmetiğiyle tutar. İçlerinden biri ayrıca küçük asallarda formülü doğrudan sayımla karşılaştırarak kontrol eder.
\(L=6\cdot 10^6\) olsun. Asal eleği \(O(L\log\log L)\) zamanda ve \(O(L)\) bellekte çalışır. \(27u^2\) değerlerini önceden üretmek \(O(\sqrt L)\) zaman ve bellek gerektirir.
\(p\equiv 1\pmod 3\) olan asallar için temsil araması \(27u^2\le 4p\) koşulu sürdükçe devam ettiği için her böyle asal için muhafazakâr olarak \(O(\sqrt p)\) iş yapar. Toplamda pratik tahmin
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
şeklindedir ve toplam bellek \(O(L)\)'dir. Gerçekte ilk uygun temsil bulunduğunda döngü kırıldığı için çalışma süresi bu üst sınırdan daha iyidir.
Para un número primo \(p\), definimos
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}.$$
Así, \(F(p)\) cuenta ternas ordenadas de residuos no nulos módulo \(p\) que satisfacen la congruencia de tipo fermatiano \(a^3+b^3=c^3\). Lo que se pide es calcular
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
Contar directamente para cada primo sería demasiado costoso. Por eso la solución estudia el mapa cúbico en \(\mathbb F_p^\times\) y, para la clase difícil \(p\equiv 1\pmod 3\), usa una fórmula cerrada.
La observación decisiva es que el número de raíces cúbicas de un residuo no nulo depende por completo de la clase de \(p\) módulo \(3\). Eso divide el problema en dos ramas naturales.
Como \(a,b,c\) pertenecen a \(\{1,\dots,p-1\}\), las tres variables viven en el grupo multiplicativo \(\mathbb F_p^\times\), de tamaño \(p-1\).
Para un residuo no nulo \(s\), sea \(N_p(s)\) el número de soluciones no nulas de \(x^3=s\). Entonces
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3).$$
La tarea se reduce a entender cuántas raíces cúbicas tiene cada residuo y con qué frecuencia \(a^3+b^3\) cae en cada clase.
El grupo \(\mathbb F_p^\times\) es cíclico de orden \(p-1\). Si \(p\equiv 2\pmod 3\), entonces \(\gcd(3,p-1)=1\), y por tanto
$$x\longmapsto x^3$$
es una permutación de \(\mathbb F_p^\times\). Cada residuo no nulo tiene exactamente una raíz cúbica no nula.
Hay \((p-1)^2\) pares ordenados \((a,b)\). Exactamente \(p-1\) de ellos satisfacen \(a^3+b^3\equiv 0\pmod p\), porque para cada \(a\neq 0\) existe un único \(b\equiv -a\) que anula la suma.
Esos pares no aportan nada, ya que \(c\) debe ser no nulo. Todos los demás aportan exactamente un valor de \(c\). Por consiguiente,
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
Los primos pequeños encajan de forma natural: \(F(2)=0\) y \(F(3)=2\).
Si \(p\equiv 1\pmod 3\), entonces \(3\mid (p-1)\). El mapa cúbico deja de ser biyectivo: su núcleo tiene tamaño \(3\), así que cada residuo cúbico no nulo tiene exactamente tres raíces cúbicas, mientras que los no cúbicos no tienen ninguna.
La parte difícil es medir con qué frecuencia \(a^3+b^3\) vuelve a ser un residuo cúbico. Aquí entra el resultado clásico que usan las implementaciones:
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3).$$
El entero \(t\) procede de una representación cuadrática de \(p\). En otras palabras, el programa ya incorpora la evaluación cerrada asociada a caracteres cúbicos y sumas de Jacobi.
Para todo primo \(p\equiv 1\pmod 3\) existen enteros \(u\) y \(t\) tales que
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3.$$
Salvo por signos, esta representación es única. Como el signo de \(t\) sí afecta a la fórmula final, una vez conocido \(|t|\) se elige el signo que cumple \(t\equiv 1\pmod 3\).
Con ese valor, \(F(p)\) sale de inmediato.
La evaluación completa queda así:
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
La respuesta pedida se obtiene sumando estas contribuciones para todos los primos menores que \(6\cdot 10^6\).
Dos primos pequeños muestran ambas ramas.
Para \(p=5\), estamos en el caso fácil \(p\equiv 2\pmod 3\), luego
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
Para \(p=19\), estamos en el caso difícil \(p\equiv 1\pmod 3\). Se tiene
$$4p=76=27\cdot 1^2+7^2,$$
y como \(7\equiv 1\pmod 3\), tomamos \(t=7\). Entonces
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
Estos valores coinciden con la fórmula que usan las implementaciones.
Las implementaciones en C++, Python y Java siguen exactamente el mismo plan. Primero construyen una criba de primos hasta \(6\cdot 10^6\), de modo que cada primo se procesa una sola vez.
Después precalculan la lista creciente
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
hasta \(4\cdot 6\cdot 10^6\). Eso convierte la búsqueda de una representación \(4p=27u^2+t^2\) en un recorrido sobre candidatos para \(27u^2\).
Para cada primo \(p\):
Si \(p=3\), se suma \(2\).
Si \(p\equiv 2\pmod 3\), se añade directamente \((p-1)(p-2)\).
Si \(p\equiv 1\pmod 3\), la implementación recorre los valores precalculados \(27u^2\le 4p\), calcula
$$4p-27u^2,$$
comprueba si el resto es un cuadrado perfecto y, cuando lo es, toma su raíz como \(|t|\). Luego fija el signo de manera que \(t\equiv 1\pmod 3\) y suma \((p-1)(p-8+t)\).
Las tres implementaciones acumulan el total con aritmética de 64 bits. Una de ellas además verifica la fórmula mediante enumeración directa para primos pequeños.
Sea \(L=6\cdot 10^6\). La criba de primos cuesta \(O(L\log\log L)\) tiempo y \(O(L)\) memoria. Precalcular los valores \(27u^2\) requiere \(O(\sqrt L)\) tiempo y memoria.
Para los primos con \(p\equiv 1\pmod 3\), la búsqueda de la representación recorre todos los \(u\) con \(27u^2\le 4p\), así que una cota conservadora es \(O(\sqrt p)\) trabajo por primo de esa clase. Sumando sobre todos los primos, se obtiene la estimación práctica
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
con \(O(L)\) memoria total. En la práctica es más rápido, porque la búsqueda termina en cuanto aparece la primera representación válida.
对素数 \(p\)，定义
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}$$
也就是说，\(F(p)\) 统计的是模 \(p\) 意义下所有满足 \(a^3+b^3=c^3\) 的有序非零三元组。题目要求计算
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p)$$
如果对每个素数都直接做三重枚举，代价会非常高。真正可行的方法，是分析 \(\mathbb F_p^\times\) 上的立方映射，并在较难的 \(p\equiv 1\pmod 3\) 情形下使用已经化简好的闭式公式。
整个问题的核心在于：一个非零剩余到底有几个立方根，完全取决于 \(p\) 对 \(3\) 的余数。因此自然会分成两个主要分支来处理。
由于 \(a,b,c\) 都取自 \(\{1,\dots,p-1\}\)，所以它们都属于乘法群 \(\mathbb F_p^\times\)，这个群的大小是 \(p-1\)。
对任意非零剩余 \(s\)，记 \(N_p(s)\) 为方程 \(x^3=s\) 在非零元素中的解个数。那么
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3)$$
因此问题被转化成两件事：第一，搞清楚一个非零剩余会有多少个立方根；第二，弄清楚 \(a^3+b^3\) 落到各类剩余中的频率。
\(\mathbb F_p^\times\) 是一个阶为 \(p-1\) 的循环群。如果 \(p\equiv 2\pmod 3\)，那么 \(\gcd(3,p-1)=1\)，于是映射
$$x\longmapsto x^3$$
在 \(\mathbb F_p^\times\) 上是一个置换。换句话说，每一个非零剩余恰好对应一个非零立方根。
一共有 \((p-1)^2\) 个有序对 \((a,b)\)。其中恰好有 \(p-1\) 个满足 \(a^3+b^3\equiv 0\pmod p\)，因为对每个非零 \(a\)，都恰好有一个选择 \(b\equiv -a\) 使得两项互相抵消。
这些对不会贡献任何合法的 \(c\)，因为题目要求 \(c\neq 0\)。其余每个有序对都对应唯一的非零 \(c\)。因此
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3)$$
小素数也完全吻合这一框架：\(F(2)=0\)，而 \(F(3)=2\) 可以直接手工验证。
如果 \(p\equiv 1\pmod 3\)，那么 \(3\mid (p-1)\)。这时立方映射不再是双射；它的核大小为 \(3\)。因此每个非零立方剩余恰好有三个立方根，而非立方剩余则没有立方根。
真正困难的地方，不在于“一个立方剩余有几个根”，而在于“\(a^3+b^3\) 有多大概率再次落入立方剩余集合”。这正是经典数论结果发挥作用的地方。实现使用的闭式公式是
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3)$$
这里的整数 \(t\) 并不是随意引入的，而是来自 \(p\) 的一个特殊二次型表示。换句话说，程序把立方特征和 Jacobi 和的理论结果，直接压缩成了这个一行公式。
对每个满足 \(p\equiv 1\pmod 3\) 的素数，都存在整数 \(u,t\) 使得
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3$$
这个表示除了符号之外本质上是唯一的。由于最终公式里 \(t\) 的符号会直接影响结果，所以在求出 \(|t|\) 之后，还必须选取满足 \(t\equiv 1\pmod 3\) 的符号。
一旦 \(t\) 确定，\(F(p)\) 就可以立刻由闭式公式算出。
综合起来，\(F(p)\) 的分段公式为
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
题目的最终答案，就是把这个表达式在所有小于 \(6\cdot 10^6\) 的素数上累加起来。
用两个小素数可以把两条分支都看清楚。
当 \(p=5\) 时，属于简单分支 \(p\equiv 2\pmod 3\)，因此
$$F(5)=(5-1)(5-2)=4\cdot 3=12$$
当 \(p=19\) 时，属于困难分支 \(p\equiv 1\pmod 3\)。这时
$$4p=76=27\cdot 1^2+7^2$$
而且 \(7\equiv 1\pmod 3\)，所以取 \(t=7\)。于是
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324$$
这与实现实际使用的公式完全一致。
C++、Python 和 Java 三个实现使用的是同一套算法框架。第一步是做一个上界为 \(6\cdot 10^6\) 的素数筛，这样每个素数只需要处理一次。
第二步是预先生成递增序列
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
直到 \(4\cdot 6\cdot 10^6\) 为止。这样在寻找 \(4p=27u^2+t^2\) 的表示时，就只需要扫描这些候选值。
对每个素数 \(p\)：
如果 \(p=3\)，就直接加入 \(2\)。
如果 \(p\equiv 2\pmod 3\)，就直接加入 \((p-1)(p-2)\)。
如果 \(p\equiv 1\pmod 3\)，实现会枚举所有满足 \(27u^2\le 4p\) 的预计算值，计算
$$4p-27u^2$$
再检查这个余数是不是完全平方。如果是，就把平方根当作 \(|t|\)。随后再根据 \(t\equiv 1\pmod 3\) 的条件确定符号，并把 \((p-1)(p-8+t)\) 加到总和中。
三个实现都用 64 位整数保存最终总和。其中一个实现还会在小素数范围内用直接枚举来核对公式是否正确。
记 \(L=6\cdot 10^6\)。素数筛的时间复杂度是 \(O(L\log\log L)\)，空间复杂度是 \(O(L)\)。预计算所有 \(27u^2\) 值需要 \(O(\sqrt L)\) 的时间和空间。
对满足 \(p\equiv 1\pmod 3\) 的素数，表示搜索会扫描所有满足 \(27u^2\le 4p\) 的 \(u\)，因此保守上界可写成每个这样的素数 \(O(\sqrt p)\)。总计得到实用估计
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
并且总空间仍为 \(O(L)\)。在实际运行中，这个估计偏保守，因为一旦找到第一个合法表示，搜索就会立即停止。
Для простого числа \(p\) определим
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}.$$
Итак, \(F(p)\) считает упорядоченные тройки ненулевых вычетов по модулю \(p\), удовлетворяющие ферматоподобной конгруэнции \(a^3+b^3=c^3\). Требуется вычислить сумму
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
Прямой перебор по всем тройкам для каждого простого здесь неприемлем. Поэтому решение использует структуру отображения \(x\mapsto x^3\) на \(\mathbb F_p^\times\) и закрытую формулу для трудного случая \(p\equiv 1\pmod 3\).
Главное наблюдение состоит в том, что число кубических корней ненулевого вычета полностью определяется классом \(p\) по модулю \(3\). Именно это и приводит к естественному разбиению на случаи.
Поскольку \(a,b,c\) выбираются из \(\{1,\dots,p-1\}\), все три переменные лежат в мультипликативной группе \(\mathbb F_p^\times\) размера \(p-1\).
Для ненулевого вычета \(s\) обозначим через \(N_p(s)\) число ненулевых решений уравнения \(x^3=s\). Тогда
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3).$$
Тем самым задача сводится к двум вопросам: сколько кубических корней имеет данный вычет и как часто сумма \(a^3+b^3\) попадает в ту или иную категорию вычетов.
Группа \(\mathbb F_p^\times\) циклическая и имеет порядок \(p-1\). Если \(p\equiv 2\pmod 3\), то \(\gcd(3,p-1)=1\), а значит отображение
$$x\longmapsto x^3$$
является перестановкой на \(\mathbb F_p^\times\). Следовательно, каждый ненулевой вычет имеет ровно один ненулевой кубический корень.
Существует \((p-1)^2\) упорядоченных пар \((a,b)\). Из них ровно \(p-1\) дают \(a^3+b^3\equiv 0\pmod p\), потому что для каждого ненулевого \(a\) есть единственный выбор \(b\equiv -a\), зануляющий сумму.
Такие пары не дают допустимого \(c\), поскольку \(c\) тоже должен быть ненулевым. Все остальные пары дают ровно одно значение \(c\). Поэтому
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
Малые простые вписываются сюда естественно: \(F(2)=0\), а \(F(3)=2\) проверяется напрямую.
Если \(p\equiv 1\pmod 3\), то \(3\mid (p-1)\). Тогда кубическое отображение уже не биективно: размер его ядра равен \(3\). Значит, каждый ненулевой кубический вычет имеет ровно три кубических корня, а некубические вычеты не имеют ни одного.
Сложность состоит в том, чтобы понять, как часто величина \(a^3+b^3\) сама оказывается кубическим вычетом. Здесь используется классический результат, который в реализации уже записан в виде
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3).$$
Число \(t\) приходит из специального квадратичного представления простого \(p\). Иначе говоря, теория кубических характеров и сумм Якоби уже свернута в одну компактную формулу.
Для каждого простого \(p\equiv 1\pmod 3\) существуют целые \(u\) и \(t\), такие что
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3.$$
С точностью до знаков это представление единственно. Поскольку знак \(t\) влияет на итоговое значение, после нахождения \(|t|\) выбирают тот знак, который удовлетворяет условию \(t\equiv 1\pmod 3\).
После этого \(F(p)\) сразу вычисляется по закрытой формуле.
Итак, итоговая кусочная формула имеет вид
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
Искомый ответ получается суммированием этих значений по всем простым \(p\lt 6\cdot 10^6\).
Два небольших простых показывают обе ветви.
Для \(p=5\) имеем лёгкий случай \(p\equiv 2\pmod 3\), поэтому
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
Для \(p=19\) имеем трудный случай \(p\equiv 1\pmod 3\). Здесь
$$4p=76=27\cdot 1^2+7^2,$$
и \(7\equiv 1\pmod 3\), значит \(t=7\). Следовательно,
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
Эти значения полностью совпадают с формулой, используемой в реализации.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала строится решето простых чисел до \(6\cdot 10^6\), чтобы каждый простой обрабатывался ровно один раз.
Затем заранее вычисляется возрастающий список
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
до границы \(4\cdot 6\cdot 10^6\). Это превращает поиск представления \(4p=27u^2+t^2\) в перебор кандидатов для \(27u^2\).
Для каждого простого \(p\):
Если \(p=3\), к ответу добавляется \(2\).
Если \(p\equiv 2\pmod 3\), сразу добавляется \((p-1)(p-2)\).
Если \(p\equiv 1\pmod 3\), реализация перебирает все заранее вычисленные значения \(27u^2\le 4p\), считает
$$4p-27u^2,$$
проверяет, является ли остаток полным квадратом, и при успехе берёт его корень как \(|t|\). Затем знак выбирается так, чтобы выполнялось \(t\equiv 1\pmod 3\), после чего к сумме прибавляется \((p-1)(p-8+t)\).
Во всех трёх реализациях общий результат хранится в 64-битной арифметике. Одна из реализаций дополнительно сверяет формулу с прямым перебором на малых простых.
Положим \(L=6\cdot 10^6\). Решето простых работает за \(O(L\log\log L)\) времени и использует \(O(L)\) памяти. Предварительный расчёт значений \(27u^2\) требует \(O(\sqrt L)\) времени и памяти.
Для простых с \(p\equiv 1\pmod 3\) поиск представления перебирает все \(u\), для которых \(27u^2\le 4p\), так что консервативная оценка составляет \(O(\sqrt p)\) работы на один такой простой. В сумме это даёт практическую оценку
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
при общей памяти \(O(L)\). На практике программа работает быстрее этой верхней границы, потому что поиск заканчивается сразу после первого подходящего представления.
لعدد أولي \(p\) نعرّف
$$F(p)=\#\left\{(a,b,c)\in\{1,\dots,p-1\}^3 : a^3+b^3\equiv c^3 \pmod p\right\}.$$
أي إن \(F(p)\) يحسب عدد الثلاثيات المرتبة من البواقي غير الصفرية التي تحقق العلاقة \(a^3+b^3=c^3\) بترديد \(p\). والمطلوب هو حساب
$$\sum_{\substack{p\lt 6\cdot 10^6 \\ p\text{ prime}}} F(p).$$
العد المباشر لكل ثلاثية مع كل عدد أولي سيكون بطيئاً جداً، لذلك تعتمد الحلول على بنية تطبيق التكعيب فوق \(\mathbb F_p^\times\)، وتستخدم صيغة مغلقة في الحالة الأصعب \(p\equiv 1\pmod 3\).
الفكرة الأساسية هي أن عدد الجذور التكعيبية لباقٍ غير صفري يعتمد كلياً على قيمة \(p\bmod 3\). ومن هنا ينشأ التقسيم الطبيعي للمسألة إلى حالتين رئيسيتين.
بما أن \(a,b,c\) تؤخذ من المجموعة \(\{1,\dots,p-1\}\)، فإنها جميعاً تنتمي إلى المجموعة الضربية \(\mathbb F_p^\times\) ذات الحجم \(p-1\).
ولكل باقٍ غير صفري \(s\)، لنرمز بـ \(N_p(s)\) إلى عدد الحلول غير الصفرية للمعادلة \(x^3=s\). عندئذ يصبح
$$F(p)=\sum_{a\in\mathbb F_p^\times}\sum_{b\in\mathbb F_p^\times} N_p(a^3+b^3).$$
إذن جوهر المسألة هو فهم عدد الجذور التكعيبية لكل باقٍ، وفهم مدى تكرار وقوع \(a^3+b^3\) في أصناف البواقي المختلفة.
المجموعة \(\mathbb F_p^\times\) دورية ورتبتها \(p-1\). وإذا كان \(p\equiv 2\pmod 3\)، فإن \(\gcd(3,p-1)=1\)، وبالتالي يكون التطبيق
$$x\longmapsto x^3$$
تبادلياً على \(\mathbb F_p^\times\). وهذا يعني أن كل باقٍ غير صفري يملك جذراً تكعيبياً غير صفري واحداً فقط.
عدد الأزواج المرتبة \((a,b)\) هو \((p-1)^2\). ومن بينها يوجد بالضبط \(p-1\) زوجاً تحقق \(a^3+b^3\equiv 0\pmod p\)، لأن كل قيمة غير صفرية لـ \(a\) تقابلها قيمة وحيدة \(b\equiv -a\) تلغي المجموع.
هذه الأزواج لا تسهم في \(F(p)\)، لأن \(c\) يجب أن يكون غير صفري. وكل زوج آخر يعطي قيمة وحيدة لـ \(c\). لذا نحصل على
$$F(p)=(p-1)^2-(p-1)=(p-1)(p-2)\qquad (p\equiv 2\pmod 3).$$
والأعداد الأولية الصغيرة تنسجم مع ذلك: \(F(2)=0\)، بينما \(F(3)=2\) ويمكن التحقق منها مباشرة.
إذا كان \(p\equiv 1\pmod 3\)، فإن \(3\mid (p-1)\). عندها لا يعود تطبيق التكعيب تقابلياً؛ إذ إن نواته ذات حجم \(3\). لذلك فإن كل باقٍ تكعيبي غير صفري يملك ثلاثة جذور تكعيبية، أما البواقي غير التكعيبية فلا تملك أي جذر.
الصعوبة الحقيقية ليست في عدد الجذور نفسها، بل في معرفة عدد المرات التي يكون فيها \(a^3+b^3\) باقياً تكعيبياً من جديد. هنا تدخل النتيجة الكلاسيكية التي تستخدمها الحلول:
$$F(p)=(p-1)(p-8+t)\qquad (p\equiv 1\pmod 3).$$
والعدد \(t\) يأتي من تمثيل تربيعي خاص للعدد الأولي \(p\). وبعبارة أخرى، فإن نظرية المحارف التكعيبية ومجاميع Jacobi قد اختُزلت في هذه الصيغة المغلقة.
لكل عدد أولي يحقق \(p\equiv 1\pmod 3\)، توجد أعداد صحيحة \(u\) و\(t\) بحيث
$$4p=27u^2+t^2,\qquad t\equiv 1\pmod 3.$$
وهذا التمثيل وحيد جوهرياً إذا تجاهلنا الإشارات. لكن إشارة \(t\) تؤثر فعلاً في الصيغة النهائية، لذلك بعد إيجاد \(|t|\) نختار الإشارة التي تحقق الشرط \(t\equiv 1\pmod 3\).
وبمجرد تحديد \(t\)، يصبح حساب \(F(p)\) مباشراً.
وهكذا تكون الصيغة القطعية الكاملة هي
$$F(p)= \begin{cases} 0,&p=2,\\ 2,&p=3,\\ (p-1)(p-2),&p\equiv 2\pmod 3,\\ (p-1)(p-8+t),&p\equiv 1\pmod 3,\ 4p=27u^2+t^2,\ t\equiv 1\pmod 3. \end{cases}$$
والجواب المطلوب في المسألة ينتج من جمع هذه القيم على جميع الأعداد الأولية الأصغر من \(6\cdot 10^6\).
يمكن إيضاح الفرعين بواسطة عددين أوليين صغيرين.
عندما \(p=5\)، فنحن في الحالة السهلة \(p\equiv 2\pmod 3\)، ومن ثم
$$F(5)=(5-1)(5-2)=4\cdot 3=12.$$
وعندما \(p=19\)، فنحن في الحالة الأصعب \(p\equiv 1\pmod 3\). عندئذ
$$4p=76=27\cdot 1^2+7^2,$$
ولأن \(7\equiv 1\pmod 3\)، نأخذ \(t=7\). لذلك
$$F(19)=(19-1)(19-8+7)=18\cdot 18=324.$$
وهذه القيم مطابقة تماماً للصيغة التي تعتمدها التطبيقات.
تتبع تطبيقات C++ وPython وJava الخطة نفسها. أولاً تُبنى غربال للأعداد الأولية حتى \(6\cdot 10^6\)، بحيث يُعالَج كل عدد أولي مرة واحدة فقط.
بعد ذلك تُحسب مسبقاً القائمة المتزايدة
$$27\cdot 1^2,\ 27\cdot 2^2,\ 27\cdot 3^2,\ \dots$$
حتى الحد \(4\cdot 6\cdot 10^6\). وهكذا يتحول البحث عن تمثيل من الشكل \(4p=27u^2+t^2\) إلى مسح لقيم مرشحة من نوع \(27u^2\).
لكل عدد أولي \(p\):
إذا كان \(p=3\)، تُضاف القيمة \(2\).
إذا كان \(p\equiv 2\pmod 3\)، تُضاف مباشرة القيمة \((p-1)(p-2)\).
إذا كان \(p\equiv 1\pmod 3\)، تمرّ الخوارزمية على كل قيمة محسوبة مسبقاً تحقق \(27u^2\le 4p\)، ثم تحسب
$$4p-27u^2,$$
وتختبر هل الباقي مربع كامل أم لا. فإذا كان مربعاً كاملاً، يؤخذ جذره على أنه \(|t|\)، ثم تُختار الإشارة بحيث يتحقق \(t\equiv 1\pmod 3\)، وبعدها تُضاف القيمة \((p-1)(p-8+t)\) إلى المجموع.
جميع التطبيقات الثلاثة تستخدم حساباً صحيحياً بعرض 64 بت من أجل المجموع النهائي. وأحدها يضيف أيضاً فحصاً على الأعداد الأولية الصغيرة بمقارنة الصيغة مع العد المباشر.
إذا رمزنا إلى \(L=6\cdot 10^6\)، فإن بناء غربال الأعداد الأولية يكلف \(O(L\log\log L)\) زمناً و\(O(L)\) ذاكرة. أما توليد قيم \(27u^2\) مسبقاً فيكلف \(O(\sqrt L)\) زمناً وذاكرة.
بالنسبة إلى الأعداد الأولية التي تحقق \(p\equiv 1\pmod 3\)، فإن البحث عن التمثيل يفحص جميع القيم \(u\) التي تحقق \(27u^2\le 4p\)، ولذا يمكن إعطاء حد محافظ مقداره \(O(\sqrt p)\) لكل عدد أولي من هذا النوع. وبجمع ذلك نحصل على التقدير العملي
$$O\!\left(L\log\log L+\pi(L)\sqrt L\right)$$
مع ذاكرة كلية قدرها \(O(L)\). وفي الواقع يكون الأداء أفضل من هذا الحد، لأن البحث يتوقف بمجرد العثور على أول تمثيل صالح.