For a positive integer \(N\), let \(T(N)\) be the number of distinct positive integer Pythagorean triples \((a,b,c)\) with \(a^2+b^2=c^2\) in which \(N\) appears as one of the three side lengths, counting \((a,b,c)\) and \((b,a,c)\) as the same triple. The task is to find, for each target count \(10^k\) with \(1\le k\le 18\), the smallest \(N\) satisfying \(T(N)=10^k\), and then sum those minima modulo \(409120391\).
A direct search over triples or over candidate integers is infeasible. The solution instead derives a closed multiplicative formula for \(T(N)\), then inverts that formula by a constrained minimization over prime exponents.
Write the prime factorization of \(N\) as
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
Define the two odd products
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
It is also convenient to encode the power of \(2\) by
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
Distinct right triangles with hypotenuse \(N\) correspond to positive representations of \(N^2\) as a sum of two squares. A standard consequence of the sum-of-two-squares theorem is
$$r_2(N^2)=4A,$$
where \(r_2(m)\) counts ordered integer pairs \((x,y)\) satisfying \(x^2+y^2=m\).
Among these representations, four are degenerate: \((\pm N,0)\) and \((0,\pm N)\). Every genuine triangle is counted eight times because of sign choices and swapping the two legs. Therefore the number of distinct triangles having hypotenuse \(N\) is
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
Only primes congruent to \(1 \pmod{4}\) affect this count. Primes congruent to \(3 \pmod{4}\) and the factor \(2\) only appear as square contributions in \(N^2\), so they do not create additional representations.
If \(N\) is odd, every factorization \(N^2=st\) with \(s<t\) gives one triangle
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right),$$
so the number of such triangles is the number of unordered divisor pairs of \(N^2\):
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
If \(N\) is even, write \(N=2m\). Then every factorization \(m^2=st\) with \(s<t\) gives
$$\left(N,t-s,t+s\right),$$
hence
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
Using the factorization of \(N\), both cases collapse to one formula:
$$L(N)=\frac{uAR-1}{2}.$$
A number cannot be both a leg and the hypotenuse in the same right triangle, so the total occurrence count is simply
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
This is the key identity used by the solver. If we want exactly \(n\) occurrences, then after setting
$$s=n+1,$$
we must satisfy
$$s=\frac{A(uR+1)}{2}.$$
Since \(A\) is odd, every solution begins by choosing an odd divisor \(a\mid s\), forcing
$$uR=\frac{2s}{a}-1.$$
The right-hand side is again odd, so we split it once more as
$$u\cdot r=\frac{2s}{a}-1,$$
where \(u\) is either \(1\) or of the form \(2e_2-1\), and \(r\) must equal \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\).
The quantity \(A\) must be represented as a product of odd factors
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
and similarly
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
Once an odd factor is chosen, the exponent is fixed: \(\alpha=(f-1)/2\) or \(\beta=(g-1)/2\). So the inverse problem becomes: partition the required odd product into factors of the form \(2e+1\), then place those exponents on allowed primes.
To minimize \(N\), larger exponents must be assigned to smaller primes. Indeed, if \(p<q\) and \(x>y\), then
$$p^x q^y < p^y q^x.$$
Therefore the optimal partition in each residue class is searched in nonincreasing odd factors and assigned to the increasing primes of that class.
The actual minima can be enormous, so the implementations compare candidates using high-precision base-2 logarithms:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
Because the logarithm is strictly increasing, the candidate with smaller logarithmic value is exactly the smaller integer. Once the best exponent pattern is known, the final value is reconstructed modulo \(409120391\) by modular exponentiation.
We have \(15=3^1\cdot 5^1\), so
$$A=3,\qquad R=3,\qquad u=1.$$
The hypotenuse contribution is
$$H(15)=\frac{3-1}{2}=1,$$
coming from \((9,12,15)\).
The leg contribution is
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
coming from \((8,15,17)\), \((15,20,25)\), \((15,36,39)\), and \((15,112,113)\).
Therefore
$$T(15)=1+4=5.$$
So 15 is a valid witness for target count \(5\), and the implementations verify that it is the smallest such integer.
The C++, Python, and Java implementations first generate enough small primes in the residue classes \(1 \pmod{4}\) and \(3 \pmod{4}\). They also use fast 64-bit primality testing and factorization so that every odd divisor needed by the search can be generated and cached efficiently.
For a fixed odd product in one residue class, the implementation runs a memoized depth-first search over its odd divisors. Choosing one divisor corresponds to choosing one factor \(2e+1\), hence one prime exponent. The recursion enforces nonincreasing chosen factors, which avoids duplicate partitions and automatically places larger exponents on smaller primes.
For a target count \(n\), the implementation sets \(s=n+1\), enumerates odd divisors \(a\mid s\), computes the forced odd remainder \(2s/a-1\), and then tries every odd divisor of that remainder as the possible \(u\) attached to the power of \(2\). The remaining factor is solved in the \(3 \pmod{4}\) prime class, while \(a\) itself is solved in the \(1 \pmod{4}\) prime class. The best combined logarithmic score gives the smallest integer with exactly \(n\) occurrences.
Finally, the implementation evaluates this inverse solver for \(n=10,10^2,\dots,10^{18}\), reconstructs each minimum modulo \(409120391\), and sums those values modulo the same modulus.
The dominant cost comes from factoring the odd integers derived from \(n+1\) and enumerating their odd divisors. If \(\tau(m)\) denotes the divisor function, then each recursive optimization depends on the divisor structure of the relevant odd product rather than on the size of the final minimum itself. Memoization collapses repeated subproblems determined by the remaining product, the next prime slot, and the previously chosen odd factor.
For the concrete targets \(10^1,\dots,10^{18}\), the search trees stay manageable because every recursive step removes at least one odd factor \(2e+1\). In practice, runtime is dominated by Pollard-rho factorization plus divisor generation, while memory is dominated by cached divisor lists and memoized optimal subproblems.
Für eine positive ganze Zahl \(N\) sei \(T(N)\) die Anzahl verschiedener positiver pythagoreischer Tripel \((a,b,c)\) mit \(a^2+b^2=c^2\), in denen \(N\) als eine der drei Seitenlängen vorkommt; die beiden Katheten werden dabei nicht nach Reihenfolge unterschieden. Gesucht ist für jeden Zielwert \(10^k\) mit \(1\le k\le 18\) die kleinste Zahl \(N\) mit \(T(N)=10^k\), und anschließend die Summe dieser Minimalwerte modulo \(409120391\).
Eine direkte Suche über Tripel oder Kandidaten ist unbrauchbar. Die Lösung leitet stattdessen eine geschlossene multiplikative Formel für \(T(N)\) her und invertiert sie dann als Minimierungsproblem über Primexponenten.
Schreibe die Primfaktorzerlegung von \(N\) als
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
Definiere die beiden ungeraden Produkte
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
Außerdem kodieren wir die Zweierpotenz durch
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
Verschiedene rechtwinklige Dreiecke mit Hypotenuse \(N\) entsprechen positiven Darstellungen von \(N^2\) als Summe zweier Quadrate. Eine Standardfolge des Satzes über Summen zweier Quadrate ist
$$r_2(N^2)=4A,$$
wobei \(r_2(m)\) die geordneten ganzzahligen Paare \((x,y)\) mit \(x^2+y^2=m\) zählt.
Darunter sind vier degenerierte Darstellungen: \((\pm N,0)\) und \((0,\pm N)\). Jedes echte Dreieck wird wegen Vorzeichenwahl und Vertauschung der Katheten achtfach gezählt. Daher ist die Anzahl verschiedener Dreiecke mit Hypotenuse \(N\)
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
Nur Primzahlen \(1 \pmod{4}\) beeinflussen diese Anzahl. Primzahlen \(3 \pmod{4}\) und der Faktor \(2\) erscheinen in \(N^2\) nur als quadratische Beiträge und erzeugen keine neuen Darstellungen.
Ist \(N\) ungerade, so liefert jede Faktorisierung \(N^2=st\) mit \(s<t\) genau ein Dreieck
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
Die Anzahl solcher Dreiecke ist also die Anzahl ungeordneter Teilerpaare von \(N^2\):
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
Ist \(N\) gerade, schreibe \(N=2m\). Dann ergibt jede Faktorisierung \(m^2=st\) mit \(s<t\)
$$\left(N,t-s,t+s\right),$$
also
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
Mit der Primfaktorzerlegung von \(N\) fallen beide Fälle zu einer einzigen Formel zusammen:
$$L(N)=\frac{uAR-1}{2}.$$
Eine Zahl kann in demselben rechtwinkligen Dreieck nicht zugleich Kathete und Hypotenuse sein. Daher ist die gesamte Auftretenszahl einfach
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
Diese Identität ist der Kern des Lösers. Für genau \(n\) Vorkommen setzen wir
$$s=n+1,$$
und müssen dann erfüllen
$$s=\frac{A(uR+1)}{2}.$$
Da \(A\) ungerade ist, beginnt jede Lösung mit der Wahl eines ungeraden Teilers \(a\mid s\). Dann ist fest erzwungen
$$uR=\frac{2s}{a}-1.$$
Die rechte Seite ist wieder ungerade, also zerlegen wir noch einmal
$$u\cdot r=\frac{2s}{a}-1,$$
wobei \(u\) entweder \(1\) oder von der Form \(2e_2-1\) ist und \(r\) gleich \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\) sein muss.
Die Größe \(A\) muss als Produkt ungerader Faktoren dargestellt werden:
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
und analog
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
Ist ein ungerader Faktor gewählt, steht der Exponent sofort fest: \(\alpha=(f-1)/2\) bzw. \(\beta=(g-1)/2\). Das inverse Problem lautet also: zerlege das verlangte ungerade Produkt in Faktoren der Form \(2e+1\) und ordne diese Exponenten zulässigen Primzahlen zu.
Um \(N\) zu minimieren, müssen größere Exponenten auf kleinere Primzahlen gelegt werden. Denn für \(p<q\) und \(x>y\) gilt
$$p^x q^y < p^y q^x.$$
Daher wird in jeder Restklasse nach einer Zerlegung in nichtzunehmenden ungeraden Faktoren gesucht und diese dann den wachsenden Primzahlen dieser Klasse zugeordnet.
Die eigentlichen Minimalwerte können enorm groß sein. Deshalb vergleichen die Implementierungen Kandidaten über hochpräzise Zweierlogarithmen:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
Da der Logarithmus streng monoton ist, ist der Kandidat mit kleinerem Logarithmus exakt die kleinere ganze Zahl. Sobald das beste Exponentenmuster feststeht, wird der geforderte Wert modulo \(409120391\) per modularer Potenzierung rekonstruiert.
Es gilt \(15=3^1\cdot 5^1\), also
$$A=3,\qquad R=3,\qquad u=1.$$
Der Hypotenusenbeitrag ist
$$H(15)=\frac{3-1}{2}=1,$$
und stammt von \((9,12,15)\).
Der Kathetenbeitrag ist
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
und stammt von \((8,15,17)\), \((15,20,25)\), \((15,36,39)\) und \((15,112,113)\).
Damit folgt
$$T(15)=1+4=5.$$
Somit ist 15 ein gültiger Zeuge für den Zielwert \(5\), und die Implementierungen bestätigen, dass keine kleinere Zahl dieselbe Auftretenszahl besitzt.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst genügend kleine Primzahlen der Restklassen \(1 \pmod{4}\) und \(3 \pmod{4}\). Zusätzlich verwenden sie schnelle 64-Bit-Primzahltests und Faktorisierung, damit alle für die Suche benötigten ungeraden Teiler effizient erzeugt und zwischengespeichert werden können.
Für ein festes ungerades Produkt in einer Restklasse läuft anschließend eine memoisierten Tiefensuche über dessen ungerade Teiler. Jeder gewählte Teiler entspricht genau einem Faktor \(2e+1\) und damit genau einem Primexponenten. Die Rekursion erzwingt nichtzunehmende gewählte Faktoren, vermeidet so doppelte Zerlegungen und ordnet größere Exponenten automatisch kleineren Primzahlen zu.
Für einen Zielwert \(n\) setzt die Implementierung \(s=n+1\), durchläuft ungerade Teiler \(a\mid s\), berechnet den erzwungenen ungeraden Rest \(2s/a-1\) und probiert dann jeden ungeraden Teiler dieses Restes als möglichen Wert \(u\) für den Zweieranteil aus. Der verbleibende Faktor wird in der Primklasse \(3 \pmod{4}\) minimiert, während \(a\) selbst in der Primklasse \(1 \pmod{4}\) minimiert wird. Der beste kombinierte Logarithmus liefert die kleinste Zahl mit genau \(n\) Vorkommen.
Zum Schluss wird dieser inverse Löser für \(n=10,10^2,\dots,10^{18}\) ausgeführt, jeder Minimalwert modulo \(409120391\) rekonstruiert und alles modulo demselben Modul aufsummiert.
Die dominante Arbeit steckt im Faktorisieren der aus \(n+1\) abgeleiteten ungeraden Zahlen und im Erzeugen ihrer ungeraden Teiler. Bezeichnet \(\tau(m)\) die Teilerfunktion, dann hängt jede rekursive Optimierung von der Teilerstruktur des relevanten ungeraden Produkts ab und nicht direkt von der Größe des endgültigen Minimalwerts. Memoisierung fasst wiederholte Teilprobleme zusammen, die durch Restprodukt, nächste Primzahlposition und zuvor gewählten ungeraden Faktor bestimmt sind.
Für die konkreten Zielwerte \(10^1,\dots,10^{18}\) bleiben die Suchbäume überschaubar, weil jeder rekursive Schritt mindestens einen ungeraden Faktor \(2e+1\) entfernt. Praktisch wird die Laufzeit von Pollard-Rho-Faktorisierung und Teilererzeugung dominiert, der Speicherverbrauch von zwischengespeicherten Teilerlisten und memoisierten optimalen Teilproblemen.
Pozitif bir \(N\) tamsayısı için \(T(N)\), \(a^2+b^2=c^2\) koşulunu sağlayan ve \(N\)'nin üç kenardan biri olarak geçtiği farklı pozitif Pisagor üçlülerinin sayısı olsun; burada \((a,b,c)\) ile \((b,a,c)\) aynı üçlü sayılır. İstenen şey, \(1\le k\le 18\) için her \(10^k\) hedefi adına \(T(N)=10^k\) koşulunu sağlayan en küçük \(N\)'yi bulmak ve sonra bu minimumları \(409120391\) modunda toplamaktır.
Doğrudan üçlü üretmek ya da aday sayıları tek tek denemek pratik değildir. Çözüm bunun yerine önce \(T(N)\) için kapalı bir çarpımsal formül çıkarır, sonra bu formülü asal üsler üzerinde kısıtlı bir minimizasyon problemine dönüştürerek tersine çözer.
\(N\)'nin asal çarpanlara ayrılışını
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}$$
şeklinde yazalım. Şimdi iki tek çarpımı tanımlayalım:
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
Ayrıca 2'nin üssünü şu yardımcı ifade ile kodlamak uygundur:
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
Hipotenüsü \(N\) olan farklı dik üçgenler, \(N^2\)'nin iki kare toplamı olarak pozitif gösterimlerine karşılık gelir. İki kare toplamı teoreminin standart bir sonucu
$$r_2(N^2)=4A$$
eşitliğidir; burada \(r_2(m)\), \(x^2+y^2=m\) denklemini sağlayan sıralı tam sayı çiftlerini \((x,y)\) sayar.
Bu gösterimlerin dördü yozdur: \((\pm N,0)\) ve \((0,\pm N)\). Gerçek bir üçgen ise işaret değişimleri ve iki dik kenarın yer değiştirmesi nedeniyle sekiz kez sayılır. Dolayısıyla hipotenüsü \(N\) olan farklı üçgen sayısı
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}$$
olur. Bu sayımı yalnızca \(1 \pmod{4}\) sınıfındaki asallar etkiler. \(3 \pmod{4}\) sınıfındaki asallar ve 2 çarpanı, \(N^2\) içinde yalnızca kare biçiminde yer alır ve yeni gösterim üretmez.
\(N\) tek ise, \(N^2=st\) olacak şekilde \(s<t\) her çarpan ayrışımı bir üçlü verir:
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
Bu nedenle böyle üçlülerin sayısı, \(N^2\)'nin sırasız bölen çiftlerinin sayısıdır:
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
\(N\) çift ise \(N=2m\) yazalım. Bu kez \(m^2=st\) olacak şekilde \(s<t\) her ayrışım
$$\left(N,t-s,t+s\right)$$
üçlüsünü verir ve dolayısıyla
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1)$$
elde edilir. \(N\)'nin asal çarpanlara ayrılışı kullanıldığında bu iki durum tek bir formülde birleşir:
$$L(N)=\frac{uAR-1}{2}.$$
Bir sayı aynı dik üçgende hem dik kenar hem hipotenüs olamayacağı için toplam occurrence sayısı doğrudan
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1$$
olur. Çözücünün temel eşitliği budur. Tam olarak \(n\) occurrence istiyorsak
$$s=n+1$$
tanımını yapıp
$$s=\frac{A(uR+1)}{2}$$
koşulunu sağlamalıyız. \(A\) tek olduğundan her çözüm, \(a\mid s\) olacak bir tek bölen seçimiyle başlar ve bu seçim
$$uR=\frac{2s}{a}-1$$
değerini zorunlu kılar. Sağ taraf yine tek olduğu için bunu bir kez daha
$$u\cdot r=\frac{2s}{a}-1$$
şeklinde ayırırız; burada \(u\) ya 1'dir ya da \(2e_2-1\) biçimindedir, \(r\) ise \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\) olmalıdır.
\(A\) sayısı şu biçimde tek çarpanlara ayrılmalıdır:
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
ve benzer biçimde
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
Tek bir çarpan seçildiğinde üs artık sabittir: \(\alpha=(f-1)/2\) ve \(\beta=(g-1)/2\). Böylece ters problem, istenen tek çarpımı \(2e+1\) tipindeki parçalara bölmek ve bu üsleri izin verilen asallara dağıtmak haline gelir.
\(N\)'yi minimize etmek için daha büyük üsler daha küçük asal sayılara verilmelidir. Gerçekten \(p<q\) ve \(x>y\) için
$$p^x q^y < p^y q^x$$
olur. Bu yüzden her kalıntı sınıfında, azalmayan değil azalan tek çarpanlarla arama yapılır ve bunlar o sınıftaki artan asallara yerleştirilir.
Gerçek minimumlar çok büyük olabildiğinden uygulamalar adayları yüksek hassasiyetli taban-2 logaritmalarla karşılaştırır:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
Logaritma sıkı biçimde artan olduğundan, logaritması küçük olan aday tam olarak daha küçük tam sayıdır. En iyi üs deseni belirlendikten sonra sonuç \(409120391\) modunda modüler üs alma ile yeniden kurulur.
\(15=3^1\cdot 5^1\) olduğundan
$$A=3,\qquad R=3,\qquad u=1.$$
Hipotenüs katkısı
$$H(15)=\frac{3-1}{2}=1$$
olur; bu da \((9,12,15)\) üçlüsünden gelir.
Dik kenar katkısı ise
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4$$
olur; bunlar \((8,15,17)\), \((15,20,25)\), \((15,36,39)\) ve \((15,112,113)\) üçlüleridir.
Sonuç olarak
$$T(15)=1+4=5.$$
Yani 15, hedef occurrence sayısı \(5\) için geçerli bir örnektir ve uygulamalar bunun en küçüğü olduğunu doğrular.
C++, Python ve Java uygulamaları önce \(1 \pmod{4}\) ve \(3 \pmod{4}\) kalıntı sınıflarında yeterli sayıda küçük asal üretir. Ayrıca aramada gereken her tek bölenin verimli biçimde çıkarılabilmesi ve önbelleğe alınabilmesi için hızlı 64 bit asallık testi ve faktorizasyon kullanırlar.
Belirli bir kalıntı sınıfına ait sabit tek çarpım için, uygulama onun tek bölenleri üzerinde memoization destekli bir derinlik öncelikli arama yürütür. Seçilen her bölen tam olarak bir \(2e+1\) çarpanına, dolayısıyla bir asal üssüne karşılık gelir. Rekürsiyon seçilen çarpanların azalmayan değil azalan sırada olmasını zorlar; böylece aynı parçalanma iki kez üretilmez ve büyük üsler otomatik olarak küçük asallara gider.
Bir hedef \(n\) için uygulama \(s=n+1\) yazar, \(a\mid s\) olacak tek bölenleri dolaşır, zorunlu tek kalan \(2s/a-1\) değerini hesaplar ve bu kalanın her tek bölenini 2-adik katkıya ait olası \(u\) değeri olarak dener. Kalan çarpım \(3 \pmod{4}\) asal sınıfında çözülürken, \(a\) değeri \(1 \pmod{4}\) sınıfında çözülür. En iyi birleşik logaritmik skor, tam olarak \(n\) occurrence veren en küçük tam sayıyı verir.
Son olarak bu ters çözücü \(n=10,10^2,\dots,10^{18}\) için çalıştırılır, her minimum \(409120391\) modunda yeniden kurulur ve hepsi aynı mod altında toplanır.
Baskın maliyet, \(n+1\)'den türeyen tek sayıların çarpanlara ayrılması ve tek bölenlerinin üretilmesidir. \(\tau(m)\) bölen sayısı fonksiyonu olmak üzere, her özyinelemeli optimizasyonun maliyeti son minimumun büyüklüğünden çok ilgili tek çarpımın bölen yapısına bağlıdır. Memoization, kalan çarpım, sıradaki asal konumu ve son seçilen tek çarpan ile tanımlanan tekrar eden alt problemleri birleştirir.
Somut hedefler \(10^1,\dots,10^{18}\) için arama ağaçları yönetilebilir boyutta kalır; çünkü her özyinelemeli adım en az bir \(2e+1\) tipinde tek çarpan kaldırır. Pratikte süreyi Pollard-rho faktorizasyonu ve bölen üretimi, belleği ise önbelleğe alınmış bölen listeleri ile en iyi alt problem tabloları belirler.
Para un entero positivo \(N\), sea \(T(N)\) el número de ternas pitagóricas positivas distintas \((a,b,c)\) con \(a^2+b^2=c^2\) en las que \(N\) aparece como una de las tres longitudes, considerando \((a,b,c)\) y \((b,a,c)\) como la misma terna. La tarea consiste en encontrar, para cada objetivo \(10^k\) con \(1\le k\le 18\), el menor \(N\) que satisface \(T(N)=10^k\), y luego sumar esos mínimos módulo \(409120391\).
Una búsqueda directa sobre ternas o sobre enteros candidatos es inviable. La solución obtiene primero una fórmula multiplicativa cerrada para \(T(N)\) y después invierte esa fórmula mediante una minimización restringida sobre exponentes primos.
Escribamos la factorización prima de \(N\) como
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
Definimos los dos productos impares
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
También conviene codificar la potencia de \(2\) mediante
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
Las ternas rectángulas distintas con hipotenusa \(N\) corresponden a representaciones positivas de \(N^2\) como suma de dos cuadrados. Una consecuencia estándar del teorema de suma de dos cuadrados es
$$r_2(N^2)=4A,$$
donde \(r_2(m)\) cuenta los pares enteros ordenados \((x,y)\) tales que \(x^2+y^2=m\).
Entre esas representaciones hay cuatro degeneradas: \((\pm N,0)\) y \((0,\pm N)\). Cada triángulo genuino queda contado ocho veces por los cambios de signo y por intercambiar las dos piernas. Por tanto, el número de ternas distintas cuya hipotenusa es \(N\) vale
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
Sólo los primos congruentes con \(1 \pmod{4}\) influyen en este conteo. Los primos congruentes con \(3 \pmod{4}\) y el factor \(2\) aparecen en \(N^2\) sólo como contribuciones cuadradas y no generan nuevas representaciones.
Si \(N\) es impar, cada factorización \(N^2=st\) con \(s<t\) produce una terna
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
Así, el número de tales ternas es el número de pares no ordenados de divisores de \(N^2\):
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
Si \(N\) es par, escribimos \(N=2m\). Entonces cada factorización \(m^2=st\) con \(s<t\) produce
$$\left(N,t-s,t+s\right),$$
de modo que
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
Usando la factorización prima de \(N\), ambos casos se unifican en
$$L(N)=\frac{uAR-1}{2}.$$
Un número no puede ser a la vez cateto e hipotenusa dentro del mismo triángulo rectángulo, así que el número total de apariciones es simplemente
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
Ésta es la identidad central del algoritmo. Si queremos exactamente \(n\) apariciones, definimos
$$s=n+1,$$
y debemos cumplir
$$s=\frac{A(uR+1)}{2}.$$
Como \(A\) es impar, toda solución empieza eligiendo un divisor impar \(a\mid s\), lo que fuerza
$$uR=\frac{2s}{a}-1.$$
El lado derecho también es impar, así que lo volvemos a separar como
$$u\cdot r=\frac{2s}{a}-1,$$
donde \(u\) es o bien \(1\) o bien de la forma \(2e_2-1\), y \(r\) debe coincidir con \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\).
La cantidad \(A\) debe escribirse como producto de factores impares
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
y de forma análoga
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
Una vez elegido un factor impar, el exponente queda fijado: \(\alpha=(f-1)/2\) o \(\beta=(g-1)/2\). Por tanto, el problema inverso consiste en partir el producto impar deseado en factores de la forma \(2e+1\) y colocar esos exponentes en primos permitidos.
Para minimizar \(N\), los exponentes grandes deben ir sobre los primos más pequeños. En efecto, si \(p<q\) y \(x>y\), entonces
$$p^x q^y < p^y q^x.$$
Así, en cada clase residual se busca una partición en factores impares no crecientes y luego se asigna a los primos crecientes de esa clase.
Los mínimos reales pueden ser enormes, así que las implementaciones comparan candidatos mediante logaritmos en base 2 de alta precisión:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
Como el logaritmo es estrictamente creciente, el candidato con menor valor logarítmico es exactamente el entero más pequeño. Una vez fijado el mejor patrón de exponentes, el valor final se reconstruye módulo \(409120391\) usando exponenciación modular.
Tenemos \(15=3^1\cdot 5^1\), así que
$$A=3,\qquad R=3,\qquad u=1.$$
La contribución como hipotenusa es
$$H(15)=\frac{3-1}{2}=1,$$
proveniente de \((9,12,15)\).
La contribución como cateto es
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
proveniente de \((8,15,17)\), \((15,20,25)\), \((15,36,39)\) y \((15,112,113)\).
Por tanto,
$$T(15)=1+4=5.$$
Así, 15 es un testigo válido para el objetivo \(5\), y las implementaciones confirman que es el menor posible.
Las implementaciones en C++, Python y Java generan primero suficientes primos pequeños en las clases residuales \(1 \pmod{4}\) y \(3 \pmod{4}\). Además usan tests rápidos de primalidad en 64 bits y factorización para que todos los divisores impares necesarios en la búsqueda puedan obtenerse y almacenarse en caché con eficiencia.
Para un producto impar fijo dentro de una clase residual, la implementación ejecuta una búsqueda en profundidad con memoización sobre sus divisores impares. Elegir un divisor equivale a elegir un factor \(2e+1\), y por tanto un exponente primo. La recursión impone que los factores elegidos no aumenten, lo que evita particiones duplicadas y coloca automáticamente exponentes mayores en primos más pequeños.
Para un objetivo \(n\), la implementación fija \(s=n+1\), enumera divisores impares \(a\mid s\), calcula el resto impar forzado \(2s/a-1\) y luego prueba cada divisor impar de ese resto como posible valor \(u\) asociado a la potencia de \(2\). El factor restante se resuelve en la clase de primos \(3 \pmod{4}\), mientras que \(a\) se resuelve en la clase \(1 \pmod{4}\). La mejor puntuación logarítmica combinada da el entero más pequeño con exactamente \(n\) apariciones.
Por último, la implementación ejecuta este solucionador inverso para \(n=10,10^2,\dots,10^{18}\), reconstruye cada mínimo módulo \(409120391\) y suma todos esos valores bajo el mismo módulo.
El coste dominante proviene de factorizar los enteros impares derivados de \(n+1\) y enumerar sus divisores impares. Si \(\tau(m)\) denota la función número de divisores, cada optimización recursiva depende de la estructura de divisores del producto impar relevante, no del tamaño del mínimo final. La memoización colapsa subproblemas repetidos determinados por el producto restante, la siguiente posición prima y el último factor impar elegido.
Para los objetivos concretos \(10^1,\dots,10^{18}\), los árboles de búsqueda siguen siendo manejables porque cada paso recursivo elimina al menos un factor impar \(2e+1\). En la práctica, el tiempo está dominado por la factorización de Pollard-rho y por la generación de divisores, mientras que la memoria está dominada por las listas de divisores en caché y los subproblemas óptimos memoizados.
对一个正整数 \(N\)，记 \(T(N)\) 为满足 \(a^2+b^2=c^2\) 的不同正整数勾股三元组 \((a,b,c)\) 中，\(N\) 作为三条边之一出现的次数；其中 \((a,b,c)\) 与 \((b,a,c)\) 视为同一个三元组。题目要求：对每个目标值 \(10^k\)（\(1\le k\le 18\)），求出满足 \(T(N)=10^k\) 的最小 \(N\)，再把这些最小值按模 \(409120391\) 相加。
如果直接枚举三元组或者从小到大扫描候选整数，规模都会完全失控。可行的方法是先把 \(T(N)\) 推导成一个封闭的乘法公式，再把“给定出现次数反求最小 \(N\)”改写成一个关于素数指数的受限最优化问题。
把 \(N\) 的素因数分解写成
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
定义两个奇数乘积
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
同时，用下面的量把 2 的指数统一编码：
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
如果 \(N\) 是勾股三元组的斜边，那么问题就变成把 \(N^2\) 写成两个平方数之和。由两平方和定理的标准结论可知
$$r_2(N^2)=4A,$$
其中 \(r_2(m)\) 表示满足 \(x^2+y^2=m\) 的有序整数对 \((x,y)\) 的个数。
这些表示里有四个是退化的：\((\pm N,0)\) 和 \((0,\pm N)\)。除去退化情形后，每一个真正的直角三角形还会因为两条直角边交换顺序以及符号变化而被计数 8 次。因此，斜边为 \(N\) 的不同三元组个数是
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
这个数量只受 \(1 \pmod{4}\) 类素数影响。因为 \(3 \pmod{4}\) 类素数和因子 2 在 \(N^2\) 中只以平方的形式出现，不会额外产生新的两平方和表示。
当 \(N\) 为奇数时，每个满足 \(N^2=st\) 且 \(s<t\) 的因子分解都会给出一个三元组
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
所以这类三元组的个数就是 \(N^2\) 的无序因子对个数：
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
当 \(N\) 为偶数时，写成 \(N=2m\)。这时每个满足 \(m^2=st\) 且 \(s<t\) 的分解都会给出
$$\left(N,t-s,t+s\right),$$
因此
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
把 \(N\) 的素因数分解代入后，这两个情形可以统一写成
$$L(N)=\frac{uAR-1}{2}.$$
一个数不可能在同一个直角三角形里既是直角边又是斜边，因此总出现次数就是两部分直接相加：
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
这是整个求解器的核心恒等式。若目标是恰好出现 \(n\) 次，定义
$$s=n+1,$$
则必须满足
$$s=\frac{A(uR+1)}{2}.$$
由于 \(A\) 一定是奇数，所以任意解都可以从选择一个奇因子 \(a\mid s\) 开始，然后被迫满足
$$uR=\frac{2s}{a}-1.$$
右边仍然是奇数，于是再拆成
$$u\cdot r=\frac{2s}{a}-1,$$
其中 \(u\) 要么等于 1，要么必须是 \(2e_2-1\) 的形式；而 \(r\) 必须等于 \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\)。
量 \(A\) 必须分解成若干奇因子
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
而同理
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
一旦选定某个奇因子，对应指数就立刻确定为 \(\alpha=(f-1)/2\) 或 \(\beta=(g-1)/2\)。因此逆问题实际上变成：把目标奇数乘积拆成若干个 \(2e+1\) 形式的因子，再把这些指数放到允许的素数上。
为了使 \(N\) 最小，大指数必须分配给更小的素数。因为当 \(p<q\) 且 \(x>y\) 时，有
$$p^x q^y < p^y q^x.$$
所以在每个模 \(4\) 的剩余类里，最优搜索都可以限制为“按不增顺序选择奇因子，再按从小到大的素数顺序分配”。
真正的最小值可能极大，直接比较大整数并不方便。因此实现用高精度的二进制对数来比较候选项：
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
因为对数函数严格单调，谁的对数更小，谁对应的整数就更小。确定最优指数模式之后，再通过模幂运算把结果恢复成模 \(409120391\) 下的值。
有 \(15=3^1\cdot 5^1\)，因此
$$A=3,\qquad R=3,\qquad u=1.$$
它作为斜边的贡献为
$$H(15)=\frac{3-1}{2}=1,$$
对应三元组 \((9,12,15)\)。
它作为直角边的贡献为
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
对应 \((8,15,17)\)、\((15,20,25)\)、\((15,36,39)\) 和 \((15,112,113)\)。
因此
$$T(15)=1+4=5.$$
所以 15 确实对应目标次数 5，而且实现也验证了它是满足该条件的最小整数。
C++、Python 和 Java 实现首先生成足够多的 \(1 \pmod{4}\) 与 \(3 \pmod{4}\) 类小素数。同时，它们使用快速的 64 位素性测试和整数分解方法，以便把搜索过程中需要的所有奇因子高效地列举出来并缓存。
对于某个固定的奇数乘积，实现会在对应剩余类内对它的奇因子执行带记忆化的深度优先搜索。每选中一个因子，就等价于选中了一个 \(2e+1\) 因子，也就确定了一个素数指数。递归强制这些选中的奇因子按不增顺序出现，这样既避免重复分拆，也自动把较大的指数放到较小的素数上。
对于目标次数 \(n\)，实现先设 \(s=n+1\)，枚举所有奇因子 \(a\mid s\)，计算被强制得到的奇数余量 \(2s/a-1\)，然后把这个余量的每个奇因子都尝试为与 2 的幂相关的候选 \(u\)。剩下的部分在 \(3 \pmod{4}\) 素数类中求最优，而 \(a\) 本身在 \(1 \pmod{4}\) 素数类中求最优。最终，总对数值最小的组合就是恰好出现 \(n\) 次时的最小整数。
最后，实现对 \(n=10,10^2,\dots,10^{18}\) 逐一调用这个逆向求解器，把每个最小值恢复为模 \(409120391\) 下的结果，再在同一模数下求和。
主要开销来自对由 \(n+1\) 推出的奇数进行分解，并枚举它们的奇因子。若用 \(\tau(m)\) 表示约数个数函数，那么每次递归优化的成本取决于相关奇数乘积的约数结构，而不是最终最小整数本身有多大。记忆化会把由“剩余乘积、下一个素数位置、上一次选取的奇因子”确定的重复子问题合并起来。
对于具体的目标 \(10^1,\dots,10^{18}\)，搜索树之所以仍然可控，是因为每一步递归至少都会去掉一个 \(2e+1\) 型奇因子。实际运行时，时间主要耗在 Pollard-rho 分解和约数枚举上，内存主要耗在约数缓存以及最优子问题的记忆化表上。
Для положительного целого \(N\) обозначим через \(T(N)\) число различных положительных пифагоровых троек \((a,b,c)\), удовлетворяющих \(a^2+b^2=c^2\), в которых \(N\) встречается как одна из трёх сторон; при этом \((a,b,c)\) и \((b,a,c)\) считаются одной и той же тройкой. Требуется для каждого целевого значения \(10^k\), где \(1\le k\le 18\), найти наименьшее \(N\), для которого \(T(N)=10^k\), а затем сложить все эти минимумы по модулю \(409120391\).
Прямой перебор троек или последовательная проверка кандидатов нереалистичны. Поэтому решение сначала выводит замкнутую мультипликативную формулу для \(T(N)\), а затем обращает её, сводя задачу к минимизации по показателям простых.
Запишем разложение \(N\) на простые множители в виде
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
Определим два нечётных произведения
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
Степень двойки удобно кодировать величиной
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
Различные прямоугольные треугольники с гипотенузой \(N\) соответствуют положительным представлениям числа \(N^2\) в виде суммы двух квадратов. Стандартное следствие теоремы о сумме двух квадратов даёт
$$r_2(N^2)=4A,$$
где \(r_2(m)\) считает упорядоченные целочисленные пары \((x,y)\), удовлетворяющие \(x^2+y^2=m\).
Среди них четыре представления вырожденные: \((\pm N,0)\) и \((0,\pm N)\). Каждый настоящий треугольник учитывается восемь раз из-за смены знаков и перестановки катетов. Поэтому число различных троек с гипотенузой \(N\) равно
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
На этот счёт влияют только простые числа \(1 \pmod{4}\). Простые \(3 \pmod{4}\) и множитель \(2\) входят в \(N^2\) только через квадраты и не создают новых представлений.
Если \(N\) нечётно, то каждое разложение \(N^2=st\) при \(s<t\) задаёт тройку
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
Значит, число таких троек равно числу неупорядоченных пар делителей числа \(N^2\):
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
Если \(N\) чётно, пишем \(N=2m\). Тогда каждое разложение \(m^2=st\) при \(s<t\) порождает
$$\left(N,t-s,t+s\right),$$
поэтому
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
После подстановки разложения \(N\) оба случая объединяются в одну формулу:
$$L(N)=\frac{uAR-1}{2}.$$
Одно и то же число не может быть одновременно катетом и гипотенузой в одном и том же прямоугольном треугольнике, поэтому общее число вхождений равно
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
Это и есть ключевая формула решения. Если требуется ровно \(n\) вхождений, положим
$$s=n+1,$$
тогда должно выполняться
$$s=\frac{A(uR+1)}{2}.$$
Поскольку \(A\) нечётно, любое решение начинается с выбора нечётного делителя \(a\mid s\), после чего неизбежно
$$uR=\frac{2s}{a}-1.$$
Правая часть снова нечётна, поэтому мы ещё раз раскладываем её как
$$u\cdot r=\frac{2s}{a}-1,$$
где \(u\) либо равно \(1\), либо имеет вид \(2e_2-1\), а \(r\) должно совпадать с \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\).
Величина \(A\) должна быть представлена как произведение нечётных множителей
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
и аналогично
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
Как только выбран нечётный множитель, соответствующий показатель уже фиксирован: \(\alpha=(f-1)/2\) или \(\beta=(g-1)/2\). Значит, обратная задача сводится к разбиению нужного нечётного произведения на множители вида \(2e+1\) и размещению этих показателей на допустимых простых числах.
Чтобы минимизировать \(N\), большие показатели нужно ставить на меньшие простые. Действительно, если \(p<q\) и \(x>y\), то
$$p^x q^y < p^y q^x.$$
Поэтому в каждом классе вычетов поиск можно ограничить неувеличивающимися нечётными множителями, которые затем назначаются возрастающим простым этого класса.
Истинные минимумы могут быть огромными, поэтому реализации сравнивают кандидатов по высокоточным двоичным логарифмам:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
Так как логарифм строго возрастает, меньший логарифм означает строго меньшее целое число. После выбора лучшего набора показателей результат восстанавливается по модулю \(409120391\) с помощью быстрого возведения в степень по модулю.
Имеем \(15=3^1\cdot 5^1\), следовательно
$$A=3,\qquad R=3,\qquad u=1.$$
Вклад в качестве гипотенузы равен
$$H(15)=\frac{3-1}{2}=1,$$
что соответствует тройке \((9,12,15)\).
Вклад в качестве катета равен
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
что соответствует \((8,15,17)\), \((15,20,25)\), \((15,36,39)\) и \((15,112,113)\).
Следовательно,
$$T(15)=1+4=5.$$
Значит, 15 действительно является примером для целевого значения \(5\), и реализации подтверждают, что меньшего подходящего числа нет.
Реализации на C++, Python и Java сначала генерируют достаточное количество малых простых чисел в классах вычетов \(1 \pmod{4}\) и \(3 \pmod{4}\). Кроме того, они используют быстрые 64-битные тесты на простоту и факторизацию, чтобы все нужные нечётные делители в ходе поиска строились эффективно и переиспользовались через кэш.
Для фиксированного нечётного произведения внутри одного класса вычетов реализация запускает мемоизированный поиск в глубину по нечётным делителям этого произведения. Выбор одного делителя означает выбор одного множителя \(2e+1\), а значит, и одного показателя простого числа. Рекурсия требует, чтобы выбираемые множители не возрастали, тем самым исключая дубликаты разбиений и автоматически сопоставляя большие показатели меньшим простым.
Для целевого значения \(n\) реализация кладёт \(s=n+1\), перебирает нечётные делители \(a\mid s\), вычисляет вынужденный нечётный остаток \(2s/a-1\), а затем пробует каждый нечётный делитель этого остатка как возможное значение \(u\), связанное со степенью двойки. Оставшаяся часть оптимизируется в классе простых \(3 \pmod{4}\), тогда как \(a\) оптимизируется в классе \(1 \pmod{4}\). Лучшая суммарная логарифмическая оценка даёт минимальное число с ровно \(n\) вхождениями.
В конце реализации применяют этот обратный решатель к \(n=10,10^2,\dots,10^{18}\), восстанавливают каждый минимум по модулю \(409120391\) и суммируют всё по тому же модулю.
Основная стоимость связана с факторизацией нечётных чисел, получаемых из \(n+1\), и с перечислением их нечётных делителей. Если \(\tau(m)\) обозначает функцию числа делителей, то каждая рекурсивная оптимизация определяется структурой делителей соответствующего нечётного произведения, а не величиной конечного минимума. Мемоизация схлопывает повторяющиеся подзадачи, определяемые оставшимся произведением, позицией следующего простого и ранее выбранным нечётным множителем.
Для конкретных целей \(10^1,\dots,10^{18}\) деревья поиска остаются умеренными, потому что каждый рекурсивный шаг удаляет как минимум один нечётный множитель вида \(2e+1\). На практике время в основном тратится на факторизацию Pollard-rho и перечисление делителей, а память — на кэши списков делителей и оптимальных подзадач.
لعدد صحيح موجب \(N\)، نرمز بـ \(T(N)\) إلى عدد الثلاثيات الفيثاغورية الموجبة المختلفة \((a,b,c)\) التي تحقق \(a^2+b^2=c^2\) ويظهر فيها \(N\) كأحد الأضلاع الثلاثة، مع اعتبار \((a,b,c)\) و\((b,a,c)\) ثلاثية واحدة. المطلوب هو إيجاد أصغر \(N\) يحقق \(T(N)=10^k\) لكل \(10^k\) حيث \(1\le k\le 18\)، ثم جمع هذه القيم الدنيا بترديد \(409120391\).
العدّ المباشر للثلاثيات أو تجربة الأعداد المرشحة واحدًا واحدًا غير عملي تمامًا. لذلك يعتمد الحل على اشتقاق صيغة ضربيّة مغلقة لـ \(T(N)\)، ثم عكس هذه الصيغة عبر مسألة تصغير مقيّدة على أسس الأعداد الأولية.
نكتب التحليل الأولي للعدد \(N\) على الصورة
$$N=2^{e_2}\prod_{p\equiv 1 \pmod{4}} p^{\alpha_p}\prod_{q\equiv 3 \pmod{4}} q^{\beta_q}.$$
ونعرّف حاصلَي الضرب الفرديين
$$A=\prod_{p\equiv 1 \pmod{4}} (2\alpha_p+1),\qquad R=\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1).$$
كما أنّه من الملائم ترميز أسّ العدد 2 بالكمية
$$u=\begin{cases} 1,& e_2=0,\\ 2e_2-1,& e_2\ge 1. \end{cases}$$
الثلاثيات القائمة المختلفة ذات الوتر \(N\) تقابل التمثيلات الموجبة للعدد \(N^2\) على شكل مجموع مربعين. ومن النتائج القياسية لمبرهنة مجموع مربعين أنّ
$$r_2(N^2)=4A,$$
حيث \(r_2(m)\) يعدّ الأزواج الصحيحة المرتبة \((x,y)\) التي تحقق \(x^2+y^2=m\).
ضمن هذه التمثيلات توجد أربع حالات منحلة هي \((\pm N,0)\) و\((0,\pm N)\). أمّا كل مثلث قائم حقيقي فيُحسب ثماني مرات بسبب تبديل الإشارات وتبادل الضلعين القائمين. لذلك فإن عدد الثلاثيات المختلفة التي يكون فيها \(N\) وترًا يساوي
$$H(N)=\frac{r_2(N^2)-4}{8}=\frac{A-1}{2}.$$
هذا الجزء لا يتأثر إلا بالأعداد الأولية الموافقة لـ \(1 \pmod{4}\). أمّا الأوليات الموافقة لـ \(3 \pmod{4}\) والعامل 2 فلا تضيف تمثيلات جديدة، لأنها تدخل في \(N^2\) فقط على شكل مربعات.
إذا كان \(N\) فرديًا، فإن كل تحليل \(N^2=st\) مع \(s<t\) يعطي مثلثًا واحدًا:
$$\left(N,\frac{t-s}{2},\frac{t+s}{2}\right).$$
إذًا عدد هذه الثلاثيات يساوي عدد أزواج القواسم غير المرتبة للعدد \(N^2\):
$$L(N)=\frac{d(N^2)-1}{2}\qquad (e_2=0).$$
أما إذا كان \(N\) زوجيًا، فنكتب \(N=2m\). عندئذ يعطي كل تحليل \(m^2=st\) مع \(s<t\)
$$\left(N,t-s,t+s\right),$$
ومن ثم
$$L(N)=\frac{d(m^2)-1}{2}=\frac{d\!\left((N/2)^2\right)-1}{2}\qquad (e_2\ge 1).$$
وباستخدام التحليل الأولي لـ \(N\)، يمكن توحيد الحالتين في الصيغة
$$L(N)=\frac{uAR-1}{2}.$$
لا يمكن للعدد نفسه أن يكون وترًا وضلعًا قائمًا في المثلث القائم نفسه، لذلك فإن عدد مرات الظهور الكلي هو ببساطة
$$T(N)=H(N)+L(N)=\frac{A(uR+1)}{2}-1.$$
وهذه هي الهوية الأساسية التي يعتمد عليها الحل. فإذا أردنا بالضبط \(n\) مرات ظهور، نضع
$$s=n+1,$$
وعندها يجب أن يتحقق
$$s=\frac{A(uR+1)}{2}.$$
وبما أن \(A\) فردي، فإن كل حل يبدأ باختيار قاسم فردي \(a\mid s\)، مما يفرض
$$uR=\frac{2s}{a}-1.$$
والطرف الأيمن فردي أيضًا، لذا نعيد تفكيكه على الصورة
$$u\cdot r=\frac{2s}{a}-1,$$
حيث يكون \(u\) إمّا 1 أو من الشكل \(2e_2-1\)، بينما يجب أن يساوي \(r\) المقدار \(\prod_{q\equiv 3 \pmod{4}} (2\beta_q+1)\).
يجب أن يُكتب \(A\) على هيئة حاصل ضرب عوامل فردية
$$A=\prod_i f_i,\qquad f_i=2\alpha_i+1,$$
وبالمثل
$$R=\prod_j g_j,\qquad g_j=2\beta_j+1.$$
بمجرد اختيار عامل فردي، يصبح الأس المقابل محددًا تمامًا: \(\alpha=(f-1)/2\) أو \(\beta=(g-1)/2\). وهكذا تتحول المسألة العكسية إلى تقسيم حاصل الضرب الفردي المطلوب إلى عوامل من الشكل \(2e+1\)، ثم وضع هذه الأسس على الأعداد الأولية المسموح بها.
ولكي نصغّر \(N\)، يجب إسناد الأسس الأكبر إلى الأعداد الأولية الأصغر. فمثلًا إذا كان \(p<q\) و\(x>y\)، فإن
$$p^x q^y < p^y q^x.$$
لذلك يمكن قصر البحث في كل فئة توافقية على عوامل فردية غير متزايدة، ثم إسنادها إلى الأعداد الأولية المتزايدة في تلك الفئة.
القيم الدنيا الحقيقية قد تكون ضخمة جدًا، لذلك تقارن التطبيقات بين المرشحين باستخدام لوغاريتمات ثنائية عالية الدقة:
$$\log_2 N=e_2+\sum_i \alpha_i\log_2 p_i+\sum_j \beta_j\log_2 q_j.$$
وبما أن اللوغاريتم دالة تزايدية تمامًا، فإن المرشح ذي القيمة اللوغاريتمية الأصغر هو العدد الصحيح الأصغر فعلًا. وبعد تحديد أفضل نمط للأسس، يُعاد بناء القيمة المطلوبة بترديد \(409120391\) باستعمال الأسّ المعياري.
لدينا \(15=3^1\cdot 5^1\)، ومن ثم
$$A=3,\qquad R=3,\qquad u=1.$$
مساهمة الوتر هي
$$H(15)=\frac{3-1}{2}=1,$$
وهي ناتجة من الثلاثية \((9,12,15)\).
أما مساهمة الضلع القائم فهي
$$L(15)=\frac{1\cdot 3\cdot 3-1}{2}=4,$$
وتأتي من \((8,15,17)\) و\((15,20,25)\) و\((15,36,39)\) و\((15,112,113)\).
إذًا
$$T(15)=1+4=5.$$
وعليه فإن 15 يحقق فعلًا هدف الظهور \(5\)، كما تؤكد التطبيقات أنه أصغر عدد يحقق ذلك.
تقوم تطبيقات C++ وPython وJava أولًا بتوليد عدد كافٍ من الأعداد الأولية الصغيرة في الفئتين \(1 \pmod{4}\) و\(3 \pmod{4}\). كما تستخدم اختبارات أولية سريعة على 64 بت وخوارزميات تحليل إلى عوامل أولية حتى يمكن توليد كل القواسم الفردية اللازمة أثناء البحث مع تخزينها مؤقتًا بكفاءة.
بالنسبة إلى حاصل ضرب فردي ثابت ضمن إحدى الفئتين، تنفّذ التطبيقات بحثًا عمقيًا مع حفظ النتائج السابقة على قواسمه الفردية. واختيار قاسم واحد يعادل اختيار عامل من الشكل \(2e+1\)، أي اختيار أس أولي واحد. وتفرض العودية أن تكون العوامل المختارة غير متزايدة، وهذا يمنع التكرار في التقسيمات ويضمن تلقائيًا أن تُسند الأسس الأكبر إلى الأعداد الأولية الأصغر.
ولقيمة هدف \(n\)، تضع التطبيقات \(s=n+1\)، وتعدّد القواسم الفردية \(a\mid s\)، ثم تحسب الباقي الفردي المفروض \(2s/a-1\)، وبعد ذلك تجرّب كل قاسم فردي لهذا الباقي بوصفه القيمة المحتملة \(u\) الخاصة بمساهمة قوة العدد 2. أما العامل المتبقي فيُحل في فئة الأوليات \(3 \pmod{4}\)، بينما يُحل \(a\) نفسه في فئة \(1 \pmod{4}\). وأفضل مجموع لوغاريتمي يعطي أصغر عدد يملك بالضبط \(n\) مرات ظهور.
وفي النهاية، تُطبّق هذه العملية العكسية على \(n=10,10^2,\dots,10^{18}\)، ثم يُعاد بناء كل قيمة دنيا بترديد \(409120391\)، وتُجمع كلها تحت الترديد نفسه.
الكلفة الأساسية تأتي من تحليل الأعداد الفردية المشتقة من \(n+1\) إلى عوامل أولية، ثم تعداد قواسمها الفردية. وإذا رمزنا إلى دالة عدد القواسم بـ \(\tau(m)\)، فإن تكلفة كل تحسين عودي تعتمد على بنية قواسم حاصل الضرب الفردي المعني، لا على حجم القيمة الدنيا النهائية نفسها. كما أن الحفظ المسبق يدمج المسائل الفرعية المتكررة التي يحددها حاصل الضرب المتبقي، وموضع العدد الأولي التالي، وآخر عامل فردي تم اختياره.
بالنسبة إلى الأهداف المحددة \(10^1,\dots,10^{18}\)، تبقى أشجار البحث قابلة للإدارة لأن كل خطوة عودية تزيل عاملًا فرديًا واحدًا على الأقل من الشكل \(2e+1\). عمليًا، يهيمن على الزمن تحليل Pollard-rho وتوليد القواسم، بينما تهيمن على الذاكرة قوائم القواسم المخزنة وجدوال أفضل المسائل الفرعية.