We need the value of
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ is a cube}}} n.$$
A direct scan up to \(10^{10}\) would be hopelessly slow, even with a fast totient routine. The key is to describe exactly which prime-exponent patterns make \(\varphi(n^2)\) a perfect cube, and then construct only those \(n\). The numerical Project Euler answer itself is intentionally omitted here.
Write the prime factorization of \(n\) as
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
Only finitely many exponents are nonzero. The entire solution is built around turning the cube condition on \(\varphi(n^2)\) into congruence constraints modulo \(3\).
Euler's totient function is multiplicative on coprime arguments, and for prime powers we have
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
Applying this to \(n^2=\prod_{p \mid n} p^{2e_p}\) yields
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
Equivalently, since \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\), we also obtain the compact identity
$$\varphi(n^2)=n\varphi(n).$$
This factorization is what exposes the prime exponents that must be checked modulo \(3\).
An integer is a perfect cube if and only if every prime exponent in its factorization is divisible by \(3\). Using the \(p\)-adic valuation \(\nu_q(m)\), this becomes
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{for every prime }q.$$
From the product formula above, each prime \(q\) receives contributions from two sources:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
The first term is the exponent contributed by the \(q\)-part of \(n\) itself. The second term records how often \(q\) appears inside the factors \(p-1\) contributed by every chosen prime \(p\).
The code processes primes in descending order. This is crucial because every prime divisor of \(p-1\) is strictly smaller than \(p\). Therefore, once the search reaches a prime \(q\), no later unprocessed prime can create a new \(q\)-contribution through a factor of the form \(p-1\).
So when \(q\) is examined, the residue
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
is already final. The array residue_mod3 stores exactly these pending residues. This makes the decision at each prime local rather than global, which is why the DFS can prune so aggressively.
Suppose the current residue at prime \(q\) is \(c\in\{0,1,2\}\).
If \(q\) is excluded from \(n\), then its own contribution \(2e_q-1\) does not exist. Since no smaller future prime can add more \(q\)-valuation, exclusion is legal only when \(c=0\).
If \(q\) is included with exponent \(e_q\), then we must satisfy
$$c+(2e_q-1)\equiv 0\pmod 3.$$
Solving modulo \(3\) gives
$$e_q\equiv c+2\pmod 3.$$
Hence the minimal admissible exponents are
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
This is exactly the branch structure used in the implementation. Residue \(0\) means the prime is optional; residues \(1\) and \(2\) force inclusion with the smallest matching exponent class.
A small nontrivial valid example is
$$72=2^3\cdot 3^2.$$
Using the prime-power formula,
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
The residue interpretation is illuminating. Prime \(3\) may start with exponent \(2\) because residue \(0\) requires the class \(e_3\equiv 2\pmod 3\). But \(3-1=2\) contributes one pending factor of \(2\), so when the DFS later reaches prime \(2\) it sees residue \(c=1\). Then
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
and the minimal choice is \(e_2=3\). This is how the search reconstructs \(72\) from congruence data alone.
Once a minimal valid base solution \(n_0\) is fixed, every included prime exponent may be increased by multiples of \(3\):
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
This preserves the cube condition because adding \(3\) to an exponent changes \(2e_p-1\) by \(6\), which is \(0\pmod 3\), while the factors \(p-1\) remain unchanged. The program therefore enumerates each minimal base only once, and then sums the entire cube-power family attached to it.
The solver first builds a smallest-prime-factor sieve up to \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). That range is enough for minimal base factors: whenever a new prime is introduced from residue \(0\), its smallest admissible exponent is \(2\), so it must satisfy \(p^2 \lt 10^{10}\).
Next, the code pre-factors every \(p-1\) and stores only the exponents modulo \(3\) in factors_mod3_of_p_minus_1. During DFS, choosing a prime \(p\) simply adds those stored contributions into residue_mod3.
The DFS proceeds from large primes to small primes. At each step it reads the current residue, decides whether the prime is excluded, optional, or forced, multiplies the current base by the smallest valid power, and updates the residue table. A useful prune appears when the residue is \(0\) but even \(p^2\) would exceed the limit: then that prime cannot start a new branch and is skipped deterministically.
When the search reaches the end, it has produced one minimal base solution. The auxiliary recursion multiplier_sum_rec then sums all admissible multipliers \(1,p^3,p^6,\dots\) for the included primes, so the C++, Java, and Python versions all count whole families without rediscovering them one by one.
The preprocessing stage is essentially a sieve plus factorizations of \(p-1\) for primes up to \(\sqrt{L}\), where \(L=10^{10}\). The DFS itself does not have a neat closed-form worst-case bound; in the abstract it is exponential in the number of candidate primes, but in practice the tree is much smaller because residues frequently force a unique decision and the limit cuts off large branches early.
Compared with brute-force totient evaluation for every \(n \lt 10^{10}\), the savings are enormous. Memory usage stays modest: mainly the SPF table, the precomputed factor lists, the residue array, and the recursion stack.
Gesucht ist der Wert von
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ ein Kubus ist}}} n.$$
Ein direkter Durchlauf bis \(10^{10}\) wäre selbst mit schneller Totientenberechnung unpraktikabel. Deshalb beschreibt die Lösung nicht alle Kandidaten einzeln, sondern charakterisiert genau jene Primexponenten-Muster, für die \(\varphi(n^2)\) ein perfekter Kubus wird. Der numerische Projekt-Euler-Endwert wird hier bewusst nicht ausgeschrieben.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
Nur endlich viele Exponenten sind ungleich null. Die ganze Methode besteht darin, die Kubusbedingung für \(\varphi(n^2)\) in Kongruenzbedingungen modulo \(3\) zu übersetzen.
Die Eulersche Phi-Funktion ist für teilerfremde Argumente multiplikativ, und für Primzahlpotenzen gilt
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
Auf \(n^2=\prod_{p \mid n} p^{2e_p}\) angewandt ergibt das
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
Äquivalent dazu erhält man wegen \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\) auch
$$\varphi(n^2)=n\varphi(n).$$
Gerade diese Zerlegung macht sichtbar, welche Primexponenten am Ende modulo \(3\) kontrolliert werden müssen.
Eine ganze Zahl ist genau dann ein perfekter Kubus, wenn jeder Primexponent in ihrer Zerlegung durch \(3\) teilbar ist. Mit der \(p\)-adischen Bewertung \(\nu_q(m)\) lautet die Bedingung also
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{für jede Primzahl }q.$$
Aus der Produktformel folgt, dass jeder Primfaktor \(q\) aus zwei Quellen Beiträge erhält:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
Der erste Term stammt aus der eigenen \(q\)-Potenz von \(n\), der zweite zählt, wie oft \(q\) in den Faktoren \(p-1\) der ausgewählten Primzahlen vorkommt.
Der Code verarbeitet Primzahlen in absteigender Reihenfolge. Das ist entscheidend, weil jeder Primteiler von \(p-1\) strikt kleiner als \(p\) ist. Sobald die Suche also eine Primzahl \(q\) erreicht, kann keine später behandelte kleinere Primzahl einen neuen \(q\)-Beitrag über einen Faktor \(p-1\) erzeugen.
Wenn \(q\) betrachtet wird, ist daher das Residuum
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
bereits endgültig. Das Array residue_mod3 speichert genau diese noch auszugleichenden Residuen. Dadurch wird die Entscheidung an jeder Primzahl lokal und nicht global.
Sei \(c\in\{0,1,2\}\) das aktuelle Residuum an der Primzahl \(q\).
Wird \(q\) nicht in \(n\) aufgenommen, fehlt ihr eigener Beitrag \(2e_q-1\). Da keine kleinere spätere Primzahl weiteres \(q\) liefern kann, ist Ausschluss nur dann erlaubt, wenn \(c=0\).
Wird \(q\) mit Exponent \(e_q\) aufgenommen, muss gelten
$$c+(2e_q-1)\equiv 0\pmod 3.$$
Modulo \(3\) ergibt das
$$e_q\equiv c+2\pmod 3.$$
Die kleinsten zulässigen Exponenten sind also
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
Genau diese Fallunterscheidung benutzt die Implementierung. Residuum \(0\) bedeutet: Primzahl ist optional. Residuum \(1\) oder \(2\) bedeutet: Die Primzahl wird mit der kleinsten passenden Exponentenklasse erzwungen.
Ein kleines, aber nichttriviales gültiges Beispiel ist
$$72=2^3\cdot 3^2.$$
Mit der Primzahlpotenz-Formel folgt
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
Die Residuen-Sicht macht den Mechanismus transparent. Für \(3\) darf man mit Exponent \(2\) starten, weil bei Residuum \(0\) die Klasse \(e_3\equiv 2\pmod 3\) gefordert ist. Aber \(3-1=2\) erzeugt einen offenen \(2\)-Beitrag. Wenn die DFS später die Primzahl \(2\) erreicht, sieht sie also \(c=1\). Dann gilt
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
und die kleinste Möglichkeit ist \(e_2=3\). So rekonstruiert die Suche \(72\) allein aus den Kongruenzbedingungen.
Ist eine minimale gültige Basislösung \(n_0\) gefunden, dürfen die Exponenten aller enthaltenen Primzahlen um Vielfache von \(3\) erhöht werden:
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
Das erhält die Kubusbedingung, denn eine Erhöhung des Exponenten um \(3\) vergrößert \(2e_p-1\) um \(6\), also um \(0\pmod 3\), und die Faktoren \(p-1\) ändern sich überhaupt nicht. Daher zählt das Programm jede Minimalbasis nur einmal und summiert anschließend die ganze zugehörige Kubuspotenz-Familie.
Zuerst baut der Solver ein Sieb der kleinsten Primteiler bis \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). Dieser Bereich genügt für minimale Basisfaktoren: Wenn eine neue Primzahl aus Residuum \(0\) eingeführt wird, ist ihr kleinster zulässiger Exponent \(2\), also muss \(p^2 \lt 10^{10}\) gelten.
Danach wird für jede Primzahl \(p\) die Zahl \(p-1\) faktorisiert, und es werden nur die Exponenten modulo \(3\) in factors_mod3_of_p_minus_1 gespeichert. Wählt die DFS eine Primzahl \(p\), addiert sie genau diese vorberechneten Beiträge in residue_mod3.
Die DFS läuft von großen zu kleinen Primzahlen. An jedem Schritt liest sie das aktuelle Residuum, entscheidet über Ausschluss, Optionalität oder Zwang, multipliziert die aktuelle Basis mit der kleinsten gültigen Potenz und aktualisiert die Residuentabelle. Ein wichtiges Pruning tritt auf, wenn das Residuum \(0\) ist, aber schon \(p^2\) die Schranke überschreiten würde: Dann kann diese Primzahl keinen neuen Zweig mehr eröffnen und wird deterministisch übersprungen.
Am Ende der DFS liegt eine minimale Basislösung vor. Die Hilfsrekursion multiplier_sum_rec summiert anschließend alle zulässigen Multiplikatoren \(1,p^3,p^6,\dots\) für die bereits enthaltenen Primzahlen. C++, Java und Python implementieren also dieselbe Struktur: erst Minimalbasen erzeugen, dann ganze Familien addieren.
Die Vorverarbeitung besteht im Wesentlichen aus einem Sieb und Faktorisierungen von \(p-1\) für Primzahlen bis \(\sqrt{L}\) mit \(L=10^{10}\). Für die eigentliche DFS gibt es keine besonders elegante geschlossene Worst-Case-Formel; abstrakt ist der Suchbaum exponentiell in der Zahl der Kandidaten, praktisch aber viel kleiner, weil Residuen oft nur eine einzige Entscheidung zulassen und die Schranke große Äste früh abschneidet.
Gegenüber einer naiven Totientenprüfung für alle \(n \lt 10^{10}\) ist das ein dramatischer Gewinn. Der Speicherverbrauch bleibt moderat: benötigt werden hauptsächlich SPF-Tabelle, vorberechnete Faktorenlisten, Residuenarray und Rekursionsstack.
Aranan değer şudur:
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ tam küp}}} n.$$
\(10^{10}\) sınırına kadar bütün \(n\) değerlerini tek tek taramak, hızlı bir totient yordamıyla bile pratik değildir. Bu yüzden çözüm, hangi asal üs düzenlerinin \(\varphi(n^2)\)'yi tam küp yaptığına doğrudan karar verip yalnızca o \(n\)'leri inşa eder. Sayısal Project Euler cevabı burada bilinçli olarak verilmez.
\(n\)'in asal çarpanlara ayrılışını
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0$$
şeklinde yazalım. Sıfır olmayan üs sayısı sonludur. Tüm çözüm, \(\varphi(n^2)\)'nin küp olma şartını \(3\)'e göre kalıntı koşullarına çevirmek üzerine kuruludur.
Euler totient fonksiyonu aralarında asal sayılar üzerinde çarpımsaldır ve asal kuvvetler için
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$$
eşitliği vardır. Bunu \(n^2=\prod_{p \mid n} p^{2e_p}\) ifadesine uygularsak
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1)$$
elde edilir. Ayrıca \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\) olduğundan
$$\varphi(n^2)=n\varphi(n)$$
kimliği de doğrudan çıkar. Bu çarpan ayrışımı, hangi asal üslerin mod \(3\) kontrol edileceğini açık hale getirir.
Bir tamsayı ancak ve ancak asal çarpan ayrışımındaki her üs \(3\)'e bölünebiliyorsa tam küptür. \(q\) asalının \(m\) içindeki üssünü gösteren \(\nu_q(m)\) notasyonuyla şart
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{her asal }q\text{ için}$$
haline gelir. Yukarıdaki çarpım formülünden her \(q\) için iki katkı kaynağı olduğu görülür:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
İlk terim, \(q\) asalı gerçekten \(n\)'de varsa kendi kuvvetinden gelen katkıdır. İkinci terim ise seçilen bütün asalların \(p-1\) çarpanları içinde \(q\)'nun kaç kez göründüğünü sayar.
Kod, asalları büyükten küçüğe işler. Bunun kritik nedeni şudur: \(p-1\)'in her asal böleni \(p\)'den küçüktür. Dolayısıyla arama \(q\) asalına geldiğinde, daha sonra işlenecek hiçbir küçük asal \(q\) için yeni bir \(\nu_q(p-1)\) katkısı üretemez.
Bu yüzden \(q\) ele alınırken
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
kalıntısı artık kesindir. Koddaki residue_mod3 dizisi tam olarak bu henüz dengelenmemiş kalıntıları tutar. Böylece her asaldaki karar, küresel değil yerel hale gelir ve budama çok güçlenir.
\(q\) asalı için eldeki kalıntı \(c\in\{0,1,2\}\) olsun.
Eğer \(q\), \(n\)'ye hiç dahil edilmezse kendi katkısı olan \(2e_q-1\) terimi oluşmaz. Gelecekteki daha küçük asallar da ek \(q\)-üssü üretemeyeceğinden, dışlama ancak \(c=0\) ise mümkündür.
\(q\), üs \(e_q\) ile dahil edilirse şu koşul sağlanmalıdır:
$$c+(2e_q-1)\equiv 0\pmod 3.$$
Buradan mod \(3\)'te
$$e_q\equiv c+2\pmod 3$$
çıkar. Dolayısıyla en küçük geçerli üsler
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1$$
olur. Uygulamadaki dal yapısı tam olarak budur: kalıntı \(0\) ise asal opsiyoneldir; \(1\) ya da \(2\) ise uygun en küçük üs sınıfıyla zorunlu hale gelir.
Küçük ama öğretici bir geçerli örnek
$$72=2^3\cdot 3^2$$
sayısıdır. Asal kuvvet formülünü uygularsak
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3$$
elde edilir. Kalıntı açısından bakınca mekanizma daha net görünür. \(3\) asalı, kalıntı \(0\) iken \(e_3\equiv 2\pmod 3\) sınıfından başlamalıdır; en küçük seçim \(e_3=2\)'dir. Fakat \(3-1=2\) olduğundan bu seçim, \(2\) asalı için bir adet bekleyen katkı üretir. DFS daha sonra \(2\)'ye geldiğinde \(c=1\) görür ve
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3$$
zorunluluğu doğar. En küçük seçim \(e_2=3\)'tür. Böylece arama, ilgisiz sayıları denemeden yalnızca kalıntı dengelemesiyle \(72\)'yi yeniden kurar.
Minimal bir temel çözüm \(n_0\) bulunduğunda, dahil edilmiş her asalın üssü \(3\)'ün katları kadar artırılabilir:
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
Bu işlem küp şartını bozmaz; çünkü üsse \(3\) eklemek, \(2e_p-1\) değerini \(6\) artırır ve \(6\equiv 0\pmod 3\)'tür. Ayrıca \(p-1\) çarpanları hiç değişmez. Bu yüzden program her minimal tabanı yalnızca bir kez üretip bağlı olduğu tüm küp-kuvvet ailesini topluca sayar.
Çözücü önce \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\)'e kadar en küçük asal bölen tablosu kurar. Bu aralık minimal temel asallar için yeterlidir; çünkü kalıntı \(0\) iken yeni bir asalın ilk geçerli üssü \(2\) olduğundan, mutlaka \(p^2 \lt 10^{10}\) olmalıdır.
Ardından her \(p\) için \(p-1\) sayısı çarpanlarına ayrılır ve yalnızca mod \(3\) kalıntıları factors_mod3_of_p_minus_1 içinde saklanır. DFS bir asal \(p\)'yi seçtiğinde, bu önceden hesaplanmış katkılar residue_mod3 dizisine eklenir.
DFS büyük asaldan küçük asala ilerler. Her adımda mevcut kalıntı okunur, asalın dışlanacağı mı, opsiyonel mi yoksa zorunlu mu olduğu belirlenir, geçerli en küçük üsle mevcut taban güncellenir ve kalıntı tablosu ayarlanır. Güçlü bir budama da şuradan gelir: kalıntı \(0\) olduğu halde \(p^2\) bile limiti aşacaksa, o asal yeni bir dal başlatamaz ve kesin olarak atlanır.
DFS sonlandığında elimizde bir minimal temel çözüm vardır. Daha sonra multiplier_sum_rec yardımcı yordamı, dahil edilmiş asallar için \(1,p^3,p^6,\dots\) biçimindeki tüm geçerli çarpanları toplar. C++, Java ve Python sürümleri aynı iskeleti uygular: önce minimal temeller, sonra bütün ailelerin toplamı.
Ön işleme aşaması, özünde bir sieve ve \(p-1\) sayılarının çarpanlara ayrılmasıdır; burada \(p\) değerleri \(\sqrt{L}\)'ye kadar gider ve \(L=10^{10}\)'dur. DFS için temiz bir kapalı worst-case formül vermek zordur; soyut düzeyde aday asal sayısına göre üstel davranabilir, fakat pratikte kalıntıların çoğu tek seçim dayattığı ve limit büyük dalları erkenden kestiği için arama ağacı çok daha küçüktür.
\(10^{10}\)'a kadar tüm sayılar için totient hesaplayan kaba kuvvet yaklaşımıyla karşılaştırıldığında kazanç devasa boyuttadır. Bellek kullanımı da makuldür: esas olarak SPF tablosu, ön hesaplanmış faktör listeleri, kalıntı dizisi ve özyineleme yığını tutulur.
Buscamos el valor de
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ es un cubo}}} n.$$
Recorrer todos los \(n\) hasta \(10^{10}\) sería inviable incluso con una rutina rápida para \(\varphi\). Por eso la solución no prueba candidatos uno por uno, sino que describe exactamente qué patrones de exponentes primos hacen que \(\varphi(n^2)\) sea un cubo perfecto y construye solo esos \(n\). El valor numérico final de Project Euler se omite deliberadamente.
Escribamos la factorización prima de \(n\) como
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
Solo un número finito de exponentes es distinto de cero. Toda la idea consiste en convertir la condición de que \(\varphi(n^2)\) sea un cubo en congruencias módulo \(3\).
La función phi de Euler es multiplicativa en argumentos coprimos y, para potencias primas, cumple
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
Aplicando esto a \(n^2=\prod_{p \mid n} p^{2e_p}\) obtenemos
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
Equivalentemente, como \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\), también se deduce
$$\varphi(n^2)=n\varphi(n).$$
Esta factorización es la que deja visibles los exponentes primos que deben controlarse módulo \(3\).
Un entero es un cubo perfecto si y solo si cada exponente primo de su factorización es divisible por \(3\). Usando la valuación \(\nu_q(m)\), la condición se escribe
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{para todo primo }q.$$
La fórmula anterior muestra que cada primo \(q\) recibe contribuciones de dos sitios:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
El primer término es la contribución del propio factor \(q\) dentro de \(n\). El segundo cuenta cuántas veces aparece \(q\) dentro de los factores \(p-1\) generados por los primos elegidos.
El código procesa los primos de mayor a menor. Eso es esencial porque todo divisor primo de \(p-1\) es estrictamente menor que \(p\). Por tanto, una vez que el recorrido llega a un primo \(q\), ningún primo más pequeño que quede por procesar puede producir una nueva contribución a \(q\) a través de un término \(p-1\).
Así, cuando se examina \(q\), el residuo
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
ya está completamente determinado. El arreglo residue_mod3 guarda exactamente estos residuos pendientes. Por eso la decisión en cada primo es local y la poda resulta tan fuerte.
Supongamos que el residuo actual en el primo \(q\) es \(c\in\{0,1,2\}\).
Si \(q\) se excluye de \(n\), entonces no aparece su contribución propia \(2e_q-1\). Como ningún primo futuro más pequeño puede añadir más valuación de \(q\), la exclusión solo es válida cuando \(c=0\).
Si \(q\) se incluye con exponente \(e_q\), debe cumplirse
$$c+(2e_q-1)\equiv 0\pmod 3.$$
Resolver esto módulo \(3\) da
$$e_q\equiv c+2\pmod 3.$$
Por tanto, los menores exponentes admisibles son
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
Esta es exactamente la lógica del programa. Residuo \(0\): el primo es opcional. Residuo \(1\) o \(2\): el primo queda forzado con la menor clase de exponente compatible.
Un ejemplo válido pequeño pero interesante es
$$72=2^3\cdot 3^2.$$
Con la fórmula para potencias primas,
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
La lectura por residuos aclara el mecanismo. El primo \(3\) puede entrar con exponente \(2\) porque, cuando el residuo es \(0\), la clase mínima exigida es \(e_3\equiv 2\pmod 3\). Pero \(3-1=2\) aporta una unidad pendiente para el primo \(2\). Cuando el DFS llega después al primo \(2\), ve \(c=1\), y entonces
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
de modo que la menor elección es \(e_2=3\). Así el buscador reconstruye \(72\) sin probar valores ajenos.
Una vez fijada una solución base mínima \(n_0\), los exponentes de todos los primos incluidos pueden aumentarse en múltiplos de \(3\):
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
Esto conserva la condición de cubo porque sumar \(3\) a un exponente cambia \(2e_p-1\) en \(6\), y \(6\equiv 0\pmod 3\). Los factores \(p-1\) tampoco cambian. Por eso el programa enumera cada base mínima una sola vez y luego suma toda la familia asociada de multiplicadores cúbicos.
El solver construye primero un cribado de menor factor primo hasta \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). Ese rango basta para los factores de una base mínima: si un primo nuevo se introduce desde residuo \(0\), su menor exponente admisible es \(2\), luego necesariamente debe cumplir \(p^2 \lt 10^{10}\).
Después, el código factoriza cada \(p-1\) y guarda solo los exponentes módulo \(3\) en factors_mod3_of_p_minus_1. Cuando el DFS decide incluir un primo \(p\), añade exactamente esas contribuciones precomputadas a residue_mod3.
El DFS avanza de primos grandes a primos pequeños. En cada paso lee el residuo actual, decide si el primo se excluye, es opcional o está forzado, multiplica la base actual por la menor potencia válida y actualiza la tabla de residuos. Hay una poda importante cuando el residuo es \(0\) pero incluso \(p^2\) ya excede el límite: en ese caso ese primo no puede abrir una rama nueva y se omite de forma determinista.
Cuando el DFS termina, ha construido una base mínima. La recursión auxiliar multiplier_sum_rec suma entonces todos los multiplicadores admisibles \(1,p^3,p^6,\dots\) para los primos incluidos. Las versiones en C++, Java y Python siguen exactamente esa misma estructura.
La fase de preprocesamiento es, en esencia, un cribado más la factorización de \(p-1\) para primos hasta \(\sqrt{L}\), con \(L=10^{10}\). El DFS no tiene una cota cerrada especialmente elegante en el peor caso; abstractamente puede crecer de forma exponencial con el número de primos candidatos, pero en la práctica el árbol es muchísimo menor porque los residuos suelen forzar una única decisión y el límite poda ramas grandes muy pronto.
Frente a una evaluación ingenua de \(\varphi\) para todos los \(n \lt 10^{10}\), la mejora es enorme. El uso de memoria se mantiene moderado: principalmente la tabla SPF, las listas precomputadas de factores, el arreglo de residuos y la pila recursiva.
我们要求的是
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ 为完全立方}}} n.$$
如果把 \(1\) 到 \(10^{10}-1\) 的所有 \(n\) 都逐个计算一遍，即使 totient 实现很快也根本不可行。真正有效的方法，是先刻画出哪些素因子指数模式会让 \(\varphi(n^2)\) 成为完全立方，然后只构造这些 \(n\)。这里有意不直接给出最终的 Project Euler 数值答案。
把 \(n\) 的素因子分解写成
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
只有有限个指数非零。整个解法的核心，就是把“\(\varphi(n^2)\) 是立方数”转化为模 \(3\) 的同余约束。
欧拉函数在互素参数上是乘法性的，而对素数幂有
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
应用到 \(n^2=\prod_{p \mid n} p^{2e_p}\) 上可得
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
另一方面，由 \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\) 也可立即推出
$$\varphi(n^2)=n\varphi(n).$$
这一步把最终需要检查的素数指数完全暴露出来。
一个整数是完全立方，当且仅当其素因子分解中每个素数的指数都能被 \(3\) 整除。记 \(\nu_q(m)\) 为素数 \(q\) 在 \(m\) 中的指数，那么条件就是
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{对所有素数 }q.$$
由上面的乘积公式可知，任意素数 \(q\) 的指数来自两个来源：
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
第一项是 \(q\) 自己作为 \(n\) 的素因子时贡献出的指数；第二项则统计所有已选素数 \(p\) 的 \(p-1\) 中，\(q\) 出现了多少次。
代码按照素数从大到小搜索。这一点非常关键，因为 \(p-1\) 的任一素因子都严格小于 \(p\)。因此，当搜索走到某个素数 \(q\) 时，之后还没处理的更小素数，不可能再通过某个 \(p-1\) 给 \(q\) 增加新的贡献。
也就是说，处理 \(q\) 时，下式中的残量已经是最终值：
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3.$$
代码中的 residue_mod3 数组正是用来保存这些“还未被抵消”的模 \(3\) 残量。于是每个素数上的决定都可以局部完成，而不用回头全局修正。
设当前素数 \(q\) 上的残量为 \(c\in\{0,1,2\}\)。
如果把 \(q\) 排除在 \(n\) 之外，那么它自己的贡献 \(2e_q-1\) 根本不存在。由于未来更小的素数也不可能再给 \(q\) 增加指数，所以只有在 \(c=0\) 时，排除 \(q\) 才合法。
如果要把 \(q\) 以指数 \(e_q\) 放入 \(n\)，就必须满足
$$c+(2e_q-1)\equiv 0\pmod 3.$$
解这个同余可得
$$e_q\equiv c+2\pmod 3.$$
因此最小可行指数分别为
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
这正是程序中的分支逻辑。残量为 \(0\) 时该素数是可选的；残量为 \(1\) 或 \(2\) 时，它被强制纳入，而且指数取最小匹配类。
一个小而不平凡的有效例子是
$$72=2^3\cdot 3^2.$$
根据素数幂公式，
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
如果从残量角度理解，机制会更清楚。素数 \(3\) 在残量为 \(0\) 时，最小允许同余类是 \(e_3\equiv 2\pmod 3\)，所以可以先选 \(e_3=2\)。但 \(3-1=2\) 会给素数 \(2\) 留下一个待平衡贡献。于是 DFS 之后处理到素数 \(2\) 时，会看到 \(c=1\)，因此
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
最小选择就是 \(e_2=3\)。程序正是凭借这种残量平衡，在不枚举无关整数的情况下重建出 \(72\)。
一旦找到一个最小可行基解 \(n_0\)，所有已选素数的指数都可以再加上 \(3\) 的倍数：
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
这样做不会破坏立方条件，因为指数加 \(3\) 会让 \(2e_p-1\) 增加 \(6\)，而 \(6\equiv 0\pmod 3\)；与此同时，\(p-1\) 本身完全不变。所以程序只需枚举每个最小基解一次，再把与之对应的整族立方倍增因子一次性求和。
程序先建立到 \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\) 为止的最小素因子筛。这个范围足以覆盖最小基解中可能新引入的素数，因为当残量为 \(0\) 时，一个新素数的最小可行指数是 \(2\)，因此必须满足 \(p^2 \lt 10^{10}\)。
随后，代码会把每个 \(p-1\) 分解质因数，并且只保存各质因子的指数模 \(3\) 的结果，存入 factors_mod3_of_p_minus_1。DFS 一旦决定纳入素数 \(p\)，就把这些预处理好的贡献加到 residue_mod3 中。
DFS 从大素数走到小素数。每一步读取当前残量，判断该素数是排除、可选还是被强制纳入，再把当前基数乘上最小合法幂次，并同步更新残量表。还有一个很重要的剪枝：如果当前残量是 \(0\)，但即使选择最小新幂 \(p^2\) 也已经超出上界，那么这个素数不可能开启新分支，可以直接跳过。
当 DFS 走到底时，得到的是一个最小基解。之后辅助递归 multiplier_sum_rec 会把所有允许的乘子 \(1,p^3,p^6,\dots\) 一起求和，因此 C++、Java 和 Python 三个版本都在“枚举最小基解”而不是“重复枚举同一族中的所有成员”。
预处理阶段本质上是一个筛法，再加上对所有相关 \(p-1\) 的分解，其中 \(p\) 只需要到 \(\sqrt{L}\)，这里 \(L=10^{10}\)。DFS 自身没有一个特别漂亮的封闭 worst-case 公式；抽象地说，它可能随着候选素数数量呈指数增长，但实际搜索树要小得多，因为很多残量会直接强制唯一选择，而上界又会尽早砍掉大分支。
和对所有 \(n \lt 10^{10}\) 逐个计算 totient 的暴力法相比，这种方法快了很多个数量级。空间占用也比较克制，主要来自 SPF 表、预处理后的因子列表、残量数组以及递归栈。
Нужно вычислить
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ является точным кубом}}} n.$$
Перебирать все \(n\) до \(10^{10}\) напрямую бессмысленно даже при быстрой реализации функции Эйлера. Поэтому решение не проверяет каждое число по отдельности, а описывает точные шаблоны показателей простых, при которых \(\varphi(n^2)\) становится кубом, и строит только такие \(n\). Сам численный ответ Project Euler здесь намеренно не раскрывается.
Запишем разложение \(n\) на простые множители в виде
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
Ненулевых показателей конечное число. Вся идея решения состоит в том, чтобы переписать условие кубичности для \(\varphi(n^2)\) как систему сравнений по модулю \(3\).
Функция Эйлера мультипликативна на взаимно простых аргументах, а для простой степени выполняется
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
Применяя это к \(n^2=\prod_{p \mid n} p^{2e_p}\), получаем
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
Эквивалентно, так как \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\), сразу следует и компактная формула
$$\varphi(n^2)=n\varphi(n).$$
Именно это разложение показывает, какие простые показатели нужно контролировать по модулю \(3\).
Целое число является точным кубом тогда и только тогда, когда каждый показатель простого множителя в его разложении делится на \(3\). Если обозначить через \(\nu_q(m)\) показатель простого \(q\) в числе \(m\), то условие принимает вид
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{для любого простого }q.$$
Из формулы выше видно, что вклад в показатель простого \(q\) приходит из двух источников:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
Первый член отвечает за собственную степень простого \(q\) в \(n\), второй подсчитывает, сколько раз \(q\) появляется в множителях \(p-1\), приходящих от уже выбранных простых \(p\).
Код обходит простые числа от больших к меньшим. Это принципиально, потому что любой простой делитель числа \(p-1\) строго меньше самого \(p\). Значит, когда поиск дошел до простого \(q\), никакой еще не обработанный меньший простой уже не сможет создать новый вклад в \(q\) через фактор вида \(p-1\).
Следовательно, к моменту обработки \(q\) остаток
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
уже окончателен. Массив residue_mod3 хранит именно эти еще не компенсированные остатки. Благодаря этому решение на каждом простом становится локальным.
Пусть текущий остаток у простого \(q\) равен \(c\in\{0,1,2\}\).
Если \(q\) исключается из \(n\), то собственный вклад \(2e_q-1\) отсутствует. Поскольку будущие меньшие простые уже не могут добавить показатель \(q\), исключение допустимо только при \(c=0\).
Если же \(q\) включается с показателем \(e_q\), необходимо выполнить
$$c+(2e_q-1)\equiv 0\pmod 3.$$
Отсюда по модулю \(3\) получаем
$$e_q\equiv c+2\pmod 3.$$
Поэтому минимальные допустимые показатели таковы:
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
Это в точности и делает программа. Остаток \(0\) означает, что простой множитель необязателен; остатки \(1\) и \(2\) заставляют включить его с минимальным подходящим показателем.
Небольшой, но показательный допустимый пример:
$$72=2^3\cdot 3^2.$$
По формуле для степеней простых имеем
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
Интерпретация через остатки особенно наглядна. Простой \(3\) можно взять с показателем \(2\), потому что при остатке \(0\) требуется класс \(e_3\equiv 2\pmod 3\). Но поскольку \(3-1=2\), это создает один отложенный вклад для простого \(2\). Когда DFS позже доходит до \(2\), он видит \(c=1\), и тогда
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
так что минимальный выбор равен \(e_2=3\). Именно так поиск восстанавливает число \(72\) без проверки посторонних значений.
После нахождения минимального допустимого базового решения \(n_0\) показатели всех уже включенных простых можно увеличивать на кратные \(3\):
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
Кубичность при этом сохраняется, потому что прибавление \(3\) к показателю меняет величину \(2e_p-1\) на \(6\), а \(6\equiv 0\pmod 3\). Множители \(p-1\) тоже не меняются. Поэтому программа перечисляет каждую минимальную базу только один раз, а затем суммирует целое семейство разрешенных множителей.
Сначала решатель строит решето минимальных простых делителей до \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). Этого диапазона достаточно для минимальных базовых множителей: если новый простой появляется из состояния с остатком \(0\), то его наименьший допустимый показатель равен \(2\), а значит требуется \(p^2 \lt 10^{10}\).
Затем для каждого \(p\) факторизуется число \(p-1\), и в factors_mod3_of_p_minus_1 сохраняются только показатели по модулю \(3\). Когда DFS включает простой \(p\), он просто добавляет эти заранее подготовленные вклады в массив residue_mod3.
DFS идет от больших простых к меньшим. На каждом шаге он читает текущий остаток, решает, запрещен ли простой, необязателен или обязателен, умножает текущую базу на наименьшую допустимую степень и обновляет таблицу остатков. Важная отсечка возникает тогда, когда остаток равен \(0\), но даже \(p^2\) уже превышает предел: такой простой уже не может открыть новую ветвь и пропускается автоматически.
Когда DFS доходит до конца, получена минимальная базовая конфигурация. После этого вспомогательная рекурсия multiplier_sum_rec суммирует все допустимые множители \(1,p^3,p^6,\dots\) для уже выбранных простых. Версии на C++, Java и Python реализуют именно эту схему.
Предобработка по сути состоит из решета и факторизации чисел \(p-1\) для простых до \(\sqrt{L}\), где \(L=10^{10}\). Для самого DFS нет особенно красивой замкнутой оценки в худшем случае; абстрактно дерево поиска экспоненциально по числу кандидатов, но на практике оно намного меньше, потому что остатки часто навязывают единственный выбор, а ограничение по величине рано обрезает крупные ветви.
По сравнению с наивным вычислением \(\varphi\) для всех \(n \lt 10^{10}\) выигрыш огромен. Памяти требуется немного: в основном таблица SPF, заранее вычисленные списки факторов, массив остатков и рекурсивный стек.
المطلوب هو حساب
$$\sum_{\substack{1 \le n \lt 10^{10}\\ \varphi(n^2)\text{ مكعب كامل}}} n.$$
فحص جميع القيم حتى \(10^{10}\) مباشرة غير عملي إطلاقًا حتى مع تنفيذ سريع لدالة أويلر. لذلك لا يجرّب الحل كل \(n\) على حدة، بل يحدد بدقة أنماط أسس العوامل الأولية التي تجعل \(\varphi(n^2)\) مكعبًا كاملاً، ثم يبني هذه القيم فقط. الجواب العددي النهائي لمسألة Project Euler لا يُعرض هنا عمدًا.
لنكتب التحليل الأولي لـ \(n\) على الصورة
$$n=\prod_{p} p^{e_p},\qquad e_p\ge 0.$$
ولا يكون إلا عدد منتهٍ من هذه الأسس غير صفري. الفكرة المركزية في الحل هي تحويل شرط كون \(\varphi(n^2)\) مكعبًا إلى شروط توافق modulo \(3\).
دالة أويلر \(\varphi\) دالة ضربية على الأعداد المتباينة أوليًا، وللقوى الأولية لدينا
$$\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1).$$
بتطبيق ذلك على \(n^2=\prod_{p \mid n} p^{2e_p}\) نحصل على
$$\varphi(n^2)=\prod_{p \mid n}\varphi\!\left(p^{2e_p}\right)=\prod_{p \mid n} p^{2e_p-1}(p-1).$$
وبصورة مكافئة، لأن \(\varphi(n)=n\prod_{p \mid n}\left(1-\frac1p\right)\)، نستنتج أيضًا العلاقة المختصرة
$$\varphi(n^2)=n\varphi(n).$$
هذا التفكيك هو الذي يكشف الأسس الأولية التي يجب فحصها modulo \(3\).
يكون العدد الصحيح مكعبًا كاملاً إذا وفقط إذا كان أس كل عامل أولي في تحليله قابلاً للقسمة على \(3\). وإذا رمزنا بـ \(\nu_q(m)\) إلى أس الأولي \(q\) في \(m\)، فإن الشرط يصبح
$$\nu_q\bigl(\varphi(n^2)\bigr)\equiv 0\pmod 3\qquad\text{لكل عدد أولي }q.$$
ومن الصيغة السابقة نرى أن مساهمة أي أولي \(q\) تأتي من مصدرين:
$$\nu_q\bigl(\varphi(n^2)\bigr)=\mathbf{1}_{q\mid n}(2e_q-1)+\sum_{p \mid n}\nu_q(p-1).$$
الحد الأول هو مساهمة \(q\) من ظهوره هو نفسه داخل \(n\)، أما الحد الثاني فيعدّ عدد مرات ظهور \(q\) داخل العوامل \(p-1\) القادمة من جميع الأعداد الأولية المختارة.
يعالج الكود الأعداد الأولية من الأكبر إلى الأصغر. وهذه نقطة جوهرية، لأن كل قاسم أولي لـ \(p-1\) يكون أصغر strictly من \(p\). لذلك عندما تصل عملية البحث إلى أولي \(q\)، فلن يتمكن أي أولي أصغر لم يُعالج بعد من توليد مساهمة جديدة تخص \(q\) عبر حد من شكل \(p-1\).
وبالتالي فإن الباقي
$$c_q\equiv\sum_{\substack{p \mid n\\ p>q}}\nu_q(p-1)\pmod 3$$
يكون قد استقر نهائيًا عند لحظة معالجة \(q\). ويخزن المصفوفة residue_mod3 هذه البواقي غير المسواة بعد. وهكذا يصبح القرار عند كل أولي قرارًا محليًا، لا قرارًا يحتاج مراجعة شاملة لاحقًا.
افترض أن الباقي الحالي عند الأولي \(q\) هو \(c\in\{0,1,2\}\).
إذا استُبعد \(q\) من \(n\)، فلن توجد مساهمته الذاتية \(2e_q-1\). وبما أن أي أولي أصغر لاحقًا لا يمكنه إضافة مزيد من تقييم \(q\)، فلا يكون الاستبعاد مسموحًا إلا إذا كان \(c=0\).
أما إذا أُدخل \(q\) بأس \(e_q\)، فلا بد أن يتحقق
$$c+(2e_q-1)\equiv 0\pmod 3.$$
ومن هذا نحصل modulo \(3\) على
$$e_q\equiv c+2\pmod 3.$$
إذن أصغر الأسس المسموح بها هي
$$c=0 \Rightarrow e_q=2,\qquad c=1 \Rightarrow e_q=3,\qquad c=2 \Rightarrow e_q=1.$$
وهذا هو بالضبط تفرع التنفيذ. إذا كان الباقي \(0\) فالأولي اختياري. وإذا كان \(1\) أو \(2\) فإنه يصبح إلزاميًا مع أصغر فئة أس تحقق الشرط.
مثال صغير لكنه غير تافه هو
$$72=2^3\cdot 3^2.$$
وباستخدام صيغة القوى الأولية نجد
$$\varphi(72^2)=2^{2\cdot 3-1}(2-1)\cdot 3^{2\cdot 2-1}(3-1)=2^5\cdot 1\cdot 3^3\cdot 2=2^6\cdot 3^3=12^3.$$
تفسير ذلك عبر البواقي يوضح الآلية. يمكن للأولي \(3\) أن يبدأ بالأس \(2\) لأن الباقي \(0\) يفرض الفئة \(e_3\equiv 2\pmod 3\). لكن \(3-1=2\) يضيف مساهمة معلقة واحدة تخص الأولي \(2\). وعندما يصل DFS لاحقًا إلى \(2\)، يجد \(c=1\)، ومن ثم
$$1+(2e_2-1)\equiv 0\pmod 3\Rightarrow e_2\equiv 0\pmod 3,$$
فتكون أصغر قيمة ممكنة هي \(e_2=3\). بهذه الطريقة يعيد البحث بناء \(72\) مباشرة من شروط التوافق فقط.
بعد تثبيت حل أساسي أصغري \(n_0\)، يمكن زيادة أسس جميع العوامل الأولية المدرجة بمضاعفات \(3\):
$$n=n_0\prod_{p\in\mathcal{P}} p^{3t_p},\qquad t_p\ge 0.$$
وهذا لا يغيّر شرط المكعب، لأن إضافة \(3\) إلى الأس تغير \(2e_p-1\) بمقدار \(6\)، و\(6\equiv 0\pmod 3\)، بينما تبقى العوامل \(p-1\) نفسها كما هي. لذلك لا يكرر البرنامج اكتشاف أفراد العائلة الواحدة، بل يبني الحل الأساسي مرة واحدة ثم يجمع كل مضاعفاته المسموح بها.
يبدأ الحل ببناء sieve لأصغر قاسم أولي حتى \(\left\lfloor\sqrt{10^{10}-1}\right\rfloor\). وهذا يكفي للعوامل الأولية التي يمكن أن تظهر في حل أساسي أصغري، لأن أي أولي جديد يُدخل من حالة بقايا صفرية يحتاج في الحد الأدنى إلى أس \(2\)، أي لا بد أن يحقق \(p^2 \lt 10^{10}\).
بعد ذلك يُحلَّل كل \(p-1\) إلى عوامله الأولية، ولا يُحفظ إلا الأس modulo \(3\) داخل factors_mod3_of_p_minus_1. وعندما يقرر DFS إدخال أولي \(p\)، فإنه يضيف هذه المساهمات المحسوبة مسبقًا إلى residue_mod3.
يسير DFS من الأوليات الكبيرة إلى الصغيرة. في كل خطوة يقرأ الباقي الحالي، ويحدد هل الأولي مستبعد أم اختياري أم إجباري، ثم يضرب الحل الأساسي الحالي في أصغر قوة صالحة ويحدّث جدول البواقي. وهناك عملية تقليم مهمة: إذا كان الباقي \(0\) ولكن حتى \(p^2\) تتجاوز الحد، فهذا يعني أن ذلك الأولي لا يستطيع فتح فرع جديد، فيُتجاوز مباشرة.
وحين يصل DFS إلى النهاية يكون قد كوّن حلاً أساسيًا أصغريًا. بعد ذلك تقوم الدالة المساعدة multiplier_sum_rec بجمع جميع المضاعفات المسموح بها من الشكل \(1,p^3,p^6,\dots\) للأعداد الأولية المدرجة. ولهذا تتبع نسخ C++ وJava وPython البنية نفسها تمامًا.
مرحلة المعالجة المسبقة هي أساسًا sieve مع تحليل للأعداد \(p-1\) للأوليات حتى \(\sqrt{L}\)، حيث \(L=10^{10}\). أما DFS نفسه فلا يملك حدًا مغلقًا بسيطًا في أسوأ الحالات؛ تجريديًا قد يكون عدد فروعه أسيًا في عدد الأوليات المرشحة، لكن عمليًا تكون الشجرة أصغر بكثير لأن البواقي غالبًا ما تفرض قرارًا وحيدًا، كما أن الحد العددي يقطع الفروع الكبيرة مبكرًا.
وبالمقارنة مع حساب \(\varphi\) لكل \(n \lt 10^{10}\) بطريقة brute force، فإن التوفير هائل جدًا. كما أن استهلاك الذاكرة يظل معتدلًا: جدول أصغر قاسم أولي، قوائم العوامل المحسوبة مسبقًا، مصفوفة البواقي، ومكدس الاستدعاء العودي.