Start with the one-element list \(\{n\}\). Alice may replace two list elements \(a,b>1\) by the single value \(a^b\), and she may replace one element \(c\) by two values \(a,b>1\) whenever \(c=a^b\). A number \(n>1\) is called creative if, for every target \(m>1\), there exists some sequence of such moves that leads to a list containing \(m\).
For Problem 616 we must compute
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n.$$
The implementations do not explore the move graph directly. Instead they use a classification theorem for all creative numbers up to the required limit and then turn the problem into a finite enumeration.
Let \(X=10^{12}\). Define the two sets
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ prime},\ q\text{ prime}\}.$$
The C++, Python, and Java implementations rely on the classification
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
where \(\mathcal{C}(X)\) denotes the set of creative numbers not exceeding \(X\). The remaining work is to understand why this description is natural and how to sum it efficiently.
If \(n\) is not a perfect power, then the starting list \(\{n\}\) cannot be split at all, because there do not exist integers \(a,b>1\) with \(n=a^b\). Therefore the process is stuck immediately, and the only number ever present is \(n\) itself.
But a creative number must be able to reach every target \(m>1\), so a non-perfect power is impossible. Hence every creative \(n\le X\) must lie in \(\mathrm{PP}(X)\).
Now consider
$$n=p^q,$$
with \(p\) prime and \(q\) prime. Splitting \(n\) yields the two-element list \(\{p,q\}\). Neither of those values can be split any further, because primes are not nontrivial perfect powers.
From \(\{p,q\}\), the only possible merges are \(p^q\) and \(q^p\). If \(p=q\), even that swap does nothing. So the reachable state space stays extremely small and cannot contain arbitrary targets.
Therefore every member of \(\mathrm{PQ}(X)\) must be removed from the creative set.
The number \(16\) is a perfect power, but it is not in \(\mathrm{PQ}(X)\), because its standard forms are
$$16=2^4=4^2.$$
Nevertheless it is still not creative. Every nontrivial split of \(16\) produces only powers of \(2\), and splitting those outputs again still produces only powers of \(2\).
This is stable under merging as well. If all current elements are powers of \(2\), say \(2^r\) and \(2^s\), then
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
which is again a power of \(2\). So starting from \(16\), the process never leaves the world of powers of \(2\). In particular, a target such as \(3\) can never appear. That is why the implementations subtract \(16\) separately.
The difficult direction is the converse: apart from the excluded family \(\mathrm{PQ}(X)\) and the special case \(16\), every remaining perfect power up to \(10^{12}\) is creative. The implementations take exactly that theorem as their mathematical foundation.
Once this classification is accepted, the answer is no longer about searching for transformations. It is just the sum of all perfect powers up to \(X\), minus the sum of the prime-prime powers, minus the single exceptional value \(16\).
Hence
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
with \(X=10^{12}\).
Two implementation details matter here:
First, \(\mathrm{PP}(X)\) must be deduplicated, because the same integer can appear from several exponent choices. For example,
$$64=2^6=4^3=8^2.$$
Second, \(\mathrm{PQ}(X)\) does not need deduplication. If \(p^q=r^s\) with \(p,r\) prime and \(q,s\) prime, unique prime factorization forces \(p=r\) and \(q=s\).
The perfect powers up to \(100\) are
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
The prime-prime powers among them are
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
Removing those values and then removing \(16\) leaves
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
Therefore
$$S(100)=36+64+81+100=281.$$
This small example mirrors the full computation exactly: generate perfect powers, subtract the prime-prime family, and subtract the isolated exception \(16\).
The implementations first determine the largest relevant exponent \(E\) with \(2^E\le X\). For \(X=10^{12}\), this gives \(E=39\), because \(2^{39}\le 10^{12} < 2^{40}\).
For each exponent \(e=2,3,\dots,E\), the implementation computes the largest base \(a\) satisfying \(a^e\le X\) by integer binary search. It then enumerates every value \(a^e\) in that range and stores all of them in a list or set. After sorting and deduplication, their total gives the sum over \(\mathrm{PP}(X)\).
Next, the implementation builds the subtraction term \(\mathrm{PQ}(X)\). Since \(p^q\le X\) and \(q\ge 2\), every prime base satisfies \(p\le \sqrt{X}=10^6\), so a sieve up to \(10^6\) is enough. The only relevant exponents are the primes between \(2\) and \(39\). Every valid value \(p^q\le X\) is added to the prime-prime sum.
Finally, the answer is computed as
$$\text{sum of perfect powers}-\text{sum of prime-prime powers}-16.$$
The implementations also contain short sanity checks: several included values such as \(36\), \(81\), \(100\), and \(216\) are shown to reach \(64\), while \(16\) fails a negative check because all reachable values remain powers of \(2\).
Let
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
This is the number of raw perfect-power candidates generated before deduplication. The square case dominates, so \(M=O(X^{1/2})\). Sorting and deduplicating those candidates costs \(O(M\log M)\) time and \(O(M)\) memory.
The prime sieve up to \(10^6\) costs \(O(10^6\log\log 10^6)\) time and \(O(10^6)\) memory. The list of prime exponents is tiny because \(E=39\). Overall, the method is easily fast enough for \(X=10^{12}\) and avoids any attempt to search the full transformation graph.
Wir starten mit der Liste \(\{n\}\). Alice darf zwei Listenelemente \(a,b>1\) durch \(a^b\) ersetzen, und sie darf ein Element \(c\) durch \(a,b>1\) ersetzen, falls \(c=a^b\) gilt. Eine Zahl \(n>1\) heißt kreativ, wenn es zu jedem Zielwert \(m>1\) eine Folge solcher Operationen gibt, die zu einer Liste führt, in der \(m\) vorkommt.
Für Problem 616 ist also zu berechnen
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ kreativ}}} n.$$
Die Implementierungen durchsuchen den Zustandsgraphen nicht direkt. Stattdessen verwenden sie eine Klassifikation aller kreativen Zahlen bis zur Schranke und reduzieren die Aufgabe damit auf eine endliche Aufzählung.
Setze \(X=10^{12}\) und definiere
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ prim},\ q\text{ prim}\}.$$
Die C++-, Python- und Java-Implementierungen benutzen die Klassifikation
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
wobei \(\mathcal{C}(X)\) die Menge der kreativen Zahlen bis \(X\) bezeichnet. Die eigentliche Arbeit besteht dann darin, diese Beschreibung sauber zu summieren.
Ist \(n\) keine perfekte Potenz, dann kann die Startliste \(\{n\}\) gar nicht aufgespalten werden, denn es existieren keine ganzen Zahlen \(a,b>1\) mit \(n=a^b\). Der Prozess steckt also sofort fest, und die einzige jemals sichtbare Zahl ist \(n\) selbst.
Eine kreative Zahl muss aber jeden Zielwert \(m>1\) erreichen können. Folglich muss jede kreative Zahl in \(\mathrm{PP}(X)\) liegen.
Betrachte
$$n=p^q,$$
wobei \(p\) prim und \(q\) prim ist. Eine Aufspaltung liefert die Liste \(\{p,q\}\). Keiner dieser beiden Werte lässt sich weiter zerlegen, weil Primzahlen keine nichttrivialen perfekten Potenzen sind.
Aus \(\{p,q\}\) kann man nur wieder \(p^q\) oder durch Vertauschen \(q^p\) erzeugen. Falls \(p=q\), bleibt sogar genau derselbe Zustand erhalten. Der erreichbare Bereich bleibt also viel zu klein, um beliebige Zielwerte zu enthalten.
Deshalb müssen alle Elemente aus \(\mathrm{PQ}(X)\) ausgeschlossen werden.
Die Zahl \(16\) ist zwar eine perfekte Potenz, gehört aber nicht zu \(\mathrm{PQ}(X)\), denn ihre üblichen Darstellungen sind
$$16=2^4=4^2.$$
Trotzdem ist \(16\) nicht kreativ. Jede nichttriviale Aufspaltung von \(16\) erzeugt nur Zweierpotenzen, und wenn man diese Ergebnisse weiter zerlegt, entstehen wieder nur Zweierpotenzen.
Auch beim Zusammenführen bleibt das erhalten. Sind alle aktuellen Listenelemente von der Form \(2^r\) bzw. \(2^s\), dann gilt
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
also wieder eine Zweierpotenz. Vom Startwert \(16\) aus verlässt man diese Welt niemals. Insbesondere kann \(3\) nie erscheinen. Darum wird \(16\) separat subtrahiert.
Der schwierige Teil ist die Umkehrung: Abgesehen von der ausgeschlossenen Familie \(\mathrm{PQ}(X)\) und dem Sonderfall \(16\) ist jede übrige perfekte Potenz bis \(10^{12}\) kreativ. Genau dieses Resultat ist die mathematische Grundlage der Implementierungen.
Sobald man diese Aussage akzeptiert, muss man keine Transformationsfolgen mehr suchen. Man summiert einfach alle perfekten Potenzen bis \(X\), zieht davon alle Prime-Prime-Potenzen ab und entfernt anschließend noch \(16\).
Damit gilt
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
mit \(X=10^{12}\).
Zwei Details sind wichtig:
Erstens muss \(\mathrm{PP}(X)\) dedupliziert werden, weil dieselbe Zahl bei verschiedenen Exponenten auftauchen kann. Zum Beispiel
$$64=2^6=4^3=8^2.$$
Zweitens braucht \(\mathrm{PQ}(X)\) keine Deduplikation. Aus \(p^q=r^s\) mit primen Basen und primen Exponenten folgt durch eindeutige Primfaktorzerlegung sofort \(p=r\) und \(q=s\).
Die perfekten Potenzen bis \(100\) sind
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
Die Prime-Prime-Potenzen darunter sind
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
Nach dem Entfernen dieser Werte und anschließend von \(16\) bleibt
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
Daher ist
$$S(100)=36+64+81+100=281.$$
Dieses kleine Beispiel spiegelt die volle Rechnung exakt wider: perfekte Potenzen erzeugen, die Prime-Prime-Familie abziehen und den isolierten Ausnahmefall \(16\) separat abziehen.
Die Implementierungen bestimmen zuerst den größten relevanten Exponenten \(E\) mit \(2^E\le X\). Für \(X=10^{12}\) ist das \(E=39\), denn \(2^{39}\le 10^{12} < 2^{40}\).
Für jeden Exponenten \(e=2,3,\dots,E\) wird per ganzzahliger Binärsuche die größte Basis \(a\) bestimmt, für die \(a^e\le X\) gilt. Anschließend werden alle Werte \(a^e\) in diesem Bereich erzeugt und gesammelt. Nach Sortierung und Deduplikation liefert ihre Summe den Beitrag von \(\mathrm{PP}(X)\).
Danach erzeugt die Implementierung den Subtraktionsterm \(\mathrm{PQ}(X)\). Aus \(p^q\le X\) und \(q\ge 2\) folgt \(p\le \sqrt{X}=10^6\), daher genügt ein Primzahlsieb bis \(10^6\). Die relevanten Exponenten sind genau die Primzahlen zwischen \(2\) und \(39\). Jeder gültige Wert \(p^q\le X\) wird zur Prime-Prime-Summe addiert.
Am Ende lautet die Rechnung
$$\text{Summe aller perfekten Potenzen}-\text{Summe aller Prime-Prime-Potenzen}-16.$$
Außerdem enthalten die Implementierungen kurze Plausibilitätsprüfungen: Einige zugelassene Werte wie \(36\), \(81\), \(100\) und \(216\) werden konstruktiv zu \(64\) geführt, während \(16\) einen Negativtest nicht besteht, weil alle erreichbaren Werte Zweierpotenzen bleiben.
Sei
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
Das ist die Anzahl der rohen Kandidaten für perfekte Potenzen vor der Deduplikation. Der quadratische Fall dominiert, also gilt \(M=O(X^{1/2})\). Sortieren und Deduplizieren kostet daher \(O(M\log M)\) Zeit und \(O(M)\) Speicher.
Das Primzahlsieb bis \(10^6\) benötigt \(O(10^6\log\log 10^6)\) Zeit und \(O(10^6)\) Speicher. Die Liste der Primexponenten ist winzig, weil \(E=39\) ist. Insgesamt ist die Methode für \(X=10^{12}\) problemlos schnell genug und vermeidet jede Suche im vollständigen Transformationsgraphen.
Başlangıçta elimizde tek elemanlı \(\{n\}\) listesi vardır. Alice, listedeki iki elemanı \(a,b>1\) alıp bunları \(a^b\) ile birleştirebilir; ayrıca listedeki bir eleman \(c\), \(c=a^b\) olacak şekilde yazılabiliyorsa onu \(a,b>1\) biçiminde ayırabilir. Bir \(n>1\) sayısı, her \(m>1\) hedefi için sonunda \(m\)'yi içeren bir listeye ulaşılabiliyorsa creative olarak adlandırılır.
Problem 616'da hesaplanması istenen toplam
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n$$
şeklindedir. Uygulamalar tüm işlem ağacını aramaz; bunun yerine \(10^{12}\)'ye kadar creative sayıların sınıflandırmasını kullanıp işi sonlu bir sayma problemine indirger.
\(X=10^{12}\) olsun. Şu iki kümeyi tanımlayalım:
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ asal},\ q\text{ asal}\}.$$
C++, Python ve Java uygulamalarının dayandığı sınıflandırma şudur:
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
burada \(\mathcal{C}(X)\), \(X\)'i aşmayan creative sayıların kümesidir. Bundan sonra yapılacak iş, bu kümeleri doğru biçimde üretip toplamaktır.
Eğer \(n\) bir perfect power değilse, başlangıç listesi \(\{n\}\) hiç ayrılamaz; çünkü \(n=a^b\) olacak şekilde \(a,b>1\) tamsayıları yoktur. Böylece süreç daha ilk adımda kilitlenir ve listede görülebilecek tek sayı yine \(n\) olur.
Oysa creative bir sayı her \(m>1\) hedefine ulaşabilmelidir. Demek ki creative olan her \(n\le X\), mutlaka \(\mathrm{PP}(X)\) içinde yer almalıdır.
Şimdi
$$n=p^q$$
durumunu ele alalım; burada \(p\) asal ve \(q\) asaldır. \(n\)'yi ayırınca \(\{p,q\}\) listesine ulaşırız. Bu iki sayı daha fazla ayrılamaz, çünkü asal sayılar nontrivial perfect power değildir.
\(\{p,q\}\) listesinden yapılabilecek tek birleşmeler tekrar \(p^q\) üretmek veya sıralamayı ters çevirip \(q^p\) üretmektir. Eğer \(p=q\) ise bu bile yeni bir durum vermez. Yani erişilebilen durum uzayı çok küçüktür ve keyfi hedefleri içeremez.
Bu nedenle \(\mathrm{PQ}(X)\) kümesindeki her değer creative kümeden çıkarılmalıdır.
\(16\) bir perfect power'dır ama \(\mathrm{PQ}(X)\) içinde değildir; çünkü doğal yazılışları
$$16=2^4=4^2$$
şeklindedir. Buna rağmen creative değildir. \(16\)'nın her nontrivial ayrışması yalnızca \(2\)'nin kuvvetlerini üretir; bu çıktılar tekrar ayrıldığında yine sadece \(2\)'nin kuvvetleri ortaya çıkar.
Birleştirme işlemi de bu özelliği bozmaz. Listedeki her eleman \(2^r\) ve \(2^s\) biçimindeyse
$$\left(2^r\right)^{2^s}=2^{r2^s}$$
olur ve sonuç yine bir \(2\) kuvvetidir. Dolayısıyla \(16\)'dan başlayınca süreç hiçbir zaman \(2\) kuvvetlerinin dışına çıkmaz. Özellikle \(3\) asla ortaya çıkamaz. Uygulamalar bu yüzden \(16\)'yı ayrıca çıkarır.
Zor olan taraf ters yöndür: \(\mathrm{PQ}(X)\) ailesi ve özel durum \(16\) hariç, \(10^{12}\)'ye kadar kalan her perfect power creative'dir. Uygulamaların matematiksel temeli tam olarak bu sonuçtur.
Bu teorem kabul edildiğinde artık dönüşüm aramak gerekmez. Yapılacak iş, \(X\)'e kadar bütün perfect power'ları toplamak, prime-prime ailesini çıkarmak ve son olarak \(16\)'yı düşmektir.
Böylece
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16$$
elde edilir; burada \(X=10^{12}\).
İki ayrıntı önemlidir:
Birincisi, \(\mathrm{PP}(X)\) tekilleştirilmelidir; çünkü aynı sayı farklı üslerle birden çok kez üretilebilir. Örneğin
$$64=2^6=4^3=8^2.$$
İkincisi, \(\mathrm{PQ}(X)\) için tekilleştirme gerekmez. Eğer \(p^q=r^s\) ve hem tabanlar hem üsler asal ise, asal çarpanlara ayırmanın tekliliği doğrudan \(p=r\) ve \(q=s\) sonucunu verir.
\(100\)'e kadar olan perfect power'lar
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}$$
şeklindedir. Bunların içindeki prime-prime terimler ise
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}$$
olur. Bu değerler ve ardından \(16\) çıkarılınca
$$\mathcal{C}(100)=\{36,64,81,100\}$$
kalır. Dolayısıyla
$$S(100)=36+64+81+100=281.$$
Bu küçük örnek, tam programın yaptığı işi bire bir gösterir: perfect power listesini üret, prime-prime listesini çıkar, sonra da tekil istisna \(16\)'yı düş.
Uygulamalar önce \(2^E\le X\) şartını sağlayan en büyük \(E\) değerini bulur. \(X=10^{12}\) için bu \(E=39\)'dur; çünkü \(2^{39}\le 10^{12} < 2^{40}\).
Ardından her \(e=2,3,\dots,E\) için \(a^e\le X\) koşulunu sağlayan en büyük taban \(a\), tamsayı ikili arama ile bulunur. Bu aralıktaki tüm \(a^e\) değerleri üretilip bir listede veya kümede toplanır. Sıralama ve tekilleştirme sonrasında bunların toplamı \(\mathrm{PP}(X)\) katkısını verir.
Sonraki adım \(\mathrm{PQ}(X)\) toplamını oluşturmaktır. \(p^q\le X\) ve \(q\ge 2\) olduğundan her asal taban için \(p\le \sqrt{X}=10^6\) yeterlidir; bu yüzden \(10^6\)'ya kadar bir asal süzgeci kurulur. Üs tarafında ise yalnızca \(2\) ile \(39\) arasındaki asallar gerekir. Sınırı aşmayan her \(p^q\) değeri prime-prime toplamına eklenir.
Son cevap
$$\text{perfect power toplamı}-\text{prime-prime toplamı}-16$$
olarak hesaplanır. Uygulamalarda ayrıca kısa doğrulamalar vardır: \(36\), \(81\), \(100\) ve \(216\) gibi dahil edilen örnekler için \(64\)'e ulaşan zincirler kurulurken, \(16\) için negatif kontrol yapılır ve tüm erişilebilir sayıların \(2\) kuvveti olarak kaldığı görülür.
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor$$
olsun. Bu, tekilleştirme öncesinde üretilen ham perfect power adaylarının sayısıdır. Baskın terim kareler olduğu için \(M=O(X^{1/2})\) olur. Dolayısıyla sıralama ve tekilleştirme \(O(M\log M)\) zaman ve \(O(M)\) bellek gerektirir.
\(10^6\)'ya kadar asal süzgeci \(O(10^6\log\log 10^6)\) zamanda ve \(O(10^6)\) bellekte çalışır. Asal üs listesi çok küçüktür; çünkü \(E=39\). Sonuç olarak yöntem \(X=10^{12}\) için rahatlıkla yeterlidir ve tüm dönüşüm ağacını arama maliyetinden tamamen kaçınır.
Partimos de la lista de un solo elemento \(\{n\}\). Alice puede reemplazar dos elementos \(a,b>1\) por \(a^b\), y también puede reemplazar un elemento \(c\) por dos valores \(a,b>1\) siempre que \(c=a^b\). Un número \(n>1\) se llama creativo si, para todo objetivo \(m>1\), existe alguna secuencia de operaciones que conduce a una lista que contiene \(m\).
En el Problema 616 debemos calcular
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creativo}}} n.$$
Las implementaciones no recorren directamente el grafo completo de transformaciones. En su lugar usan una clasificación de todos los números creativos hasta el límite y convierten el problema en una enumeración finita.
Sea \(X=10^{12}\). Definimos
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ primo},\ q\text{ primo}\}.$$
Las implementaciones en C++, Python y Java usan la clasificación
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
donde \(\mathcal{C}(X)\) es el conjunto de números creativos no mayores que \(X\). A partir de aquí todo consiste en justificar esa descripción y sumarla sin contar duplicados.
Si \(n\) no es una potencia perfecta, la lista inicial \(\{n\}\) no puede dividirse, porque no existen enteros \(a,b>1\) tales que \(n=a^b\). El proceso queda bloqueado de inmediato y el único valor que puede aparecer es \(n\).
Pero un número creativo debe poder alcanzar cualquier objetivo \(m>1\). Por lo tanto, todo número creativo debe pertenecer a \(\mathrm{PP}(X)\).
Consideremos
$$n=p^q,$$
con \(p\) primo y \(q\) primo. Al dividir \(n\) obtenemos la lista \(\{p,q\}\). Ninguno de esos dos valores puede seguir dividiéndose, porque los números primos no son potencias perfectas no triviales.
Desde \(\{p,q\}\), las únicas fusiones posibles vuelven a producir \(p^q\) o, al invertir el orden, \(q^p\). Si \(p=q\), ni siquiera aparece un nuevo estado. El espacio alcanzable es demasiado pequeño para contener objetivos arbitrarios.
Por eso hay que excluir todos los elementos de \(\mathrm{PQ}(X)\).
El número \(16\) sí es una potencia perfecta, pero no pertenece a \(\mathrm{PQ}(X)\), porque sus descomposiciones naturales son
$$16=2^4=4^2.$$
Aun así, no es creativo. Toda división no trivial de \(16\) produce solo potencias de \(2\), y al seguir dividiendo esos resultados siguen apareciendo únicamente potencias de \(2\).
La operación de fusión también conserva esa propiedad. Si todos los elementos actuales son \(2^r\) y \(2^s\), entonces
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
que vuelve a ser una potencia de \(2\). Así, partiendo de \(16\), nunca se sale de ese universo. En particular, un objetivo como \(3\) jamás puede aparecer. De ahí la resta separada de \(16\).
La parte difícil es la recíproca: salvo la familia excluida \(\mathrm{PQ}(X)\) y el caso especial \(16\), toda otra potencia perfecta hasta \(10^{12}\) es creativa. Ese es exactamente el teorema que las implementaciones toman como base matemática.
Una vez aceptada esta clasificación, ya no hace falta buscar secuencias de transformaciones. Basta con sumar todas las potencias perfectas hasta \(X\), restar las potencias primo-primo y restar después el valor aislado \(16\).
Por tanto,
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
con \(X=10^{12}\).
Hay dos observaciones importantes:
Primero, \(\mathrm{PP}(X)\) sí necesita deduplicación, porque el mismo entero puede aparecer con distintos exponentes. Por ejemplo,
$$64=2^6=4^3=8^2.$$
Segundo, \(\mathrm{PQ}(X)\) no necesita deduplicarse. Si \(p^q=r^s\) con bases primas y exponentes primos, la factorización prima única obliga a que \(p=r\) y \(q=s\).
Las potencias perfectas hasta \(100\) son
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
Las potencias primo-primo dentro de ese conjunto son
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
Al quitar esos valores y después quitar \(16\), queda
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
Entonces
$$S(100)=36+64+81+100=281.$$
Este ejemplo pequeño reproduce exactamente la lógica del programa completo: generar potencias perfectas, restar la familia primo-primo y restar la excepción aislada \(16\).
Las implementaciones primero determinan el mayor exponente relevante \(E\) tal que \(2^E\le X\). Para \(X=10^{12}\), eso da \(E=39\), porque \(2^{39}\le 10^{12} < 2^{40}\).
Para cada exponente \(e=2,3,\dots,E\), la implementación calcula mediante búsqueda binaria entera la mayor base \(a\) que satisface \(a^e\le X\). Después enumera todos los valores \(a^e\) en ese rango y los guarda. Tras ordenar y deduplicar, su suma produce el término correspondiente a \(\mathrm{PP}(X)\).
Luego se construye el término de resta \(\mathrm{PQ}(X)\). Como \(p^q\le X\) y \(q\ge 2\), toda base prima satisface \(p\le \sqrt{X}=10^6\); por eso basta una criba hasta \(10^6\). Los exponentes relevantes son solo los primos entre \(2\) y \(39\). Cada valor \(p^q\le X\) se añade a la suma primo-primo.
Por último, la respuesta se obtiene como
$$\text{suma de potencias perfectas}-\text{suma de potencias primo-primo}-16.$$
Las implementaciones también incluyen comprobaciones cortas: varios valores aceptados, como \(36\), \(81\), \(100\) y \(216\), se transforman constructivamente en \(64\), mientras que \(16\) falla una comprobación negativa porque todos los valores alcanzables siguen siendo potencias de \(2\).
Sea
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
Ese es el número de candidatos crudos a potencia perfecta antes de deduplicar. El caso de los cuadrados domina, así que \(M=O(X^{1/2})\). En consecuencia, ordenar y deduplicar cuesta \(O(M\log M)\) tiempo y \(O(M)\) memoria.
La criba de primos hasta \(10^6\) cuesta \(O(10^6\log\log 10^6)\) tiempo y \(O(10^6)\) memoria. La lista de exponentes primos es minúscula porque \(E=39\). En conjunto, el método es más que suficiente para \(X=10^{12}\) y evita cualquier búsqueda explosiva sobre secuencias de transformaciones.
我们从单元素列表 \(\{n\}\) 出发。Alice 可以把两个元素 \(a,b>1\) 合并成 \(a^b\)，也可以在某个元素 \(c\) 满足 \(c=a^b\) 的时候，把它拆成两个值 \(a,b>1\)。如果对任意目标 \(m>1\)，都存在一串这样的操作，最终得到一个包含 \(m\) 的列表，那么 \(n>1\) 就称为 creative。
Problem 616 要求计算
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n.$$
实现并不直接搜索全部操作路径，而是利用一个针对 \(10^{12}\) 以内 creative 数的分类结论，把问题转化为“生成若干集合并求和”的数论枚举。
记 \(X=10^{12}\)。定义两个集合
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ 是素数},\ q\text{ 是素数}\}.$$
C++、Python 和 Java 实现采用的核心分类是
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
其中 \(\mathcal{C}(X)\) 表示不超过 \(X\) 的 creative 数集合。也就是说，creative 数恰好等于所有完全幂，去掉“素数底数且素数指数”的那一族，再去掉单独的异常值 \(16\)。下面把这件事分解成几个层次来看。
如果 \(n\) 不是完全幂，那么初始列表 \(\{n\}\) 根本无法执行拆分，因为不存在整数 \(a,b>1\) 使得 \(n=a^b\)。这样过程在第一步就停住了，列表中永远只会出现 \(n\) 本身。
而 creative 的定义要求它能到达任意目标 \(m>1\)。因此，任何 creative 数都必须首先是完全幂，也就是必须属于 \(\mathrm{PP}(X)\)。这是搜索空间压缩的第一层。
考虑
$$n=p^q,$$
其中 \(p\) 和 \(q\) 都是素数。把它拆开以后，只能得到 \(\{p,q\}\)。由于素数本身不是非平凡完全幂，这两个元素都不能继续拆分。
从 \(\{p,q\}\) 出发，唯一能做的合并只有重新得到 \(p^q\)，或者交换顺序得到 \(q^p\)。如果 \(p=q\)，那连“交换”都不会产生新状态。也就是说，这类起点对应的可达状态图非常小，远远不足以覆盖任意目标。
因此，\(\mathrm{PQ}(X)\) 里的数都必须从 creative 集合中删除。
\(16\) 是完全幂，但它不属于 \(\mathrm{PQ}(X)\)，因为它的典型写法是
$$16=2^4=4^2.$$
然而 \(16\) 仍然不是 creative。原因在于：\(16\) 的任何非平凡拆分都会只产生 \(2\) 的幂，而这些结果继续拆分后，仍然只会得到 \(2\) 的幂。
合并操作也不会打破这个性质。若列表里的元素始终都是 \(2^r\) 与 \(2^s\) 这样的形式，那么
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
结果仍是 \(2\) 的幂。于是从 \(16\) 出发，整个过程永远被困在“只含 \(2\) 的幂”的世界里。特别地，像 \(3\) 这样的目标永远不可能出现，所以 \(16\) 必须单独排除。
真正困难的是反过来的方向：除了 \(\mathrm{PQ}(X)\) 这一族以及特殊值 \(16\) 之外，其余所有不超过 \(10^{12}\) 的完全幂都是 creative。实现恰恰把这条结论作为数学基础。
一旦接受这个分类，问题就不再是“如何构造一条操作链”，而是“怎样把这个集合完整枚举并求和”。于是目标直接变成三部分之差：完全幂总和，减去 prime-prime 幂总和，再减去 \(16\)。
因此有
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
其中 \(X=10^{12}\)。
这里有两个实现层面的细节：
第一，\(\mathrm{PP}(X)\) 必须去重，因为同一个整数可能对应多种幂表示。最典型的例子是
$$64=2^6=4^3=8^2.$$
第二，\(\mathrm{PQ}(X)\) 不需要去重。若有 \(p^q=r^s\)，并且 \(p,r\) 都是素数、\(q,s\) 都是素数，那么由唯一分解定理立刻得到 \(p=r\) 且 \(q=s\)。
先列出不超过 \(100\) 的完全幂：
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
其中 prime-prime 幂是
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
删去这一组，再删去特殊值 \(16\)，就得到
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
于是
$$S(100)=36+64+81+100=281.$$
这个小例子完整体现了程序的工作方式：先枚举完全幂，再减去 prime-prime 幂，最后减去单独的异常值 \(16\)。
实现首先求出满足 \(2^E\le X\) 的最大指数 \(E\)。当 \(X=10^{12}\) 时，\(E=39\)，因为 \(2^{39}\le 10^{12} < 2^{40}\)。
接下来对每个指数 \(e=2,3,\dots,E\)，实现都会用整数二分查找求出满足 \(a^e\le X\) 的最大底数 \(a\)。然后枚举所有这样的 \(a^e\)，把它们加入容器。等所有指数都处理完之后，再排序并去重，得到 \(\mathrm{PP}(X)\) 的总和。
然后程序构造 \(\mathrm{PQ}(X)\) 的求和项。因为 \(p^q\le X\) 且 \(q\ge 2\)，所以素数底数只需要枚举到 \(\sqrt{X}=10^6\)。实现用筛法生成不超过 \(10^6\) 的全部素数，再取 \(2\) 到 \(39\) 之间的素数作为可能的指数，对每个合法的 \(p^q\le X\) 累加到 prime-prime 总和中。
最后答案就是
$$\text{完全幂总和}-\text{prime-prime 幂总和}-16.$$
实现里还加入了几组小规模校验：像 \(36\)、\(81\)、\(100\)、\(216\) 这样的正例都被构造性地变换到 \(64\)，而 \(16\) 的负例则说明它的所有可达值始终停留在 \(2\) 的幂之中。
记
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
这表示去重之前生成出的原始完全幂候选个数。由于平方项规模最大，所以 \(M=O(X^{1/2})\)。因此，对这些候选值排序并去重需要 \(O(M\log M)\) 时间和 \(O(M)\) 空间。
生成 \(10^6\) 以内素数的筛法需要 \(O(10^6\log\log 10^6)\) 时间和 \(O(10^6)\) 空间。指数端只有少量素数，因为 \(E=39\)。总体上，这个方法对 \(X=10^{12}\) 完全足够，而且避免了对操作序列进行爆炸式搜索。
Мы начинаем со списка \(\{n\}\), содержащего один элемент. Alice может заменить два элемента \(a,b>1\) одним числом \(a^b\), а может заменить один элемент \(c\) двумя числами \(a,b>1\), если \(c=a^b\). Число \(n>1\) называется creative, если для любого целевого \(m>1\) существует некоторая последовательность таких операций, приводящая к списку, содержащему \(m\).
В задаче 616 нужно вычислить
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n.$$
Реализации не перебирают весь граф преобразований напрямую. Вместо этого они используют классификацию всех creative-чисел до заданной границы и сводят задачу к явному перечислению нескольких множеств.
Положим \(X=10^{12}\). Введем множества
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ простое},\ q\text{ простое}\}.$$
Реализации на C++, Python и Java используют классификацию
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
где \(\mathcal{C}(X)\) обозначает множество creative-чисел, не превосходящих \(X\). То есть надо взять все совершенные степени, удалить семейство prime-prime и отдельно удалить число \(16\).
Если \(n\) не является совершенной степенью, то стартовый список \(\{n\}\) вообще нельзя разложить: не существует целых \(a,b>1\) таких, что \(n=a^b\). Значит, процесс немедленно останавливается, и единственное число, которое когда-либо появится в списке, это само \(n\).
Но creative-число по определению должно уметь достигать любого целевого \(m>1\). Следовательно, всякое creative \(n\le X\) обязано лежать в \(\mathrm{PP}(X)\).
Рассмотрим
$$n=p^q,$$
где \(p\) и \(q\) простые. После разложения мы получаем список \(\{p,q\}\). Ни одно из этих чисел нельзя разложить дальше, потому что простые числа не являются нетривиальными совершенными степенями.
Из состояния \(\{p,q\}\) можно только снова получить \(p^q\) или, поменяв порядок, \(q^p\). Если \(p=q\), то даже нового состояния не возникает. Значит, множество достижимых состояний слишком мало и никак не может содержать произвольные цели.
Поэтому все элементы \(\mathrm{PQ}(X)\) нужно исключить.
Число \(16\) является совершенной степенью, но не принадлежит \(\mathrm{PQ}(X)\), потому что естественные разложения таковы:
$$16=2^4=4^2.$$
Тем не менее оно не creative. Любое нетривиальное разложение \(16\) порождает только степени двойки, и дальнейшие разложения этих значений снова дают только степени двойки.
Операция слияния тоже сохраняет это свойство. Если текущие элементы имеют вид \(2^r\) и \(2^s\), то
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
то есть результат опять является степенью двойки. Значит, стартуя из \(16\), мы никогда не покидаем мир степеней двойки. В частности, число \(3\) никогда не появится. Поэтому \(16\) вычитается отдельно.
Трудная часть заключается в обратном утверждении: кроме исключенного семейства \(\mathrm{PQ}(X)\) и специального случая \(16\), все остальные совершенные степени до \(10^{12}\) являются creative. Именно эту теорему реализации принимают как математическую основу.
После этого задача уже не связана с поиском последовательностей операций. Нужно просто аккуратно просуммировать правильное множество чисел.
Следовательно,
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
где \(X=10^{12}\).
Здесь есть два важных вычислительных замечания.
Во-первых, \(\mathrm{PP}(X)\) нужно дедуплицировать, потому что одно и то же число может появиться из разных пар основание-показатель. Например,
$$64=2^6=4^3=8^2.$$
Во-вторых, для \(\mathrm{PQ}(X)\) дедупликация не нужна. Если \(p^q=r^s\) при простых основаниях и простых показателях, то из единственности разложения на простые множители немедленно следует \(p=r\) и \(q=s\).
Совершенные степени, не превосходящие \(100\), таковы:
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
Среди них family prime-prime составляет
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
Если удалить эти значения, а затем удалить \(16\), останется
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
Поэтому
$$S(100)=36+64+81+100=281.$$
Этот пример в точности повторяет структуру полной программы: перечислить совершенные степени, вычесть prime-prime и отдельно убрать исключение \(16\).
Сначала реализации находят максимальный показатель \(E\), для которого \(2^E\le X\). При \(X=10^{12}\) получаем \(E=39\), так как \(2^{39}\le 10^{12} < 2^{40}\).
Далее для каждого \(e=2,3,\dots,E\) код с помощью целочисленного бинарного поиска находит наибольшее основание \(a\), удовлетворяющее \(a^e\le X\). После этого перечисляются все значения \(a^e\) в соответствующем диапазоне. Они собираются в контейнер, затем сортируются и очищаются от повторов; их сумма дает вклад \(\mathrm{PP}(X)\).
Затем строится вычитаемое множество \(\mathrm{PQ}(X)\). Из условия \(p^q\le X\) и неравенства \(q\ge 2\) следует \(p\le \sqrt{X}=10^6\), поэтому достаточно простого решета до \(10^6\). Возможные показатели - это простые числа от \(2\) до \(39\). Каждый допустимый член \(p^q\le X\) добавляется к сумме prime-prime.
После этого ответ вычисляется как
$$\text{сумма совершенных степеней}-\text{сумма prime-prime степеней}-16.$$
В реализациях также есть короткие проверки здравого смысла: для положительных примеров \(36\), \(81\), \(100\) и \(216\) явно строятся цепочки, ведущие к \(64\), а для \(16\) выполняется отрицательная проверка, показывающая, что все достижимые значения остаются степенями двойки.
Пусть
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
Это количество сырых кандидатов в совершенные степени до дедупликации. Доминируют квадраты, поэтому \(M=O(X^{1/2})\). Значит, сортировка и удаление повторов требуют \(O(M\log M)\) времени и \(O(M)\) памяти.
Решето до \(10^6\) работает за \(O(10^6\log\log 10^6)\) времени и использует \(O(10^6)\) памяти. Список простых показателей очень мал, потому что \(E=39\). В итоге метод более чем достаточно быстр для \(X=10^{12}\) и полностью избегает перебора всего графа преобразований.
نبدأ بالقائمة \(\{n\}\) التي تحتوي على عنصر واحد. تستطيع Alice أن تستبدل عنصرين \(a,b>1\) بالعدد \(a^b\)، كما تستطيع أن تستبدل عنصرًا واحدًا \(c\) بعنصرين \(a,b>1\) إذا كان \(c=a^b\). يسمى العدد \(n>1\) creative إذا كان بالإمكان، لأي هدف \(m>1\)، الوصول عبر سلسلة من هذه العمليات إلى قائمة تحتوي على \(m\).
في المسألة 616 نريد حساب
$$S=\sum_{\substack{n\le 10^{12} \\ n\text{ creative}}} n.$$
التنفيذات لا تبحث مباشرة في كامل فضاء التحولات، بل تعتمد على توصيف رياضي للأعداد creative حتى الحد المطلوب، ثم تحول المسألة إلى تعداد منظم لمجموعات عددية محددة.
لنضع \(X=10^{12}\). نعرّف المجموعتين
$$\mathrm{PP}(X)=\{a^e\le X : a\ge 2,\ e\ge 2\},$$
$$\mathrm{PQ}(X)=\{p^q\le X : p\text{ prime},\ q\text{ prime}\}.$$
تعتمد تنفيذات C++ وPython وJava على التصنيف
$$\mathcal{C}(X)=\mathrm{PP}(X)\setminus \mathrm{PQ}(X)\setminus \{16\},$$
حيث تمثل \(\mathcal{C}(X)\) مجموعة الأعداد creative التي لا تتجاوز \(X\). أي أن الأعداد المطلوبة هي كل القوى الكاملة، بعد حذف عائلة الأساس الأولي والأسّ الأولي، ثم حذف القيمة الشاذة المنفردة \(16\).
إذا لم يكن \(n\) قوة كاملة، فلا يمكن تفكيك القائمة الابتدائية \(\{n\}\) أصلًا، لأنه لا توجد أعداد صحيحة \(a,b>1\) تحقق \(n=a^b\). عندئذ تتوقف العملية فورًا، ويبقى العدد الوحيد الذي يمكن أن يظهر هو \(n\) نفسه.
لكن العدد creative يجب أن يستطيع الوصول إلى كل هدف \(m>1\). لذلك لا بد أن يكون كل عدد creative ضمن \(\mathrm{PP}(X)\).
لننظر إلى
$$n=p^q,$$
حيث \(p\) أولي و\(q\) أولي. عند تفكيك \(n\) نحصل فقط على القائمة \(\{p,q\}\). ولا يمكن تفكيك أي من هذين العنصرين أكثر، لأن الأعداد الأولية ليست قوى كاملة غير تافهة.
ومن الحالة \(\{p,q\}\) لا توجد إلا عمليتا دمج ممكنتان: إعادة تكوين \(p^q\)، أو عكس الترتيب وإنتاج \(q^p\). وإذا كان \(p=q\)، فلا نحصل حتى على حالة جديدة. إذًا فضاء الحالات الممكنة صغير جدًا، ولا يمكن أن يحتوي أهدافًا اعتباطية.
لهذا السبب يجب استبعاد جميع عناصر \(\mathrm{PQ}(X)\).
العدد \(16\) قوة كاملة فعلًا، لكنه لا ينتمي إلى \(\mathrm{PQ}(X)\)، لأن تمثيلاته الطبيعية هي
$$16=2^4=4^2.$$
ومع ذلك فهو ليس creative. فأي تفكيك غير تافه للعدد \(16\) يولد فقط قوى للعدد \(2\)، والاستمرار في تفكيك هذه القيم يعطينا أيضًا قوى للعدد \(2\) فقط.
وعملية الدمج تحافظ على هذه الخاصية كذلك. فإذا كانت العناصر الحالية كلها من الصورة \(2^r\) و\(2^s\)، فإن
$$\left(2^r\right)^{2^s}=2^{r2^s},$$
وهو أيضًا قوة للعدد \(2\). لذلك، إذا بدأنا من \(16\)، فلن نغادر عالم قوى \(2\) أبدًا. وعلى وجه الخصوص، لن يظهر هدف مثل \(3\). ولهذا تطرح التنفيذات القيمة \(16\) طرحًا منفصلًا.
الجزء الأصعب هو الاتجاه العكسي: باستثناء العائلة \(\mathrm{PQ}(X)\) والحالة الخاصة \(16\)، فإن كل قوة كاملة أخرى حتى \(10^{12}\) هي creative. وهذا هو بالضبط الأساس الرياضي الذي تعتمد عليه التنفيذات.
وبمجرد قبول هذا التوصيف، لا تعود المسألة مسألة بحث عن سلاسل تحويل، بل تصبح مسألة جمع منظم: نجمع كل القوى الكاملة حتى \(X\)، ثم نطرح قوى prime-prime، ثم نطرح \(16\).
إذًا نحصل على
$$S(X)=\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16,$$
مع \(X=10^{12}\).
وتوجد هنا ملاحظتان حسابيتان مهمتان:
أولًا، يجب إزالة التكرارات من \(\mathrm{PP}(X)\)، لأن العدد نفسه قد يظهر بعدة صور أسية مختلفة. ومن أمثلة ذلك
$$64=2^6=4^3=8^2.$$
ثانيًا، لا حاجة إلى إزالة التكرار من \(\mathrm{PQ}(X)\). فإذا كان \(p^q=r^s\) مع كون الأساسين أوليين والأسين أوليين، فإن التحليل الأولي الوحيد يفرض مباشرة \(p=r\) و\(q=s\).
القوى الكاملة التي لا تتجاوز \(100\) هي
$$\mathrm{PP}(100)=\{4,8,9,16,25,27,32,36,49,64,81,100\}.$$
ومن بينها تكون قوى prime-prime
$$\mathrm{PQ}(100)=\{4,8,9,25,27,32,49\}.$$
بعد حذف هذه القيم ثم حذف \(16\) نحصل على
$$\mathcal{C}(100)=\{36,64,81,100\}.$$
وعليه فإن
$$S(100)=36+64+81+100=281.$$
هذا المثال الصغير يطابق الحساب الكامل تمامًا: نولّد القوى الكاملة، ثم نطرح عائلة prime-prime، ثم نطرح الاستثناء المنفرد \(16\).
تبدأ التنفيذات بتحديد أكبر أس \(E\) يحقق \(2^E\le X\). وعندما يكون \(X=10^{12}\)، نحصل على \(E=39\)، لأن \(2^{39}\le 10^{12} < 2^{40}\).
بعد ذلك، ولكل أس \(e=2,3,\dots,E\)، تحسب الشيفرة بأداة بحث ثنائي صحيحة أكبر أساس \(a\) يحقق \(a^e\le X\). ثم تعدّد جميع القيم \(a^e\) في هذا المجال وتخزنها. وبعد الفرز وإزالة التكرارات نحصل على مجموع \(\mathrm{PP}(X)\).
في الخطوة التالية تُبنى قيمة \(\mathrm{PQ}(X)\). بما أن \(p^q\le X\) و\(q\ge 2\)، فإن كل أساس أولي يحقق \(p\le \sqrt{X}=10^6\)، ولذلك يكفي غربال للأعداد الأولية حتى \(10^6\). أما الأسس الممكنة فهي الأعداد الأولية بين \(2\) و\(39\). وكل قيمة \(p^q\le X\) تضاف إلى مجموع prime-prime.
وفي النهاية يكون الجواب وفق الصيغة نفسها المستخدمة في القسم الرياضي:
$$\sum_{x\in \mathrm{PP}(X)} x-\sum_{x\in \mathrm{PQ}(X)} x-16.$$
وتحتوي التنفيذات أيضًا على فحوصات قصيرة للاتساق: بعض القيم المقبولة مثل \(36\) و\(81\) و\(100\) و\(216\) تُظهر سلاسل تصل إلى \(64\)، في حين أن \(16\) يفشل في فحص سلبي لأن كل القيم الممكن الوصول إليها تبقى قوى للعدد \(2\).
لنعرّف
$$M=\sum_{e=2}^{E}\left\lfloor X^{1/e}\right\rfloor.$$
وهذا يمثل عدد مرشحي القوى الكاملة الخام قبل إزالة التكرارات. والحالة المسيطرة هي المربعات، لذلك \(M=O(X^{1/2})\). ومن ثم فإن الفرز وإزالة التكرارات يكلفان \(O(M\log M)\) زمنًا و\(O(M)\) ذاكرة.
أما غربال الأعداد الأولية حتى \(10^6\) فيكلف \(O(10^6\log\log 10^6)\) زمنًا و\(O(10^6)\) ذاكرة. وقائمة الأسس الأولية صغيرة جدًا لأن \(E=39\). وبصورة عامة فإن هذه الطريقة مناسبة جدًا لـ \(X=10^{12}\)، وتتفادى كليًا محاولة استكشاف فضاء التحولات الكامل.