We seek the smallest positive integer \(n\) whose number of unordered representations as a sum of prime numbers exceeds 5000. Repetitions are allowed, so expressions such as \(2+2+3+3\) are valid, but order does not matter: \(3+2+3+2\) is the same representation.
If \(q(n)\) denotes this prime-partition count, the task is to find the first \(n\) with \(q(n) > 5000\). The implementations do not assume an a priori bound; they test \(n=2,3,4,\dots\) in order and stop at the first successful value.
The central object is not the list of partitions itself, but a counting function that remembers which primes are currently allowed. That viewpoint turns the problem into the same kind of combinatorial recurrence used in unrestricted coin-change counting, except the available parts are precisely the primes.
Let the primes up to \(n\) be \(p_1 < p_2 < \cdots < p_k\). Define \(Q_i(s)\) to be the number of unordered ways to write \(s\) as a sum of the first \(i\) primes \(p_1,\dots,p_i\). Then the quantity we really want is
$$q(n)=Q_k(n),$$
because primes larger than \(n\) cannot appear in a sum equal to \(n\).
This definition introduces the right invariant for dynamic programming: after we finish processing the first \(i\) primes, the count for each \(s\) must already equal \(Q_i(s)\).
Each prime \(p\) may be used \(0,1,2,\dots\) times, so its contribution to the generating function is
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$$
Multiplying over all usable primes gives
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
Equivalently, for the final target \(n\),
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
The coefficient extraction says exactly what we are counting: every time the product produces \(x^n\), we have chosen a multiset of primes summing to \(n\).
The generating function leads directly to a recurrence. For \(i \ge 1\) and \(s \ge 0\), split the representations counted by \(Q_i(s)\) into two disjoint classes:
One class uses no copy of \(p_i\), contributing \(Q_{i-1}(s)\).
The other class uses at least one \(p_i\). Removing one copy of \(p_i\) leaves an unordered representation of \(s-p_i\) that may still use \(p_i\), contributing \(Q_i(s-p_i)\).
Therefore
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
with boundary conditions
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0.$$
If \(s<p_i\), then \(Q_i(s)=Q_{i-1}(s)\), because the prime \(p_i\) is too large to appear.
The implementations compress the recurrence into one array indexed by the current sum. When processing a fixed prime \(p_i\), they sweep the sums upward from \(p_i\) to \(n\). At that moment, the entry for \(s-p_i\) already includes all representations that use the primes \(p_1,\dots,p_i\), so adding it into the entry for \(s\) realizes the term \(Q_i(s-p_i)\).
This ascending sweep is what prevents overcounting. A representation such as \(5+3+2\) is created only when the prime 5 is being processed from the already canonical representation of \(3+2\); it is not created again from a different order such as \(2+5+3\). In other words, the outer loop over primes imposes a nondecreasing order on the parts, so each unordered multiset is counted once.
For \(n=10\), the usable primes are \(2,3,5,7\). The unordered prime partitions are
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
so \(q(10)=5\).
This example also explains the smaller validation target used by two of the implementations. Since \(q(10)=5\) is not yet greater than 5, the next candidate must be checked. For \(n=11\) there are six unordered prime partitions, so the first value with more than 5 representations is 11.
The C++, Python, and Java implementations search upward one integer at a time. At each step they test whether the current candidate is prime; if it is, they append it to the stored list of available primes. The primality tests are simple trial-division routines up to \(\sqrt{n}\), with minor language-level differences in how candidate divisors are skipped.
For each candidate \(n\), the implementation allocates a table of length \(n+1\), initializes the count for sum 0 to 1, and leaves all other counts at 0. It then processes the known primes in increasing order, ignoring any prime larger than \(n\). For each prime \(p\), it updates every sum \(s=p,p+1,\dots,n\) by adding the current count for \(s-p\) into the count for \(s\).
After the loop for a given prime finishes, the table entry for each \(s\) equals the number of unordered representations of \(s\) using only the primes processed so far. That is exactly the invariant \(Q_i(s)\) described above.
Once the table entry for the current candidate \(n\) exceeds the requested threshold, the search terminates immediately and returns \(n\). The C++ and Python versions also include a small validation step: for threshold 5, the first qualifying value must be 11. The Java version hardcodes the Project Euler threshold directly.
Suppose \(N\) is the first integer with \(q(N)\) above the threshold. Because the implementations rebuild the dynamic-programming table from scratch for every candidate \(2,3,\dots,N\), the total counting work is
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
where \(\pi(n)\) is the prime-counting function. Using the rough estimate \(\pi(n)\sim n/\log n\), this behaves like \(O(N^3/\log N)\), and it is certainly bounded by \(O(N^3)\).
The primality tests contribute less than the repeated DP construction, and memory usage is only \(O(N)\) because each implementation keeps one count table for the current candidate plus the list of discovered primes. For this problem the first successful \(N\) is small, so the straightforward recomputation strategy is entirely adequate.
Gesucht ist die kleinste positive ganze Zahl \(n\), deren Anzahl ungeordneter Darstellungen als Summe von Primzahlen größer als 5000 ist. Wiederholungen sind erlaubt, also ist etwa \(2+2+3+3\) zulässig, aber die Reihenfolge spielt keine Rolle: \(3+2+3+2\) ist keine neue Darstellung.
Bezeichnen wir diese Anzahl mit \(q(n)\), dann soll das erste \(n\) mit \(q(n) > 5000\) gefunden werden. Die Implementierungen setzen keine feste obere Schranke voraus; sie prüfen \(n=2,3,4,\dots\) nacheinander und brechen beim ersten Treffer ab.
Der richtige Zugang ist nicht das explizite Auflisten aller Zerlegungen, sondern eine Zählfunktion, die festhält, welche Primzahlen bereits verwendet werden dürfen. Damit wird das Problem zu derselben Art von Rekurrenz wie beim ungeordneten Münzwechsel, nur dass die zulässigen Summanden genau die Primzahlen sind.
Seien \(p_1 < p_2 < \cdots < p_k\) die Primzahlen bis \(n\). Definiere \(Q_i(s)\) als die Anzahl ungeordneter Darstellungen von \(s\) als Summe der ersten \(i\) Primzahlen \(p_1,\dots,p_i\). Dann ist die gesuchte Größe
$$q(n)=Q_k(n),$$
denn Primzahlen größer als \(n\) können in einer Summe mit Wert \(n\) nicht vorkommen.
Damit ist auch die zentrale Invariante für das dynamische Programm festgelegt: Nach Verarbeitung der ersten \(i\) Primzahlen muss der gespeicherte Wert für jedes \(s\) bereits gleich \(Q_i(s)\) sein.
Jede Primzahl \(p\) darf \(0,1,2,\dots\) Mal verwendet werden, also trägt sie den Faktor
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}$$
zur erzeugenden Funktion bei. Über alle zulässigen Primzahlen multipliziert ergibt das
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
Für das Ziel \(n\) kann man äquivalent schreiben
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
Jeder Beitrag zum Koeffizienten von \(x^n\) entspricht genau einer Multimenge von Primzahlen mit Summe \(n\).
Aus dieser Sicht folgt unmittelbar eine Fallunterscheidung. Für \(i \ge 1\) und \(s \ge 0\) zerfallen die von \(Q_i(s)\) gezählten Darstellungen in zwei disjunkte Klassen:
Darstellungen ohne \(p_i\), also \(Q_{i-1}(s)\).
Darstellungen mit mindestens einem \(p_i\). Entfernt man ein Exemplar von \(p_i\), bleibt eine ungeordnete Darstellung von \(s-p_i\), in der \(p_i\) weiterhin vorkommen darf. Das liefert \(Q_i(s-p_i)\).
Damit gilt
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
mit Randbedingungen
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ für }s>0.$$
Ist \(s<p_i\), dann bleibt nur \(Q_i(s)=Q_{i-1}(s)\), weil \(p_i\) zu groß ist.
Die Implementierungen komprimieren diese Rekurrenz auf ein einziges Array über den aktuellen Summenwert. Für eine feste Primzahl \(p_i\) laufen sie die Summen aufsteigend von \(p_i\) bis \(n\) durch. Zu diesem Zeitpunkt enthält der Eintrag für \(s-p_i\) bereits alle Darstellungen mit den Primzahlen \(p_1,\dots,p_i\), sodass das Hinzufügen zu \(s\) genau den Term \(Q_i(s-p_i)\) realisiert.
Gerade diese aufsteigende Reihenfolge verhindert Mehrfachzählungen. Eine Darstellung wie \(5+3+2\) entsteht genau dann, wenn die 5 verarbeitet wird und an die bereits kanonische Darstellung \(3+2\) angehängt wird. Andere Reihenfolgen wie \(2+5+3\) erzeugen keinen neuen Fall. Die äußere Schleife über Primzahlen erzwingt also implizit eine nicht fallende Ordnung der Teile.
Für \(n=10\) sind die zulässigen Primzahlen \(2,3,5,7\). Die ungeordneten Primzerlegungen lauten
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
also ist \(q(10)=5\).
Das erklärt zugleich den kleineren Testfall aus zwei Implementierungen. Da \(q(10)=5\) noch nicht größer als 5 ist, muss weitergesucht werden. Für \(n=11\) gibt es sechs ungeordnete Primzerlegungen, also ist 11 die erste Zahl mit mehr als 5 Darstellungen.
Die C++-, Python- und Java-Implementierungen erhöhen den Kandidaten schrittweise um eins. Bei jedem Schritt wird geprüft, ob die aktuelle Zahl prim ist; falls ja, wird sie an die gespeicherte Primzahlliste angehängt. Die Primtests sind einfache Teilbarkeitsprüfungen bis \(\sqrt{n}\), mit kleinen sprachspezifischen Unterschieden bei den übersprungenen Teilern.
Für jedes aktuelle \(n\) wird eine Tabelle der Länge \(n+1\) angelegt. Der Wert für Summe 0 wird auf 1 gesetzt, alle übrigen Werte beginnen bei 0. Danach werden die bekannten Primzahlen in aufsteigender Reihenfolge verarbeitet; Primzahlen größer als \(n\) werden ignoriert. Für jede Primzahl \(p\) werden alle Summen \(s=p,p+1,\dots,n\) aktualisiert, indem der aktuelle Wert für \(s-p\) zum Wert für \(s\) addiert wird.
Nach Abschluss der Schleife für eine bestimmte Primzahl enthält jeder Eintrag genau die Anzahl ungeordneter Darstellungen mit den bisher verarbeiteten Primzahlen. Das ist exakt die oben eingeführte Invariante \(Q_i(s)\).
Sobald der Tabelleneintrag für den aktuellen Kandidaten \(n\) den gewünschten Schwellenwert übersteigt, endet die Suche sofort. Die C++- und Python-Versionen prüfen zusätzlich einen kleinen Kontrollfall: Beim Schwellwert 5 muss der erste Treffer 11 sein. Die Java-Version verwendet direkt den festen Project-Euler-Schwellenwert.
Sei \(N\) die erste Zahl mit \(q(N)\) oberhalb der Schranke. Weil die Implementierungen die dynamische Tabelle für jedes \(n=2,3,\dots,N\) vollständig neu aufbauen, ist der gesamte Zählaufwand
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
wobei \(\pi(n)\) die Anzahl der Primzahlen bis \(n\) bezeichnet. Mit der groben Abschätzung \(\pi(n)\sim n/\log n\) erhält man heuristisch \(O(N^3/\log N)\), und sicher gilt \(O(N^3)\).
Die Primtests fallen gegenüber dem wiederholten DP-Aufbau weniger ins Gewicht, und der Speicherbedarf bleibt bei \(O(N)\), weil nur eine Zähltabelle für den aktuellen Kandidaten plus die Liste der gefundenen Primzahlen gehalten wird. Für dieses Problem ist das erste erfolgreiche \(N\) klein genug, dass diese direkte Strategie vollkommen ausreicht.
Aranan şey, asal sayıların toplamı olarak 5000'den fazla farklı biçimde yazılabilen en küçük pozitif tam sayı \(n\)'dir. Tekrarlar serbesttir; örneğin \(2+2+3+3\) geçerlidir. Ancak sıra önemsizdir, dolayısıyla \(3+2+3+2\) yeni bir gösterim sayılmaz.
Bu sayıyı \(q(n)\) ile gösterirsek hedef, \(q(n) > 5000\) eşitsizliğini sağlayan ilk \(n\)'yi bulmaktır. Uygulamalar önceden sabit bir üst sınır kabul etmez; \(n=2,3,4,\dots\) adaylarını sırayla dener ve koşul ilk kez sağlandığında durur.
Ana fikir, bütün asal toplamları tek tek üretmek değil, hangi asalların kullanılmasına izin verildiğini hatırlayan bir sayma fonksiyonu kurmaktır. Böylece problem, klasik bozuk para değişimi sayımının asal sayılarla sınırlanmış bir sürümüne dönüşür.
\(n\)'e kadar olan asalları \(p_1 < p_2 < \cdots < p_k\) diye sıralayalım. \(Q_i(s)\), \(s\)'yi ilk \(i\) asalın, yani \(p_1,\dots,p_i\)'nin toplamı olarak sırasız biçimde yazma sayısı olsun. O zaman aradığımız büyüklük
$$q(n)=Q_k(n)$$
olur; çünkü \(n\)'den büyük bir asal, toplamı \(n\) olan bir gösterimde yer alamaz.
Bu tanım, dinamik programlama için gereken değişmezi de verir: ilk \(i\) asal işlendiğinde her \(s\) için saklanan değer tam olarak \(Q_i(s)\) olmalıdır.
Bir asal \(p\), toplamda \(0,1,2,\dots\) kez kullanılabilir. Bu nedenle üreteç fonksiyonuna katkısı
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}$$
şeklindedir. Kullanılabilir tüm asallar için çarpınca
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}$$
elde edilir. Sonuç olarak hedef \(n\) için
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}$$
yazabiliriz. Buradaki \(x^n\) katsayısı, toplamı \(n\) olan bir asal çoklu kümesinin tam karşılığıdır.
Bu bakıştan doğal bir ayrım çıkar. \(i \ge 1\) ve \(s \ge 0\) için, \(Q_i(s)\)'nin saydığı gösterimler iki ayrık sınıfa ayrılır:
Birinci sınıf, \(p_i\) hiç kullanmayan gösterimlerdir; bunların sayısı \(Q_{i-1}(s)\) olur.
İkinci sınıf, en az bir tane \(p_i\) kullanan gösterimlerdir. Bir tane \(p_i\) çıkarılırsa geriye \(s-p_i\)'nin yine sırasız bir asal toplamı kalır ve bu toplam \(p_i\)'yi kullanmaya devam edebilir. Bu katkı \(Q_i(s-p_i)\)'dir.
Dolayısıyla
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i)$$
ve sınır koşulları
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0$$
şeklindedir. Eğer \(s<p_i\) ise \(p_i\) kullanılamayacağından \(Q_i(s)=Q_{i-1}(s)\) kalır.
Uygulamalar bu özyinelemeyi toplam değerine göre indekslenmiş tek bir diziye sıkıştırır. Sabit bir \(p_i\) asalı işlenirken toplamlar \(p_i\)'den \(n\)'ye kadar artan sırada gezilir. Böylece \(s-p_i\) hücresi, \(p_1,\dots,p_i\) asallarıyla kurulabilen tüm gösterimleri zaten içerir; onun \(s\)'ye eklenmesi tam olarak \(Q_i(s-p_i)\) terimini üretir.
Bu artan tarama fazla sayımı engeller. Örneğin \(5+3+2\) çoklu kümesi yalnızca 5 işlenirken, zaten kanonik biçimde bulunan \(3+2\)'ye 5 eklenerek oluşur. \(2+5+3\) gibi başka sıralamalar ayrı bir yol açmaz. Yani dış döngü asal parçaları fiilen küçükten büyüğe kilitleyerek sırayı otomatik olarak etkisiz hale getirir.
\(n=10\) için kullanılabilir asallar \(2,3,5,7\)'dir. Sırasız asal bölünüşler
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2$$
olduğundan \(q(10)=5\) bulunur.
Bu örnek, iki uygulamadaki küçük doğrulama adımını da açıklar. Çünkü \(q(10)=5\) henüz 5'ten büyük değildir. Sonraki aday olan \(11\) için altı farklı asal bölünüş vardır; dolayısıyla 5 eşiğini ilk aşan değer 11 olur.
C++, Python ve Java uygulamaları aday değeri birer birer artırır. Her adımda mevcut sayının asal olup olmadığı kontrol edilir; asal ise kullanılabilir asal listesine eklenir. Asallık testi \(\sqrt{n}\)'ye kadar deneme bölmesiyle yapılır; diller arasında yalnızca hangi bölenlerin atlandığına dair küçük farklar vardır.
Her aday \(n\) için uzunluğu \(n+1\) olan bir tablo oluşturulur. Toplam 0 için sayaç 1 yapılır, diğer bütün sayaçlar 0 başlar. Ardından bilinen asallar artan sırayla işlenir; \(n\)'den büyük olanlar dikkate alınmaz. Her asal \(p\) için \(s=p,p+1,\dots,n\) toplamları dolaşılır ve \(s-p\)'nin mevcut sayısı \(s\)'nin sayısına eklenir.
Belirli bir asalın döngüsü bittiğinde, her hücre o ana kadar işlenmiş asallarla kurulabilen sırasız gösterim sayısını taşır. Bu tam olarak yukarıdaki \(Q_i(s)\) değişmezidir.
Tabloda güncel aday \(n\)'ye karşılık gelen sayı istenen eşiği geçtiği anda arama sonlanır. C++ ve Python sürümleri ayrıca küçük bir kontrol de yapar: eşik 5 ise ilk uygun değer 11 olmalıdır. Java sürümü doğrudan Project Euler eşiğini sabit kullanır.
\(N\), eşiği ilk aşan sayı olsun. Uygulamalar \(2,3,\dots,N\) için dinamik programlama tablosunu her defasında sıfırdan kurduğu için toplam sayım maliyeti
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right)$$
şeklindedir; burada \(\pi(n)\), \(n\)'e kadar olan asal sayısıdır. Kaba \(\pi(n)\sim n/\log n\) tahminiyle bu \(O(N^3/\log N)\) davranışı gösterir; güvenli bir üst sınır olarak \(O(N^3)\) da söylenebilir.
Asallık testlerinin maliyeti, tekrar tekrar kurulan DP tablosuna göre daha küçüktür. Bellek kullanımı ise yalnızca \(O(N)\)'dir; çünkü elde tutulan şey güncel adayın tek tablosu ile şimdiye kadar bulunan asallar listesidir. Bu problemde ilk başarılı \(N\) küçük olduğundan, bu doğrudan yaklaşım pratik olarak fazlasıyla yeterlidir.
Se busca el menor entero positivo \(n\) cuyo número de representaciones no ordenadas como suma de números primos supera 5000. Se permiten repeticiones, así que \(2+2+3+3\) es válido, pero el orden no importa: \(3+2+3+2\) no cuenta como una representación distinta.
Si llamamos \(q(n)\) a esa cantidad, el objetivo es hallar el primer \(n\) con \(q(n) > 5000\). Las implementaciones no suponen de antemano un límite superior fijo; prueban \(n=2,3,4,\dots\) en orden y se detienen en cuanto aparece el primer valor que supera el umbral.
La clave no es enumerar todas las particiones primas una por una, sino definir una función de conteo que recuerde qué primos están permitidos en cada etapa. Eso convierte el problema en la versión restringida a primos del recuento clásico de cambio de monedas sin importar el orden.
Sean \(p_1 < p_2 < \cdots < p_k\) los primos no mayores que \(n\). Definimos \(Q_i(s)\) como el número de maneras no ordenadas de escribir \(s\) como suma de los primeros \(i\) primos \(p_1,\dots,p_i\). Entonces la cantidad buscada es
$$q(n)=Q_k(n),$$
porque ningún primo mayor que \(n\) puede formar parte de una suma igual a \(n\).
Esta definición también da la invariante correcta para la programación dinámica: después de procesar los primeros \(i\) primos, el valor almacenado para cada \(s\) debe ser exactamente \(Q_i(s)\).
Cada primo \(p\) puede usarse \(0,1,2,\dots\) veces, así que su contribución es
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$$
Multiplicando sobre todos los primos disponibles obtenemos
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
De manera equivalente, para el objetivo final \(n\),
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
Extraer el coeficiente de \(x^n\) significa contar exactamente los multisets de primos cuya suma vale \(n\).
La función generadora lleva a una descomposición natural. Para \(i \ge 1\) y \(s \ge 0\), las representaciones contadas por \(Q_i(s)\) se separan en dos clases disjuntas:
Las que no usan el primo \(p_i\), que aportan \(Q_{i-1}(s)\).
Las que usan al menos una copia de \(p_i\). Si retiramos una copia de \(p_i\), queda una representación no ordenada de \(s-p_i\) que todavía puede usar \(p_i\), y eso aporta \(Q_i(s-p_i)\).
Por tanto,
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
con condiciones de borde
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ para }s>0.$$
Si \(s<p_i\), entonces simplemente \(Q_i(s)=Q_{i-1}(s)\), porque \(p_i\) no cabe en la suma.
Las implementaciones comprimen esta recurrencia en un solo arreglo indexado por la suma actual. Al procesar un primo fijo \(p_i\), recorren las sumas de \(p_i\) hasta \(n\) en orden creciente. En ese momento, la entrada correspondiente a \(s-p_i\) ya incluye todas las representaciones construidas con \(p_1,\dots,p_i\), así que añadirla a la entrada de \(s\) realiza exactamente el término \(Q_i(s-p_i)\).
Ese recorrido ascendente es lo que elimina el sobreconteo por orden. Una descomposición como \(5+3+2\) aparece una sola vez, cuando se procesa el 5 a partir de la representación ya canónica \(3+2\); no vuelve a aparecer como \(2+5+3\) ni como \(3+2+5\). El bucle exterior sobre los primos impone de hecho un orden no decreciente en las partes.
Para \(n=10\), los primos disponibles son \(2,3,5,7\). Las particiones primas no ordenadas son
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
de modo que \(q(10)=5\).
Esto también explica la comprobación pequeña incluida en dos implementaciones. Como \(q(10)=5\) todavía no supera 5, hay que examinar el siguiente candidato. Para \(n=11\) ya existen seis particiones primas no ordenadas, así que 11 es el primer valor con más de 5 representaciones.
Las implementaciones en C++, Python y Java avanzan un entero cada vez. En cada paso comprueban si el candidato actual es primo; si lo es, lo agregan a la lista almacenada de primos disponibles. Las pruebas de primalidad son divisiones de prueba hasta \(\sqrt{n}\), con pequeñas diferencias de bajo nivel según el lenguaje.
Para cada candidato \(n\), la implementación crea una tabla de longitud \(n+1\), fija en 1 el contador correspondiente a la suma 0 y deja el resto en 0. Después procesa los primos conocidos en orden creciente, ignorando los que sean mayores que \(n\). Para cada primo \(p\), actualiza todas las sumas \(s=p,p+1,\dots,n\) añadiendo el contador actual de \(s-p\) al contador de \(s\).
Una vez termina el bucle de un primo concreto, cada entrada contiene exactamente el número de representaciones no ordenadas que usan solo los primos ya procesados. Esa es precisamente la invariante \(Q_i(s)\).
En cuanto el contador correspondiente al candidato actual \(n\) supera el umbral pedido, la búsqueda termina y devuelve ese \(n\). Las versiones de C++ y Python además validan un caso menor: con umbral 5, el primer valor correcto debe ser 11. La versión de Java fija directamente el umbral del problema.
Sea \(N\) el primer entero con \(q(N)\) por encima del umbral. Como las implementaciones reconstruyen desde cero la tabla dinámica para cada candidato \(2,3,\dots,N\), el coste total del conteo es
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
donde \(\pi(n)\) es la función contadora de primos. Usando la estimación aproximada \(\pi(n)\sim n/\log n\), esto se comporta como \(O(N^3/\log N)\), y en cualquier caso queda acotado por \(O(N^3)\).
Las pruebas de primalidad cuestan menos que la reconstrucción repetida del DP, y la memoria es solo \(O(N)\), porque cada implementación conserva una única tabla para el candidato actual junto con la lista de primos ya descubiertos. En este problema el primer \(N\) exitoso es pequeño, por lo que esta estrategia directa es más que suficiente.
题目要求找出最小的正整数 \(n\)，使得它能被写成素数之和的无序表示超过 5000 种。允许重复使用同一个素数，例如 \(2+2+3+3\) 合法；但顺序不重要，所以 \(3+2+3+2\) 不能算作新的表示。
如果把这种计数记为 \(q(n)\)，目标就是找到第一个满足 \(q(n) > 5000\) 的 \(n\)。实现并没有预先假设固定上界，而是按 \(2,3,4,\dots\) 依次检查候选值，一旦第一次越过阈值就立即停止。
真正有用的对象不是“所有分解的列表”，而是一个会随着可用素数集合逐步扩张的计数函数。这样一来，问题就变成了“硬币种类是素数，且不区分顺序”的组合计数问题。
设不超过 \(n\) 的素数为 \(p_1 < p_2 < \cdots < p_k\)。定义 \(Q_i(s)\) 为：只允许使用前 \(i\) 个素数 \(p_1,\dots,p_i\) 时，把 \(s\) 写成素数和的无序方式数。那么题目真正要求的就是
$$q(n)=Q_k(n),$$
因为大于 \(n\) 的素数不可能出现在和为 \(n\) 的表示里。
这个定义同时给出了动态规划的核心不变量：当处理完前 \(i\) 个素数之后，表中每个和 \(s\) 的计数都应该恰好等于 \(Q_i(s)\)。
每个素数 \(p\) 可以使用 \(0,1,2,\dots\) 次，因此它对应的生成函数因子是
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$$
把所有可用素数的因子相乘，就得到
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
于是，对最终目标 \(n\) 而言，
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
这说明 \(x^n\) 的系数正好是在数“所有素数多重集合，其元素和等于 \(n\)”的个数。
由此可以直接写出递推。对 \(i \ge 1\) 和 \(s \ge 0\)，把 \(Q_i(s)\) 所计数的表示分成两类：
第一类完全不使用素数 \(p_i\)，贡献 \(Q_{i-1}(s)\)。
第二类至少使用一个 \(p_i\)。去掉其中一个 \(p_i\) 后，剩下的是 \(s-p_i\) 的一个无序素数表示，而且其中仍然允许继续使用 \(p_i\)，因此贡献 \(Q_i(s-p_i)\)。
所以有
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
边界条件为
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0.$$
如果 \(s<p_i\)，那么 \(p_i\) 根本放不进去，只能有 \(Q_i(s)=Q_{i-1}(s)\)。
实现把上述递推压缩成一个按当前和索引的一维数组。处理固定素数 \(p_i\) 时，和 \(s\) 按从 \(p_i\) 到 \(n\) 的升序更新。这样一来，在更新 \(s\) 时，位置 \(s-p_i\) 中已经包含了所有只使用 \(p_1,\dots,p_i\) 的合法表示，所以把它加到 \(s\) 上，正好实现递推中的 \(Q_i(s-p_i)\)。
升序更新也是“不区分顺序”的关键。像 \(5+3+2\) 这样的表示，只会在处理素数 5 时，由已经规范化的表示 \(3+2\) 扩展得到一次；它不会再因为 \(2+5+3\) 或 \(3+2+5\) 这样的排列而被重复计算。换句话说，外层按素数递增处理，等价于强制每个分解按非降顺序生成。
当 \(n=10\) 时，可用素数是 \(2,3,5,7\)。所有无序素数拆分为
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
因此 \(q(10)=5\)。
这个例子也解释了两个实现里出现的小校验。因为 \(q(10)=5\) 还没有严格大于 5，所以必须继续检查下一个候选值。对 \(n=11\) 而言，无序素数拆分共有 6 种，因此“表示数大于 5 的第一个整数”就是 11。
C++、Python 和 Java 实现都从小到大逐个尝试整数。每到一个新候选值，就先判断它是否为素数；如果是，就把它加入当前可用素数列表。素性判断本质上都是做到 \(\sqrt{n}\) 为止的试除法，只是在不同语言里略微改变了跳过哪些除数的方式。
对于每个候选 \(n\)，实现都会分配一个长度为 \(n+1\) 的计数表，把和为 0 的计数设为 1，其余位置设为 0。随后按从小到大的顺序处理已知素数，任何大于 \(n\) 的素数都直接忽略。对每个素数 \(p\)，依次更新 \(s=p,p+1,\dots,n\)，把位置 \(s-p\) 的当前计数加到位置 \(s\) 上。
当某个素数处理完毕后，表中每个位置都准确表示“只使用目前已经处理过的素数时，该和的无序表示数”。这正是前面定义的 \(Q_i(s)\) 不变量。
一旦当前候选值 \(n\) 的计数超过要求阈值，搜索立刻终止并返回该 \(n\)。C++ 和 Python 版本还额外检查了一个较小的验证点：当阈值是 5 时，第一个满足条件的值必须是 11。Java 版本则直接固定使用题目要求的阈值。
设 \(N\) 是第一个满足 \(q(N)\) 超过阈值的整数。由于实现会对每个候选值 \(2,3,\dots,N\) 都从头重建一次动态规划表，总计数工作量为
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
其中 \(\pi(n)\) 表示不超过 \(n\) 的素数个数。用粗略估计 \(\pi(n)\sim n/\log n\) 来看，这大致是 \(O(N^3/\log N)\)；保守地说，它当然也被 \(O(N^3)\) 所界定。
素性检测的代价比反复重建 DP 表要小，而空间复杂度只有 \(O(N)\)，因为实现只保留当前候选值的一张计数表和已经发现的素数列表。对本题而言，首次成功的 \(N\) 很小，所以这种直接重算的策略已经完全足够。
Нужно найти наименьшее положительное целое \(n\), для которого число неупорядоченных представлений в виде суммы простых чисел превышает 5000. Повторения разрешены, поэтому запись \(2+2+3+3\) допустима, но порядок не важен: \(3+2+3+2\) не считается новым вариантом.
Обозначим это количество через \(q(n)\). Тогда требуется найти первое \(n\), для которого \(q(n) > 5000\). Реализации не предполагают заранее фиксированной верхней границы: они проверяют \(n=2,3,4,\dots\) по порядку и останавливаются на первом подходящем значении.
Ключевой объект здесь не список всех разложений, а функция подсчета, которая помнит, какие простые числа уже разрешено использовать. Это переводит задачу в стандартную комбинаторную схему подсчета разменов без учета порядка, где роли номиналов играют простые числа.
Пусть простые числа, не превосходящие \(n\), равны \(p_1 < p_2 < \cdots < p_k\). Обозначим через \(Q_i(s)\) число неупорядоченных способов представить \(s\) как сумму первых \(i\) простых \(p_1,\dots,p_i\). Тогда искомая величина равна
$$q(n)=Q_k(n),$$
поскольку простое число больше \(n\) не может входить в сумму, равную \(n\).
Это определение сразу задает правильную инварианту динамики: после обработки первых \(i\) простых чисел сохраненное значение для каждого \(s\) должно совпадать с \(Q_i(s)\).
Каждое простое \(p\) можно использовать \(0,1,2,\dots\) раз, поэтому соответствующий множитель имеет вид
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$$
Перемножая такие множители по всем допустимым простым, получаем
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
Следовательно, для конечной цели \(n\)
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
Коэффициент при \(x^n\) ровно и считает мультимножества простых чисел с суммой \(n\).
Из этого представления сразу следует разбиение на случаи. Для \(i \ge 1\) и \(s \ge 0\) все представления, учитываемые в \(Q_i(s)\), делятся на два непересекающихся класса:
Те, которые не используют простое \(p_i\), и их число равно \(Q_{i-1}(s)\).
Те, которые используют хотя бы одну копию \(p_i\). Если убрать одну такую копию, останется неупорядоченное представление числа \(s-p_i\), в котором \(p_i\) все еще разрешено использовать. Это дает вклад \(Q_i(s-p_i)\).
Поэтому
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
при граничных условиях
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0.$$
Если \(s<p_i\), то \(p_i\) участвовать не может, и остается \(Q_i(s)=Q_{i-1}(s)\).
Реализации сжимают эту рекурсию в один массив по текущей сумме. При обработке фиксированного простого \(p_i\) суммы \(s\) проходят по возрастанию от \(p_i\) до \(n\). К этому моменту ячейка для \(s-p_i\) уже содержит все представления, построенные с помощью \(p_1,\dots,p_i\), поэтому ее добавление к ячейке \(s\) реализует слагаемое \(Q_i(s-p_i)\).
Именно возрастание суммы не дает считать одно и то же мультимножество несколько раз. Представление \(5+3+2\) появляется только один раз: когда обрабатывается 5 и добавляется к уже каноническому варианту \(3+2\). Порядки вроде \(2+5+3\) и \(3+2+5\) новых случаев не создают. Внешний цикл по простым фактически навязывает неубывающий порядок частей.
Для \(n=10\) допустимы простые \(2,3,5,7\). Все неупорядоченные разложения на простые таковы:
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
следовательно, \(q(10)=5\).
Этот пример одновременно объясняет маленькую проверку, встроенную в две реализации. Поскольку \(q(10)=5\) еще не больше 5, нужно рассмотреть следующий кандидат. Для \(n=11\) уже существует шесть неупорядоченных разложений на простые, поэтому именно 11 является первым числом с числом представлений больше 5.
Реализации на C++, Python и Java увеличивают кандидат по одному. На каждом шаге они проверяют, является ли текущее число простым; если да, оно добавляется в сохраненный список доступных простых. Проверка простоты основана на пробном делении до \(\sqrt{n}\), с небольшими языковыми отличиями в том, какие делители пропускаются.
Для каждого кандидата \(n\) создается таблица длины \(n+1\). Счетчик для суммы 0 устанавливается в 1, все остальные значения начинают с 0. Затем известные простые обрабатываются по возрастанию; простые числа больше \(n\) игнорируются. Для каждого простого \(p\) пересчитываются суммы \(s=p,p+1,\dots,n\): к текущему счетчику для \(s\) прибавляется счетчик для \(s-p\).
После завершения цикла по данному простому каждая ячейка уже содержит число неупорядоченных представлений соответствующей суммы с использованием только тех простых, которые уже обработаны. Это и есть инварианта \(Q_i(s)\).
Как только счетчик для текущего кандидата \(n\) становится больше заданного порога, поиск немедленно завершается. Версии на C++ и Python дополнительно проверяют малый контрольный случай: при пороге 5 первым подходящим числом должно быть 11. В версии на Java порог задачи зафиксирован напрямую.
Пусть \(N\) - первое число, для которого \(q(N)\) превышает порог. Поскольку реализации заново строят динамическую таблицу для каждого кандидата \(2,3,\dots,N\), общий объем работы равен
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
где \(\pi(n)\) обозначает число простых, не превосходящих \(n\). Если воспользоваться грубой оценкой \(\pi(n)\sim n/\log n\), получается поведение порядка \(O(N^3/\log N)\); без всяких тонкостей это, конечно, ограничено сверху величиной \(O(N^3)\).
Проверки простоты стоят меньше, чем многократная пересборка DP, а память равна всего \(O(N)\), потому что одновременно хранятся только одна таблица для текущего кандидата и список уже найденных простых чисел. Для этой задачи первое подходящее \(N\) мало, так что такой прямой подход полностью оправдан.
المطلوب هو إيجاد أصغر عدد صحيح موجب \(n\) يكون عدد تمثيلاته غير المرتبة كمجموع أعداد أولية أكبر من 5000. يُسمح بالتكرار، لذا فإن \(2+2+3+3\) تمثيل صالح، لكن ترتيب الحدود لا يصنع تمثيلًا جديدًا، أي إن \(3+2+3+2\) هو نفسه.
إذا رمزنا لهذا العدد بالرمز \(q(n)\)، فالمسألة تطلب أول \(n\) يحقق \(q(n) > 5000\). التنفيذات لا تفترض حدًا أعلى ثابتًا مسبقًا، بل تفحص القيم \(2,3,4,\dots\) بالتتابع وتتوقف عند أول قيمة تتجاوز العتبة.
الفكرة الأساسية ليست سرد جميع التحليلات إلى مجموعات أولية، بل بناء دالة عد تحفظ مجموعة الأعداد الأولية المسموح باستخدامها في كل مرحلة. بهذا تتحول المسألة إلى نسخة مقيدة بالأعداد الأولية من مسألة عد تبديل العملات من دون اعتبار للترتيب.
لتكن الأعداد الأولية التي لا تتجاوز \(n\) هي \(p_1 < p_2 < \cdots < p_k\). نعرّف \(Q_i(s)\) بأنه عدد الطرق غير المرتبة لكتابة \(s\) كمجموع من أول \(i\) أعداد أولية \(p_1,\dots,p_i\). عندئذ تكون الكمية المطلوبة هي
$$q(n)=Q_k(n),$$
لأن أي عدد أولي أكبر من \(n\) لا يمكن أن يظهر داخل مجموع يساوي \(n\).
هذا التعريف يحدد أيضًا الثابت الذي تعتمد عليه البرمجة الديناميكية: بعد معالجة أول \(i\) أعداد أولية، يجب أن تكون القيمة المخزنة لكل \(s\) مساوية تمامًا لـ \(Q_i(s)\).
كل عدد أولي \(p\) يمكن استخدامه \(0,1,2,\dots\) مرة، ولذلك فإن مساهمته في دالة التوليد هي
$$1+x^p+x^{2p}+x^{3p}+\cdots=\frac{1}{1-x^p}.$$
وبضرب هذه العوامل لجميع الأعداد الأولية المتاحة نحصل على
$$\sum_{s=0}^{\infty} Q_k(s)x^s=\prod_{i=1}^{k}\frac{1}{1-x^{p_i}}.$$
وبالتالي يمكن كتابة العدد المطلوب على الصورة
$$q(n)=\left[x^n\right]\prod_{p \le n,\; p\text{ prime}}\frac{1}{1-x^p}.$$
ومعامل \(x^n\) هنا يعد بدقة كل متعدد مجموعة من الأعداد الأولية التي مجموعها يساوي \(n\).
من هذا المنظور تظهر قسمة طبيعية إلى حالتين. لكل \(i \ge 1\) و\(s \ge 0\)، يمكن تقسيم التمثيلات التي يعدها \(Q_i(s)\) إلى فئتين منفصلتين:
الفئة الأولى لا تستخدم العدد الأولي \(p_i\) إطلاقًا، ومساهمتها هي \(Q_{i-1}(s)\).
الفئة الثانية تستخدم نسخة واحدة على الأقل من \(p_i\). إذا حذفنا نسخة واحدة من \(p_i\)، بقي تمثيل غير مرتب للعدد \(s-p_i\) لا يزال مسموحًا له باستخدام \(p_i\)، ومساهمته هي \(Q_i(s-p_i)\).
إذن
$$Q_i(s)=Q_{i-1}(s)+Q_i(s-p_i)\qquad (s \ge p_i),$$
مع الشروط الحدية
$$Q_i(0)=1,\qquad Q_0(s)=0\text{ for }s>0.$$
أما إذا كان \(s<p_i\)، فلا يمكن استعمال \(p_i\) أصلًا، ومن ثم يكون \(Q_i(s)=Q_{i-1}(s)\).
التنفيذات تضغط هذه العلاقة العودية في مصفوفة واحدة مفهرسة بقيمة المجموع الحالي. عند معالجة عدد أولي ثابت \(p_i\)، تُحدَّث المجاميع \(s\) تصاعديًا من \(p_i\) حتى \(n\). في تلك اللحظة تكون الخانة الخاصة بـ \(s-p_i\) قد ضمّت بالفعل جميع التمثيلات المبنية من \(p_1,\dots,p_i\)، ولذلك فإن إضافتها إلى الخانة الخاصة بـ \(s\) يحقق الحد \(Q_i(s-p_i)\) تمامًا.
هذا المسح التصاعدي هو ما يمنع التكرار بسبب اختلاف الترتيب. فالتمثيل \(5+3+2\) يتكون مرة واحدة فقط عندما يُعالَج العدد 5 انطلاقًا من التمثيل المعياري \(3+2\). أما ترتيبات مثل \(2+5+3\) أو \(3+2+5\) فلا تولد حالات جديدة. بعبارة أخرى، الحلقة الخارجية على الأعداد الأولية تفرض ضمنيًا ترتيبًا غير تنازلي على الحدود.
عندما يكون \(n=10\)، فإن الأعداد الأولية المتاحة هي \(2,3,5,7\). وجميع التقسيمات الأولية غير المرتبة هي
$$10=7+3=5+5=5+3+2=3+3+2+2=2+2+2+2+2,$$
ومن ثم \(q(10)=5\).
وهذا المثال يفسر أيضًا خطوة التحقق الصغيرة الموجودة في اثنين من التنفيذات. بما أن \(q(10)=5\) ليس أكبر من 5 بعد، فلا بد من فحص القيمة التالية. وعند \(n=11\) توجد ستة تمثيلات أولية غير مرتبة، ولهذا تكون 11 هي أول قيمة يتجاوز فيها العد العتبة 5.
تنفيذات C++ وPython وJava ترفع قيمة المرشح واحدًا واحدًا. في كل خطوة تختبر هل العدد الحالي أولي، وإذا كان كذلك يُضاف إلى قائمة الأعداد الأولية المكتشفة. اختبارات الأولية كلها من نوع القسمة التجريبية حتى \(\sqrt{n}\)، مع فروق بسيطة بين اللغات في كيفية تجاوز بعض القواسم.
لكل مرشح \(n\)، يُنشأ جدول طوله \(n+1\). يُضبط عداد المجموع 0 على 1 وتبدأ بقية الخانات من الصفر. بعد ذلك تُعالَج الأعداد الأولية المعروفة بترتيب تصاعدي، ويُتجاهل كل عدد أولي أكبر من \(n\). ولكل عدد أولي \(p\)، تُحدَّث المجاميع \(s=p,p+1,\dots,n\) بإضافة العداد الحالي للمقدار \(s-p\) إلى العداد الخاص بالمقدار \(s\).
بعد اكتمال الحلقة الخاصة بعدد أولي معين، تصبح كل خانة مساوية لعدد التمثيلات غير المرتبة التي تستخدم فقط الأعداد الأولية التي عولجت حتى تلك اللحظة. وهذا هو الثابت \(Q_i(s)\) المذكور في الاشتقاق الرياضي.
بمجرد أن يتجاوز العداد المرتبط بالمرشح الحالي \(n\) العتبة المطلوبة، تتوقف عملية البحث فورًا وتُعاد تلك القيمة. نسختا C++ وPython تضيفان أيضًا تحققًا صغيرًا: عندما تكون العتبة 5 يجب أن تكون أول قيمة صحيحة هي 11. أما نسخة Java فتثبت عتبة المسألة مباشرة.
إذا كانت \(N\) هي أول قيمة تحقق \(q(N)\) أعلى من العتبة، فإن كلفة العد الكلية تساوي
$$\sum_{n=2}^{N}\sum_{p \le n,\; p\text{ prime}} (n-p+1)=O\!\left(\sum_{n=2}^{N} n\,\pi(n)\right),$$
حيث \(\pi(n)\) هي دالة عد الأعداد الأولية. وباستخدام التقدير التقريبي \(\pi(n)\sim n/\log n\)، يكون السلوك من رتبة \(O(N^3/\log N)\)، ومن المؤكد أيضًا أنه لا يتجاوز \(O(N^3)\).
اختبارات الأولية أقل كلفة من إعادة بناء جدول البرمجة الديناميكية مرارًا، أما الذاكرة فهي \(O(N)\) فقط لأن التنفيذ يحتفظ بجدول واحد للمرشح الحالي إضافة إلى قائمة الأعداد الأولية المكتشفة. وفي هذه المسألة تكون أول قيمة ناجحة صغيرة بما يكفي لجعل هذا الأسلوب المباشر عمليًا تمامًا.