For a fixed positive integer cathetus \(n\), let \(T(n)\) be the number of distinct integer right triangles that use \(n\) as one leg. The task is to find the smallest \(n\) for which \(T(n)=47547\).
A brute-force search over candidate catheti would be completely impractical. The key observation is that each triangle can be encoded by a factor pair of a square, so the problem becomes an inverse divisor-count problem rather than a geometric search.
Write the triangle as \((a,n,c)\), where \(a\) is the other leg and \(c\) is the hypotenuse. The whole derivation comes from rewriting the Pythagorean equation in a form that exposes divisors of a square.
Starting from
$$a^2+n^2=c^2,$$
we rewrite it as
$$c^2-a^2=(c-a)(c+a)=n^2.$$
Now define
$$u=c-a,\qquad v=c+a.$$
Then \(u\) and \(v\) are positive integers with \(u<v\) and
$$uv=n^2.$$
Conversely, every factor pair \(u<v\) of \(n^2\) with the same parity produces
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
which are integers and therefore define a valid right triangle. So counting triangles with cathetus \(n\) is exactly the same as counting same-parity factor pairs of \(n^2\), excluding the central pair \(u=v\), which would give the degenerate case \(a=0\).
If \(n\) is odd, then \(n^2\) is odd, so every divisor pair of \(n^2\) is automatically odd-odd and therefore admissible. Because \(n^2\) is a square, it has an odd number of divisors, and one of them is the middle divisor \(\sqrt{n^2}=n\). Hence
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{when \(n\) is odd}.$$
If \(n\) is even, then \(u\) and \(v\) cannot both be odd because their product is even, so they must both be even. Write
$$u=2r,\qquad v=2s.$$
Then
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
and every factor pair \(r<s\) of \(\left(\frac{n}{2}\right)^2\) produces one triangle. Therefore
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{when \(n\) is even}.$$
It is convenient to introduce a reduced parameter \(m\): take \(m=n\) for odd \(n\), and \(m=n/2\) for even \(n\). Then both cases collapse to
$$T(n)=\frac{d(m^2)-1}{2}.$$
For the target value \(T(n)=47547\), the previous formula becomes
$$d(m^2)=2\cdot 47547+1=95095.$$
If
$$m=\prod_i p_i^{e_i},$$
then
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
So the inverse problem is: write \(95095\) as a product of odd integers, and interpret each factor \(f\) as an exponent contribution
$$e=\frac{f-1}{2}.$$
The implementations do not guess a single factorization. They enumerate every odd multiplicative partition of \(95095\) in nondecreasing order, so every valid exponent multiset is considered exactly once.
For this particular target,
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
but grouping some of these prime factors together is also allowed, because a term such as \(35\) would simply mean an exponent \((35-1)/2=17\) on one prime of \(m\).
Once a multiset of exponents is fixed, the smallest corresponding integer is obtained by assigning the largest exponent to the smallest available prime, the next-largest exponent to the next-smallest prime, and so on. The reason is the swap inequality
$$p^a q^b \le p^b q^a\qquad\text{for }p<q\text{ and }a\ge b.$$
That is why the implementations sort the exponent list in descending order before building a candidate.
The even case needs one extra remark. If \(n\) is even, then \(n=2m\). Suppose the exponent of \(2\) inside \(m\) is \(a\). Its contribution to \(d(m^2)\) is
$$2a+1.$$
The search therefore reserves one odd factor of \(95095\) for the power of \(2\), translates it to \(a=(f-1)/2\), and then the final cathetus receives the power
$$2^{a+1},$$
because \(n=2m\). All remaining odd factors are converted into exponents on \(3,5,7,\dots\).
This smaller target is useful because it is explicitly checked by the implementations. If \(T(n)=4\), then
$$d(m^2)=2\cdot 4+1=9.$$
For an odd cathetus, the only odd-factor partition is \(9\), which gives exponent \(4\) on one odd prime and leads to the candidate \(n=3^4=81\).
For an even cathetus, we can reserve a factor \(3\) for the power of \(2\). Then
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
and the remaining factor \(3\) gives exponent \(1\) on the odd prime \(3\). So
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
Indeed, \(\left(\frac{12}{2}\right)^2=36\) has the factor pairs
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$$
which correspond to the four triangles
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
The full target works the same way. After exploring every admissible odd multiplicative partition of \(95095\), the minimum cathetus is
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
The C++, Python, and Java implementations all follow the same mathematical pipeline. First they convert the target count into
$$2T+1=95095,$$
because that is the required value of \(d(m^2)\).
The main search is a recursion over odd multiplicative partitions. It generates factorizations in nondecreasing order, which prevents duplicate exponent multisets from appearing in different orders. One pass handles odd catheti, where the entire product \(95095\) is assigned to odd primes. A second pass handles even catheti by choosing one odd divisor to represent the contribution \(2a+1\) of the prime \(2\) inside \(m\), and then factorizing the remaining quotient among odd primes.
Each odd factor \(f\) becomes an exponent \((f-1)/2\). The resulting exponent list is sorted from large to small and attached to the primes \(3,5,7,\dots\), while the even branch contributes a leading power of \(2^{a+1}\). The implementations keep the smallest candidate seen so far.
The candidate integer can be very large, so the implementations build it with arbitrary-precision arithmetic in Python and Java, and with carefully capped 128-bit arithmetic in C++. The C++ version also includes small checkpoint tests: it verifies that a cathetus of \(12\) produces \(4\) triangles, that target count \(4\) has smallest solution \(12\), and that target count \(1\) has smallest solution \(3\).
Although the final solver never searches directly over catheti, the implementations also contain the direct divisor-count formula for \(T(n)\). That routine is useful for the checkpoints and makes the link between the derivation and the computed answer explicit.
Let \(P=2T+1\). The hard part is not scanning values of \(n\); it is enumerating all odd multiplicative partitions of \(P\) and, in the even branch, doing the same for quotients \(P/f\) where \(f\) is an odd divisor of \(P\). If \(\Pi(P)\) denotes the number of such partitions explored, the search cost is essentially proportional to \(\Pi(P)\), with only a short exponent list to sort for each candidate.
For the actual problem \(P=95095\), this search space is tiny. Memory usage is \(O(k)\) for a recursion stack and a current factor list of length \(k\), so the practical footprint is minimal. The algorithm is fast because it replaces an impossible brute-force search over catheti by a very small recursive search over divisor patterns.
Für eine feste positive Kathete \(n\) bezeichne \(T(n)\) die Anzahl verschiedener ganzzahliger rechtwinkliger Dreiecke, die \(n\) als eine Kathete besitzen. Gesucht ist das kleinste \(n\) mit \(T(n)=47547\).
Eine naive Suche über mögliche Katheten wäre völlig unpraktisch. Der entscheidende Gedanke ist, dass sich jedes solche Dreieck durch ein Teilerpaar eines Quadrats beschreiben lässt. Dadurch wird aus der geometrischen Aufgabe ein inverses Problem zur Teileranzahl.
Schreibe das Dreieck als \((a,n,c)\), wobei \(a\) die andere Kathete und \(c\) die Hypotenuse ist. Die gesamte Herleitung entsteht dadurch, dass man die pythagoreische Gleichung in eine Form mit Quadratteilern umschreibt.
Aus
$$a^2+n^2=c^2$$
wird
$$c^2-a^2=(c-a)(c+a)=n^2.$$
Definiere nun
$$u=c-a,\qquad v=c+a.$$
Dann sind \(u\) und \(v\) positive ganze Zahlen mit \(u<v\) und
$$uv=n^2.$$
Umgekehrt liefert jedes Teilerpaar \(u<v\) von \(n^2\) mit gleicher Parität die Werte
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
also wieder ein gültiges rechtwinkliges Dreieck. Das Zählen der Dreiecke mit Kathete \(n\) ist daher genau das Zählen gleichpariger Teilerpaare von \(n^2\), wobei das mittlere Paar \(u=v\) ausgeschlossen werden muss, weil es zum degenerierten Fall \(a=0\) führt.
Ist \(n\) ungerade, dann ist auch \(n^2\) ungerade. Jedes Teilerpaar von \(n^2\) ist also automatisch ungerade-ungerade und damit zulässig. Weil \(n^2\) ein Quadrat ist, besitzt es eine ungerade Anzahl von Teilern, darunter den mittleren Teiler \(\sqrt{n^2}=n\). Somit gilt
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{für ungerades \(n\)}.$$
Ist \(n\) gerade, dann können \(u\) und \(v\) nicht beide ungerade sein, denn ihr Produkt ist gerade. Also müssen beide gerade sein. Schreibe
$$u=2r,\qquad v=2s.$$
Dann folgt
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
und jedes Teilerpaar \(r<s\) von \(\left(\frac{n}{2}\right)^2\) erzeugt genau ein Dreieck. Daher
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{für gerades \(n\)}.$$
Es ist praktisch, einen reduzierten Parameter \(m\) einzuführen: für ungerades \(n\) setze \(m=n\), für gerades \(n\) setze \(m=n/2\). Dann fassen sich beide Fälle zu
$$T(n)=\frac{d(m^2)-1}{2}$$
zusammen.
Für den Zielwert \(T(n)=47547\) erhält man damit
$$d(m^2)=2\cdot 47547+1=95095.$$
Hat \(m\) die Primfaktorzerlegung
$$m=\prod_i p_i^{e_i},$$
dann gilt
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
Das inverse Problem lautet also: Schreibe \(95095\) als Produkt ungerader Zahlen und deute jeden Faktor \(f\) als Exponentenbeitrag
$$e=\frac{f-1}{2}.$$
Die Implementierungen raten dabei nicht eine einzelne Zerlegung. Sie erzeugen alle ungeraden multiplikativen Partitionen von \(95095\) in nicht fallender Reihenfolge, sodass jedes zulässige Exponenten-Multiset genau einmal vorkommt.
Für diese Aufgabe ist
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
aber man darf diese Primfaktoren auch zusammenfassen. Ein Faktor wie \(35\) bedeutet dann einfach einen Exponenten \((35-1)/2=17\) auf einer Primzahl von \(m\).
Ist das Exponenten-Multiset fest, dann erhält man die kleinste Zahl, indem man den größten Exponenten der kleinsten verfügbaren Primzahl zuordnet, den zweitgrößten der zweitkleinsten und so weiter. Der Grund ist die Tauschungleichung
$$p^a q^b \le p^b q^a\qquad\text{für }p<q\text{ und }a\ge b.$$
Deshalb sortieren die Implementierungen die Exponentenliste absteigend, bevor daraus ein Kandidat konstruiert wird.
Im geraden Fall kommt ein zusätzlicher Punkt hinzu. Ist \(n\) gerade, dann gilt \(n=2m\). Hat die Primzahl \(2\) in \(m\) den Exponenten \(a\), dann ist ihr Beitrag zu \(d(m^2)\)
$$2a+1.$$
Die Suche reserviert daher einen ungeraden Faktor von \(95095\) für die Zweierpotenz, setzt \(a=(f-1)/2\) und versieht die endgültige Kathete wegen \(n=2m\) mit dem Faktor
$$2^{a+1}.$$
Alle übrigen ungeraden Faktoren werden in Exponenten auf \(3,5,7,\dots\) umgewandelt.
Dieses kleinere Ziel ist nützlich, weil es in den Implementierungen ausdrücklich geprüft wird. Aus \(T(n)=4\) folgt
$$d(m^2)=2\cdot 4+1=9.$$
Für eine ungerade Kathete gibt es nur die ungerade Faktorpartition \(9\). Sie liefert den Exponenten \(4\) auf einer ungeraden Primzahl und damit den Kandidaten \(n=3^4=81\).
Für eine gerade Kathete kann man den Faktor \(3\) für die Zweierpotenz reservieren. Dann ist
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
und der verbleibende Faktor \(3\) liefert den Exponenten \(1\) auf der ungeraden Primzahl \(3\). Also
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
Tatsächlich besitzt \(\left(\frac{12}{2}\right)^2=36\) die Teilerpaare
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$$
die genau die vier Dreiecke
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13)$$
erzeugen. Beim eigentlichen Ziel funktioniert dieselbe Methode. Nach dem Durchlauf über alle zulässigen ungeraden multiplikativen Partitionen von \(95095\) ergibt sich
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
Die C++-, Python- und Java-Implementierungen folgen alle derselben mathematischen Pipeline. Zuerst wird die Zielanzahl in
$$2T+1=95095$$
umgerechnet, denn genau dieser Wert muss als \(d(m^2)\) erreicht werden.
Die eigentliche Suche ist eine Rekursion über ungerade multiplikative Partitionen. Die Faktoren werden in nicht fallender Reihenfolge erzeugt, sodass keine doppelten Exponenten-Multisets in anderer Reihenfolge auftauchen. Ein Durchlauf behandelt ungerade Katheten, bei denen das gesamte Produkt \(95095\) auf ungerade Primzahlen verteilt wird. Ein zweiter Durchlauf behandelt gerade Katheten, indem zunächst ein ungerader Teiler als Beitrag \(2a+1\) der Primzahl \(2\) in \(m\) gewählt und danach der verbleibende Quotient auf ungerade Primzahlen faktorisiert wird.
Jeder ungerade Faktor \(f\) wird in einen Exponenten \((f-1)/2\) übersetzt. Die Exponentenliste wird dann absteigend sortiert und den Primzahlen \(3,5,7,\dots\) zugeordnet, während der gerade Zweig vorne eine Potenz \(2^{a+1}\) erhält. Von allen gebauten Kandidaten bleibt nur der kleinste erhalten.
Der Kandidat kann sehr groß werden. Deshalb verwenden die Implementierungen in Python und Java beliebig große Ganzzahlen, während C++ mit vorsichtig begrenzter 128-Bit-Arithmetik arbeitet. Die C++-Version enthält außerdem kleine Prüffälle: Sie bestätigt, dass die Kathete \(12\) genau \(4\) Dreiecke liefert, dass für Zielanzahl \(4\) die kleinste Lösung \(12\) ist und dass für Zielanzahl \(1\) die kleinste Lösung \(3\) lautet.
Obwohl der eigentliche Löser nie direkt über Katheten iteriert, enthalten die Implementierungen auch die direkte Teilerformel für \(T(n)\). Diese wird für die Prüffälle benutzt und macht die Verbindung zwischen Herleitung und Ergebnis besonders transparent.
Sei \(P=2T+1\). Der Aufwand liegt nicht in einem Durchprobieren von \(n\), sondern im Erzeugen aller ungeraden multiplikativen Partitionen von \(P\) sowie im geraden Zweig zusätzlich der Partitionen der Quotienten \(P/f\), wobei \(f\) ein ungerader Teiler von \(P\) ist. Bezeichnet \(\Pi(P)\) die Zahl der tatsächlich besuchten Partitionen, dann ist die Laufzeit im Wesentlichen proportional zu \(\Pi(P)\); pro Kandidat muss nur eine kurze Exponentenliste sortiert werden.
Für die konkrete Aufgabe mit \(P=95095\) ist dieser Suchraum sehr klein. Der Speicherbedarf beträgt nur \(O(k)\) für Rekursionsstapel und aktuelle Faktorenliste der Länge \(k\). Praktisch ist das Verfahren deshalb schnell: Es ersetzt eine unbrauchbare brute-force-Suche über Katheten durch eine sehr kleine rekursive Suche über Teilermuster.
Sabit bir pozitif \(n\) dik kenarı için \(T(n)\), \(n\) kenarını paylaşan farklı tam sayılı dik üçgenlerin sayısı olsun. Amaç, \(T(n)=47547\) koşulunu sağlayan en küçük \(n\) değerini bulmaktır.
Doğrudan \(n\) değerlerini tek tek denemek pratik değildir. Asıl fikir, her üçgeni bir tam kare sayının bölen çiftiyle kodlayabilmektir. Böylece problem geometrik bir aramadan çıkıp ters yönde bir bölen sayısı problemine dönüşür.
Üçgeni \((a,n,c)\) biçiminde yazalım; burada \(a\) diğer dik kenar, \(c\) ise hipotenüstür. Tüm çözüm, Pisagor eşitliğini kare bir sayının bölenlerini açığa çıkaran bir forma dönüştürmeye dayanır.
$$a^2+n^2=c^2$$
eşitliğinden
$$c^2-a^2=(c-a)(c+a)=n^2$$
sonucunu elde ederiz. Şimdi
$$u=c-a,\qquad v=c+a$$
tanımlarını yapalım. Böylece \(u\) ve \(v\) pozitif tam sayılardır, \(u<v\) olur ve
$$uv=n^2$$
sağlanır. Ters yönde de, \(n^2\)'nin aynı parity'ye sahip her \(u<v\) bölen çifti
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2}$$
formülleriyle tam sayılı bir dik üçgen üretir. Dolayısıyla \(n\) dik kenarını paylaşan üçgenleri saymak, \(n^2\)'nin aynı parity'li bölen çiftlerini saymakla tamamen aynıdır. Burada \(u=v\) olan orta çift dışlanır; çünkü o durumda \(a=0\) olur ve üçgen bozulur.
\(n\) tek ise \(n^2\) de tektir. O zaman \(n^2\)'nin her bölen çifti otomatik olarak tek-tek olur ve uygun kabul edilir. \(n^2\) bir kare olduğu için bölen sayısı tektir ve ortadaki bölen \(\sqrt{n^2}=n\) olur. Bu yüzden
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{\(n\) tek olduğunda}.$$
\(n\) çift ise \(u\) ve \(v\) hem tek olamaz; çünkü çarpımları çifttir. Demek ki ikisi de çift olmak zorundadır. O halde
$$u=2r,\qquad v=2s$$
yazalım. Buradan
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2$$
elde edilir ve \(\left(\frac{n}{2}\right)^2\)'nin her \(r<s\) bölen çifti tam bir üçgen verir. Dolayısıyla
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{\(n\) çift olduğunda}.$$
Bu iki durumu tek bir formülde toplamak için indirgenmiş bir \(m\) parametresi tanımlamak uygundur: \(n\) tekse \(m=n\), \(n\) çiftse \(m=n/2\). Böylece
$$T(n)=\frac{d(m^2)-1}{2}$$
olur.
Aranan değer \(T(n)=47547\) olduğuna göre
$$d(m^2)=2\cdot 47547+1=95095$$
olmalıdır. Eğer
$$m=\prod_i p_i^{e_i}$$
ise
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1)$$
elde edilir. Yani ters problem şudur: \(95095\) sayısını tek çarpanların çarpımı olarak yaz ve her \(f\) çarpanını
$$e=\frac{f-1}{2}$$
üsüne dönüştür. Uygulamalar tek bir ayrışım tahmin etmez; \(95095\)'in tüm tek çarpımsal bölünmelerini küçükten büyüğe sıralı biçimde üretir. Böylece her geçerli üs çokluğu tam bir kez incelenir.
Bu problemde
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19$$
olsa da, bu asal çarpanları gruplayıp örneğin \(35\) gibi bir terim üretmek de serbesttir. Böyle bir terim, \(m\)'in bir asalında \((35-1)/2=17\) üssü anlamına gelir.
Bir üs çokluğu sabitlendiğinde, ortaya çıkan en küçük sayı en büyük üssü en küçük asala, ikinci büyük üssü ikinci küçük asala verince elde edilir. Bunun nedeni
$$p^a q^b \le p^b q^a\qquad\text{eğer }p<q\text{ ve }a\ge b$$
eşitsizliğidir. Bu yüzden uygulamalar aday oluştururken üs listesini büyükten küçüğe sıralar.
Çift durumda ek bir ayrıntı vardır. \(n\) çiftse \(n=2m\) yazılır. Diyelim ki \(m\) içinde \(2\) asalı \(a\) üssüyle bulunuyor. O zaman \(d(m^2)\) içindeki katkısı
$$2a+1$$
olur. Arama bu yüzden \(95095\)'in tek çarpanlarından birini \(2\)'nin katkısı için ayırır, \(a=(f-1)/2\) hesaplar ve son katete
$$2^{a+1}$$
çarpanını ekler; çünkü \(n=2m\). Kalan tek çarpanlar ise \(3,5,7,\dots\) asallarının üslerine dönüştürülür.
Bu küçük hedef özellikle yararlıdır; çünkü uygulamalarda açıkça kontrol edilir. Eğer \(T(n)=4\) ise
$$d(m^2)=2\cdot 4+1=9$$
olur. Tek katet durumunda tek çarpan bölünmesi yalnızca \(9\)'dur. Bu da tek bir tek asalda üs \(4\) verir ve aday \(n=3^4=81\) olur.
Çift katet durumunda \(3\) çarpanı \(2\)'nin katkısı için ayrılabilir. O zaman
$$2a+1=3\qquad\Longrightarrow\qquad a=1$$
ve geriye kalan \(3\) çarpanı \(3\) asalında üs \(1\) verir. Böylece
$$m=2^1\cdot 3^1=6,\qquad n=2m=12$$
elde edilir. Gerçekten de \(\left(\frac{12}{2}\right)^2=36\) sayısının
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9$$
bölen çiftleri tam olarak şu dört üçgeni üretir:
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
Asıl hedefte de aynı mekanizma çalışır. \(95095\)'in tüm uygun tek çarpımsal bölünmeleri tarandığında en küçük ortak dik kenar
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000$$
olarak bulunur.
C++, Python ve Java uygulamalarının üçü de aynı matematiksel akışı izler. Önce hedef sayı
$$2T+1=95095$$
değerine çevrilir; çünkü \(d(m^2)\)'nin alması gereken değer budur.
Ana arama, tek çarpımsal bölünmeler üzerinde çalışan özyinelemeli bir yapıdır. Çarpanlar artmayan değil, artan sırayla üretildiği için aynı üs çokluğu farklı sıralarla tekrar oluşmaz. Bir geçiş tek katetleri ele alır ve \(95095\)'in tamamını tek asallara dağıtır. İkinci geçiş ise çift katetleri ele alır; burada önce tek bir bölen \(2a+1\) katkısını temsil edecek şekilde \(2\) asalı için ayrılır, sonra kalan bölüm tek asallar arasında parçalanır.
Her tek çarpan \(f\), \((f-1)/2\) üssüne dönüştürülür. Üs listesi büyükten küçüğe sıralanır ve \(3,5,7,\dots\) asallarına atanır; çift dalda ise başa ayrıca \(2^{a+1}\) çarpanı eklenir. Uygulamalar şimdiye kadar görülen en küçük adayı saklar.
Aday sayı oldukça büyük olabileceği için Python ve Java sürümleri keyfi büyüklükte tamsayılar kullanır. C++ sürümü ise dikkatle sınırlandırılmış 128-bit aritmetiği uygular. C++ tarafında küçük doğrulama kontrolleri de vardır: \(12\) katetinin \(4\) üçgen verdiği, hedef \(4\) için en küçük çözümün \(12\) olduğu ve hedef \(1\) için en küçük çözümün \(3\) olduğu doğrulanır.
Son çözücü doğrudan \(n\) üzerinde arama yapmasa da, uygulamalarda \(T(n)\) için doğrudan bölen sayısı formülü de bulunur. Bu formül küçük kontrollerde kullanılır ve türetim ile hesaplanan sonuç arasındaki bağı açık hale getirir.
\(P=2T+1\) olsun. Asıl maliyet, \(n\) değerlerini tek tek taramak değildir; \(P\)'nin tüm tek çarpımsal bölünmelerini ve çift dal için \(P/f\) biçimindeki bölümlerin bölünmelerini üretmektir. Burada \(f\), \(P\)'nin tek bir bölenidir. Ziyaret edilen bu bölünmelerin sayısına \(\Pi(P)\) dersek, çalışma süresi özünde \(\Pi(P)\) ile orantılıdır; her aday için yalnızca kısa bir üs listesi sıralanır.
Gerçek problemde \(P=95095\) olduğu için bu arama uzayı çok küçüktür. Bellek kullanımı, uzunluğu \(k\) olan güncel çarpan listesi ve özyineleme yığını için \(O(k)\) düzeyindedir. Yöntem bu nedenle çok verimlidir; imkansız bir brute-force katet aramasını, çok küçük bir bölen-deseni aramasına indirger.
Para un cateto positivo fijo \(n\), sea \(T(n)\) el número de triángulos rectángulos enteros distintos que usan \(n\) como uno de sus catetos. El objetivo es hallar el menor \(n\) tal que \(T(n)=47547\).
Probar valores de \(n\) uno por uno sería completamente inviable. La idea decisiva es que cada triángulo se puede codificar mediante un par de divisores de un cuadrado, de modo que el problema pasa a ser una cuestión inversa sobre la función de divisores y no una búsqueda geométrica directa.
Escribamos el triángulo como \((a,n,c)\), donde \(a\) es el otro cateto y \(c\) la hipotenusa. Toda la derivación nace de reescribir la ecuación pitagórica en una forma que haga visibles los divisores de un cuadrado.
A partir de
$$a^2+n^2=c^2$$
obtenemos
$$c^2-a^2=(c-a)(c+a)=n^2.$$
Definamos
$$u=c-a,\qquad v=c+a.$$
Entonces \(u\) y \(v\) son enteros positivos con \(u<v\) y
$$uv=n^2.$$
Recíprocamente, cualquier par de divisores \(u<v\) de \(n^2\) con la misma paridad produce
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
que son enteros y por tanto definen un triángulo rectángulo válido. Así, contar triángulos con cateto \(n\) equivale exactamente a contar pares de divisores de \(n^2\) con la misma paridad, excluyendo el par central \(u=v\), que daría el caso degenerado \(a=0\).
Si \(n\) es impar, entonces \(n^2\) también es impar. Por ello, todo par de divisores de \(n^2\) es automáticamente impar-impar y queda admitido. Como \(n^2\) es un cuadrado, tiene un número impar de divisores, y uno de ellos es el divisor central \(\sqrt{n^2}=n\). En consecuencia,
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{cuando \(n\) es impar}.$$
Si \(n\) es par, \(u\) y \(v\) no pueden ser ambos impares, porque su producto es par. Luego ambos deben ser pares. Escribimos
$$u=2r,\qquad v=2s.$$
Entonces
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
y cada par de divisores \(r<s\) de \(\left(\frac{n}{2}\right)^2\) genera exactamente un triángulo. Por tanto,
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{cuando \(n\) es par}.$$
Conviene introducir un parámetro reducido \(m\): tomar \(m=n\) si \(n\) es impar y \(m=n/2\) si \(n\) es par. Entonces ambos casos se unifican como
$$T(n)=\frac{d(m^2)-1}{2}.$$
Para el valor pedido \(T(n)=47547\), la fórmula anterior se convierte en
$$d(m^2)=2\cdot 47547+1=95095.$$
Si
$$m=\prod_i p_i^{e_i},$$
entonces
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
Así, el problema inverso consiste en escribir \(95095\) como producto de enteros impares e interpretar cada factor \(f\) como una contribución al exponente
$$e=\frac{f-1}{2}.$$
Las implementaciones no suponen una sola factorización. Enumeran todas las particiones multiplicativas impares de \(95095\) en orden no decreciente, de manera que cada multiconjunto válido de exponentes aparece exactamente una vez.
En este problema,
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
pero también se permite agrupar algunos de esos factores primos. Un término como \(35\) significaría simplemente un exponente \((35-1)/2=17\) sobre un primo de \(m\).
Una vez fijado un multiconjunto de exponentes, el entero más pequeño se obtiene asignando el exponente mayor al primo disponible más pequeño, el segundo exponente mayor al segundo primo más pequeño, y así sucesivamente. La razón es la desigualdad de intercambio
$$p^a q^b \le p^b q^a\qquad\text{si }p<q\text{ y }a\ge b.$$
Por eso las implementaciones ordenan la lista de exponentes de mayor a menor antes de construir cada candidato.
El caso par requiere una observación adicional. Si \(n\) es par, entonces \(n=2m\). Supongamos que el exponente de \(2\) dentro de \(m\) es \(a\). Su contribución a \(d(m^2)\) es
$$2a+1.$$
La búsqueda reserva entonces un factor impar de \(95095\) para la potencia de \(2\), traduce ese factor a \(a=(f-1)/2\), y el cateto final recibe la potencia
$$2^{a+1},$$
porque \(n=2m\). Todos los factores impares restantes se convierten en exponentes sobre \(3,5,7,\dots\).
Este objetivo menor es útil porque las implementaciones lo verifican explícitamente. Si \(T(n)=4\), entonces
$$d(m^2)=2\cdot 4+1=9.$$
Para un cateto impar, la única partición impar es \(9\), que produce exponente \(4\) sobre un primo impar y conduce al candidato \(n=3^4=81\).
Para un cateto par, podemos reservar un factor \(3\) para la potencia de \(2\). Entonces
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
y el factor restante \(3\) aporta exponente \(1\) sobre el primo impar \(3\). Por lo tanto,
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
En efecto, \(\left(\frac{12}{2}\right)^2=36\) tiene los pares de factores
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$$
que corresponden a los cuatro triángulos
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
Con el objetivo real sucede lo mismo. Tras recorrer todas las particiones multiplicativas impares admisibles de \(95095\), el menor cateto compartido es
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
Las implementaciones en C++, Python y Java siguen exactamente la misma tubería matemática. Primero transforman la cuenta objetivo en
$$2T+1=95095,$$
porque ese es el valor que debe tomar \(d(m^2)\).
La búsqueda principal es una recursión sobre particiones multiplicativas impares. Las factorizaciones se generan en orden no decreciente, lo que evita repetir el mismo multiconjunto de exponentes en órdenes distintos. Un recorrido maneja los catetos impares, donde todo el producto \(95095\) se asigna a primos impares. Un segundo recorrido maneja los catetos pares, eligiendo antes un divisor impar que represente la contribución \(2a+1\) del primo \(2\) dentro de \(m\), y factorizando luego el cociente restante entre los primos impares.
Cada factor impar \(f\) se convierte en el exponente \((f-1)/2\). La lista resultante se ordena de mayor a menor y se asigna a los primos \(3,5,7,\dots\), mientras que la rama par añade por delante una potencia \(2^{a+1}\). Las implementaciones conservan el menor candidato encontrado.
El entero candidato puede ser muy grande, así que las implementaciones lo construyen con aritmética de precisión arbitraria en Python y Java, y con aritmética de 128 bits cuidadosamente acotada en C++. La versión en C++ también incluye comprobaciones pequeñas: verifica que el cateto \(12\) produce \(4\) triángulos, que la cuenta objetivo \(4\) tiene solución mínima \(12\), y que la cuenta objetivo \(1\) tiene solución mínima \(3\).
Aunque el solucionador final nunca recorre catetos de manera directa, las implementaciones también contienen la fórmula directa para \(T(n)\) a partir del número de divisores. Esa rutina sirve para las comprobaciones y deja muy clara la conexión entre la derivación matemática y la respuesta final.
Sea \(P=2T+1\). El coste importante no es recorrer valores de \(n\), sino enumerar todas las particiones multiplicativas impares de \(P\) y, en la rama par, hacer lo mismo con los cocientes \(P/f\), donde \(f\) es un divisor impar de \(P\). Si \(\Pi(P)\) denota el número de particiones realmente exploradas, el tiempo de ejecución es esencialmente proporcional a \(\Pi(P)\), con solo una lista corta de exponentes que ordenar por candidato.
En el problema real \(P=95095\), ese espacio de búsqueda es muy pequeño. El uso de memoria es \(O(k)\) para la pila recursiva y la lista actual de factores de longitud \(k\). En la práctica el método es rápido porque reemplaza una búsqueda imposible por fuerza bruta sobre los catetos por una búsqueda recursiva muy pequeña sobre patrones de divisores.
对固定的正整数直角边 \(n\)，记 \(T(n)\) 为所有把 \(n\) 当作一条直角边的不同整数直角三角形的个数。题目要求找出满足 \(T(n)=47547\) 的最小 \(n\)。
如果直接枚举直角边并逐个统计，会非常低效。真正有效的办法是把每个三角形改写成一个平方数的因子对问题，于是原题就从几何搜索转化成了一个关于约数函数的逆问题。
把三角形记为 \((a,n,c)\)，其中 \(a\) 是另一条直角边，\(c\) 是斜边。整套推导都来自于把勾股等式改写成能够直接暴露平方数因子的形式。
由
$$a^2+n^2=c^2$$
可得
$$c^2-a^2=(c-a)(c+a)=n^2.$$
定义
$$u=c-a,\qquad v=c+a.$$
那么 \(u\) 和 \(v\) 都是正整数，满足 \(u<v\)，并且
$$uv=n^2.$$
反过来，只要 \(u<v\) 是 \(n^2\) 的一个同奇偶因子对，就有
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
这两个量都会是整数，从而对应一个合法的整数直角三角形。因此，统计以 \(n\) 为直角边的三角形个数，等价于统计 \(n^2\) 的同奇偶因子对个数，并且要排除中间的 \(u=v\) 情形，因为那时 \(a=0\)，得到的是退化三角形。
如果 \(n\) 是奇数，那么 \(n^2\) 也是奇数，所以 \(n^2\) 的每一组因子对天然都是奇数-奇数，自动满足同奇偶条件。由于 \(n^2\) 是完全平方数，它的约数个数是奇数，其中正中间的约数就是 \(\sqrt{n^2}=n\)。因此
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{当 \(n\) 为奇数时}.$$
如果 \(n\) 是偶数，那么 \(u\) 和 \(v\) 不可能同时是奇数，因为它们的乘积是偶数，所以它们必须同时为偶数。写成
$$u=2r,\qquad v=2s.$$
于是有
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
而 \(\left(\frac{n}{2}\right)^2\) 的每一组 \(r<s\) 因子对都会对应一个三角形。所以
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{当 \(n\) 为偶数时}.$$
为了统一记号，可以引入一个缩减参数 \(m\)：当 \(n\) 为奇数时取 \(m=n\)，当 \(n\) 为偶数时取 \(m=n/2\)。于是两种情况可以合并成
$$T(n)=\frac{d(m^2)-1}{2}.$$
题目要求 \(T(n)=47547\)，所以必须满足
$$d(m^2)=2\cdot 47547+1=95095.$$
如果
$$m=\prod_i p_i^{e_i},$$
那么
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
因此逆问题就变成：把 \(95095\) 写成若干个奇数因子的乘积，并把每个因子 \(f\) 解释成一个指数贡献
$$e=\frac{f-1}{2}.$$
实现并不会只猜一种分解方式，而是按非递减顺序枚举 \(95095\) 的所有奇数乘法拆分，这样每一种可行的指数多重集都恰好出现一次。
在本题中，
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
但这些质因子也可以重新组合。例如，一个因子 \(35\) 只是表示在 \(m\) 的某个质因子上出现指数 \((35-1)/2=17\)。
当指数多重集已经固定时，得到最小整数的办法是：把最大指数给最小的可用质数，把第二大指数给第二小的质数，依次类推。原因是交换不等式
$$p^a q^b \le p^b q^a\qquad\text{当 }p<q\text{ 且 }a\ge b.$$
所以实现会先把指数按从大到小排序，再去构造候选值。
偶数情形还要多看一步。如果 \(n\) 是偶数，则 \(n=2m\)。设 \(m\) 中质因子 \(2\) 的指数是 \(a\)，那么它对 \(d(m^2)\) 的贡献就是
$$2a+1.$$
因此搜索会从 \(95095\) 的奇数因子里预留出一个因子给 \(2\) 的贡献，令 \(a=(f-1)/2\)，而最终的直角边由于 \(n=2m\) 会多出一个幂
$$2^{a+1}.$$
其余的奇数因子再转换成 \(3,5,7,\dots\) 这些奇质数上的指数。
这个小例子很重要，因为实现中明确用它做了校验。若 \(T(n)=4\)，则
$$d(m^2)=2\cdot 4+1=9.$$
如果要求 \(n\) 为奇数，那么唯一的奇数乘法拆分就是 \(9\)，它对应某个奇质数上的指数 \(4\)，于是得到候选值 \(n=3^4=81\)。
如果允许 \(n\) 为偶数，就可以把一个因子 \(3\) 预留给质因子 \(2\)。这时
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
剩下的因子 \(3\) 则给奇质数 \(3\) 一个指数 \(1\)。于是
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
确实，\(\left(\frac{12}{2}\right)^2=36\) 的因子对
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9$$
恰好对应四个三角形
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
真正的目标完全依照同样的机制。把 \(95095\) 的所有允许的奇数乘法拆分都检查完之后，得到的最小公共直角边是
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
C++、Python 和 Java 三份实现遵循完全相同的数学流程。第一步都是把目标计数改写成
$$2T+1=95095,$$
因为这就是 \(d(m^2)\) 必须达到的值。
核心搜索是一段针对奇数乘法拆分的递归。它按非递减顺序生成因子，因此不会因为顺序不同而重复得到同一组指数。第一轮处理奇数直角边，此时整个 \(95095\) 都要分配给奇质数。第二轮处理偶数直角边，先选一个奇数因子来表示 \(m\) 中质因子 \(2\) 的贡献 \(2a+1\)，然后再把剩余的商分配给奇质数。
每个奇数因子 \(f\) 都被转换成指数 \((f-1)/2\)。所得指数表按从大到小排序，并依次配给 \(3,5,7,\dots\)；偶数分支还会额外添加一个前导幂 \(2^{a+1}\)。实现始终保留当前最小的候选值。
候选值可能非常大，因此 Python 和 Java 直接使用任意精度整数，C++ 则使用带上界保护的 128 位整数运算。C++ 实现还包含几个小型校验：它会确认直角边 \(12\) 对应 \(4\) 个三角形，目标值 \(4\) 的最小解是 \(12\)，目标值 \(1\) 的最小解是 \(3\)。
虽然最终求解过程从不直接枚举直角边，但实现里也保留了通过约数个数公式直接计算 \(T(n)\) 的逻辑。这个部分既服务于校验，也把数学推导和最终输出紧密连接起来。
设 \(P=2T+1\)。真正的成本不在于扫描 \(n\) 的取值，而在于枚举 \(P\) 的所有奇数乘法拆分；在偶数分支中，还要枚举各个商 \(P/f\) 的奇数乘法拆分，其中 \(f\) 是 \(P\) 的一个奇数因子。若把实际访问到的这类拆分总数记为 \(\Pi(P)\)，那么运行时间本质上与 \(\Pi(P)\) 成正比，每个候选值只需要对一个很短的指数表排序。
在本题里 \(P=95095\)，搜索空间非常小。内存占用只有 \(O(k)\)，其中 \(k\) 是当前递归深度或因子表长度。因此，这个算法之所以高效，是因为它把原本不可能的暴力枚举直角边问题，压缩成了一个很小的约数模式递归搜索。
Для фиксированного положительного катета \(n\) обозначим через \(T(n)\) число различных целочисленных прямоугольных треугольников, в которых \(n\) является одним из катетов. Требуется найти минимальное \(n\), для которого \(T(n)=47547\).
Прямой перебор возможных катетов здесь бесполезен. Ключевая идея состоит в том, что каждый такой треугольник можно закодировать парой делителей полного квадрата. После этого геометрическая задача превращается в обратную задачу о числе делителей.
Запишем треугольник в виде \((a,n,c)\), где \(a\) — второй катет, а \(c\) — гипотенуза. Вся схема решения появляется после переписывания теоремы Пифагора в виде, который напрямую связывает задачу с делителями квадрата.
Из равенства
$$a^2+n^2=c^2$$
получаем
$$c^2-a^2=(c-a)(c+a)=n^2.$$
Введем обозначения
$$u=c-a,\qquad v=c+a.$$
Тогда \(u\) и \(v\) — положительные целые числа, \(u<v\), и при этом
$$uv=n^2.$$
Наоборот, любая пара делителей \(u<v\) числа \(n^2\) с одинаковой четностью дает
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
то есть снова целочисленный прямоугольный треугольник. Следовательно, подсчет треугольников с катетом \(n\) эквивалентен подсчету пар делителей числа \(n^2\) одной четности. Пара \(u=v\) исключается, потому что в этом случае \(a=0\), а треугольник вырождается.
Если \(n\) нечетно, то и \(n^2\) нечетно. Поэтому каждая пара делителей числа \(n^2\) автоматически является парой нечетных чисел и подходит. Так как \(n^2\) — квадрат, число его делителей нечетно, а средний делитель равен \(\sqrt{n^2}=n\). Отсюда
$$T(n)=\frac{d(n^2)-1}{2}\qquad\text{для нечетного \(n\)}.$$
Если \(n\) четно, то \(u\) и \(v\) не могут быть одновременно нечетными, потому что их произведение четно. Значит, оба они должны быть четными. Положим
$$u=2r,\qquad v=2s.$$
Тогда
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
и каждая пара делителей \(r<s\) числа \(\left(\frac{n}{2}\right)^2\) задает ровно один треугольник. Следовательно,
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}\qquad\text{для четного \(n\)}.$$
Удобно ввести сокращенный параметр \(m\): при нечетном \(n\) взять \(m=n\), а при четном \(n\) взять \(m=n/2\). Тогда обе формулы объединяются в одну:
$$T(n)=\frac{d(m^2)-1}{2}.$$
Для требуемого значения \(T(n)=47547\) получаем
$$d(m^2)=2\cdot 47547+1=95095.$$
Если
$$m=\prod_i p_i^{e_i},$$
то
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
Значит, нужно разложить \(95095\) в произведение нечетных чисел и трактовать каждый множитель \(f\) как вклад в показатель степени
$$e=\frac{f-1}{2}.$$
Реализации не угадывают одно разложение заранее. Они перебирают все нечетные мультипликативные разбиения числа \(95095\) в неубывающем порядке, так что каждое допустимое мультимножество показателей рассматривается ровно один раз.
Для этой задачи
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
но эти простые множители можно также объединять. Например, множитель \(35\) просто означает показатель \((35-1)/2=17\) у одного из простых множителей числа \(m\).
Когда мультимножество показателей уже выбрано, минимальное число получается, если самый большой показатель поставить к самому маленькому доступному простому, следующий — к следующему простому и так далее. Причина — неравенство перестановки
$$p^a q^b \le p^b q^a\qquad\text{при }p<q\text{ и }a\ge b.$$
Именно поэтому реализации сортируют список показателей по убыванию перед построением кандидата.
Для четного случая нужен еще один комментарий. Если \(n\) четно, то \(n=2m\). Пусть показатель степени простого \(2\) в числе \(m\) равен \(a\). Тогда его вклад в \(d(m^2)\) равен
$$2a+1.$$
Поэтому поиск резервирует один нечетный множитель числа \(95095\) под степень двойки, берет \(a=(f-1)/2\), а затем окончательный катет получает множитель
$$2^{a+1},$$
потому что \(n=2m\). Оставшиеся нечетные множители преобразуются в показатели при простых \(3,5,7,\dots\).
Этот меньший пример полезен, потому что он явно проверяется в реализациях. Если \(T(n)=4\), то
$$d(m^2)=2\cdot 4+1=9.$$
Для нечетного катета существует только одно нечетное разбиение: \(9\). Оно дает показатель \(4\) на одном нечетном простом, а значит кандидат равен \(n=3^4=81\).
Для четного катета можно зарезервировать множитель \(3\) под степень двойки. Тогда
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
а оставшийся множитель \(3\) дает показатель \(1\) при нечетном простом \(3\). Следовательно,
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
И действительно, число \(\left(\frac{12}{2}\right)^2=36\) имеет пары делителей
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$$
которые соответствуют четырем треугольникам
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
Для настоящей цели работает тот же механизм. После перебора всех допустимых нечетных мультипликативных разбиений числа \(95095\) минимальный общий катет равен
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала целевое количество преобразуется в
$$2T+1=95095,$$
потому что именно такое значение должно принять \(d(m^2)\).
Основной поиск — это рекурсия по нечетным мультипликативным разбиениям. Множители генерируются в неубывающем порядке, что исключает повторение одного и того же набора показателей в другой последовательности. Один проход обрабатывает нечетные катеты, когда весь продукт \(95095\) распределяется по нечетным простым. Второй проход обрабатывает четные катеты, сначала выбирая нечетный делитель как вклад \(2a+1\) простого \(2\) в числе \(m\), а затем факторизуя оставшееся частное по нечетным простым.
Каждый нечетный множитель \(f\) превращается в показатель \((f-1)/2\). Полученный список сортируется по убыванию и сопоставляется простым \(3,5,7,\dots\), а четная ветвь дополнительно добавляет ведущий множитель \(2^{a+1}\). Из всех построенных кандидатов сохраняется минимальный.
Кандидат может быть очень большим, поэтому в Python и Java используется арифметика произвольной точности, а в C++ — аккуратно ограниченная 128-битная арифметика. Версия на C++ также содержит небольшие контрольные проверки: она подтверждает, что катет \(12\) дает \(4\) треугольника, что для целевого значения \(4\) минимальное решение равно \(12\), и что для целевого значения \(1\) минимальное решение равно \(3\).
Хотя финальный решатель никогда не перебирает катеты напрямую, реализации также содержат прямую формулу подсчета \(T(n)\) через число делителей. Эта часть используется для проверок и наглядно связывает математический вывод с вычисленным ответом.
Пусть \(P=2T+1\). Главная стоимость заключается не в переборе \(n\), а в перечислении всех нечетных мультипликативных разбиений числа \(P\), а в четной ветви еще и разбиений частных \(P/f\), где \(f\) — нечетный делитель \(P\). Если обозначить через \(\Pi(P)\) число реально просмотренных разбиений, то время работы по существу пропорционально \(\Pi(P)\), а на каждый кандидат требуется отсортировать только короткий список показателей.
Для реальной задачи \(P=95095\) это пространство поиска очень мало. Память составляет \(O(k)\) для стека рекурсии и текущего списка множителей длины \(k\). На практике алгоритм быстр именно потому, что он заменяет невозможный грубый перебор по катетам очень маленьким рекурсивным перебором шаблонов делителей.
لضلع قائم موجب ثابت \(n\)، نرمز بـ \(T(n)\) إلى عدد المثلثات القائمة المختلفة ذات الأضلاع الصحيحة التي تستخدم \(n\) كأحد الضلعين القائمين. المطلوب هو إيجاد أصغر \(n\) يحقق \(T(n)=47547\).
البحث المباشر على قيم \(n\) غير عملي تمامًا. الفكرة الأساسية هي أن كل مثلث يمكن ترميزه بزوج من قواسم مربع كامل، وبذلك تتحول المسألة من بحث هندسي مباشر إلى مسألة عكسية حول دالة عدد القواسم.
لنكتب المثلث على الصورة \((a,n,c)\)، حيث \(a\) هو الضلع القائم الآخر و\(c\) هو الوتر. كل الاشتقاق ينبع من إعادة كتابة معادلة فيثاغورس في صيغة تكشف قواسم مربع كامل.
انطلاقًا من
$$a^2+n^2=c^2$$
نحصل على
$$c^2-a^2=(c-a)(c+a)=n^2.$$
عرّف الآن
$$u=c-a,\qquad v=c+a.$$
عندئذ يكون \(u\) و\(v\) عددين صحيحين موجبين مع \(u<v\)، كما أن
$$uv=n^2.$$
وبالعكس، فإن كل زوج قواسم \(u<v\) للعدد \(n^2\) له نفس الفردية أو الزوجية يعطي
$$a=\frac{v-u}{2},\qquad c=\frac{u+v}{2},$$
وهما عددان صحيحان، وبالتالي نحصل على مثلث قائم صحيح. إذن عدّ المثلثات التي تشترك في الضلع \(n\) يكافئ تمامًا عدّ أزواج القواسم ذات الفردية نفسها للعدد \(n^2\)، مع استبعاد الحالة الوسطى \(u=v\) لأنها تعطي \(a=0\) أي مثلثًا منعدمًا.
إذا كان \(n\) فرديًا، فإن \(n^2\) فردي أيضًا. وهذا يعني أن كل زوج قواسم للعدد \(n^2\) يكون تلقائيًا فرديًّا-فرديًّا، وبالتالي يكون صالحًا. وبما أن \(n^2\) مربع كامل، فعدد قواسمه فردي، ومن بينها القاسم الأوسط \(\sqrt{n^2}=n\). لذلك
$$T(n)=\frac{d(n^2)-1}{2}.$$
أما إذا كان \(n\) زوجيًا، فلا يمكن أن يكون \(u\) و\(v\) كلاهما فرديين لأن جداءهما زوجي، ولذلك يجب أن يكونا كلاهما زوجيين. نكتب
$$u=2r,\qquad v=2s.$$
ومن ثم
$$rs=\frac{n^2}{4}=\left(\frac{n}{2}\right)^2,$$
وكل زوج قواسم \(r<s\) للعدد \(\left(\frac{n}{2}\right)^2\) يولد مثلثًا واحدًا. وعليه
$$T(n)=\frac{d\!\left(\left(\frac{n}{2}\right)^2\right)-1}{2}.$$
ومن المناسب إدخال وسيط مختزل \(m\): نأخذ \(m=n\) إذا كان \(n\) فرديًا، ونأخذ \(m=n/2\) إذا كان \(n\) زوجيًا. عندها تتوحد الصيغتان في العلاقة
$$T(n)=\frac{d(m^2)-1}{2}.$$
بما أن المطلوب هو \(T(n)=47547\)، فإن الصيغة السابقة تعطي
$$d(m^2)=2\cdot 47547+1=95095.$$
إذا كان
$$m=\prod_i p_i^{e_i},$$
فإن
$$m^2=\prod_i p_i^{2e_i}\qquad\Longrightarrow\qquad d(m^2)=\prod_i (2e_i+1).$$
إذن المسألة العكسية تصبح: اكتب \(95095\) على صورة حاصل ضرب أعداد فردية، ثم فسّر كل عامل \(f\) على أنه مساهمة في الأس
$$e=\frac{f-1}{2}.$$
التنفيذات لا تخمّن تحليلًا واحدًا فقط، بل تعدّد كل التحليلات الضربية الفردية الممكنة للعدد \(95095\) بترتيب غير تنازلي، بحيث يظهر كل متعدد للأسس الصالح مرة واحدة فقط.
في هذه المسألة تحديدًا
$$95095=5\cdot 7\cdot 11\cdot 13\cdot 19,$$
لكن يمكن أيضًا دمج بعض هذه العوامل الأولية. فعامل مثل \(35\) يعني ببساطة أسًا مقداره \((35-1)/2=17\) على أحد العوامل الأولية في \(m\).
إذا كان متعدد الأسس ثابتًا، فإن أصغر عدد ناتج نحصل عليه عندما نضع أكبر أس على أصغر عدد أولي متاح، ثم نضع الأس التالي على العدد الأولي التالي، وهكذا. السبب هو متباينة التبديل
$$p^a q^b \le p^b q^a\qquad (p<q,\ a\ge b).$$
ولهذا السبب تقوم التنفيذات بترتيب قائمة الأسس ترتيبًا تنازليًا قبل بناء أي مرشح.
أما في الحالة الزوجية فهناك ملاحظة إضافية. إذا كان \(n\) زوجيًا، فإن \(n=2m\). ولنفترض أن أس العدد الأولي \(2\) داخل \(m\) يساوي \(a\). عندها تكون مساهمته في \(d(m^2)\) هي
$$2a+1.$$
لذلك يخصص البحث أحد العوامل الفردية للعدد \(95095\) من أجل قوة \(2\)، ثم يحسب \(a=(f-1)/2\)، وبعد ذلك يحصل الضلع القائم النهائي على العامل
$$2^{a+1},$$
لأن \(n=2m\). أما بقية العوامل الفردية فتتحول إلى أسس على \(3,5,7,\dots\).
هذا الهدف الأصغر مفيد لأنه يُستخدم صراحةً في اختبارات التنفيذ. إذا كان \(T(n)=4\)، فإن
$$d(m^2)=2\cdot 4+1=9.$$
في الحالة الفردية يوجد تحليل فردي واحد فقط وهو \(9\)، وهذا يعطي الأس \(4\) على عدد أولي فردي واحد، وبالتالي يكون المرشح \(n=3^4=81\).
في الحالة الزوجية يمكن حجز العامل \(3\) لقوة \(2\). وعندئذ
$$2a+1=3\qquad\Longrightarrow\qquad a=1,$$
ويعطي العامل المتبقي \(3\) الأس \(1\) على العدد الأولي الفردي \(3\). ومن ثم
$$m=2^1\cdot 3^1=6,\qquad n=2m=12.$$
وبالفعل فإن \(\left(\frac{12}{2}\right)^2=36\) يملك أزواج القواسم
$$1\cdot 36,\quad 2\cdot 18,\quad 3\cdot 12,\quad 4\cdot 9,$$
التي تقابل المثلثات الأربعة
$$(12,35,37),\quad (12,16,20),\quad (12,9,15),\quad (12,5,13).$$
الهدف الحقيقي يعمل بالطريقة نفسها تمامًا. وبعد فحص كل التحليلات الضربية الفردية المسموح بها للعدد \(95095\)، نحصل على أصغر ضلع قائم مشترك
$$n=2^{10}\cdot 3^6\cdot 5^5\cdot 7^3\cdot 11^2=96818198400000.$$
تنفيذات C++ وPython وJava تتبع جميعها المسار الرياضي نفسه. تبدأ أولًا بتحويل العدد الهدف إلى
$$2T+1=95095,$$
لأن هذه هي القيمة التي يجب أن تأخذها \(d(m^2)\).
البحث الرئيسي عبارة عن عودية على التحليلات الضربية الفردية. يتم توليد العوامل بترتيب غير تنازلي، وهذا يمنع تكرار مجموعة الأسس نفسها بترتيب مختلف. مرور واحد يعالج الأضلاع القائمة الفردية، حيث يُسند حاصل الضرب الكامل \(95095\) إلى الأعداد الأولية الفردية. ومرور ثانٍ يعالج الأضلاع القائمة الزوجية، وذلك باختيار قاسم فردي ليمثل المساهمة \(2a+1\) الخاصة بالعدد الأولي \(2\) داخل \(m\)، ثم تحليل خارج القسمة المتبقي على الأعداد الأولية الفردية.
كل عامل فردي \(f\) يتحول إلى الأس \((f-1)/2\). بعد ذلك تُرتب قائمة الأسس من الأكبر إلى الأصغر وتُسنَد إلى الأعداد الأولية \(3,5,7,\dots\)، بينما يضيف الفرع الزوجي في البداية قوة \(2^{a+1}\). وتحتفظ التنفيذات بأصغر مرشح يظهر أثناء البحث.
قد يكون المرشح الناتج كبيرًا جدًا، لذلك تستخدم نسختا Python وJava أعدادًا صحيحة ذات دقة غير محدودة، بينما تستخدم نسخة C++ حسابًا من نوع 128-بت مع حماية من تجاوز الحدود. كما تتضمن نسخة C++ اختبارات صغيرة للتأكد من أن الضلع \(12\) يولد \(4\) مثلثات، وأن العدد الهدف \(4\) يعطي الحل الأدنى \(12\)، وأن العدد الهدف \(1\) يعطي الحل الأدنى \(3\).
ورغم أن الحلال النهائي لا يبحث مباشرةً في قيم الأضلاع، فإن التنفيذات تحتوي أيضًا على الصيغة المباشرة لحساب \(T(n)\) من عدد القواسم. تُستخدم هذه الصيغة في الاختبارات وتوضح بجلاء الصلة بين الاشتقاق الرياضي والنتيجة النهائية.
ليكن \(P=2T+1\). الكلفة الحقيقية ليست في فحص قيم \(n\)، بل في تعداد جميع التحليلات الضربية الفردية للعدد \(P\)، وفي الفرع الزوجي أيضًا تعداد تحليلات القيم \(P/f\) حيث \(f\) قاسم فردي لـ \(P\). إذا رمزنا بعدد هذه التحليلات التي تُزار فعليًا بـ \(\Pi(P)\)، فإن زمن التنفيذ يتناسب في الجوهر مع \(\Pi(P)\)، مع وجود قائمة قصيرة فقط من الأسس تُرتب لكل مرشح.
في المسألة الفعلية \(P=95095\)، يكون فضاء البحث هذا صغيرًا جدًا. أما الذاكرة فهي \(O(k)\) لمكدس العودية وقائمة العوامل الحالية ذات الطول \(k\). عمليًا، الخوارزمية سريعة لأنها تستبدل بحثًا مستحيلًا بالقوة الغاشمة على الأضلاع القائمة ببحث عودي صغير جدًا على أنماط القواسم.