For a positive integer \(n\), let \(p(n)\) denote the number of ways to write \(n\) as a sum of positive integers when order does not matter. For example, \(p(4)=5\) because the partitions are \(4\), \(3+1\), \(2+2\), \(2+1+1\), and \(1+1+1+1\).
Problem 78 asks for the least \(n\) such that \(p(n)\) is divisible by one million:
$$p(n)\equiv 0 \pmod{10^6}.$$
The partition function grows very quickly, so the useful task is not to compute exact giant integers, but to generate the residues \(p(0),p(1),p(2),\dots\) modulo \(10^6\) until the first zero residue appears.
The implementations are built around Euler's pentagonal recurrence for the partition function. That recurrence is not a generic dynamic-programming trick; it comes from the generating function of integer partitions and the pentagonal number theorem.
If we choose how many \(1\)'s, how many \(2\)'s, how many \(3\)'s, and so on appear in a partition, then the generating function for \(p(n)\) is
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
Each factor \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) records how many copies of the part \(m\) are used. The coefficient of \(x^n\) in the full product is therefore exactly the number of partitions of \(n\).
Euler proved the identity
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
Since this product is the reciprocal of \(P(x)\), we have
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
Now compare coefficients of \(x^n\). With the conventions \(p(0)=1\) and \(p(m)=0\) for \(m<0\), the coefficient identity becomes
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
For any fixed \(n\), only finitely many terms contribute, because once the offset exceeds \(n\), every later term is automatically zero.
The two offsets that appear for each \(k\ge 1\) are
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
These generate the sequence
$$1,2,5,7,12,15,22,26,35,40,\dots$$
called the generalized pentagonal numbers. The sign attached to the pair \((g_k^-,g_k^+)\) depends only on the parity of \(k\): when \(k\) is odd, both terms are added; when \(k\) is even, both terms are subtracted. So the recurrence follows the pattern
$$+,+,-,-,+,+,-,-,\dots$$
across successive generalized pentagonal offsets.
For \(n=7\), the generalized pentagonal numbers not exceeding 7 are \(1,2,5,7\). Therefore
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
Using the earlier values \(p(6)=11\), \(p(5)=7\), \(p(2)=2\), and \(p(0)=1\), we get
$$p(7)=11+7-2-1=15.$$
This matches the direct count of the 15 partitions of 7. The example shows why the recurrence is practical: instead of recomputing partitions from scratch, each new value is assembled from already known smaller ones.
The recurrence is linear, so reducing every stored value modulo \(10^6\) preserves correctness:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
This is the crucial invariant used by the implementation. At step \(n\), the table already contains correct residues for all smaller indices, and those residues are sufficient to compute the next residue. No exact huge partition number ever needs to be stored.
The C++, Python, and Java implementations begin with the base case \(p(0)=1\). They then build the sequence incrementally: compute the residue for \(p(1)\), append it, compute the residue for \(p(2)\), append it, and continue until a zero residue is found.
For a fixed \(n\), the implementation loops over \(k=1,2,3,\dots\), forms the two offsets \(k(3k-1)/2\) and \(k(3k+1)/2\), and stops as soon as the smaller offset already exceeds \(n\). The contribution of each pair is added or subtracted according to whether \(k\) is odd or even. If the second offset is still within range, it contributes too; otherwise only the first one is used.
The partial sum can become negative, so the implementation reduces the result modulo the target modulus and then normalizes it into the standard range \(0\) through \(10^6-1\). The C++ and Java versions use a wider accumulator type for this temporary sum before taking the modulus.
After each new residue is computed, the implementation checks whether it is zero. The first \(n\) for which that happens is the required answer. One implementation also includes a small checkpoint with modulus \(5\): since \(p(4)=5\), the least \(n\) satisfying \(p(n)\equiv 0\pmod 5\) is \(4\). That verifies that the recurrence and stopping rule are wired correctly before running the full search with modulus \(10^6\).
Let \(N\) be the least index with \(p(N)\equiv 0\pmod{10^6}\). For a given \(n\), the number of usable generalized pentagonal numbers is \(O(\sqrt{n})\), because the offsets grow quadratically in \(k\). Summing that cost over \(n=1\) through \(N\) gives total time
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
The table stores one residue for each value from \(0\) through \(N\), so the space usage is \(O(N)\). This is why Euler's recurrence is so effective here: it turns an apparently difficult partition-counting search into a single sequential computation with modest memory.
Für eine positive ganze Zahl \(n\) bezeichne \(p(n)\) die Anzahl der Zerlegungen von \(n\) in positive Summanden, wobei die Reihenfolge nicht zählt. Zum Beispiel gilt \(p(4)=5\), denn die Partitionen sind \(4\), \(3+1\), \(2+2\), \(2+1+1\) und \(1+1+1+1\).
Gesucht ist das kleinste \(n\), für das \(p(n)\) durch eine Million teilbar ist:
$$p(n)\equiv 0 \pmod{10^6}.$$
Die Partitionsfunktion wächst extrem schnell. Deshalb ist die richtige Sichtweise nicht, riesige exakte Werte zu berechnen, sondern die Reste \(p(0),p(1),p(2),\dots\) modulo \(10^6\) sukzessive zu erzeugen, bis erstmals der Rest 0 auftaucht.
Die drei Implementierungen beruhen vollständig auf Eulers pentagonaler Rekursion für die Partitionsfunktion. Diese Rekursion fällt nicht aus einem allgemeinen Schema heraus, sondern entsteht direkt aus der erzeugenden Funktion der Partitionen und aus dem Pentagonalzahlensatz.
Wählt man unabhängig, wie viele \(1\)er, \(2\)er, \(3\)er und so weiter in einer Partition vorkommen, dann erhält man
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
Jeder Faktor \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) beschreibt, wie oft der Summand \(m\) benutzt wird. Der Koeffizient von \(x^n\) im Gesamtprodukt zählt daher genau die Partitionen von \(n\).
Euler bewies die Identität
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
Da dieses Produkt der Kehrwert von \(P(x)\) ist, folgt
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
Vergleicht man nun die Koeffizienten von \(x^n\), erhält man mit den Konventionen \(p(0)=1\) und \(p(m)=0\) für \(m<0\)
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
Für festes \(n\) tragen nur endlich viele Terme bei, denn sobald ein Versatz größer als \(n\) ist, verschwinden alle späteren Beiträge automatisch.
Für jedes \(k\ge 1\) erscheinen die beiden Verschiebungen
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
Sie erzeugen die Folge
$$1,2,5,7,12,15,22,26,35,40,\dots$$
der verallgemeinerten Pentagonalzahlen. Das Vorzeichen hängt nur von der Parität von \(k\) ab: Für ungerades \(k\) werden beide Terme addiert, für gerades \(k\) werden beide subtrahiert. Entlang der Folge ergibt sich also das Muster
$$+,+,-,-,+,+,-,-,\dots$$
und genau dieses Muster taucht in den Implementierungen wieder auf.
Für \(n=7\) sind die verallgemeinerten Pentagonalzahlen höchstens 7 gleich \(1,2,5,7\). Daher gilt
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
Mit \(p(6)=11\), \(p(5)=7\), \(p(2)=2\) und \(p(0)=1\) folgt
$$p(7)=11+7-2-1=15.$$
Das stimmt mit der direkten Anzahl der 15 Partitionen von 7 überein. Das Beispiel zeigt die eigentliche Stärke der Rekursion: Jeder neue Wert wird allein aus bereits bekannten kleineren Werten zusammengesetzt.
Die Rekursion ist linear. Deshalb bleibt sie korrekt, wenn man alle gespeicherten Werte sofort modulo \(10^6\) reduziert:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
Das ist das zentrale Invariant der Implementierung. Beim Schritt \(n\) enthält die Tabelle bereits die richtigen Reste für alle kleineren Indizes, und genau diese Reste reichen aus, um den nächsten Rest zu berechnen. Exakte riesige Partitionszahlen müssen nie gespeichert werden.
Die C++-, Python- und Java-Implementierungen starten mit dem Basisfall \(p(0)=1\). Danach erzeugen sie die Folge inkrementell: erst den Rest von \(p(1)\), dann den von \(p(2)\), dann den von \(p(3)\) und so weiter, bis erstmals ein Nullrest auftritt.
Für ein festes \(n\) läuft die Implementierung über \(k=1,2,3,\dots\), berechnet die beiden Versätze \(k(3k-1)/2\) und \(k(3k+1)/2\) und bricht ab, sobald schon der kleinere Versatz größer als \(n\) ist. Ob ein Paar addiert oder subtrahiert wird, bestimmt allein die Parität von \(k\). Liegt auch der zweite Versatz noch innerhalb des Bereichs, wird sein Beitrag ebenfalls eingerechnet.
Die Zwischensumme kann negativ werden. Daher wird nach der Summation modulo der Zielzahl reduziert und anschließend in den Standardbereich \(0\) bis \(10^6-1\) zurückgeführt. Die C++- und Java-Versionen benutzen für diese Zwischensumme einen breiteren Zahltyp.
Nach jedem neuen Rest prüft die Implementierung, ob er gleich 0 ist. Das erste \(n\), bei dem das geschieht, ist die gesuchte Antwort. Eine der Implementierungen enthält zusätzlich einen kleinen Test mit Modulus \(5\): Da \(p(4)=5\) ist, muss das kleinste \(n\) mit \(p(n)\equiv 0\pmod 5\) gleich \(4\) sein. So wird die Rekursion vor der eigentlichen Suche modulo \(10^6\) abgesichert.
Sei \(N\) der kleinste Index mit \(p(N)\equiv 0\pmod{10^6}\). Für ein gegebenes \(n\) gibt es nur \(O(\sqrt{n})\) relevante verallgemeinerte Pentagonalzahlen, weil die Versätze quadratisch in \(k\) wachsen. Über alle \(n=1\) bis \(N\) summiert ergibt das
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
Gespeichert wird genau eine Restklasse pro Wert von \(0\) bis \(N\), also beträgt der Speicherbedarf \(O(N)\). Deshalb ist Eulers Rekursion hier so wirkungsvoll: Aus einer scheinbar schweren Partitionssuche wird eine lineare Vorwärtsberechnung mit moderatem Speicherbedarf.
Pozitif bir \(n\) tam sayısı için \(p(n)\), \(n\) sayısının pozitif tam sayıların toplamı olarak kaç farklı biçimde yazılabildiğini göstersin; burada sıranın önemi yoktur. Örneğin \(p(4)=5\) olur, çünkü 4 sayısının bölünüşleri \(4\), \(3+1\), \(2+2\), \(2+1+1\) ve \(1+1+1+1\) biçimleridir.
Problem 78, \(p(n)\) bir milyona tam bölünen en küçük \(n\) değerini sorar:
$$p(n)\equiv 0 \pmod{10^6}.$$
Bölünüş sayıları çok hızlı büyüdüğü için burada yapılması gereken şey devasa tam sayıları tam olarak üretmek değil, \(p(0),p(1),p(2),\dots\) kalıntılarını \(10^6\) modunda ardışık olarak hesaplayıp ilk sıfır kalıntısını bulmaktır.
C++, Python ve Java çözümleri bütünüyle Euler'in beşgensel tekrar bağıntısına dayanır. Bu bağıntı rastgele bir şablon değil, tamsayı bölünüşlerinin üreteç fonksiyonundan ve beşgensel sayı teoreminden gelir.
Bir bölünüşte kaç tane \(1\), kaç tane \(2\), kaç tane \(3\) kullanılacağını bağımsız olarak düşünürsek
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}$$
elde edilir. Her \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) çarpanı, parçanın \(m\) değerini kaç kez kullandığımızı kodlar. Böylece tüm çarpımdaki \(x^n\) katsayısı tam olarak \(n\)'nin bölünüş sayısını verir.
Euler şu özdeşliği ispatladı:
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
Bu çarpım \(P(x)\)'in tersi olduğuna göre
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1$$
yazılır. Şimdi \(x^n\) katsayılarını karşılaştırırsak ve \(p(0)=1\), \(p(m)=0\) (\(m<0\) için) kabullerini yaparsak
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right)$$
bağıntısı elde edilir. Sabit bir \(n\) için yalnızca sonlu sayıda terim katkı verir; çünkü kaydırma miktarı \(n\)'yi aştığı anda sonraki tüm terimler otomatik olarak sıfır olur.
Her \(k\ge 1\) için iki kaydırma değeri vardır:
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
Bunlar
$$1,2,5,7,12,15,22,26,35,40,\dots$$
dizisini, yani genelleştirilmiş beşgensel sayıları üretir. İşaret yalnızca \(k\)'nin tek ya da çift olmasına bağlıdır: \(k\) tekse iki terim de eklenir, \(k\) çiftse iki terim de çıkarılır. Bu yüzden dizi boyunca işaret düzeni
$$+,+,-,-,+,+,-,-,\dots$$
şeklindedir. Kodun iç döngüsündeki temel mantık tam olarak budur.
\(n=7\) için 7'yi aşmayan genelleştirilmiş beşgensel sayılar \(1,2,5,7\) olur. Dolayısıyla
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
Önceden bilinen \(p(6)=11\), \(p(5)=7\), \(p(2)=2\) ve \(p(0)=1\) değerlerini kullanırsak
$$p(7)=11+7-2-1=15$$
elde edilir. Bu sonuç, 7'nin doğrudan sayılan 15 bölünüşüyle birebir uyuşur. Örnek, her yeni değerin yalnızca daha küçük ve önceden hesaplanmış değerlere dayanarak bulunduğunu açıkça gösterir.
Tekrar bağıntısı doğrusaldır. Bu nedenle bütün kayıtlı değerleri her adımda \(10^6\) moduna indirgemek sonucu bozmaz:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
Uygulamanın kullandığı temel değişmez budur. \(n\) adımına gelindiğinde tablo, daha küçük tüm indisler için doğru kalıntıları zaten içerir ve bir sonraki kalıntıyı üretmek için bunlar yeterlidir. Hiçbir aşamada tam ve devasa bir \(p(n)\) değeri saklanmaz.
C++, Python ve Java uygulamaları \(p(0)=1\) temel durumuyla başlar. Ardından diziyi sırayla büyütürler: önce \(p(1)\)'in kalıntısı, sonra \(p(2)\)'nin kalıntısı, sonra \(p(3)\)'ünki hesaplanır ve ilk sıfır kalıntısı görülene kadar bu süreç devam eder.
Sabit bir \(n\) için uygulama \(k=1,2,3,\dots\) üzerinden gider, \(k(3k-1)/2\) ve \(k(3k+1)/2\) kaydırmalarını hesaplar ve küçük olan kaydırma bile \(n\)'yi geçtiği anda döngüyü durdurur. Çiftin ekleneceği ya da çıkarılacağı yalnızca \(k\)'nin parity'sine göre belirlenir. İkinci kaydırma da aralık içindeyse onun katkısı da hesaba katılır.
Ara toplam negatif olabileceği için sonuç önce hedef modüle göre indirgenir, sonra \(0\) ile \(10^6-1\) aralığına normalize edilir. C++ ve Java sürümleri bu ara toplam için daha geniş bir sayı tipi kullanır.
Her yeni kalıntı üretildikten sonra sıfır olup olmadığı kontrol edilir. Sıfırın ilk görüldüğü \(n\) aranan cevaptır. Çözümlerden biri ayrıca modül \(5\) için küçük bir kontrol içerir: \(p(4)=5\) olduğundan \(p(n)\equiv 0\pmod 5\) koşulunu sağlayan en küçük \(n\) değeri \(4\) olmalıdır. Bu, asıl \(10^6\) aramasından önce bağıntının ve durma mantığının doğru kurulduğunu gösterir.
\(N\), \(p(N)\equiv 0\pmod{10^6}\) koşulunu sağlayan en küçük indis olsun. Sabit bir \(n\) için kullanılabilen genelleştirilmiş beşgensel sayı sayısı \(O(\sqrt{n})\)'dir; çünkü kaydırmalar \(k\)'ye göre ikinci dereceden büyür. Bu maliyeti \(1\)'den \(N\)'ye kadar topladığımızda
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2})$$
elde edilir. Tablo yalnızca \(0\) ile \(N\) arasındaki her değer için bir kalıntı tuttuğu için bellek maliyeti \(O(N)\)'dir. Euler bağıntısının gücü burada ortaya çıkar: zor görünen bir bölünüş problemi, makul bellekte çalışan tek yönlü bir hesaplamaya dönüşür.
Para un entero positivo \(n\), sea \(p(n)\) el numero de particiones de \(n\), es decir, el numero de formas de escribir \(n\) como suma de enteros positivos sin distinguir el orden. Por ejemplo, \(p(4)=5\) porque las particiones son \(4\), \(3+1\), \(2+2\), \(2+1+1\) y \(1+1+1+1\).
El problema pide el menor \(n\) tal que \(p(n)\) sea divisible por un millon:
$$p(n)\equiv 0 \pmod{10^6}.$$
Como la funcion de particiones crece con enorme rapidez, no conviene calcular enteros exactos gigantes. Lo util es generar sucesivamente los residuos \(p(0),p(1),p(2),\dots\) modulo \(10^6\) hasta encontrar el primero que vale cero.
Las implementaciones se apoyan en la recurrencia pentagonal de Euler para la funcion de particiones. No es una plantilla reutilizable sin contexto: nace de la funcion generadora correcta para las particiones enteras y del teorema del numero pentagonal.
Si decidimos independientemente cuantas veces aparece cada parte \(1,2,3,\dots\), obtenemos
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
Cada factor \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) representa usar la parte \(m\) cero veces, una vez, dos veces y asi sucesivamente. Por eso, el coeficiente de \(x^n\) en el producto total cuenta exactamente las particiones de \(n\).
Euler demostro la identidad
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
Como este producto es el reciproco de \(P(x)\), se obtiene
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
Al comparar coeficientes de \(x^n\), con las convenciones \(p(0)=1\) y \(p(m)=0\) para \(m<0\), resulta
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
Para cada \(n\) fijo solo aparecen finitivamente muchos terminos, porque cuando un desplazamiento supera a \(n\), todos los siguientes ya quedan fuera de rango.
Para cada \(k\ge 1\) aparecen dos desplazamientos:
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
Ellos producen la sucesion
$$1,2,5,7,12,15,22,26,35,40,\dots$$
de numeros pentagonales generalizados. El signo depende solo de la paridad de \(k\): si \(k\) es impar, ambos terminos se suman; si \(k\) es par, ambos se restan. A lo largo de la sucesion aparece el patron
$$+,+,-,-,+,+,-,-,\dots$$
que es exactamente el que usan los programas.
Para \(n=7\), los numeros pentagonales generalizados no mayores que 7 son \(1,2,5,7\). Por tanto,
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
Usando \(p(6)=11\), \(p(5)=7\), \(p(2)=2\) y \(p(0)=1\), obtenemos
$$p(7)=11+7-2-1=15.$$
Eso coincide con el recuento directo de las 15 particiones de 7. El ejemplo deja claro por que la recurrencia es util: cada valor nuevo se construye solo a partir de valores anteriores ya conocidos.
La recurrencia es lineal, asi que reducir todos los valores almacenados modulo \(10^6\) no altera el resultado buscado:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
Ese es el invariante central de la implementacion. Cuando se calcula el paso \(n\), la tabla ya contiene residuos correctos para todos los indices menores, y esos residuos bastan para producir el siguiente. Nunca hace falta guardar el valor exacto gigantesco de \(p(n)\).
Las implementaciones en C++, Python y Java empiezan con el caso base \(p(0)=1\). Despues construyen la sucesion paso a paso: calculan el residuo de \(p(1)\), lo guardan; luego hacen lo mismo con \(p(2)\), \(p(3)\) y asi sucesivamente hasta encontrar el primer residuo nulo.
Para un \(n\) fijo, la implementacion recorre \(k=1,2,3,\dots\), forma los dos desplazamientos \(k(3k-1)/2\) y \(k(3k+1)/2\), y se detiene cuando incluso el menor de ellos ya es mayor que \(n\). La contribucion del par se suma o se resta segun si \(k\) es impar o par. Si el segundo desplazamiento todavia entra en rango, tambien se incorpora.
La suma parcial puede hacerse negativa, de modo que al final se toma modulo el valor objetivo y luego se normaliza al intervalo \(0\) a \(10^6-1\). Las versiones de C++ y Java usan un acumulador numerico mas amplio antes de reducir modulo.
Despues de calcular cada residuo nuevo, la implementacion comprueba si vale cero. El primer \(n\) con esa propiedad es la respuesta. Una de las implementaciones tambien incluye una verificacion pequena con modulo \(5\): como \(p(4)=5\), el menor \(n\) que satisface \(p(n)\equiv 0\pmod 5\) debe ser \(4\). Esa prueba confirma que la recurrencia y la condicion de parada estan bien conectadas antes de lanzar la busqueda con modulo \(10^6\).
Sea \(N\) el menor indice con \(p(N)\equiv 0\pmod{10^6}\). Para un \(n\) dado, el numero de desplazamientos utilizables es \(O(\sqrt{n})\), porque los numeros pentagonales generalizados crecen cuadraticamente con \(k\). Al sumar ese coste desde \(1\) hasta \(N\), se obtiene
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
La memoria es \(O(N)\), ya que se almacena un residuo por cada indice entre \(0\) y \(N\). Esa es la ventaja esencial de la recurrencia de Euler en este problema: transforma una busqueda sobre cantidades enormes en un calculo secuencial manejable.
对于正整数 \(n\)，记 \(p(n)\) 为 \(n\) 的整数拆分个数，也就是把 \(n\) 写成若干个正整数之和且不区分顺序的方法数。比如 \(p(4)=5\)，因为 4 的拆分只有 \(4\)、\(3+1\)、\(2+2\)、\(2+1+1\)、\(1+1+1+1\) 这五种。
本题要求找到最小的 \(n\)，使得 \(p(n)\) 可以被一百万整除：
$$p(n)\equiv 0 \pmod{10^6}.$$
拆分函数增长极快，所以正确的目标不是去保存庞大的精确整数，而是按顺序计算 \(p(0),p(1),p(2),\dots\) 在模 \(10^6\) 下的余数，直到第一次出现余数 0。
三个实现都围绕 Euler 的五边形递推公式展开。这个公式不是通用模板，而是由整数拆分的生成函数和五边形数定理直接推出来的。
如果我们分别决定拆分里用了多少个 \(1\)、多少个 \(2\)、多少个 \(3\)，那么拆分函数的生成函数就是
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
因为每个因子 \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) 表示部件 \(m\) 可以使用 0 次、1 次、2 次，依此类推。于是整个乘积中 \(x^n\) 的系数，恰好就是 \(n\) 的拆分个数。
Euler 证明了下面的恒等式：
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
由于这个乘积正好是 \(P(x)\) 的倒数，所以
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
比较 \(x^n\) 的系数，并约定 \(p(0)=1\)，当 \(m<0\) 时 \(p(m)=0\)，就得到
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
对每个固定的 \(n\) 而言，真正有贡献的项只有有限个，因为一旦偏移量大于 \(n\)，后面的项就全部越界了。
对每个 \(k\ge 1\)，会出现两个偏移量
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
它们形成数列
$$1,2,5,7,12,15,22,26,35,40,\dots$$
这就是广义五边形数。对应的符号只取决于 \(k\) 的奇偶性：\(k\) 为奇数时，这一对项都要相加；\(k\) 为偶数时，这一对项都要相减。因此沿着偏移量序列展开时，符号模式就是
$$+,+,-,-,+,+,-,-,\dots$$
实现中的内层循环正是按照这个模式累加。
当 \(n=7\) 时，不超过 7 的广义五边形数是 \(1,2,5,7\)。因此递推式变成
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
代入已经求出的 \(p(6)=11\)、\(p(5)=7\)、\(p(2)=2\)、\(p(0)=1\)，得到
$$p(7)=11+7-2-1=15.$$
这与 7 的 15 个实际拆分完全一致。这个例子说明了递推为何高效：每个新值都只依赖更小、已经算出的值。
递推式是线性的，所以把每个已存值都立刻化到模 \(10^6\) 下不会破坏正确性：
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
这就是实现依赖的核心不变量。计算第 \(n\) 项时，表中已经保存了所有更小下标的正确余数，而这些余数足以推出下一项。整个过程中都不需要保存巨大的精确拆分数。
C++、Python 和 Java 实现都从基例 \(p(0)=1\) 开始。之后按顺序扩展：先求 \(p(1)\) 的余数，再求 \(p(2)\)、\(p(3)\)，不断向后追加，直到第一次得到余数 0。
对于固定的 \(n\)，实现会遍历 \(k=1,2,3,\dots\)，计算两个偏移量 \(k(3k-1)/2\) 和 \(k(3k+1)/2\)。只要较小的那个偏移量已经大于 \(n\)，循环就立刻结束。每一对项是相加还是相减，只由 \(k\) 的奇偶性决定。如果第二个偏移量仍在范围内，它也会被计入。
中间和可能暂时为负，因此实现会先对目标模数取模，再把结果规范化到 \(0\) 到 \(10^6-1\) 的范围。C++ 和 Java 版本还会先用更宽的数值类型保存这个临时和，再做取模。
每求出一个新余数后，实现都会检查它是否为 0。第一次出现 0 的那个 \(n\) 就是所求答案。另有一个实现还附带了模 \(5\) 的小校验：因为 \(p(4)=5\)，所以满足 \(p(n)\equiv 0\pmod 5\) 的最小 \(n\) 必须是 4。先通过这个小例子，可以确认递推和停止逻辑都连接正确，再运行正式的 \(10^6\) 搜索。
设 \(N\) 是满足 \(p(N)\equiv 0\pmod{10^6}\) 的最小下标。对给定的 \(n\)，可用的广义五边形偏移量个数是 \(O(\sqrt{n})\)，因为这些偏移量关于 \(k\) 呈二次增长。把这个代价从 \(1\) 累加到 \(N\)，总时间就是
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
空间方面，只需要保存从 \(0\) 到 \(N\) 的一个余数表，所以是 \(O(N)\)。这正是 Euler 递推在本题中的价值：它把一个看似庞大的拆分搜索，变成了一个顺序推进、内存开销可控的计算过程。
Для положительного целого \(n\) обозначим через \(p(n)\) число разбиений \(n\) на положительные слагаемые, если порядок слагаемых не учитывается. Например, \(p(4)=5\), потому что существуют разбиения \(4\), \(3+1\), \(2+2\), \(2+1+1\) и \(1+1+1+1\).
В задаче нужно найти наименьшее \(n\), для которого \(p(n)\) делится на миллион:
$$p(n)\equiv 0 \pmod{10^6}.$$
Функция разбиений растет очень быстро, поэтому здесь важно не хранить огромные точные значения, а последовательно вычислять остатки \(p(0),p(1),p(2),\dots\) по модулю \(10^6\), пока впервые не встретится ноль.
Все три реализации опираются на пентагональную рекурсию Эйлера для функции разбиений. Это не абстрактная заготовка, а прямое следствие правильной производящей функции и теоремы о пятиугольных числах.
Если независимо выбирать, сколько раз в разбиении используется число \(1\), сколько раз число \(2\), сколько раз число \(3\) и так далее, то получаем
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
Каждый множитель \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) кодирует выбор количества частей, равных \(m\). Поэтому коэффициент при \(x^n\) в полном произведении в точности равен числу разбиений числа \(n\).
Эйлер доказал тождество
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
Так как это произведение является обратным к \(P(x)\), имеем
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
Сравнение коэффициентов при \(x^n\), вместе с соглашениями \(p(0)=1\) и \(p(m)=0\) при \(m<0\), приводит к формуле
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
Для фиксированного \(n\) в сумме реально участвует лишь конечное число членов, потому что после выхода смещения за предел \(n\) все последующие индексы уже отрицательны.
Для каждого \(k\ge 1\) возникают два смещения
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
Они образуют последовательность
$$1,2,5,7,12,15,22,26,35,40,\dots$$
обобщенных пятиугольных чисел. Знак зависит только от четности \(k\): при нечетном \(k\) обе величины прибавляются, при четном обе вычитаются. Поэтому вдоль последовательности смещений возникает рисунок
$$+,+,-,-,+,+,-,-,\dots$$
и именно его реализует внутренний цикл программы.
Для \(n=7\) обобщенные пятиугольные числа, не превосходящие 7, равны \(1,2,5,7\). Значит,
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
Подставляя ранее найденные значения \(p(6)=11\), \(p(5)=7\), \(p(2)=2\) и \(p(0)=1\), получаем
$$p(7)=11+7-2-1=15.$$
Это совпадает с прямым подсчетом 15 разбиений числа 7. Пример показывает, почему рекурсия эффективна: каждое новое значение собирается только из уже вычисленных меньших значений.
Рекурсия линейна, поэтому немедленное сокращение всех хранимых значений по модулю \(10^6\) сохраняет корректность:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
Это и есть главный инвариант реализации. К моменту вычисления шага \(n\) таблица уже содержит правильные остатки для всех меньших индексов, и этих остатков достаточно, чтобы получить следующий. Точные громадные значения функции разбиений нигде не нужны.
Реализации на C++, Python и Java начинают с базового случая \(p(0)=1\). Затем последовательность строится по порядку: вычисляется остаток для \(p(1)\), затем для \(p(2)\), затем для \(p(3)\) и так далее, пока впервые не встретится нулевой остаток.
Для фиксированного \(n\) программа перебирает \(k=1,2,3,\dots\), вычисляет смещения \(k(3k-1)/2\) и \(k(3k+1)/2\), и прекращает цикл, когда даже меньшее смещение уже больше \(n\). Прибавлять или вычитать пару, решает только четность \(k\). Если второе смещение тоже не выходит за пределы, его вклад также учитывается.
Промежуточная сумма может стать отрицательной, поэтому после накопления результат берется по модулю целевого значения и затем переводится в диапазон от \(0\) до \(10^6-1\). В версиях на C++ и Java для этой промежуточной суммы используется более широкий числовой тип.
После вычисления каждого нового остатка программа проверяет, равен ли он нулю. Первое такое \(n\) и есть ответ. Одна из реализаций также содержит маленький тест с модулем \(5\): так как \(p(4)=5\), минимальное \(n\), удовлетворяющее \(p(n)\equiv 0\pmod 5\), должно быть равно \(4\). Это удобная проверка правильности рекурсии и условия остановки перед основным запуском с модулем \(10^6\).
Пусть \(N\) - наименьший индекс, для которого \(p(N)\equiv 0\pmod{10^6}\). Для заданного \(n\) число пригодных смещений равно \(O(\sqrt{n})\), потому что обобщенные пятиугольные числа растут квадратично по \(k\). Суммарное время тогда равно
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
Память равна \(O(N)\), поскольку хранится по одному остатку на каждый индекс от \(0\) до \(N\). В этом и состоит сила метода: сложный на вид поиск по функции разбиений сводится к одному последовательному вычислению с умеренными затратами памяти.
لعدد صحيح موجب \(n\)، نرمز بـ \(p(n)\) إلى عدد طرق كتابة \(n\) على صورة مجموع أعداد صحيحة موجبة من دون اعتبار الترتيب. فمثلًا \(p(4)=5\)، لأن تقسيمات العدد 4 هي \(4\)، و\(3+1\)، و\(2+2\)، و\(2+1+1\)، و\(1+1+1+1\).
المطلوب هو إيجاد أصغر \(n\) يحقق أن \(p(n)\) يقبل القسمة على مليون:
$$p(n)\equiv 0 \pmod{10^6}.$$
دالة التقسيم تنمو بسرعة هائلة، لذلك ليس من العملي تتبع القيم الدقيقة الضخمة. المطلوب فعليًا هو توليد البواقي \(p(0),p(1),p(2),\dots\) بترديد \(10^6\) حتى يظهر أول باقي يساوي صفرًا.
تعتمد الحلول الثلاثة اعتمادًا كاملًا على علاقة أويلر التكرارية المبنية على الأعداد الخماسية المعممة. هذه ليست فكرة عامة قابلة للنسخ في أي مسألة، بل اشتقاق مباشر من دالة التوليد الخاصة بتقسيمات الأعداد ومن نظرية أويلر للأعداد الخماسية.
إذا قررنا بشكل مستقل كم مرة يظهر العدد \(1\)، وكم مرة يظهر العدد \(2\)، وكم مرة يظهر العدد \(3\)، وهكذا، فإن دالة التوليد تصبح
$$P(x)=\sum_{n=0}^{\infty} p(n)x^n=\prod_{m=1}^{\infty}\frac{1}{1-x^m}.$$
وذلك لأن كل عامل من الشكل \(1/(1-x^m)=1+x^m+x^{2m}+\cdots\) يصف استعمال الجزء \(m\) صفر مرة أو مرة واحدة أو مرتين وهكذا. لذلك فإن معامل \(x^n\) في حاصل الضرب الكامل يساوي تمامًا عدد تقسيمات \(n\).
أثبت أويلر الهوية
$$\prod_{m=1}^{\infty}(1-x^m)=1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right).$$
وبما أن هذا الحاصل هو مقلوب \(P(x)\)، نحصل على
$$P(x)\cdot\left(1+\sum_{k=1}^{\infty}(-1)^k\left(x^{k(3k-1)/2}+x^{k(3k+1)/2}\right)\right)=1.$$
بمقارنة معاملات \(x^n\)، ومع اعتماد \(p(0)=1\) و\(p(m)=0\) عندما يكون \(m<0\)، تنتج العلاقة
$$p(n)=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p\left(n-\frac{k(3k-1)}{2}\right)+p\left(n-\frac{k(3k+1)}{2}\right)\right).$$
ولكل \(n\) ثابت لا يظهر إلا عدد منته من الحدود، لأن الإزاحات تصبح في النهاية أكبر من \(n\)، وعندها تسقط بقية الحدود تلقائيًا.
لكل \(k\ge 1\) تظهر إزاحتان:
$$g_k^-=\frac{k(3k-1)}{2},\qquad g_k^+=\frac{k(3k+1)}{2}.$$
وهما ينتجان المتتالية
$$1,2,5,7,12,15,22,26,35,40,\dots$$
المعروفة باسم الأعداد الخماسية المعممة. وتعتمد الإشارة فقط على زوجية \(k\): إذا كان \(k\) فرديًا فإن الحدين يضافان، وإذا كان زوجيًا فإن الحدين يطرحان. لذا يكون النمط على امتداد الإزاحات هو
$$+,+,-,-,+,+,-,-,\dots$$
وهذا بالتحديد هو النمط الذي تنفذه الحلقات الداخلية في الشفرة.
عندما \(n=7\)، فإن الأعداد الخماسية المعممة التي لا تتجاوز 7 هي \(1,2,5,7\). لذلك تصبح العلاقة
$$p(7)=p(6)+p(5)-p(2)-p(0).$$
وباستخدام القيم السابقة \(p(6)=11\)، و\(p(5)=7\)، و\(p(2)=2\)، و\(p(0)=1\)، نجد
$$p(7)=11+7-2-1=15.$$
وهذا يطابق العد المباشر لخمسة عشر تقسيمًا للعدد 7. المثال يوضح سبب فاعلية العلاقة: كل قيمة جديدة تبنى فقط من قيم أصغر سبق حسابها.
العلاقة التكرارية خطية، ولذلك فإن اختزال كل قيمة مخزنة مباشرة بترديد \(10^6\) يحافظ على الصحة:
$$p(n)\bmod 10^6=\sum_{k=1}^{\infty}(-1)^{k+1}\left(p(n-g_k^-)+p(n-g_k^+)\right)\bmod 10^6.$$
هذا هو الثابت الأساسي الذي تعتمد عليه الخوارزمية. فعند حساب الخطوة \(n\)، يكون الجدول قد احتوى مسبقًا على البواقي الصحيحة لكل الفهارس الأصغر، وهذه البواقي وحدها تكفي لإنتاج الباقي التالي. لا حاجة في أي لحظة إلى حفظ قيمة دقيقة ضخمة للدالة \(p(n)\).
تبدأ تطبيقات C++ وPython وJava من الحالة الأساسية \(p(0)=1\). ثم تبني المتتالية على الترتيب: تحسب باقي \(p(1)\)، ثم \(p(2)\)، ثم \(p(3)\)، وتواصل الإضافة إلى الجدول حتى يظهر أول باقي صفري.
لكل \(n\) ثابت، تمر الخوارزمية على \(k=1,2,3,\dots\)، وتحسب الإزاحتين \(k(3k-1)/2\) و\(k(3k+1)/2\)، وتتوقف عندما تصبح حتى الإزاحة الأصغر أكبر من \(n\). أما كون الزوج يضاف أو يطرح فيتحدد فقط من فردية \(k\) أو زوجيته. وإذا كانت الإزاحة الثانية ما تزال داخل المجال، فإن مساهمتها تدخل أيضًا في المجموع.
يمكن أن يصبح المجموع المؤقت سالبًا، لذلك تختزل النتيجة في النهاية بترديد القيمة المطلوبة، ثم تطبع داخل المجال \(0\) إلى \(10^6-1\). كما تستخدم نسختا C++ وJava نوعًا عدديًا أوسع لهذا المجموع المؤقت قبل تطبيق الترديد.
بعد حساب كل باقي جديد، تتحقق الخوارزمية مما إذا كان يساوي صفرًا. أول \(n\) يحقق ذلك هو الجواب المطلوب. وتحتوي إحدى النسخ أيضًا على فحص صغير عند الترديد \(5\): بما أن \(p(4)=5\)، فإن أصغر \(n\) يحقق \(p(n)\equiv 0\pmod 5\) يجب أن يكون \(4\). هذا الاختبار يعطي ثقة بأن العلاقة التكرارية وآلية التوقف تعملان بصورة صحيحة قبل تشغيل البحث الكامل بترديد \(10^6\).
لنفرض أن \(N\) هو أصغر فهرس يحقق \(p(N)\equiv 0\pmod{10^6}\). بالنسبة إلى \(n\) معين، فإن عدد الإزاحات الصالحة هو \(O(\sqrt{n})\)، لأن الأعداد الخماسية المعممة تنمو تربيعيًا بالنسبة إلى \(k\). وبجمع هذه الكلفة من \(1\) حتى \(N\) نحصل على
$$\sum_{n=1}^{N} O(\sqrt{n})=O(N^{3/2}).$$
أما الذاكرة فهي \(O(N)\)، لأن الجدول يخزن باقيًا واحدًا لكل قيمة من \(0\) حتى \(N\). وهذه هي قوة طريقة أويلر هنا: تحويل بحث يبدو ثقيلًا جدًا إلى حساب تسلسلي بسيط نسبيًا ومحدود الذاكرة.