We seek the first pentagonal number \(P_n=\frac{n(3n-1)}{2}\) that has more than 100 representations of the form
$$P_n=P_a+P_b,\qquad a\ge b\ge 1.$$
The C++, Python, and Java implementations do not search over \((a,b)\) directly. Instead, they translate the question into a constrained sum-of-two-squares problem and then count the admissible representations through Gaussian-integer factorization.
The starting point is the classical identity
$$24P_t+1=(6t-1)^2.$$
That identity turns the pentagonal equation into an arithmetic problem about quadratic forms.
If \(P_a+P_b=P_n\), then
$$24P_a+24P_b+2=24P_n+2,$$
so
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
Define
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1.$$
Then every pentagonal decomposition corresponds to a representation
$$x^2+y^2=N_n$$
with
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
Conversely, every positive unordered pair \((x,y)\) satisfying these congruences maps back uniquely to
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
So counting representations \(P_n=P_a+P_b\) is exactly the same as counting unordered positive representations of \(N_n\) as a sum of two squares with both coordinates congruent to \(5\) modulo \(6\).
Write
$$N_n=k^2+1,\qquad k=6n-1.$$
If an odd prime \(q\) divides \(N_n\), then
$$k^2\equiv -1\pmod q.$$
Therefore \(-1\) is a quadratic residue modulo \(q\), which can happen only when
$$q\equiv 1\pmod 4.$$
Also \(k\) is odd, so \(k^2\equiv 1\pmod 8\), hence
$$N_n=k^2+1\equiv 2\pmod 8.$$
This means that \(2\) divides \(N_n\) exactly once. Consequently every candidate that is fully factored has the shape
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
This is precisely the situation in which Gaussian integers give a natural parametrization of all representations by two squares.
For each odd prime \(p_i\equiv 1\pmod 4\), choose integers \(u_i,v_i>0\) such that
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
Let \(\pi_i=u_i+iv_i\). Since
$$2=(1+i)(1-i),$$
we can write
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
Now choose integers \(s_i\) with \(0\le s_i\le e_i\). The Gaussian integer
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}$$
has norm
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
If \(z=x+iy\), then automatically
$$x^2+y^2=N_n.$$
The implementations enumerate exactly these exponent splits. Distinct primes contribute independently, so the total raw search space for one candidate is multiplicative in the exponents \(e_i\).
Not every representation of \(N_n\) comes from pentagonal indices. The pair must satisfy the congruence condition
$$x\equiv y\equiv 5\pmod 6,$$
and both coordinates must be positive. Sign changes and swapping the coordinates do not create new decompositions of \(P_n\), so the implementations convert each representation to the canonical ordered pair
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr),$$
discard zero coordinates, and keep only distinct pairs that survive the modulo-\(6\) test. Each surviving pair corresponds to exactly one choice of \((a,b)\) with \(a\ge b\).
If
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
then the Gaussian construction above creates
$$2\prod_{i=1}^{r}(e_i+1)$$
signed and oriented products before deduplication, or equivalently \(\prod (e_i+1)\) choices if the factor \(2\) is included in the exponent list. Conjugate choices always collapse to the same unordered absolute pair, so the number of relevant unordered candidates is at most
$$\frac{1}{2}\prod_{j}(e_j+1),$$
where the product runs over all prime exponents, including the exponent \(1\) of \(2\). If this bound is at most \(100\), then the current \(n\) cannot solve the problem, so the exact Gaussian enumeration is skipped.
For \(n=49\),
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
and
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
The quick bound becomes
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
so exact enumeration is necessary. After constructing all Gaussian products, removing sign and order duplicates, and imposing \(x\equiv y\equiv 5\pmod 6\), the surviving pairs are
$$ (x,y)=(287,59)\quad\text{and}\quad (281,83). $$
They map back to
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
Hence
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
so \(P_{49}\) has exactly two admissible pentagonal decompositions.
The C++, Python, and Java implementations share the same core pipeline. They precompute a list of small primes and, for each prime \(p\equiv 1\pmod 4\) in that table, one concrete decomposition \(p=u^2+v^2\). Then they scan \(n=1,2,3,\dots\), form \(N_n=(6n-1)^2+1\), and trial-divide it by the precomputed primes. If a residual cofactor remains, the candidate is skipped; otherwise the full exponent list is known.
From that factorization, the implementation first evaluates the bound \(\frac12\prod(e_j+1)\). Only if this can exceed \(100\) does it build all Gaussian products coming from the exponent splits. Each product yields one pair \((x,y)\); the implementation then takes absolute values, orders the coordinates, removes zero coordinates, applies the congruence test \(x\equiv y\equiv 5\pmod 6\), and stores the surviving pairs in a set. The first \(n\) whose exact count is greater than \(100\) produces the required answer \(P_n\).
For one candidate \(n\), the cheap stage is trial division of \(N_n\) by the precomputed prime table. The expensive stage, used only for candidates that survive the upper bound, enumerates \(O\!\left(\prod(e_j+1)\right)\) Gaussian products and uses the same order of temporary storage before deduplication.
The total runtime depends on how far the search must advance before the first count above \(100\) appears. In practice most candidates are rejected early: many are not fully factored by the fixed prime table, and many fully factored candidates fail the bound \(\frac12\prod(e_j+1)>100\). That combination of cheap factor filtering and late exact counting is what makes the search feasible.
Gesucht ist die erste pentagonale Zahl \(P_n=\frac{n(3n-1)}{2}\), die mehr als 100 Darstellungen der Form
$$P_n=P_a+P_b,\qquad a\ge b\ge 1$$
besitzt. Die Implementierungen durchsuchen nicht direkt alle Paare \((a,b)\), sondern übersetzen die Aufgabe in ein Problem über Darstellungen als Summe zweier Quadrate und zählen nur die zulässigen Fälle.
Der Ausgangspunkt ist die Identität
$$24P_t+1=(6t-1)^2.$$
Dadurch lässt sich die pentagonale Gleichung in eine Form bringen, die mit Gaußschen ganzen Zahlen gut behandelt werden kann.
Aus \(P_a+P_b=P_n\) folgt
$$24P_a+24P_b+2=24P_n+2,$$
also
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
Setzen wir
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1,$$
dann wird jede Zerlegung von \(P_n\) zu einer Darstellung
$$x^2+y^2=N_n$$
mit den Nebenbedingungen
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
Umgekehrt liefert jedes positive ungeordnete Paar \((x,y)\) mit diesen Kongruenzen genau
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
Das Zählen pentagonaler Darstellungen ist daher exakt dasselbe wie das Zählen ungeordneter positiver Zwei-Quadrate-Darstellungen von \(N_n\), bei denen beide Koordinaten \(5\) modulo \(6\) sind.
Schreibe
$$N_n=k^2+1,\qquad k=6n-1.$$
Teilt eine ungerade Primzahl \(q\) die Zahl \(N_n\), dann gilt
$$k^2\equiv -1\pmod q.$$
Damit ist \(-1\) ein quadratischer Rest modulo \(q\), was nur möglich ist, wenn
$$q\equiv 1\pmod 4.$$
Außerdem ist \(k\) ungerade, also \(k^2\equiv 1\pmod 8\), und damit
$$N_n=k^2+1\equiv 2\pmod 8.$$
Folglich teilt die Primzahl \(2\) die Zahl \(N_n\) genau einmal. Jede vollständig faktorisierte Kandidatenzahl hat also die Form
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
Genau in dieser Situation liefern Gaußsche ganze Zahlen eine vollständige Beschreibung aller Darstellungen als Summe zweier Quadrate.
Für jede ungerade Primzahl \(p_i\equiv 1\pmod 4\) wähle positive ganze Zahlen \(u_i,v_i\) mit
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
Schreibe \(\pi_i=u_i+iv_i\). Wegen
$$2=(1+i)(1-i)$$
erhält man
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
Wählt man nun für jedes \(i\) eine Zahl \(s_i\) mit \(0\le s_i\le e_i\), dann hat
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}$$
die Norm
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
Schreibt man \(z=x+iy\), folgt sofort
$$x^2+y^2=N_n.$$
Die Implementierungen enumerieren genau diese Exponentenaufteilungen. Verschiedene Primzahlen tragen unabhängig voneinander bei, daher ist der rohe Suchraum multiplikativ in den Exponenten \(e_i\).
Nicht jede Darstellung von \(N_n\) liefert gültige Indizes \(a\) und \(b\). Erforderlich ist
$$x\equiv y\equiv 5\pmod 6,$$
und beide Koordinaten müssen positiv sein. Vorzeichenwechsel und das Vertauschen von \(x\) und \(y\) erzeugen keine neue Zerlegung von \(P_n\), daher wird jede Darstellung auf das kanonische Paar
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr)$$
abgebildet. Paare mit Nullkoordinate werden verworfen, danach bleibt nur der Teil übrig, der den Modulo-\(6\)-Filter besteht. Jedes verbleibende Paar entspricht genau einem \((a,b)\) mit \(a\ge b\).
Ist
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
dann liefert die Gaußsche Konstruktion insgesamt
$$2\prod_{i=1}^{r}(e_i+1)$$
vorzeichen- und richtungsabhängige Produkte vor der Deduplikation, beziehungsweise \(\prod(e_i+1)\) Möglichkeiten, wenn man den Faktor \(2\) in dieselbe Exponentenliste aufnimmt. Konjugierte Wahlmöglichkeiten führen stets auf dasselbe ungeordnete Absolutpaar, also ist die Zahl relevanter ungeordneter Kandidaten höchstens
$$\frac{1}{2}\prod_{j}(e_j+1),$$
wobei das Produkt über alle Primexponenten läuft, einschließlich des Exponenten \(1\) von \(2\). Ist diese Schranke höchstens \(100\), kann der aktuelle Wert von \(n\) die Aufgabe nicht lösen, und die teure exakte Enumeration wird übersprungen.
Für \(n=49\) gilt
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
und
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
Die schnelle Schranke ist damit
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
also muss exakt gezählt werden. Nach der Gaußschen Erzeugung aller Produkte, dem Entfernen von Vorzeichen- und Reihenfolgedubletten sowie dem Modulo-\(6\)-Filter bleiben genau die Paare
$$ (x,y)=(287,59)\quad\text{und}\quad (281,83) $$
übrig. Sie entsprechen
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
Damit gilt
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
also besitzt \(P_{49}\) genau zwei zulässige Darstellungen.
Die C++-, Python- und Java-Implementierungen folgen derselben Grundidee. Zuerst wird eine Liste kleiner Primzahlen vorab berechnet, und für jede Primzahl \(p\equiv 1\pmod 4\) in dieser Tabelle wird eine konkrete Zerlegung \(p=u^2+v^2\) gespeichert. Anschließend laufen die Programme über \(n=1,2,3,\dots\), bilden \(N_n=(6n-1)^2+1\) und faktorisieren diese Zahl per Probedivision mit den vorberechneten Primzahlen. Bleibt ein Restfaktor übrig, wird der Kandidat übersprungen; andernfalls ist die Exponentenliste vollständig bekannt.
Aus dieser Faktorisierung wird zunächst die Schranke \(\frac12\prod(e_j+1)\) berechnet. Nur wenn sie größer als \(100\) sein kann, werden alle Gaußschen Produkte aus den Exponentenaufteilungen wirklich erzeugt. Jedes Produkt liefert ein Paar \((x,y)\); danach werden Absolutbeträge genommen, die Koordinaten geordnet, Nullkoordinaten entfernt, die Bedingung \(x\equiv y\equiv 5\pmod 6\) geprüft und die verbleibenden Paare in einer Menge gesammelt. Das erste \(n\), dessen exakte Anzahl größer als \(100\) ist, liefert die gesuchte pentagonale Zahl \(P_n\).
Für einen festen Kandidaten \(n\) ist die billige Phase die Probedivision von \(N_n\) durch die vorberechnete Primtabelle. Die teure Phase, die nur für Kandidaten nach bestandener Schranke ausgeführt wird, enumeriert \(O\!\left(\prod(e_j+1)\right)\) Gaußsche Produkte und benötigt vor der Deduplikation Speicher derselben Größenordnung.
Die Gesamtlaufzeit hängt davon ab, wie weit die Suche gehen muss, bis erstmals mehr als \(100\) Darstellungen auftreten. In der Praxis werden die meisten Kandidaten früh verworfen: Viele lassen sich mit der festen Primtabelle nicht vollständig faktorisieren, und viele vollständig faktorisierte Kandidaten scheitern bereits an der Schranke \(\frac12\prod(e_j+1)>100\). Gerade diese Kombination aus billigem Vorfilter und spätem exaktem Zählen macht die Suche praktikabel.
Aranan şey, \(P_n=\frac{n(3n-1)}{2}\) pentagonal sayılarından hangisinin ilk kez
$$P_n=P_a+P_b,\qquad a\ge b\ge 1$$
biçiminde 100’den fazla gösterime sahip olduğudur. C++, Python ve Java uygulamaları \((a,b)\) çiftlerini doğrudan taramak yerine problemi kısıtlı bir iki kare toplamı sayımına dönüştürür.
Temel kimlik şudur:
$$24P_t+1=(6t-1)^2.$$
Bu sayede pentagonal denklem, Gaussian tamsayılarla çözülebilen bir biçime çevrilir.
\(P_a+P_b=P_n\) ise
$$24P_a+24P_b+2=24P_n+2,$$
dolayısıyla
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
Şimdi
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1$$
tanımını yapalım. Böylece her pentagonal ayrışım
$$x^2+y^2=N_n$$
biçiminde bir temsile karşılık gelir ve ayrıca
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5$$
olmalıdır. Ters yönde, bu koşulları sağlayan her pozitif sırasız \((x,y)\) çifti tek bir
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}$$
çiftine döner. Yani \(P_n=P_a+P_b\) sayımı ile \(N_n\)’nin iki kare toplamı temsillerini saymak tamamen aynı iştir; yalnızca mod \(6\) filtresi uygulanır.
Şöyle yazalım:
$$N_n=k^2+1,\qquad k=6n-1.$$
Eğer tek bir asal \(q\), \(N_n\)’yi bölüyorsa
$$k^2\equiv -1\pmod q$$
olur. Demek ki \(-1\), \(q\) modunda kuadratik artık olmalıdır; bu da ancak
$$q\equiv 1\pmod 4$$
olduğunda mümkündür. Ayrıca \(k\) tek olduğu için \(k^2\equiv 1\pmod 8\) ve bu yüzden
$$N_n=k^2+1\equiv 2\pmod 8.$$
Böylece \(2\), \(N_n\)’yi tam bir kez böler. Sonuç olarak tam çarpanlara ayrılmış her aday şu yapıdadır:
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
Bu yapı, Gaussian tamsayılarla tüm iki-kare temsillerini üretmek için tam olarak uygun durumdur.
Her \(p_i\equiv 1\pmod 4\) asalı için pozitif \(u_i,v_i\) sayıları seçelim:
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
\(\pi_i=u_i+iv_i\) yazarsak ve
$$2=(1+i)(1-i)$$
olduğunu kullanırsak,
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}$$
elde edilir. Şimdi her \(i\) için \(0\le s_i\le e_i\) seçip
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}$$
tanımlayalım. O zaman
$$\mathcal{N}(z)=z\overline{z}=N_n$$
olur. \(z=x+iy\) yazıldığında otomatik olarak
$$x^2+y^2=N_n$$
elde edilir. Uygulamalar tam olarak bu üs bölüşümlerini enumerate eder; farklı asallar birbirinden bağımsız katkı verdiği için ham arama uzayı çarpımsal yapıdadır.
\(N_n\)’nin her iki-kare temsili geçerli değildir. Gerekli koşul
$$x\equiv y\equiv 5\pmod 6$$
ve her iki koordinatın da pozitif olmasıdır. İşaret değişimleri ve koordinatların yer değiştirmesi yeni bir \(P_a+P_b\) ayrışımı üretmez. Bu yüzden her temsil kanonik olarak
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr)$$
çiftine dönüştürülür, sıfır koordinatlar atılır ve yalnızca mod \(6\) testini geçen farklı çiftler tutulur. Kalan her çift tek bir \(a\ge b\) çözümüne karşılık gelir.
Eğer
$$N_n=2\prod_{i=1}^{r} p_i^{e_i}$$
ise, yukarıdaki Gaussian üretim
$$2\prod_{i=1}^{r}(e_i+1)$$
adet işaretli ve yönlü çarpım oluşturur; eşdeğer olarak, \(2\)’nin üssü de listeye katılırsa \(\prod(e_i+1)\) ham seçim vardır. Eşlenik seçimler aynı sırasız mutlak değere gittiği için ilgili sırasız aday sayısı en fazla
$$\frac{1}{2}\prod_{j}(e_j+1)$$
olabilir. Buradaki çarpım, \(2\)’nin üssü \(1\) dahil tüm asal üsler üzerindedir. Bu üst sınır \(100\)’ü geçmiyorsa o \(n\) değeri problemi çözemez; dolayısıyla pahalı tam enumerate işlemi yapılmaz.
\(n=49\) için
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
ve
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
Hızlı üst sınır
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6$$
olduğundan tam sayım gerekir. Tüm Gaussian çarpımlar üretildikten, işaret ve sıra tekrarları ayıklandıktan ve \(x\equiv y\equiv 5\pmod 6\) filtresi uygulandıktan sonra kalan çiftler
$$ (x,y)=(287,59)\quad\text{ve}\quad (281,83) $$
olur. Bunlar
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14) $$
çiftlerine karşılık gelir. Böylece
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14}$$
ve \(P_{49}\)’un tam olarak iki geçerli gösterimi vardır.
C++, Python ve Java uygulamaları aynı hattı izler. Önce küçük asalların bir listesi hazırlanır ve tablodaki her \(p\equiv 1\pmod 4\) asalı için bir \(p=u^2+v^2\) ayrışımı saklanır. Sonra \(n=1,2,3,\dots\) artarken \(N_n=(6n-1)^2+1\) hesaplanır ve önceden çıkarılmış asallarla deneme bölmesi yapılır. Eğer geriye kalan bir kofaktör varsa aday atlanır; aksi halde üs listesi tamamen bilinir.
Bu çarpanlara ayırımdan önce \(\frac12\prod(e_j+1)\) üst sınırı hesaplanır. Yalnızca bu değer \(100\)’ü geçebiliyorsa Gaussian çarpımlar gerçekten üretilir. Her çarpım bir \((x,y)\) çifti verir; ardından mutlak değer alınır, büyük olan öne konur, sıfır koordinatlar atılır, \(x\equiv y\equiv 5\pmod 6\) testi uygulanır ve kalan çiftler bir kümede tekilleştirilir. Geçerli temsil sayısı ilk kez \(100\)’ü aşan \(n\), aranan pentagonal sayı \(P_n\)’u verir.
Sabit bir \(n\) adayı için ucuz aşama, \(N_n\)’nin önceden hazırlanmış asal tablosuyla deneme bölmesine sokulmasıdır. Pahalı aşama ise, yalnızca üst sınırı geçen adaylarda çalışır ve Deduplikasyon öncesinde \(O\!\left(\prod(e_j+1)\right)\) adet Gaussian çarpım üretir; geçici bellek ihtiyacı da aynı mertebededir.
Toplam çalışma süresi, sayımın ilk kez \(100\)’ü geçtiği değere kadar ne kadar ilerlenmesi gerektiğine bağlıdır. Pratikte çoğu aday erkenden elenir: bir kısmı sabit asal tablosuyla tam çarpanlara ayrılamaz, bir kısmı ise \(\frac12\prod(e_j+1)>100\) koşulunu sağlayamaz. Aramayı uygulanabilir kılan nokta, ucuz çarpan filtresi ile geç yapılan tam sayımın birleşimidir.
Se busca el primer número pentagonal \(P_n=\frac{n(3n-1)}{2}\) que admite más de 100 representaciones de la forma
$$P_n=P_a+P_b,\qquad a\ge b\ge 1.$$
Las implementaciones en C++, Python y Java no recorren directamente todos los pares \((a,b)\). En su lugar, convierten la tarea en un problema de representaciones como suma de dos cuadrados con una restricción modular adicional.
La identidad de partida es
$$24P_t+1=(6t-1)^2.$$
Esa relación permite transformar la ecuación pentagonal en una condición aritmética mucho más estructurada.
Si \(P_a+P_b=P_n\), entonces
$$24P_a+24P_b+2=24P_n+2,$$
y por tanto
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
Definimos
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1.$$
Así, toda descomposición pentagonal produce una representación
$$x^2+y^2=N_n$$
con
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
Recíprocamente, todo par positivo no ordenado \((x,y)\) con esas congruencias determina de manera única
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
Por lo tanto, contar las soluciones de \(P_n=P_a+P_b\) equivale exactamente a contar las representaciones positivas y no ordenadas de \(N_n\) como suma de dos cuadrados, exigiendo además que ambas coordenadas sean congruentes con \(5\) módulo \(6\).
Escribamos
$$N_n=k^2+1,\qquad k=6n-1.$$
Si un primo impar \(q\) divide a \(N_n\), entonces
$$k^2\equiv -1\pmod q.$$
Eso significa que \(-1\) es residuo cuadrático módulo \(q\), lo cual solo puede ocurrir si
$$q\equiv 1\pmod 4.$$
Además, como \(k\) es impar, se tiene \(k^2\equiv 1\pmod 8\), de modo que
$$N_n=k^2+1\equiv 2\pmod 8.$$
En consecuencia, el primo \(2\) divide a \(N_n\) exactamente una vez. Toda factorización completa de un candidato tiene la forma
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
Este es precisamente el escenario natural para trabajar con enteros gaussianos.
Para cada primo impar \(p_i\equiv 1\pmod 4\), elegimos enteros positivos \(u_i,v_i\) tales que
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
Si escribimos \(\pi_i=u_i+iv_i\) y usamos que
$$2=(1+i)(1-i),$$
obtenemos
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
Ahora, para cada \(i\), escogemos un entero \(s_i\) con \(0\le s_i\le e_i\) y definimos
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}.$$
Entonces
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
Si \(z=x+iy\), se obtiene automáticamente
$$x^2+y^2=N_n.$$
Las implementaciones enumeran exactamente estas distribuciones de exponentes. Como los distintos primos aportan de forma independiente, el tamaño bruto del espacio de búsqueda es multiplicativo en los exponentes \(e_i\).
No toda representación de \(N_n\) corresponde a una descomposición pentagonal válida. Debemos exigir
$$x\equiv y\equiv 5\pmod 6,$$
y además \(x\) e \(y\) deben ser positivos. Cambiar signos o permutar coordenadas no produce una nueva identidad \(P_n=P_a+P_b\), así que cada representación se lleva al par canónico
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr).$$
Se descartan las coordenadas nulas y luego se conservan únicamente los pares distintos que pasan el filtro módulo \(6\). Cada uno de esos pares determina exactamente una solución \((a,b)\) con \(a\ge b\).
Si
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
la construcción gaussiana genera
$$2\prod_{i=1}^{r}(e_i+1)$$
productos orientados y con signo antes de eliminar duplicados, o equivalentemente \(\prod(e_i+1)\) elecciones si el factor \(2\) se incorpora a la misma lista de exponentes. Las elecciones conjugadas siempre colapsan al mismo par absoluto no ordenado, de modo que el número de candidatos relevantes es a lo sumo
$$\frac{1}{2}\prod_{j}(e_j+1),$$
donde el producto recorre todos los exponentes primos, incluido el exponente \(1\) de \(2\). Si esta cota no supera \(100\), el valor actual de \(n\) no puede resolver el problema y se evita la enumeración exacta.
Para \(n=49\),
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
y
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
La cota rápida es
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
por lo que hace falta enumerar exactamente. Después de construir todos los productos gaussianos, eliminar duplicados por signo y orden, y aplicar el filtro \(x\equiv y\equiv 5\pmod 6\), sobreviven los pares
$$ (x,y)=(287,59)\quad\text{y}\quad (281,83). $$
Estos devuelven
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
Por tanto,
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
y \(P_{49}\) tiene exactamente dos representaciones admisibles.
Las implementaciones en C++, Python y Java siguen la misma estrategia. Primero precalculan una tabla de primos pequeños y, para cada primo \(p\equiv 1\pmod 4\) contenido en esa tabla, almacenan una descomposición concreta \(p=u^2+v^2\). Luego recorren \(n=1,2,3,\dots\), forman \(N_n=(6n-1)^2+1\) y lo factorizar mediante división de prueba con esos primos. Si queda un cofactor residual, el candidato se descarta; si no, la lista completa de exponentes queda determinada.
A partir de esa factorización, la implementación calcula primero la cota \(\frac12\prod(e_j+1)\). Solo si puede superar \(100\) construye de manera explícita todos los productos gaussianos asociados a las distribuciones de exponentes. Cada producto produce un par \((x,y)\); después se toman valores absolutos, se ordenan las coordenadas, se descartan coordenadas nulas, se aplica el test \(x\equiv y\equiv 5\pmod 6\) y los pares supervivientes se guardan en un conjunto. El primer \(n\) cuya cuenta exacta supera \(100\) produce el número pentagonal pedido \(P_n\).
Para un candidato fijo \(n\), la fase barata es la factorización de \(N_n\) por división de prueba con la tabla de primos precalculada. La fase costosa, reservada para los candidatos que pasan la cota previa, enumera \(O\!\left(\prod(e_j+1)\right)\) productos gaussianos y necesita memoria temporal del mismo orden antes de la deduplicación.
El tiempo total depende de cuán lejos deba avanzar la búsqueda antes de encontrar la primera cuenta superior a \(100\). En la práctica, la mayoría de los candidatos se descartan pronto: muchos no quedan completamente factorizados por la tabla fija de primos y muchos de los que sí quedan factorizados no alcanzan la desigualdad \(\frac12\prod(e_j+1)>100\). Esa combinación de filtro barato y conteo exacto tardío es la que vuelve viable la búsqueda.
目标是找到第一个五边形数 \(P_n=\frac{n(3n-1)}{2}\)，使它能够以
$$P_n=P_a+P_b,\qquad a\ge b\ge 1$$
的形式表示超过 100 次。这里的“次数”按无序对 \((a,b)\) 计数，也就是 \((a,b)\) 与 \((b,a)\) 不重复计算。C++、Python 和 Java 的实现都没有直接枚举所有 \((a,b)\)，而是先把问题改写成一个带同余限制的二平方和计数问题。
整个方法的起点是五边形数的标准恒等式
$$24P_t+1=(6t-1)^2.$$
这个恒等式把原来的加法问题转成了一个关于平方和与素因子结构的问题。
如果 \(P_a+P_b=P_n\)，那么
$$24P_a+24P_b+2=24P_n+2,$$
于是得到
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
定义
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1.$$
这样一来，每个五边形分解都对应于
$$x^2+y^2=N_n$$
的一个表示，并且必须满足
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
反过来，只要 \((x,y)\) 是满足这些条件的正整数无序对，就能唯一还原出
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
因此，原题等价于：对每个 \(n\)，统计 \(N_n\) 写成两个正平方和的无序表示数，其中两个坐标都必须与 \(5\) 同余于模 \(6\)。这一步是整个算法的核心桥梁。
记
$$N_n=k^2+1,\qquad k=6n-1.$$
若奇素数 \(q\) 整除 \(N_n\)，则
$$k^2\equiv -1\pmod q.$$
这说明 \(-1\) 在模 \(q\) 意义下是二次剩余。数论中的经典结论告诉我们，这只有在
$$q\equiv 1\pmod 4$$
时才可能发生。另一方面，\(k\) 一定是奇数，所以 \(k^2\equiv 1\pmod 8\)，从而
$$N_n=k^2+1\equiv 2\pmod 8.$$
这说明素数 \(2\) 恰好只出现一次。因此，只要某个候选值被完全分解，它一定具有形式
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
也就是说，除了 \(2\) 以外，所有奇素因子都落在 \(1 \bmod 4\) 这一类里。这正是 Gaussian 整数分解最自然的应用场景。
对每个满足 \(p_i\equiv 1\pmod 4\) 的奇素数，都可以找到正整数 \(u_i,v_i\)，使得
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
记 \(\pi_i=u_i+iv_i\)。又因为
$$2=(1+i)(1-i),$$
所以
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
现在，对每个 \(i\) 选取一个整数 \(s_i\)，满足 \(0\le s_i\le e_i\)，并构造
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}.$$
它的范数是
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
如果把 \(z\) 写成 \(x+iy\)，就立刻得到
$$x^2+y^2=N_n.$$
也就是说，所有二平方和表示都可以通过“在每个共轭因子对之间分配指数”的方式生成。实现就是按这个原则逐个素因子做组合，再把各个素因子的贡献相乘起来。
并不是 \(N_n\) 的每个二平方和表示都对应有效的 \(P_a+P_b\)。必须额外要求
$$x\equiv y\equiv 5\pmod 6,$$
而且 \(x,y\) 都要为正。再者，符号变化与坐标交换不会产生新的五边形分解，所以实现会把每个表示规范化成
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr).$$
零坐标会被丢弃，然后只保留通过模 \(6\) 检验的不同有序对。剩下的每一个规范对都对应唯一的一个 \((a,b)\)，并且自动满足 \(a\ge b\)。这一步把“所有平方和表示”精确收缩成“真正的五边形表示”。
如果
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
那么上面的 Gaussian 构造在去重之前会产生
$$2\prod_{i=1}^{r}(e_i+1)$$
个带方向和符号的信息的乘积；如果把素数 \(2\) 的指数 \(1\) 也放进同一张指数表，那么等价地可以写成 \(\prod(e_i+1)\) 个原始选择。由于共轭选择最终总会落到同一个无序绝对值对上，所以真正可能留下的无序候选数最多只有
$$\frac{1}{2}\prod_{j}(e_j+1),$$
这里的乘积对所有素数指数进行，包括 \(2\) 的指数 \(1\)。如果这个上界都不超过 \(100\)，那么当前的 \(n\) 无论如何都不可能成为答案，于是实现直接跳过昂贵的精确枚举。
当 \(n=49\) 时，
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
并且
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
快速上界为
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
所以必须进行精确枚举。把所有 Gaussian 乘积构造出来，去掉符号与顺序重复，再施加 \(x\equiv y\equiv 5\pmod 6\) 的限制后，剩下的有效对正好是
$$ (x,y)=(287,59)\quad\text{和}\quad (281,83). $$
它们分别还原为
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
因此
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
说明 \(P_{49}\) 恰好有 2 个符合条件的表示。
C++、Python 和 Java 的实现共享同一条主线。它们先预计算一张小素数表，并为表中每个满足 \(p\equiv 1\pmod 4\) 的素数预存一个 \(p=u^2+v^2\) 分解。随后按 \(n=1,2,3,\dots\) 递增，构造 \(N_n=(6n-1)^2+1\)，并用这张素数表做试除分解。如果试除结束后还有剩余因子，就直接跳过这个候选值；如果没有剩余因子，说明该候选值的指数列表已经完全知道。
有了指数列表后，实现先计算 \(\frac12\prod(e_j+1)\) 这个廉价上界。只有当它可能超过 \(100\) 时，才真正生成所有 Gaussian 乘积。每个乘积都会给出一个 \((x,y)\)；之后再取绝对值、按大小排序、去掉零坐标、检查 \(x\equiv y\equiv 5\pmod 6\)，并把合格结果放进集合中去重。第一个精确计数超过 \(100\) 的 \(n\) 就给出目标五边形数 \(P_n\)。
对单个候选 \(n\) 来说，便宜的阶段是用预先准备好的素数表对 \(N_n\) 做试除分解。昂贵的阶段只在通过上界筛选后才发生，此时需要枚举 \(O\!\left(\prod(e_j+1)\right)\) 个 Gaussian 乘积，并在去重前使用同阶的临时存储。
总运行时间取决于搜索要推进到多远，才能第一次遇到表示数大于 \(100\) 的 \(n\)。在实际运行中，大多数候选都会很早被排除：很多候选不能被固定的素数表完全分解，另外很多即使被完全分解，也无法通过 \(\frac12\prod(e_j+1)>100\) 这个门槛。正是这种“先便宜过滤，再少量精确计数”的结构让整体搜索保持可行。
Нужно найти первое пятиугольное число \(P_n=\frac{n(3n-1)}{2}\), которое имеет более 100 представлений вида
$$P_n=P_a+P_b,\qquad a\ge b\ge 1.$$
Подсчёт ведётся по неупорядоченным парам, поэтому \((a,b)\) и \((b,a)\) считаются одним и тем же разложением. Реализации на C++, Python и Java не перебирают пары \((a,b)\) напрямую, а сводят задачу к подсчёту представлений числа как суммы двух квадратов с дополнительным сравнением по модулю \(6\).
Ключевая тождественная формула такова:
$$24P_t+1=(6t-1)^2.$$
Благодаря ей задача о пятиугольных числах превращается в задачу о структуре квадратов и простых множителей.
Если \(P_a+P_b=P_n\), то
$$24P_a+24P_b+2=24P_n+2,$$
а значит,
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
Введём обозначения
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1.$$
Тогда каждое разложение пятиугольного числа соответствует представлению
$$x^2+y^2=N_n$$
при условиях
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
Обратно, любой положительный неупорядоченный набор \((x,y)\), удовлетворяющий этим сравнениям, однозначно даёт
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
Следовательно, задача сводится к точному подсчёту неупорядоченных положительных представлений числа \(N_n\) в виде суммы двух квадратов, у которых обе координаты сравнимы с \(5\) по модулю \(6\).
Пишем
$$N_n=k^2+1,\qquad k=6n-1.$$
Если нечётное простое \(q\) делит \(N_n\), то
$$k^2\equiv -1\pmod q.$$
Значит, \(-1\) является квадратичным вычетом по модулю \(q\), а это возможно только при
$$q\equiv 1\pmod 4.$$
Кроме того, \(k\) нечётно, поэтому \(k^2\equiv 1\pmod 8\), откуда
$$N_n=k^2+1\equiv 2\pmod 8.$$
Следовательно, простое число \(2\) входит ровно в первой степени. Значит, любой полностью факторизованный кандидат имеет вид
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
Именно в такой ситуации удобно использовать гауссовы целые числа для параметризации всех представлений как суммы двух квадратов.
Для каждого нечётного простого \(p_i\equiv 1\pmod 4\) можно выбрать положительные целые \(u_i,v_i\) такие, что
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
Обозначим \(\pi_i=u_i+iv_i\). Так как
$$2=(1+i)(1-i),$$
получаем разложение
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
Теперь для каждого \(i\) выбираем число \(s_i\) в диапазоне \(0\le s_i\le e_i\) и строим
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}.$$
Его норма равна
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
Если записать \(z=x+iy\), то автоматически выполняется
$$x^2+y^2=N_n.$$
Именно такие распределения показателей и перебирают реализации. Вклад разных простых множителей независим, поэтому полный сырой перебор для одного кандидата имеет мультипликативную структуру по показателям \(e_i\).
Не всякое представление \(N_n=x^2+y^2\) даёт допустимые \(a\) и \(b\). Необходимо условие
$$x\equiv y\equiv 5\pmod 6,$$
и обе координаты должны быть положительными. Изменение знаков и перестановка координат не создают нового разложения \(P_n=P_a+P_b\), поэтому каждое представление приводится к канонической паре
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr).$$
Пары с нулевой координатой отбрасываются, после чего остаются только различные пары, проходящие модульный фильтр по \(6\). Каждая такая пара соответствует ровно одному решению \((a,b)\) с \(a\ge b\).
Если
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
то гауссова конструкция до удаления дублей создаёт
$$2\prod_{i=1}^{r}(e_i+1)$$
ориентированных и знаковых произведений, или эквивалентно \(\prod(e_i+1)\) исходных вариантов, если включить степень простого \(2\) в общую таблицу показателей. Сопряжённые выборы всегда переходят в одну и ту же неупорядоченную пару абсолютных значений, поэтому число действительно релевантных неупорядоченных кандидатов не превосходит
$$\frac{1}{2}\prod_{j}(e_j+1),$$
где произведение идёт по всем простым показателям, включая показатель \(1\) у числа \(2\). Если эта оценка не больше \(100\), текущий \(n\) заведомо не подходит, и дорогой точный перебор можно пропустить.
Для \(n=49\)
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
а также
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
Быстрая оценка даёт
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
поэтому точный перебор нужен. После построения всех гауссовых произведений, удаления дублей по знаку и порядку и применения условия \(x\equiv y\equiv 5\pmod 6\) остаются ровно пары
$$ (x,y)=(287,59)\quad\text{и}\quad (281,83). $$
Они дают
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
Следовательно,
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
то есть у \(P_{49}\) ровно два допустимых представления.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала строится таблица небольших простых чисел и для каждого простого \(p\equiv 1\pmod 4\) из этой таблицы запоминается одно разложение \(p=u^2+v^2\). Затем программы перебирают \(n=1,2,3,\dots\), вычисляют \(N_n=(6n-1)^2+1\) и раскладывают это число пробным делением по предвычисленным простым. Если после деления остаётся ненулевой кофактор, кандидат пропускается; если нет, полный список показателей уже известен.
Далее сначала вычисляется верхняя оценка \(\frac12\prod(e_j+1)\). Только если она может превысить \(100\), реализация явно строит все гауссовы произведения, отвечающие распределениям показателей. Каждое произведение даёт пару \((x,y)\); потом берутся абсолютные значения, координаты упорядочиваются, нулевые координаты удаляются, проверяется условие \(x\equiv y\equiv 5\pmod 6\), а выжившие пары помещаются в множество. Первое \(n\), для которого точный счёт становится больше \(100\), и даёт искомое пятиугольное число \(P_n\).
Для одного фиксированного кандидата \(n\) дешёвая стадия состоит в пробном делении числа \(N_n\) на простые из предвычисленной таблицы. Дорогая стадия, которая выполняется только после прохождения предварительной оценки, перебирает \(O\!\left(\prod(e_j+1)\right)\) гауссовых произведений и требует того же порядка временной памяти до удаления дублей.
Общее время работы зависит от того, насколько далеко нужно продвинуться по \(n\), прежде чем впервые встретится число с количеством представлений больше \(100\). На практике большинство кандидатов отсеивается рано: многие не раскладываются полностью фиксированной таблицей простых, а многие из тех, что раскладываются, не проходят условие \(\frac12\prod(e_j+1)>100\). Именно это сочетание дешёвого фильтра и редкого точного подсчёта делает поиск выполнимым.
نريد إيجاد أول عدد خماسي \(P_n=\frac{n(3n-1)}{2}\) يملك أكثر من 100 تمثيل من الصورة
$$P_n=P_a+P_b,\qquad a\ge b\ge 1.$$
يُحسب العدد بحسب الأزواج غير المرتبة، لذلك لا يُحسب الزوجان \((a,b)\) و\((b,a)\) إلا مرة واحدة. تطبيقات C++ وPython وJava لا تجرّب كل الأزواج مباشرة، بل تحوّل المسألة إلى عدّ تمثيلات على صورة مجموع مربعين مع شرط توافقي إضافي.
النقطة الأساسية هي الهوية
$$24P_t+1=(6t-1)^2.$$
هذه الهوية تنقلنا من أعداد خماسية إلى مسألة عددية منظّمة تعتمد على تحليل العوامل وتمثيلات مجموع مربعين.
إذا كان \(P_a+P_b=P_n\)، فإن
$$24P_a+24P_b+2=24P_n+2,$$
ومن ثم
$$(6a-1)^2+(6b-1)^2=(6n-1)^2+1.$$
لنعرّف
$$x=6a-1,\qquad y=6b-1,\qquad N_n=(6n-1)^2+1.$$
عندها يصبح كل تفكيك خماسي تمثيلاً من الشكل
$$x^2+y^2=N_n$$
مع القيود
$$x\equiv y\equiv 5\pmod 6,\qquad x\ge y\ge 5.$$
وبالعكس، كل زوج موجب غير مرتب \((x,y)\) يحقق هذه الشروط يعطينا بصورة وحيدة
$$a=\frac{x+1}{6},\qquad b=\frac{y+1}{6}.$$
إذن عدّ طرق كتابة \(P_n=P_a+P_b\) يساوي تماماً عدّ التمثيلات الموجبة غير المرتبة للعدد \(N_n\) كمجموع مربعين مع اشتراط أن يكون كل من \(x\) و\(y\) مكافئاً لـ \(5\) بترديد \(6\).
اكتب
$$N_n=k^2+1,\qquad k=6n-1.$$
إذا كان عدد أولي فردي \(q\) يقسم \(N_n\)، فلدينا
$$k^2\equiv -1\pmod q.$$
وهذا يعني أن \(-1\) بقايا تربيعية بترديد \(q\)، ولا يحدث ذلك إلا عندما
$$q\equiv 1\pmod 4.$$
كذلك \(k\) فردي، وبالتالي \(k^2\equiv 1\pmod 8\)، ومنه
$$N_n=k^2+1\equiv 2\pmod 8.$$
إذن العامل \(2\) يظهر مرة واحدة بالضبط. وبالتالي كل مرشح مفكك بالكامل يأخذ الصورة
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},\qquad p_i\equiv 1\pmod 4.$$
وهذه هي البيئة الطبيعية تماماً لاستخدام الأعداد الغاوسية في توليد جميع تمثيلات مجموع مربعين.
لكل عامل أولي فردي \(p_i\equiv 1\pmod 4\) نختار عددين صحيحين موجبين \(u_i,v_i\) بحيث
$$p_i=u_i^2+v_i^2=(u_i+iv_i)(u_i-iv_i).$$
ولنكتب \(\pi_i=u_i+iv_i\). وبما أن
$$2=(1+i)(1-i),$$
فإن
$$N_n=(1+i)(1-i)\prod_{i=1}^{r}\pi_i^{e_i}\overline{\pi_i}^{\,e_i}.$$
الآن نختار لكل \(i\) عدداً صحيحاً \(s_i\) بحيث \(0\le s_i\le e_i\)، ثم نكوّن
$$z=(1+i)\prod_{i=1}^{r}\pi_i^{s_i}\overline{\pi_i}^{\,e_i-s_i}.$$
وعندئذ تكون معياره
$$\mathcal{N}(z)=z\overline{z}=N_n.$$
إذا كتبنا \(z=x+iy\)، حصلنا مباشرة على
$$x^2+y^2=N_n.$$
هذا هو بالضبط ما تعدّده التطبيقات: توزيع الأسس بين العامل الغاوسي ومرافقه، ثم ضرب المساهمات القادمة من العوامل الأولية المختلفة. وبما أن كل عامل أولي يساهم بصورة مستقلة، يصبح حجم الفضاء الخام مضروباً في حدود الأسس \(e_i\).
ليس كل تمثيل للعدد \(N_n\) على صورة \(x^2+y^2\) صالحاً للمسألة. لا بد من الشرط
$$x\equiv y\equiv 5\pmod 6,$$
كما يجب أن يكون كل من \(x\) و\(y\) موجباً. تغيير الإشارة أو تبديل الإحداثيين لا ينتج تمثيلاً جديداً للهوية \(P_n=P_a+P_b\)، لذلك تُحوَّل كل حالة إلى الزوج القياسي
$$\bigl(\max(|x|,|y|),\min(|x|,|y|)\bigr).$$
بعد ذلك تُحذف الأزواج التي تحوي صفراً، ثم لا يُحتفَظ إلا بالأزواج المختلفة التي تجتاز اختبار الترديد \(6\). وكل زوج متبقٍّ يطابق حلاً وحيداً \((a,b)\) مع \(a\ge b\).
إذا كان
$$N_n=2\prod_{i=1}^{r} p_i^{e_i},$$
فإن البنية الغاوسية السابقة تنتج قبل إزالة التكرار
$$2\prod_{i=1}^{r}(e_i+1)$$
من الضروب الموجّهة والموقّعة، أو بصورة مكافئة \(\prod(e_i+1)\) اختياراً خاماً إذا أُدرج أس \(2\) في القائمة نفسها. الاختيارات المترافقة تنتهي دائماً إلى الزوج نفسه بعد أخذ القيم المطلقة وإهمال الترتيب، لذا فإن عدد المرشحات غير المرتبة ذات الصلة لا يزيد على
$$\frac{1}{2}\prod_{j}(e_j+1),$$
حيث يشمل الجداء جميع الأسس الأولية، بما فيها الأس \(1\) للعدد \(2\). فإذا لم يتجاوز هذا الحد \(100\)، فلا يمكن أن يكون هذا \(n\) هو المطلوب، وتُتجنَّب مرحلة العدّ الدقيق المكلفة.
عندما \(n=49\)، نجد أن
$$P_{49}=\frac{49(3\cdot 49-1)}{2}=3577,$$
وكذلك
$$N_{49}=(6\cdot 49-1)^2+1=293^2+1=85850=2\cdot 5^2\cdot 17\cdot 101.$$
والحد الأعلى السريع يساوي
$$\frac{1}{2}(1+1)(2+1)(1+1)(1+1)=6,$$
ولذلك لا بد من التعداد الدقيق. بعد توليد جميع الضروب الغاوسية، وحذف التكرارات الناتجة عن الإشارات والترتيب، ثم فرض الشرط \(x\equiv y\equiv 5\pmod 6\)، يبقى الزوجان
$$ (x,y)=(287,59),\qquad (281,83). $$
وهما يعطيان
$$ (a,b)=\left(\frac{287+1}{6},\frac{59+1}{6}\right)=(48,10), $$
$$ (a,b)=\left(\frac{281+1}{6},\frac{83+1}{6}\right)=(47,14). $$
ومن ثم
$$P_{49}=P_{48}+P_{10}=P_{47}+P_{14},$$
أي إن \(P_{49}\) يملك تمثيلين صالحين بالضبط.
تتبع تطبيقات C++ وPython وJava المسار نفسه. تبدأ بتجهيز جدول للأعداد الأولية الصغيرة، ومع كل عدد أولي \(p\equiv 1\pmod 4\) في هذا الجدول تُخزَّن صورة واحدة من صور \(p=u^2+v^2\). بعد ذلك تُفحص القيم \(n=1,2,3,\dots\)، ويُحسب \(N_n=(6n-1)^2+1\)، ثم تُجرى قسمة تجريبية باستخدام الأعداد الأولية المحضّرة مسبقاً. إذا بقي عامل مرافق بعد القسمة، يُتجاوز هذا المرشح؛ وإذا اختفى الباقي، تصبح قائمة الأسس معروفة بالكامل.
بعد الحصول على التحليل، تحسب الشيفرة أولاً الحد \(\frac12\prod(e_j+1)\). وفقط إذا كان من الممكن أن يتجاوز \(100\)، تُبنى جميع الضروب الغاوسية الناتجة عن توزيع الأسس. كل ضرب يعطي زوجاً \((x,y)\)؛ ثم تؤخذ القيم المطلقة، وتُرتَّب الإحداثيات، وتُحذف الحالات ذات الإحداثي الصفري، ويُطبَّق الشرط \(x\equiv y\equiv 5\pmod 6\)، وتُجمع الأزواج الباقية في مجموعة لإزالة التكرار. أول قيمة \(n\) يكون فيها العدد الدقيق أكبر من \(100\) تعطي العدد الخماسي المطلوب \(P_n\).
بالنسبة إلى مرشح واحد \(n\)، فإن المرحلة الرخيصة هي تحليل \(N_n\) بالقسمة التجريبية على جدول أولي ثابت. أما المرحلة المكلفة، والتي لا تُنفَّذ إلا للمرشحين الذين يجتازون الحد الأعلى، فتعدّد \(O\!\left(\prod(e_j+1)\right)\) من الضروب الغاوسية وتحتاج إلى ذاكرة مؤقتة من الرتبة نفسها قبل إزالة التكرار.
أما الزمن الكلي فيعتمد على مدى التقدم المطلوب في البحث قبل العثور على أول قيمة يتجاوز فيها عدد التمثيلات \(100\). عملياً يُستبعد معظم المرشحين مبكراً: كثير منهم لا يُفكَّك بالكامل بواسطة جدول الأعداد الأولية الثابت، وكثير من المرشحين المفككين لا يحققون أصلاً المتباينة \(\frac12\prod(e_j+1)>100\). هذا الدمج بين ترشيح رخيص وعدّ دقيق متأخر هو ما يجعل البحث عملياً.