We want the number of integers \(n\) with \(0 \le n \lt 50{,}000{,}000\) that can be written in the form
$$n=p^2+q^3+r^4,$$
where \(p\), \(q\), and \(r\) are prime. The important point is that we are counting distinct values of \(n\), not counting how many prime triples produce them.
So if two different choices of primes give the same sum, that integer should still be counted only once.
The exponents \(2\), \(3\), and \(4\) make the search space much smaller than it first appears. Once those bounds are written down, the problem becomes a finite set-construction problem: build three short lists of prime powers, combine them in increasing order, and deduplicate the resulting sums.
For a general limit \(N\), define
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
Then the required answer is
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
The exponent bounds are immediate:
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
Because \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\) for \(N>1\), a single sieve up to \(\sqrt{N}\) already produces every prime that can appear in any of the three lists.
After the sieve, we are no longer searching through all integers below \(N\). We are combining one value from each of three finite sets. The square list is only moderately long, the cube list is much shorter, and the fourth-power list is tiny. That imbalance is exactly why a direct enumeration is practical for the Project Euler limit.
No recurrence or generating function is needed here. The real mathematical reduction is the observation that the problem is equivalent to taking a set sum of three bounded prime-power families.
The primes are generated in increasing order, and the maps \(x\mapsto x^2\), \(x\mapsto x^3\), and \(x\mapsto x^4\) are strictly increasing on positive integers. Therefore each of the lists \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\), and \(\mathcal{S}_4(N)\) is already sorted.
This gives the key invariant behind the nested loops. Fix \(a\in\mathcal{S}_2(N)\). If \(a+b \ge N\) for some \(b\in\mathcal{S}_3(N)\), then every later cube \(b'\ge b\) also fails. Likewise, for fixed \(a\) and \(b\), if \(a+b+c \ge N\) for some \(c\in\mathcal{S}_4(N)\), then every later fourth power \(c'\ge c\) also fails.
So the search can stop at the first overflow inside each ordered loop. That is the decisive implementation invariant: once a partial sum reaches the limit, the remainder of that sorted suffix cannot contribute any valid value.
The problem asks for representable integers, not for the number of representations. Mathematically, the object we want is the set
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
and the answer is simply \(|\mathcal{T}(N)|\).
That is why deduplication is essential. Even if different prime triples collide on the same sum, the set keeps only the underlying integer once.
For \(N=50\), the admissible prime powers are
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
Since there is only one fourth power below 50, every valid value has the form \(a+b+16\). Checking the possibilities gives
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
and every other choice is at least 50. Therefore
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
This miniature case already shows the complete strategy: form the three prime-power lists, enumerate their sums in increasing order, and count distinct valid totals.
The C++, Python, and Java implementations first generate all primes up to \(\lfloor\sqrt{N}\rfloor+1\) with the Sieve of Eratosthenes. From that single ordered prime list they build three ordered arrays: prime squares below \(N\), prime cubes below \(N\), and prime fourth powers below \(N\).
The compiled implementations use 64-bit arithmetic while forming the powers so that the repeated multiplications remain safe even though every retained value is still below the final limit.
After preprocessing, the implementation runs a triple nested enumeration over the square list, the cube list, and the fourth-power list. Because the lists are sorted, the moment a partial sum already reaches \(N\), the current loop stops immediately. This is the monotonicity argument from the mathematics section translated directly into code.
Every valid sum \(a+b+c \lt N\) is inserted into a hash-based set. If the same integer is produced again from a different triple of primes, the set keeps only one copy. The final output is the size of that set, which is exactly the number of distinct integers representable in the required form.
Let \(B=\lfloor\sqrt{N}\rfloor\), and let \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\). The sieve phase costs \(O(B\log\log B)\) time and \(O(B)\) space.
The enumeration phase has worst-case time \(O(s_2s_3s_4)\), with average \(O(1)\) insertion into the deduplication set for each valid sum. In practice the work is smaller than the full product because the sorted lists allow early termination as soon as a partial sum reaches the limit.
Total space usage is \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\), dominated by the sieve table, the three prime-power lists, and the set of distinct sums. For \(N=50{,}000{,}000\), these structures remain small enough that the direct deduplicated enumeration is entirely practical.
Gesucht ist die Anzahl der ganzen Zahlen \(n\) mit \(0 \le n \lt 50{,}000{,}000\), die sich in der Form
$$n=p^2+q^3+r^4$$
schreiben lassen, wobei \(p\), \(q\) und \(r\) Primzahlen sind. Entscheidend ist dabei, dass verschiedene Darstellungen derselben Zahl nur einmal gezählt werden.
Wir zählen also nicht Primzahltripel, sondern verschiedene Zielwerte \(n\).
Die Exponenten \(2\), \(3\) und \(4\) schrumpfen den Suchraum sehr stark. Sobald man diese Schranken sauber formuliert, wird aus der Aufgabe ein endliches Mengenproblem: drei kurze Listen von Primzahlpotenzen erzeugen, ihre Summen in geordneter Form durchlaufen und gleiche Werte zusammenfassen.
Für eine allgemeine Schranke \(N\) definieren wir
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
Die gesuchte Anzahl ist dann
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
Die Exponenten liefern sofort die Grenzen
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
Weil für \(N>1\) gilt \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\), reicht ein einziges Sieb bis \(\sqrt{N}\), um alle Primzahlen für sämtliche drei Listen zu erzeugen.
Nach dem Sieben durchsuchen wir nicht mehr alle Zahlen unterhalb von \(N\). Stattdessen kombinieren wir je ein Element aus drei endlichen Mengen. Die Quadratliste ist noch vergleichsweise lang, die Kubikliste deutlich kürzer und die Liste der vierten Potenzen sehr klein. Genau diese Asymmetrie macht die direkte Aufzählung für die feste Schranke der Aufgabe praktikabel.
Es braucht hier keine Rekursion und keine erzeugende Funktion. Die eigentliche mathematische Reduktion besteht darin, die Aufgabe als Mengensumme dreier beschränkter Primzahlpotenzfamilien zu erkennen.
Die Primzahlen werden aufsteigend erzeugt, und die Abbildungen \(x\mapsto x^2\), \(x\mapsto x^3\) und \(x\mapsto x^4\) sind auf positiven Zahlen streng monoton steigend. Deshalb sind auch die Listen \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\) und \(\mathcal{S}_4(N)\) bereits sortiert.
Daraus folgt die zentrale Invariante der verschachtelten Schleifen. Ist \(a\in\mathcal{S}_2(N)\) fest und gilt für ein \(b\in\mathcal{S}_3(N)\) bereits \(a+b \ge N\), dann scheitern auch alle späteren Kuben \(b'\ge b\). Ebenso gilt für festes \(a\) und \(b\): Sobald für ein \(c\in\mathcal{S}_4(N)\) die Ungleichung \(a+b+c \ge N\) eintritt, können auch alle späteren vierten Potenzen \(c'\ge c\) nicht mehr funktionieren.
Deshalb darf die Suche in jeder geordneten Schleife beim ersten Überschreiten der Grenze sofort abbrechen. Diese Monotonie macht den Unterschied zwischen roher Vollsuche und einer gezielten Enumeration.
Gesucht sind darstellbare Zahlen, nicht die Anzahl ihrer Darstellungen. Das mathematische Objekt ist also die Menge
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
und die Antwort ist \(|\mathcal{T}(N)|\).
Die Deduplizierung ist daher nicht bloß ein Implementierungsdetail, sondern entspricht exakt der Aufgabenstellung.
Für \(N=50\) lauten die zulässigen Primzahlpotenzen
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
Da es unter 50 nur eine vierte Primzahlpotenz gibt, hat jeder zulässige Wert die Form \(a+b+16\). Man erhält
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
während jede andere Wahl mindestens 50 ergibt. Also gilt
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
Dieses kleine Beispiel zeigt bereits die vollständige Methode: drei Listen aufbauen, geordnet kombinieren und gültige Summen als verschiedene Werte zählen.
Die Implementierungen in C++, Python und Java erzeugen zunächst mit dem Sieb des Eratosthenes alle Primzahlen bis \(\lfloor\sqrt{N}\rfloor+1\). Aus dieser einen geordneten Primzahlliste entstehen anschließend drei geordnete Arrays: Primzahlquadrate, Primzahlkuben und vierte Primzahlpotenzen unterhalb von \(N\).
Die kompilierten Versionen verwenden beim Bilden der Potenzen 64-Bit-Arithmetik, damit die wiederholten Multiplikationen sicher bleiben, obwohl alle übernommenen Werte selbst noch unter der Endgrenze liegen.
Nach dieser Vorverarbeitung folgt eine dreifach verschachtelte Enumeration über die Quadrat-, Kubik- und Viertpotenzliste. Weil alle Listen sortiert sind, kann die aktuelle Schleife sofort abbrechen, sobald eine Teilsumme bereits \(N\) erreicht. Genau so wird das Monotonieargument aus dem mathematischen Teil direkt in Programmform umgesetzt.
Jede gültige Summe \(a+b+c \lt N\) wird in eine hashbasierte Menge eingefügt. Falls dieselbe Zahl aus einem anderen Primzahltripel erneut entsteht, bleibt in der Menge trotzdem nur ein Exemplar erhalten. Am Ende wird schlicht die Größe dieser Menge ausgegeben.
Sei \(B=\lfloor\sqrt{N}\rfloor\), und seien \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\). Die Siebphase benötigt \(O(B\log\log B)\) Zeit und \(O(B)\) Speicher.
Die Enumerationsphase hat im Worst Case Laufzeit \(O(s_2s_3s_4)\), wobei das Einfügen in die Deduplizierungsmenge im Mittel \(O(1)\) kostet. Praktisch ist die Arbeit kleiner als dieses rohe Produkt, weil die sortierten Listen frühe Abbrüche erlauben, sobald eine Teilsumme die Grenze erreicht.
Der gesamte Speicherbedarf ist \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\). Dominiert wird er vom Sieb, den drei Potenzlisten und der Menge der verschiedenen Summen. Für \(N=50{,}000{,}000\) bleibt das alles in einem Bereich, der direkte deduplizierte Aufzählung gut erlaubt.
Aranan şey, \(0 \le n \lt 50{,}000{,}000\) koşulunu sağlayan ve
$$n=p^2+q^3+r^4$$
biçiminde yazılabilen tamsayıların sayısıdır; burada \(p\), \(q\) ve \(r\) asaldır. Önemli nokta, aynı sayıyı üreten farklı asal üçlülerin ayrı ayrı sayılmamasıdır.
Yani temsil sayısını değil, temsil edilebilen farklı \(n\) değerlerini sayıyoruz.
\(2\), \(3\) ve \(4\) üsleri arama alanını ilk bakışta göründüğünden çok daha küçük hale getirir. Bu sınırlar yazıldıktan sonra problem, üç kısa asal-kuvvet listesini üretip bunların toplamlarını tekilleştirme problemine dönüşür.
Genel bir \(N\) limiti için
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}$$
kümelerini tanımlayalım. O zaman aranan değer
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|$$
olur. Üslerden doğrudan şu sınırlar gelir:
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
\(N>1\) için \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\) olduğundan, \(\sqrt{N}\)'ye kadar tek bir asal eleği kurmak üç listenin tamamı için yeterlidir.
Eleği kurduktan sonra artık \(N\)'in altındaki tüm sayıları dolaşmıyoruz. Yalnızca üç sonlu kümeden birer eleman seçiyoruz. Kare listesi en uzun listedir, küp listesi belirgin biçimde daha kısadır, dördüncü kuvvet listesi ise çok küçüktür. Tam da bu dengesizlik, Project Euler sınırı için doğrudan enumerasyonu uygulanabilir kılar.
Burada bir yineleme bağıntısına ihtiyaç yoktur. Asıl matematiksel indirgeme, problemi üç sınırlı asal kuvvet ailesinin küme toplamı olarak görmektir.
Asallar artan sırada üretilir; ayrıca \(x\mapsto x^2\), \(x\mapsto x^3\) ve \(x\mapsto x^4\) fonksiyonları pozitif tamsayılarda sıkı biçimde artandır. Bu yüzden \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\) ve \(\mathcal{S}_4(N)\) listeleri zaten artan sıradadır.
İç içe döngülerin temel değişmezi budur. Sabit bir \(a\in\mathcal{S}_2(N)\) için, eğer bir \(b\in\mathcal{S}_3(N)\) değerinde \(a+b \ge N\) olursa, sonraki her \(b'\ge b\) için de durum başarısız olur. Aynı şekilde sabit \(a\) ve \(b\) için bir \(c\in\mathcal{S}_4(N)\) değerinde \(a+b+c \ge N\) olduğunda, sonraki her \(c'\ge c\) de başarısız olacaktır.
Dolayısıyla her sıralı döngü, limit ilk kez aşıldığında hemen durabilir. Bu monoton kesme noktası, çözümün hızını belirleyen ana fikirdir.
Sorulan şey temsil sayısı değil, temsil edilebilen sayıların sayısıdır. Bu yüzden asıl nesne
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\}$$
kümesidir ve cevap \(|\mathcal{T}(N)|\) olur.
Tekilleştirme yalnızca programlama kolaylığı değildir; problem metninin matematiksel anlamını tam olarak budur.
\(N=50\) için uygun asal kuvvetler
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}$$
olur. 50'nin altında yalnızca tek bir asal dördüncü kuvvet bulunduğu için bütün adaylar \(a+b+16\) biçimindedir. Olasılıkları kontrol edersek
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47$$
elde edilir; diğer tüm seçimler en az 50'dir. Bu nedenle
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
Bu küçük örnek bile tüm stratejiyi gösterir: üç listeyi kur, sıralı biçimde topla ve geçerli toplamları farklı değerler olarak say.
C++, Python ve Java uygulamaları önce Eratosthenes eleği ile \(\lfloor\sqrt{N}\rfloor+1\)'e kadar tüm asalları üretir. Ardından bu tek sıralı asal listesinden üç sıralı dizi oluşturulur: \(N\)'den küçük asal kareler, asal küpler ve asal dördüncü kuvvetler.
Derlenmiş sürümler, kuvvetleri oluştururken çarpımlar güvenli kalsın diye 64 bit aritmetik kullanır; buna rağmen tutulan her değer son limitin altındadır.
Ön hazırlıktan sonra uygulama kare listesi, küp listesi ve dördüncü kuvvet listesi üzerinde üçlü iç içe enumerasyon yapar. Listeler sıralı olduğu için bir ara toplam \(N\)'ye ulaştığı anda ilgili döngü hemen kırılır. Matematik bölümündeki monotonluk argümanı burada doğrudan kod akışına dönüşür.
Her geçerli \(a+b+c \lt N\) toplamı hash tabanlı bir kümeye eklenir. Farklı bir asal üçlüsü aynı sayıyı yeniden üretirse küme yalnızca tek kopyayı tutar. Son çıktı bu kümenin büyüklüğüdür.
\(B=\lfloor\sqrt{N}\rfloor\) olsun ve \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\) diyelim. Elek aşaması \(O(B\log\log B)\) zaman ve \(O(B)\) alan kullanır.
Sayım aşamasının en kötü durum zamanı \(O(s_2s_3s_4)\)'tür; geçerli her toplam için kümeye ekleme işlemi ortalama \(O(1)\) kabul edilir. Pratikte gerçek iş miktarı bu ham çarpımdan küçüktür, çünkü sıralı listeler limit aşıldığında erken kırılmaya izin verir.
Toplam alan kullanımı \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\) olur. Baskın yapılar elek tablosu, üç kuvvet listesi ve farklı toplamları tutan kümedir. \(N=50{,}000{,}000\) için bu yaklaşım bütünüyle pratiktir.
Se busca cuántos enteros \(n\) con \(0 \le n \lt 50{,}000{,}000\) pueden escribirse como
$$n=p^2+q^3+r^4,$$
donde \(p\), \(q\) y \(r\) son primos. El detalle importante es que no contamos representaciones, sino valores distintos de \(n\).
Si dos ternas distintas de primos producen la misma suma, ese entero debe contarse una sola vez.
Los exponentes \(2\), \(3\) y \(4\) reducen el problema a un espacio de búsqueda mucho más pequeño de lo que sugiere el límite \(50{,}000{,}000\). Una vez escritas esas cotas, la tarea se convierte en construir tres listas finitas de potencias primas, recorrer sus sumas en orden y eliminar duplicados.
Para un límite general \(N\), definimos
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
La cantidad pedida es entonces
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
Las cotas salen directamente de los exponentes:
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
Como \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\) para \(N>1\), un solo tamiz hasta \(\sqrt{N}\) ya genera todos los primos que pueden aparecer en cualquiera de las tres listas.
Después del tamiz ya no se examinan todos los enteros menores que \(N\). Solo se combina un elemento de cada uno de tres conjuntos finitos. La lista de cuadrados es la más larga, la de cubos es bastante más corta y la de cuartas potencias es muy pequeña. Esa asimetría es precisamente lo que vuelve práctica la enumeración directa para el límite fijo del problema.
No hace falta una recurrencia sofisticada. La reducción matemática real consiste en reconocer que el problema es una suma de conjuntos de tres familias acotadas de potencias primas.
Los primos se generan en orden creciente, y las funciones \(x\mapsto x^2\), \(x\mapsto x^3\) y \(x\mapsto x^4\) son estrictamente crecientes sobre los enteros positivos. Por eso las listas \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\) y \(\mathcal{S}_4(N)\) ya quedan ordenadas.
De ahí sale el invariante clave de los bucles anidados. Fijado \(a\in\mathcal{S}_2(N)\), si para cierto \(b\in\mathcal{S}_3(N)\) se cumple \(a+b \ge N\), entonces cualquier cubo posterior \(b'\ge b\) también falla. Del mismo modo, fijados \(a\) y \(b\), si para cierto \(c\in\mathcal{S}_4(N)\) ya se tiene \(a+b+c \ge N\), entonces toda cuarta potencia posterior \(c'\ge c\) también queda descartada.
Eso permite detener cada bucle exactamente en el primer desbordamiento del límite. Ese corte monotónico es la razón principal por la que el algoritmo resulta eficiente.
La pregunta pide enteros representables, no cuántas formas hay de representarlos. Por tanto, el objeto matemático correcto es el conjunto
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
y la respuesta final es \(|\mathcal{T}(N)|\).
Eliminar duplicados no es un detalle cosmético de implementación; es exactamente la traducción de lo que pide el enunciado.
Para \(N=50\), las potencias primas admisibles son
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
Como solo hay una cuarta potencia prima por debajo de 50, todo valor válido tiene la forma \(a+b+16\). Al revisar las posibilidades obtenemos
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
mientras que cualquier otra elección ya alcanza o supera 50. Por tanto,
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
Este ejemplo pequeño ya contiene toda la idea de la solución completa: formar las tres listas, combinarlas en orden y contar únicamente los totales distintos que respetan el límite.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta \(\lfloor\sqrt{N}\rfloor+1\) mediante el tamiz de Eratóstenes. A partir de esa única lista ordenada construyen tres arreglos ordenados: cuadrados primos menores que \(N\), cubos primos menores que \(N\) y cuartas potencias primas menores que \(N\).
Las versiones compiladas usan aritmética de 64 bits al formar las potencias, de modo que las multiplicaciones repetidas sean seguras aunque todos los valores retenidos sigan estando por debajo del límite final.
Después del preprocesamiento, la implementación recorre en tres bucles anidados la lista de cuadrados, la de cubos y la de cuartas potencias. Como las listas están ordenadas, en cuanto una suma parcial alcanza \(N\), el bucle actual se interrumpe de inmediato. Es exactamente el argumento de monotonía de la sección matemática convertido en flujo de control.
Cada suma válida \(a+b+c \lt N\) se inserta en un conjunto basado en hash. Si la misma cantidad vuelve a aparecer a partir de otra terna de primos, el conjunto conserva una sola copia. La salida final es simplemente el tamaño de ese conjunto.
Sea \(B=\lfloor\sqrt{N}\rfloor\), y sean \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\). La fase del tamiz cuesta \(O(B\log\log B)\) tiempo y \(O(B)\) espacio.
La enumeración tiene tiempo de peor caso \(O(s_2s_3s_4)\), con inserción promedio \(O(1)\) en el conjunto de deduplicación para cada suma válida. En la práctica el trabajo es menor que ese producto bruto porque las listas ordenadas permiten terminar antes en cuanto una suma parcial llega al límite.
El espacio total es \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\), dominado por la tabla del tamiz, las tres listas de potencias y el conjunto de sumas distintas. Para \(N=50{,}000{,}000\), esta estrategia es perfectamente manejable.
题目要求统计所有满足 \(0 \le n \lt 50{,}000{,}000\) 且可以写成
$$n=p^2+q^3+r^4$$
的整数个数，其中 \(p\)、\(q\)、\(r\) 都是素数。这里真正要数的是不同的 \(n\)，而不是有多少组素数三元组给出了表示。
如果两组不同的素数产生了同一个和，这个整数也只能计入一次。
这道题之所以可以直接算出来，核心就在于指数 \(2\)、\(3\)、\(4\) 把候选范围压得非常小。只要把这些范围写清楚，原题就会变成一个有限集合问题：构造三个很短的素数幂列表，按顺序枚举它们的和，再把重复的结果合并掉。
对一般的上界 \(N\)，定义
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
那么要求的答案就是
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
指数立刻给出界：
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
而对任何 \(N>1\)，都有 \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\)。这意味着只要把素数筛到 \(\sqrt{N}\)，三个集合所需的所有素数就都已经包含在内了，因此整道题只需要做一次筛法预处理。
做完筛以后，我们并不是在 \(0\) 到 \(N-1\) 之间暴力搜索每个整数，而是在三个有限集合里各取一个元素。平方列表最长，立方列表短得多，四次幂列表则非常小。正是这种规模差异，使得对固定上界 \(50{,}000{,}000\) 的直接枚举完全可行。
这里不需要递推式，也不需要生成函数。真正的数学化简，是把题目看成三个受限素数幂集合的集合和问题。
素数是按从小到大的顺序生成的，而函数 \(x\mapsto x^2\)、\(x\mapsto x^3\)、\(x\mapsto x^4\) 在正整数上都严格递增。因此 \(\mathcal{S}_2(N)\)、\(\mathcal{S}_3(N)\)、\(\mathcal{S}_4(N)\) 三个列表天然就是升序排列的。
这就带来了实现中最重要的不变量。固定一个 \(a\in\mathcal{S}_2(N)\)。如果对某个 \(b\in\mathcal{S}_3(N)\) 已经有 \(a+b \ge N\)，那么后面所有更大的 \(b'\ge b\) 也一定失败。同理，固定 \(a\) 和 \(b\) 以后，如果对某个 \(c\in\mathcal{S}_4(N)\) 已经满足 \(a+b+c \ge N\)，那么后面所有更大的 \(c'\ge c\) 也全部无效。
因此，每一层有序循环都可以在第一次越界时立刻停止。这个“单调截断”正是程序能高效运行的关键。
题目问的是“有多少个整数可以表示”，不是“总共有多少种表示方式”。所以真正需要构造的是集合
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
最后答案就是 \(|\mathcal{T}(N)|\)。
这也是为什么去重是必需的。即使不同的素数三元组碰巧得到同一个整数，那个整数在答案里也只能算一次。
当 \(N=50\) 时，可用的素数幂为
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
由于 50 以下只有一个素数四次幂 \(16\)，所以每个候选值都形如 \(a+b+16\)。逐个检查可得
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
其余选择都会达到或超过 50。因此
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
这个小例子已经把整套方法完整展示出来了：先构造三个列表，再按升序求和，并且只统计满足上界的不同结果。
C++、Python 和 Java 的实现都会先用埃拉托斯特尼筛生成所有不超过 \(\lfloor\sqrt{N}\rfloor+1\) 的素数。然后从这一份有序素数表中分别构造三份有序数组：小于 \(N\) 的素数平方、素数立方和素数四次幂。
编译型实现在线性构造这些幂时使用 64 位整数，这样连续乘法始终安全；而真正保留下来的所有值仍然都小于最终上界。
预处理完成后，程序在平方列表、立方列表和四次幂列表上做三重嵌套枚举。由于三个列表都是升序的，一旦某个部分和已经达到 \(N\)，当前循环就立刻终止。数学部分中的单调性论证，在这里直接变成了控制流程。
每个满足 \(a+b+c \lt N\) 的和都会被插入一个哈希集合。如果另一个素数三元组再次生成同一个整数，集合仍然只保留一份。最终输出就是这个集合的大小，也就是题目要求的不同可表示整数个数。
设 \(B=\lfloor\sqrt{N}\rfloor\)，并令 \(s_2=|\mathcal{S}_2(N)|\)、\(s_3=|\mathcal{S}_3(N)|\)、\(s_4=|\mathcal{S}_4(N)|\)。筛法阶段的时间复杂度是 \(O(B\log\log B)\)，空间复杂度是 \(O(B)\)。
枚举阶段的最坏时间复杂度为 \(O(s_2s_3s_4)\)。对每个有效和，插入去重集合的平均代价是 \(O(1)\)。实际运行时通常优于这个上界，因为有序列表让程序在部分和达到上界后可以提前停止。
总空间复杂度为 \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\)，主要由筛表、三个幂列表以及不同和的集合构成。对于 \(N=50{,}000{,}000\) 这一固定规模，这种方法完全在可处理范围内。
Нужно посчитать количество целых чисел \(n\), удовлетворяющих \(0 \le n \lt 50{,}000{,}000\), которые можно представить в виде
$$n=p^2+q^3+r^4,$$
где \(p\), \(q\) и \(r\) — простые числа. Важно, что считаются различные значения \(n\), а не число различных троек простых.
Если две разные тройки дают одну и ту же сумму, такой результат должен учитываться только один раз.
Степени \(2\), \(3\) и \(4\) резко ограничивают пространство поиска. После того как эти ограничения выписаны, задача превращается в работу с тремя конечными списками простых степеней: нужно построить их, перечислить допустимые суммы в возрастающем порядке и убрать совпадения.
Для общего предела \(N\) введем обозначения
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
Тогда искомая величина равна
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
Из показателей степеней сразу следуют оценки
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
Поскольку при \(N>1\) выполняется \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\), достаточно одного решета до \(\sqrt{N}\), чтобы получить все простые числа, которые могут появиться в любом из трех списков.
После построения решета мы больше не рассматриваем все числа меньше \(N\). Мы просто берем по одному элементу из трех конечных множеств. Список квадратов самый длинный, список кубов заметно короче, а список четвертых степеней совсем мал. Именно эта разница в размерах делает прямое перечисление практичным для фиксированного предела задачи.
Никакая специальная рекурсия здесь не нужна. Главный математический шаг — увидеть задачу как сумму множеств трех ограниченных семейств простых степеней.
Простые числа генерируются по возрастанию, а функции \(x\mapsto x^2\), \(x\mapsto x^3\) и \(x\mapsto x^4\) строго возрастают на положительных целых. Поэтому списки \(\mathcal{S}_2(N)\), \(\mathcal{S}_3(N)\) и \(\mathcal{S}_4(N)\) уже отсортированы.
Отсюда появляется ключевой инвариант вложенных циклов. Зафиксируем \(a\in\mathcal{S}_2(N)\). Если для некоторого \(b\in\mathcal{S}_3(N)\) уже выполнено \(a+b \ge N\), то для любого следующего куба \(b'\ge b\) неравенство тем более сохранится. Аналогично, при фиксированных \(a\) и \(b\), если для некоторого \(c\in\mathcal{S}_4(N)\) оказалось \(a+b+c \ge N\), то все более поздние четвертые степени \(c'\ge c\) также бесполезны.
Значит, каждый цикл можно обрывать в первый момент, когда частичная сумма достигает предела. Именно эта монотонная отсечка и обеспечивает эффективность алгоритма.
По условию нужно считать представимые числа, а не количество способов представления. Следовательно, основным объектом является множество
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
и ответ равен \(|\mathcal{T}(N)|\).
Устранение повторов здесь не является чисто технической деталью; оно буквально повторяет математический смысл вопроса.
При \(N=50\) допустимые простые степени таковы:
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
Так как ниже 50 имеется только одна простая четвертая степень, каждый допустимый результат имеет вид \(a+b+16\). Перебор дает
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
а все остальные варианты уже не меньше 50. Поэтому
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
Этот маленький пример показывает всю стратегию в миниатюре: построить три списка, складывать их в порядке возрастания и учитывать только различные допустимые суммы.
Реализации на C++, Python и Java сначала строят все простые числа до \(\lfloor\sqrt{N}\rfloor+1\) с помощью решета Эратосфена. Затем из этого одного упорядоченного списка формируются три упорядоченных массива: простые квадраты, простые кубы и простые четвертые степени, меньшие \(N\).
В компилируемых версиях при построении степеней используется 64-битная арифметика, чтобы повторные умножения оставались безопасными, хотя все сохраняемые значения по-прежнему меньше итоговой границы.
После предобработки выполняется тройной вложенный перебор по спискам квадратов, кубов и четвертых степеней. Поскольку списки отсортированы, как только частичная сумма достигает \(N\), текущий цикл немедленно завершается. Это и есть прямое программное воплощение аргумента о монотонности.
Каждая допустимая сумма \(a+b+c \lt N\) добавляется в хеш-множество. Если та же величина возникает еще раз из другой тройки простых, в множестве все равно остается одна копия. Итогом работы становится размер этого множества.
Пусть \(B=\lfloor\sqrt{N}\rfloor\), а \(s_2=|\mathcal{S}_2(N)|\), \(s_3=|\mathcal{S}_3(N)|\), \(s_4=|\mathcal{S}_4(N)|\). Этап решета требует \(O(B\log\log B)\) времени и \(O(B)\) памяти.
Этап перечисления имеет в худшем случае время \(O(s_2s_3s_4)\), а вставка каждой допустимой суммы в структуру удаления повторов занимает в среднем \(O(1)\). На практике работы меньше, чем этот грубый верхний предел, потому что отсортированные списки позволяют завершать внутренние циклы сразу после достижения границы.
Полный расход памяти равен \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\). Доминируют таблица решета, три списка степеней и множество различных сумм. Для предела \(50{,}000{,}000\) этого более чем достаточно для практического решения.
المطلوب هو عدُّ جميع الأعداد الصحيحة \(n\) التي تحقق \(0 \le n \lt 50{,}000{,}000\) ويمكن كتابتها على الصورة
$$n=p^2+q^3+r^4,$$
حيث إن \(p\) و\(q\) و\(r\) أعداد أولية. النقطة المهمة هنا هي أننا لا نعد عدد التمثيلات، بل نعد القيم المختلفة للعدد \(n\).
فإذا أعطت ثلاثيتان مختلفتان من الأعداد الأولية المجموع نفسه، فإن هذا العدد يُحسب مرة واحدة فقط.
الأسس \(2\) و\(3\) و\(4\) تجعل فضاء البحث أصغر بكثير مما يبدو من الحد \(50{,}000{,}000\). وبمجرد كتابة هذه الحدود بدقة، تتحول المسألة إلى مسألة مجموعات منتهية: نبني ثلاث قوائم قصيرة من القوى الأولية، ثم نستعرض مجاميعها بترتيب تصاعدي، ثم نزيل التكرارات.
لحد عام \(N\)، نعرّف
$$\mathcal{S}_2(N)=\{p^2 : p \text{ prime},\ p^2 \lt N\},$$
$$\mathcal{S}_3(N)=\{p^3 : p \text{ prime},\ p^3 \lt N\},$$
$$\mathcal{S}_4(N)=\{p^4 : p \text{ prime},\ p^4 \lt N\}.$$
وعندئذ يكون المطلوب هو
$$A(N)=\left|\left\{a+b+c : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N),\ a+b+c \lt N\right\}\right|.$$
وتعطي الأسس مباشرة الحدود
$$p \lt \sqrt{N},\qquad q \lt N^{1/3},\qquad r \lt N^{1/4}.$$
وبما أن \(N^{1/4} \lt N^{1/3} \lt \sqrt{N}\) متى كان \(N>1\)، فإن منخلًا واحدًا حتى \(\sqrt{N}\) يكفي لتوليد كل عدد أولي يمكن أن يظهر في أي واحدة من القوائم الثلاث.
بعد تنفيذ المنخل، لا نعود نبحث في جميع الأعداد الأصغر من \(N\). بل نختار عنصرًا واحدًا من كل واحدة من ثلاث مجموعات منتهية. قائمة المربعات هي الأطول، وقائمة المكعبات أقصر بكثير، أما قائمة القوى الرابعة فهي صغيرة جدًا. وهذه الفجوة في الأحجام هي بالضبط ما يجعل التعداد المباشر عمليًا عند الحد الثابت للمسألة.
لا نحتاج هنا إلى علاقة عودية أو إلى دالة مولدة. الاختزال الرياضي الحقيقي هو رؤية المسألة بوصفها مجموع مجموعات لثلاث عائلات محدودة من القوى الأولية.
تُولَّد الأعداد الأولية بترتيب تصاعدي، والدوال \(x\mapsto x^2\) و\(x\mapsto x^3\) و\(x\mapsto x^4\) متزايدة تمامًا على الأعداد الصحيحة الموجبة. لذلك تكون القوائم \(\mathcal{S}_2(N)\) و\(\mathcal{S}_3(N)\) و\(\mathcal{S}_4(N)\) مرتبة مسبقًا تصاعديًا.
ومن هنا يظهر ثابت الحلقات المتداخلة. إذا ثبتنا \(a\in\mathcal{S}_2(N)\)، ثم وجدنا قيمة \(b\in\mathcal{S}_3(N)\) تحقق \(a+b \ge N\)، فإن كل مكعب لاحق \(b'\ge b\) سيفشل أيضًا. وبالمثل، إذا ثبتنا \(a\) و\(b\)، ثم ظهرت قيمة \(c\in\mathcal{S}_4(N)\) تحقق \(a+b+c \ge N\)، فإن كل قوة رابعة لاحقة \(c'\ge c\) تصبح غير صالحة بالضرورة.
ولهذا يمكن إيقاف كل حلقة فور أول تجاوز للحد. هذه القطعية الرتيبة هي الفكرة التنفيذية الأساسية التي تجعل الخوارزمية سريعة.
السؤال يطلب عدد الأعداد القابلة للتمثيل، لا عدد طرق التمثيل. لذلك فإن الكائن الرياضي الصحيح هو المجموعة
$$\mathcal{T}(N)=\{a+b+c \lt N : a\in\mathcal{S}_2(N),\ b\in\mathcal{S}_3(N),\ c\in\mathcal{S}_4(N)\},$$
والجواب هو \(|\mathcal{T}(N)|\).
إزالة التكرارات ليست مجرد حيلة برمجية، بل هي الترجمة الدقيقة لما يطلبه نص المسألة.
عندما يكون \(N=50\)، تكون القوى الأولية المسموح بها هي
$$\mathcal{S}_2(50)=\{4,9,25,49\},\qquad \mathcal{S}_3(50)=\{8,27\},\qquad \mathcal{S}_4(50)=\{16\}.$$
وبما أنه لا توجد تحت 50 إلا قوة أولية رابعة واحدة، فإن كل قيمة صالحة تأخذ الشكل \(a+b+16\). وبفحص الاحتمالات نحصل على
$$4+8+16=28,\qquad 9+8+16=33,\qquad 25+8+16=49,\qquad 4+27+16=47,$$
أما بقية الاختيارات فتعطي قيمًا لا تقل عن 50. لذلك
$$\mathcal{T}(50)=\{28,33,47,49\},\qquad |\mathcal{T}(50)|=4.$$
وهذا المثال الصغير يعرض الخطة كاملة: نبني القوائم الثلاث، ثم نجمعها بترتيب تصاعدي، ثم نعد فقط القيم المختلفة التي تبقى تحت الحد.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأعداد الأولية حتى \(\lfloor\sqrt{N}\rfloor+1\) باستخدام منخل إراتوستينس. ثم تُبنى من هذه القائمة الواحدة المرتبة ثلاث قوائم مرتبة أيضًا: مربعات أولية أصغر من \(N\)، ومكعبات أولية أصغر من \(N\)، وقوى رابعة أولية أصغر من \(N\).
وتستخدم النسخ المترجمة حسابًا من نوع 64-بت أثناء تكوين هذه القوى، حتى تبقى الضربات المتكررة آمنة، رغم أن كل القيم المحتفَظ بها تبقى دون الحد النهائي.
بعد هذه التهيئة، تنفذ الشيفرة تعدادًا ثلاثيًّا متداخلًا على قوائم المربعات والمكعبات والقوى الرابعة. وبما أن القوائم مرتبة، فإن الحلقة الحالية تتوقف فورًا حالما يصل مجموع جزئي إلى \(N\). وهكذا يتحول برهان الرتابة في القسم الرياضي إلى منطق تحكم مباشر داخل التنفيذ.
كل مجموع صالح \(a+b+c \lt N\) يُدرج في مجموعة مبنية على التجزئة. وإذا وُلد العدد نفسه مرة أخرى من ثلاثية أولية أخرى، فإن المجموعة تحتفظ بنسخة واحدة فقط. والنتيجة النهائية هي حجم هذه المجموعة.
لنضع \(B=\lfloor\sqrt{N}\rfloor\)، ولتكن \(s_2=|\mathcal{S}_2(N)|\) و\(s_3=|\mathcal{S}_3(N)|\) و\(s_4=|\mathcal{S}_4(N)|\). مرحلة المنخل تكلف \(O(B\log\log B)\) زمنًا و\(O(B)\) مساحة.
أما مرحلة التعداد فلها في أسوأ الأحوال زمن \(O(s_2s_3s_4)\)، مع كلفة وسطية \(O(1)\) لإدخال كل مجموع صالح في بنية إزالة التكرارات. وعمليًا يكون العمل أقل من هذا الحد الخام، لأن القوائم المرتبة تسمح بالإيقاف المبكر فور بلوغ الحد.
إجمالي المساحة هو \(O(B+s_2+s_3+s_4+|\mathcal{T}(N)|)\)، وتسيطر عليه جدول المنخل، والقوائم الثلاث، ومجموعة المجاميع المختلفة. وعند \(N=50{,}000{,}000\) يبقى هذا كله ضمن نطاق عملي تمامًا.