The goal is to sum the perimeters of all Fortunate triangles whose perimeter does not exceed \(P_{\max}=10^7\). The C++, Python, and Java implementations do not enumerate triangles by side lengths. Instead, they enumerate primitive solutions of an equivalent quadratic condition, reconstruct actual triangle sides from that data, and then add the contribution of every scaled copy in a single arithmetic-series step.
So the computation has two layers. First, characterize the primitive Fortunate triangles through a parameterized Diophantine surface. Then, once a primitive perimeter \(\Pi\) is known, count every triangle with perimeter \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) without generating those multiples one by one.
All three implementations use the same derivation. They reduce the problem to the quadratic identity \(p^2-q^2=15t^2\), classify the compatible squarefree factor pairs, and recover up to two primitive triangles from each coprime parameter pair.
After rewriting the defining relation used by the implementations, every primitive candidate is described by positive integers \(p>q>0\) and \(t>0\) satisfying
$$p^2-q^2=15t^2.$$
Because
$$p^2-q^2=(p+q)(p-q),$$
it is natural to define
$$S=p+q,\qquad D=p-q.$$
Then
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
This already explains two hard filters in the search. We need \(D<S\) so that \(q>0\), and \(S\) and \(D\) must have the same parity so that \(p\) and \(q\) are integers.
The implementations write the factor pair \((S,D)\) as square multiples
$$S=\kappa m^2,\qquad D=\ell n^2,$$
with \(m,n\ge 1\) and \(\gcd(m,n)=1\). Substituting into \(SD=15t^2\) gives
$$15t^2=\kappa\ell\,m^2n^2.$$
So the squarefree part of \(\kappa\ell\) must be \(15\). In the odd case this leaves exactly the four divisor pairs of \(15\):
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
But \(S\) and \(D\) must have matching parity. For these four odd families that forces both \(m\) and \(n\) to be odd. The even alternative is to double both coefficients, which preserves the squarefree kernel after removing the necessary factor of \(2\). That produces the four companion families
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
These eight ordered pairs are exactly the families hard-coded in the implementations.
They also determine \(t\) explicitly. If \(\kappa\ell=15\), then \(t=mn\). If \(\kappa\ell=60\), then \(t=2mn\). The implementations still verify this with an exact integer-square-root check instead of relying only on symbolic reasoning.
Once \(p\), \(q\), and \(t\) are known, the quadratic data yields two possible side seeds:
$$ (p,\ q+t,\ t) \qquad\text{and}\qquad (p,\ q-t,\ t). $$
The second branch exists only when \(q>t\), otherwise one side would be zero or negative. At this stage the entries are still not the final triangle sides. The implementations apply a fixed power-of-two normalization: choose the smallest \(\lambda\in\{0,1,2\}\) such that after multiplying the whole seed by \(2^\lambda\), the first two entries are both divisible by \(4\). The actual side lengths are then
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $$
This matches the code literally: repeatedly double the seed until the first two entries can be divided by \(4\), then divide only those two entries by \(4\).
Since \(p+q=S\), the perimeter formulas become
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
Those closed forms are what make the perimeter cutoff effective. In particular, every accepted triangle satisfies \(\Pi\ge S/4\), so once \(S>4P_{\max}\) the outer loop can stop immediately.
Not every parameterized seed is accepted. The condition \(\gcd(m,n)=1\) removes repeated square multiples at the parameter level, and \(\gcd(p,q,t)=1\) removes non-primitive points on the quadratic surface before branching. After normalization, the final side triple \((a,b,c)\) must still satisfy \(\gcd(a,b,c)=1\).
The geometry is checked through
$$a+b+c>2\max(a,b,c),$$
which is a compact form of the triangle inequality. The additional ordering constraint
$$b\ge c$$
prevents mirrored copies from being counted twice. The inner loop also stops as soon as \(D\ge S\), because then \(q\le 0\) and neither branch can produce a positive triangle.
If a primitive triangle survives every filter and has perimeter \(\Pi\), then all similar triangles with perimeters \(k\Pi\le P_{\max}\) also contribute. Writing
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor,$$
the total addition from that primitive family is
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
This is why the implementations never enumerate non-primitive triangles individually: one primitive perimeter already determines the whole arithmetic progression of valid multiples.
Take the family \((\kappa,\ell)=(15,1)\) and the coprime pair \((m,n)=(1,1)\). Then
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
Because \(\kappa\ell=15\), we get
$$t=mn=1.$$
The plus branch starts from \((8,8,1)\). The first two entries are already divisible by \(4\), so \(\lambda=0\), and the normalized triangle is
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
with primitive perimeter \(\Pi_{+}=5\).
The minus branch starts from \((8,6,1)\). Here one doubling is needed, so \(\lambda=1\). After normalization we obtain
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
with primitive perimeter \(\Pi_{-}=9\).
If the perimeter cap were \(20\) instead of \(10^7\), the first triangle would contribute \(5\cdot 4\cdot 5/2=50\), and the second would contribute \(9\cdot 2\cdot 3/2=27\). This one example shows the two branches, the power-of-two normalization, and the arithmetic-series summation of all multiples.
The implementations first loop over the eight coefficient families, then over coprime parameter pairs \((m,n)\). The outer loop stops when \(\kappa m^2>4P_{\max}\), because even the smallest possible perimeter is already too large. The inner loop stops when \(\ell n^2\ge \kappa m^2\), which is exactly the point where \(q\le 0\) and no positive triangle can survive.
For each remaining pair, the implementation reconstructs \(p\), \(q\), and \(t\), enforces the parity condition, verifies the square relation with an exact integer square root, and discards non-primitive quadratic data before branching.
Each of the two branches goes through the same pipeline: positivity check for the second branch, power-of-two normalization, primitivity check for the final side triple, triangle-inequality test, and the ordering constraint that removes symmetric duplicates. Whenever a primitive perimeter \(\Pi\) is accepted, the implementation computes \(Q=\lfloor P_{\max}/\Pi\rfloor\) and adds \(\Pi\,Q(Q+1)/2\) to the running total.
The C++, Python, and Java versions differ only in syntax and library calls. The mathematical objects, the filters, and the accumulation order are the same in all three.
For one fixed coefficient family, the bound \(\kappa m^2\le 4P_{\max}\) gives \(m=O(\sqrt{P_{\max}})\). For each fixed \(m\), the inequality \(\ell n^2<\kappa m^2\) gives \(n=O(m)\). So each family examines \(O(P_{\max})\) parameter pairs, and the number of families is the constant \(8\).
Each candidate uses only constant-time integer arithmetic, gcd computations, parity tests, one exact square-root verification, and a few local branch checks. The total running time is therefore \(O(P_{\max})\), and the extra space usage is \(O(1)\).
Gesucht ist die Summe der Umfänge aller Fortunate-Dreiecke mit Umfang höchstens \(P_{\max}=10^7\). Die Implementierungen in C++, Python und Java gehen nicht über die Seitenlängen aller ganzzahligen Dreiecke. Stattdessen erzeugen sie primitive Lösungen einer äquivalenten quadratischen Bedingung, rekonstruieren daraus echte Dreiecksseiten und addieren danach den Beitrag aller skalierten Kopien in einem einzigen Schritt über eine arithmetische Reihe.
Die Rechnung hat also zwei Ebenen. Zuerst werden primitive Fortunate-Dreiecke über eine parametrisierte diophantische Fläche beschrieben. Danach wird aus jedem primitiven Umfang \(\Pi\) sofort der Gesamtbeitrag aller Dreiecke mit Umfängen \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) bestimmt, ohne diese Vielfachen einzeln zu erzeugen.
Alle drei Implementierungen benutzen dieselbe Herleitung. Das Problem wird auf die quadratische Identität \(p^2-q^2=15t^2\) zurückgeführt, die zulässigen quadratfreien Faktorpaare werden klassifiziert, und aus jedem teilerfremden Parameterpaar werden bis zu zwei primitive Dreiecke rekonstruiert.
Nach der Umformung der von den Implementierungen verwendeten Definitionsbeziehung wird jeder primitive Kandidat durch positive ganze Zahlen \(p>q>0\) und \(t>0\) beschrieben, die
$$p^2-q^2=15t^2$$
erfüllen. Wegen
$$p^2-q^2=(p+q)(p-q)$$
ist es natürlich,
$$S=p+q,\qquad D=p-q$$
zu setzen. Dann gilt
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
Damit werden zwei harte Suchfilter sofort verständlich. Es muss \(D<S\) gelten, damit \(q>0\) bleibt, und \(S\) sowie \(D\) müssen dieselbe Parität haben, damit \(p\) und \(q\) ganzzahlig sind.
Die Implementierungen schreiben das Faktorpaaar \((S,D)\) als Quadratmultiplikatoren
$$S=\kappa m^2,\qquad D=\ell n^2,$$
wobei \(m,n\ge 1\) und \(\gcd(m,n)=1\) gilt. Setzt man dies in \(SD=15t^2\) ein, erhält man
$$15t^2=\kappa\ell\,m^2n^2.$$
Der quadratfreie Anteil von \(\kappa\ell\) muss also \(15\) sein. Im ungeraden Fall bleiben genau die vier Teilerpaare von \(15\):
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
Allerdings müssen \(S\) und \(D\) dieselbe Parität besitzen. In diesen vier ungeraden Familien erzwingt das, dass sowohl \(m\) als auch \(n\) ungerade sind. Die gerade Alternative besteht darin, beide Koeffizienten zu verdoppeln; nach dem Herausziehen des notwendigen Faktors \(2\) bleibt derselbe quadratfreie Kern. Dadurch entstehen die vier Begleitfamilien
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
Genau diese acht geordneten Paare sind in den Implementierungen fest hinterlegt.
Sie bestimmen auch \(t\) explizit. Für \(\kappa\ell=15\) gilt \(t=mn\). Für \(\kappa\ell=60\) gilt \(t=2mn\). Trotzdem bestätigt die Implementierung das Resultat noch einmal mit einem exakten ganzzahligen Quadratwurzeltest, statt sich nur auf die symbolische Herleitung zu verlassen.
Sobald \(p\), \(q\) und \(t\) feststehen, liefert die quadratische Datenlage zwei mögliche Seitensamen:
$$ (p,\ q+t,\ t) \qquad\text{und}\qquad (p,\ q-t,\ t). $$
Der zweite Zweig existiert nur für \(q>t\); andernfalls wäre eine Seite null oder negativ. In diesem Stadium sind die Einträge noch nicht die endgültigen Dreiecksseiten. Die Implementierungen führen eine feste Zweierpotenz-Normalisierung durch: Man wählt das kleinste \(\lambda\in\{0,1,2\}\), so dass nach der Multiplikation des gesamten Samens mit \(2^\lambda\) die ersten beiden Einträge durch \(4\) teilbar sind. Die tatsächlichen Seitenlängen sind dann
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $$
Das entspricht dem Code wörtlich: Der Same wird wiederholt verdoppelt, bis die ersten beiden Einträge durch \(4\) teilbar sind; danach werden nur diese beiden Einträge durch \(4\) geteilt.
Da \(p+q=S\) ist, lauten die Umfangsformeln
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
Gerade diese geschlossenen Ausdrücke machen die Umfangsgrenze wirksam. Insbesondere erfüllt jedes akzeptierte Dreieck \(\Pi\ge S/4\). Sobald also \(S>4P_{\max}\) gilt, kann die äußere Schleife sofort enden.
Nicht jeder parametrisierte Same wird akzeptiert. Die Bedingung \(\gcd(m,n)=1\) entfernt wiederholte Quadratvielfache auf Parameter-Ebene, und \(\gcd(p,q,t)=1\) entfernt nichtprimitive Punkte auf der quadratischen Fläche noch vor der Verzweigung. Nach der Normalisierung muss das endgültige Seitentripel \((a,b,c)\) zusätzlich \(\gcd(a,b,c)=1\) erfüllen.
Die Geometrie wird über
$$a+b+c>2\max(a,b,c)$$
geprüft; das ist eine kompakte Form der Dreiecksungleichung. Die zusätzliche Ordnungsbedingung
$$b\ge c$$
verhindert, dass Spiegelbilder doppelt gezählt werden. Die innere Schleife endet außerdem sofort bei \(D\ge S\), denn dann ist \(q\le 0\) und keiner der beiden Zweige kann ein positives Dreieck erzeugen.
Wenn ein primitives Dreieck alle Filter überlebt und Umfang \(\Pi\) hat, tragen auch alle ähnlichen Dreiecke mit Umfängen \(k\Pi\le P_{\max}\) bei. Setzt man
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor,$$
dann ist der Gesamtbeitrag dieser primitiven Familie
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
Darum enumerieren die Implementierungen nichtprimitive Dreiecke niemals einzeln: Ein primitiver Umfang bestimmt bereits die ganze arithmetische Folge aller zulässigen Vielfachen.
Nehmen wir die Familie \((\kappa,\ell)=(15,1)\) und das teilerfremde Paar \((m,n)=(1,1)\). Dann gilt
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
Wegen \(\kappa\ell=15\) folgt
$$t=mn=1.$$
Der Pluszweig startet mit \((8,8,1)\). Die ersten beiden Einträge sind bereits durch \(4\) teilbar, also ist \(\lambda=0\), und das normalisierte Dreieck lautet
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
mit primitivem Umfang \(\Pi_{+}=5\).
Der Minuszweig startet mit \((8,6,1)\). Hier ist eine Verdopplung nötig, also \(\lambda=1\). Nach der Normalisierung erhält man
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
mit primitivem Umfang \(\Pi_{-}=9\).
Wäre die Umfangsgrenze \(20\) statt \(10^7\), dann würde das erste Dreieck \(5\cdot 4\cdot 5/2=50\) beitragen und das zweite \(9\cdot 2\cdot 3/2=27\). Dieses eine Beispiel zeigt beide Zweige, die Zweierpotenz-Normalisierung und die Summation aller Vielfachen per arithmetischer Reihe.
Die Implementierungen durchlaufen zuerst die acht Koeffizientenfamilien und danach die teilerfremden Parameterpaare \((m,n)\). Die äußere Schleife stoppt bei \(\kappa m^2>4P_{\max}\), weil dann bereits der kleinste mögliche Umfang zu groß ist. Die innere Schleife stoppt bei \(\ell n^2\ge \kappa m^2\); genau dort wird \(q\le 0\), und kein positives Dreieck kann mehr entstehen.
Für jedes verbleibende Paar rekonstruiert die Implementierung \(p\), \(q\) und \(t\), erzwingt die Paritätsbedingung, verifiziert die Quadratbeziehung mit einer exakten ganzzahligen Quadratwurzel und verwirft nichtprimitive quadratische Daten noch vor der Verzweigung.
Jeder der beiden Zweige durchläuft dieselbe Pipeline: Positivitätsprüfung des zweiten Zweigs, Zweierpotenz-Normalisierung, Primitivitätsprüfung des endgültigen Seitentripels, Test der Dreiecksungleichung und die Ordnungsbedingung gegen symmetrische Duplikate. Sobald ein primitiver Umfang \(\Pi\) akzeptiert ist, berechnet die Implementierung \(Q=\lfloor P_{\max}/\Pi\rfloor\) und addiert \(\Pi\,Q(Q+1)/2\) zur laufenden Summe.
Die Versionen in C++, Python und Java unterscheiden sich nur in Syntax und Bibliotheksaufrufen. Die mathematischen Objekte, die Filter und die Reihenfolge der Akkumulation sind in allen drei Sprachen identisch.
Für eine feste Koeffizientenfamilie liefert die Schranke \(\kappa m^2\le 4P_{\max}\) die Abschätzung \(m=O(\sqrt{P_{\max}})\). Für festes \(m\) ergibt \(\ell n^2<\kappa m^2\) die Abschätzung \(n=O(m)\). Damit untersucht jede Familie \(O(P_{\max})\) Parameterpaare, und die Zahl der Familien ist die Konstante \(8\).
Jeder Kandidat benötigt nur konstante ganzzahlige Arithmetik, ggT-Berechnungen, Paritätstests, eine exakte Quadratwurzelprüfung und einige lokale Zweigtests. Die Gesamtlaufzeit ist daher \(O(P_{\max})\), und der zusätzliche Speicherverbrauch ist \(O(1)\).
Amaç, çevresi \(P_{\max}=10^7\) değerini aşmayan tüm Fortunate üçgenlerinin çevre toplamını bulmaktır. C++, Python ve Java uygulamaları üçgenleri doğrudan kenarlarına göre dolaşmaz. Bunun yerine eşdeğer bir kuadratik koşulun ilkel çözümlerini üretir, bu verilerden gerçek üçgen kenarlarını geri kurar ve ardından tüm ölçekli kopyaların katkısını tek bir aritmetik seri adımıyla ekler.
Dolayısıyla hesap iki katmandan oluşur. Önce ilkel Fortunate üçgenleri parametrik bir Diofant yüzeyi üzerinden tanımlanır. Sonra da ilkel bir çevre \(\Pi\) bulunduğunda, çevresi \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) olan bütün benzer üçgenlerin toplam katkısı bu katlar tek tek üretilmeden hesaplanır.
Üç uygulama da aynı türetmeyi kullanır. Problem \(p^2-q^2=15t^2\) kuadratik özdeşliğine indirgenir, buna uyan karesiz çarpan çiftleri sınıflandırılır ve aralarında asal her parametre çiftinden en çok iki ilkel üçgen elde edilir.
Uygulamaların kullandığı tanımlayıcı ilişki yeniden yazıldığında, her ilkel aday pozitif tam sayılar \(p>q>0\) ve \(t>0\) ile temsil edilir ve
$$p^2-q^2=15t^2$$
eşitliğini sağlar. Çünkü
$$p^2-q^2=(p+q)(p-q),$$
şu tanımlar doğaldır:
$$S=p+q,\qquad D=p-q.$$
Böylece
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}$$
elde edilir. Bu, aramadaki iki sert filtreyi hemen açıklar. \(q>0\) kalması için \(D<S\) gerekir; \(p\) ve \(q\)'nun tam sayı olması için de \(S\) ile \(D\)'nin aynı paritye sahip olması gerekir.
Uygulamalar çarpan çiftini \((S,D)\) şu biçimde yazar:
$$S=\kappa m^2,\qquad D=\ell n^2,$$
burada \(m,n\ge 1\) ve \(\gcd(m,n)=1\). Bunu \(SD=15t^2\) içine koyunca
$$15t^2=\kappa\ell\,m^2n^2$$
çıkar. O halde \(\kappa\ell\)'nin karesiz çekirdeği \(15\) olmak zorundadır. Tek durumda geriye \(15\)'in tam olarak dört bölen çifti kalır:
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
Ancak \(S\) ile \(D\)'nin aynı paritye sahip olması gerekir. Bu dört tek aile için bu durum hem \(m\) hem de \(n\)'nin tek olmasını zorlar. Çift alternatif ise her iki katsayıyı da ikiyle çarpmaktır; gerekli \(2\) kuvveti ayrıştırıldıktan sonra aynı karesiz çekirdek korunur. Böylece şu dört eş aile elde edilir:
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
Uygulamalarda sabit duran sekiz sıralı çift tam olarak bunlardır.
Bu aileler \(t\)'yi de açık biçimde belirler. \(\kappa\ell=15\) ise \(t=mn\), \(\kappa\ell=60\) ise \(t=2mn\) olur. Buna rağmen uygulama yalnızca sembolik türetmeye güvenmez; sonucu tam sayı karekök testiyle tekrar doğrular.
\(p\), \(q\) ve \(t\) belirlendikten sonra kuadratik veri iki olası kenar tohumu verir:
$$ (p,\ q+t,\ t) \qquad\text{ve}\qquad (p,\ q-t,\ t). $$
İkinci dal yalnızca \(q>t\) ise vardır; aksi halde bir kenar sıfır veya negatif olur. Bu aşamada bu değerler henüz son üçgen kenarları değildir. Uygulamalar sabit bir iki kuvveti normalizasyonu uygular: tüm tohumu \(2^\lambda\) ile çarptıktan sonra ilk iki girişin de \(4\) ile bölünebildiği en küçük \(\lambda\in\{0,1,2\}\) seçilir. Gerçek kenarlar böylece
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right) $$
olur. Bu, kodun yaptığı işlemin tam karşılığıdır: ilk iki giriş \(4\)'e bölünebilir hale gelene kadar tohum ikiyle çarpılır, sonra yalnızca bu iki giriş \(4\)'e bölünür.
\(p+q=S\) olduğundan çevre formülleri
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t) $$
şeklini alır. Çevre üst sınırını etkili yapan şey tam olarak bu kapalı ifadelerdir. Özellikle her kabul edilen üçgen \(\Pi\ge S/4\) koşulunu sağlar; dolayısıyla \(S>4P_{\max}\) olduğunda dış döngü hemen durabilir.
Her parametrik tohum kabul edilmez. \(\gcd(m,n)=1\) koşulu parametre uzayındaki tekrar eden kare katlarını temizler; \(\gcd(p,q,t)=1\) koşulu ise dallanmadan önce kuadratik yüzey üzerindeki ilkel olmayan noktaları eler. Normalizasyondan sonra son kenar üçlüsü \((a,b,c)\) hâlâ \(\gcd(a,b,c)=1\) sağlamalıdır.
Geometri şu eşitsizlikle kontrol edilir:
$$a+b+c>2\max(a,b,c).$$
Bu, üçgen eşitsizliğinin kompakt bir yazımıdır. Ek olarak
$$b\ge c$$
koşulu ayna görüntülerinin iki kez sayılmasını engeller. İç döngü ayrıca \(D\ge S\) olduğu anda biter; çünkü bu durumda \(q\le 0\) olur ve iki daldan hiçbiri pozitif bir üçgen üretemez.
Bir ilkel üçgen tüm filtreleri geçip çevresi \(\Pi\) olduğunda, \(k\Pi\le P_{\max}\) sağlayan bütün benzer üçgenler de katkı verir. Şu tanımı yapalım:
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor.$$
Bu ilkel ailenin toplam katkısı o zaman
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2} $$
olur. Bu yüzden uygulamalar ilkel olmayan üçgenleri tek tek dolaşmaz; tek bir ilkel çevre, izin verilen bütün katların aritmetik dizisini zaten belirler.
\((\kappa,\ell)=(15,1)\) ailesini ve aralarında asal \((m,n)=(1,1)\) çiftini alalım. O zaman
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7 $$
elde edilir. \(\kappa\ell=15\) olduğu için
$$t=mn=1$$
olur. Artı dal \((8,8,1)\) ile başlar. İlk iki giriş zaten \(4\)'e bölündüğü için \(\lambda=0\) ve normalize üçgen
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1) $$
şeklindedir; ilkel çevre \(\Pi_{+}=5\)'tir.
Eksi dal \((8,6,1)\) ile başlar. Burada bir kez ikiyle çarpmak gerekir; yani \(\lambda=1\). Normalizasyondan sonra
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2) $$
elde edilir ve ilkel çevre \(\Pi_{-}=9\) olur.
Çevre sınırı \(10^7\) yerine \(20\) olsaydı, birinci üçgen \(5\cdot 4\cdot 5/2=50\), ikinci üçgen ise \(9\cdot 2\cdot 3/2=27\) katkı yapardı. Bu tek örnek iki dalı, iki kuvveti normalizasyonunu ve tüm katların aritmetik seriyle toplanmasını aynı anda gösterir.
Uygulamalar önce sekiz katsayı ailesi üzerinde, sonra da aralarında asal parametre çiftleri \((m,n)\) üzerinde döner. Dış döngü \(\kappa m^2>4P_{\max}\) olduğunda durur; çünkü en küçük olası çevre bile artık çok büyüktür. İç döngü \(\ell n^2\ge \kappa m^2\) olduğunda biter; tam bu noktada \(q\le 0\) olur ve pozitif bir üçgen kalmaz.
Kalan her çift için uygulama \(p\), \(q\) ve \(t\)'yi geri kurar, parity koşulunu uygular, kare ilişkisini tam sayı karekök ile doğrular ve dallanmadan önce ilkel olmayan kuadratik verileri eler.
İki dalın her biri aynı hat üzerinden ilerler: ikinci dal için pozitiflik kontrolü, iki kuvveti normalizasyonu, son kenar üçlüsünün ilkel kontrolü, üçgen eşitsizliği testi ve simetrik tekrarları engelleyen sıralama şartı. İlkel bir çevre \(\Pi\) kabul edildiğinde uygulama \(Q=\lfloor P_{\max}/\Pi\rfloor\) değerini hesaplar ve toplama \(\Pi\,Q(Q+1)/2\) ekler.
C++, Python ve Java sürümleri yalnızca sözdizimi ve standart kütüphane çağrılarında ayrılır. Matematiksel nesneler, filtreler ve toplama sırası üçünde de aynıdır.
Sabit bir katsayı ailesi için \(\kappa m^2\le 4P_{\max}\) sınırı \(m=O(\sqrt{P_{\max}})\) verir. Sabit \(m\) için \(\ell n^2<\kappa m^2\) eşitsizliği \(n=O(m)\) sonucunu verir. Dolayısıyla her aile \(O(P_{\max})\) parametre çifti inceler; aile sayısı da sabit \(8\)'dir.
Her aday yalnızca sabit zamanlı tamsayı aritmetiği, EBOB hesapları, parity testleri, bir tam karekök doğrulaması ve birkaç yerel dal testi kullanır. Toplam çalışma süresi bu yüzden \(O(P_{\max})\), ek bellek kullanımı ise \(O(1)\)'dir.
Hay que sumar los perímetros de todos los triángulos Fortunate cuyo perímetro no supera \(P_{\max}=10^7\). Las implementaciones en C++, Python y Java no recorren los triángulos por sus lados. En lugar de eso, enumeran soluciones primitivas de una condición cuadrática equivalente, reconstruyen a partir de ellas las longitudes reales del triángulo y después añaden la contribución de todas sus copias escaladas mediante un solo paso de suma aritmética.
Así, el cálculo tiene dos niveles. Primero se describen los triángulos Fortunate primitivos mediante una superficie diofántica parametrizada. Después, una vez conocido un perímetro primitivo \(\Pi\), se cuenta toda la familia de triángulos con perímetros \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) sin generar uno por uno esos múltiplos.
Las tres implementaciones siguen la misma derivación. El problema se reduce a la identidad cuadrática \(p^2-q^2=15t^2\), se clasifican los pares de factores libres de cuadrados que pueden aparecer y, a partir de cada par coprimo de parámetros, se reconstruyen hasta dos triángulos primitivos.
Tras reescribir la relación definitoria usada por las implementaciones, cada candidato primitivo queda descrito por enteros positivos \(p>q>0\) y \(t>0\) que satisfacen
$$p^2-q^2=15t^2.$$
Como
$$p^2-q^2=(p+q)(p-q),$$
lo natural es definir
$$S=p+q,\qquad D=p-q.$$
Entonces
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
Eso ya explica dos filtros duros de la búsqueda. Hace falta \(D<S\) para que \(q>0\), y \(S\) y \(D\) deben tener la misma paridad para que \(p\) y \(q\) sean enteros.
Las implementaciones escriben el par de factores \((S,D)\) como múltiplos cuadrados
$$S=\kappa m^2,\qquad D=\ell n^2,$$
con \(m,n\ge 1\) y \(\gcd(m,n)=1\). Al sustituir en \(SD=15t^2\) se obtiene
$$15t^2=\kappa\ell\,m^2n^2.$$
Por tanto, la parte libre de cuadrados de \(\kappa\ell\) debe ser \(15\). En el caso impar eso deja exactamente los cuatro pares de divisores de \(15\):
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
Pero \(S\) y \(D\) deben tener la misma paridad. En esas cuatro familias impares eso obliga a que \(m\) y \(n\) sean ambos impares. La alternativa par consiste en duplicar ambos coeficientes; al extraer la potencia necesaria de \(2\), se conserva el mismo núcleo libre de cuadrados. Así aparecen las cuatro familias compañeras
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
Esos ocho pares ordenados son exactamente los que están fijados en las implementaciones.
Además determinan \(t\) de forma explícita. Si \(\kappa\ell=15\), entonces \(t=mn\). Si \(\kappa\ell=60\), entonces \(t=2mn\). Aun así, la implementación vuelve a confirmarlo con una raíz cuadrada entera exacta en lugar de fiarse solo de la deducción simbólica.
Una vez conocidos \(p\), \(q\) y \(t\), los datos cuadráticos producen dos semillas posibles de lados:
$$ (p,\ q+t,\ t) \qquad\text{y}\qquad (p,\ q-t,\ t). $$
La segunda rama solo existe cuando \(q>t\), porque en caso contrario uno de los lados sería nulo o negativo. En este punto las entradas todavía no son los lados finales del triángulo. Las implementaciones aplican una normalización fija por potencias de \(2\): se elige el menor \(\lambda\in\{0,1,2\}\) tal que, tras multiplicar toda la semilla por \(2^\lambda\), las dos primeras entradas sean divisibles por \(4\). Las longitudes finales quedan entonces
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $$
Eso coincide literalmente con el código: se duplica la semilla hasta que las dos primeras entradas puedan dividirse por \(4\), y luego solo esas dos entradas se dividen por \(4\).
Como \(p+q=S\), las fórmulas del perímetro pasan a ser
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
Esas expresiones cerradas son las que vuelven eficaz el corte por perímetro. En particular, todo triángulo aceptado satisface \(\Pi\ge S/4\), así que en cuanto \(S>4P_{\max}\) el bucle exterior puede detenerse de inmediato.
No toda semilla parametrizada se acepta. La condición \(\gcd(m,n)=1\) elimina múltiplos cuadrados repetidos en el nivel de parámetros, y \(\gcd(p,q,t)=1\) elimina puntos no primitivos de la superficie cuadrática antes de ramificar. Tras la normalización, el triple final de lados \((a,b,c)\) todavía debe satisfacer \(\gcd(a,b,c)=1\).
La parte geométrica se comprueba mediante
$$a+b+c>2\max(a,b,c),$$
que es una forma compacta de la desigualdad triangular. La restricción adicional
$$b\ge c$$
evita contar dos veces copias reflejadas. El bucle interior también termina en cuanto \(D\ge S\), porque entonces \(q\le 0\) y ninguna de las dos ramas puede producir un triángulo positivo.
Si un triángulo primitivo supera todos los filtros y tiene perímetro \(\Pi\), entonces también contribuyen todos los triángulos semejantes con \(k\Pi\le P_{\max}\). Definimos
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor.$$
La aportación total de esa familia primitiva es
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
Por eso las implementaciones nunca enumeran por separado los triángulos no primitivos: un solo perímetro primitivo ya determina toda la progresión aritmética de múltiplos válidos.
Tomemos la familia \((\kappa,\ell)=(15,1)\) y el par coprimo \((m,n)=(1,1)\). Entonces
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
Como \(\kappa\ell=15\), resulta
$$t=mn=1.$$
La rama positiva parte de \((8,8,1)\). Las dos primeras entradas ya son divisibles por \(4\), así que \(\lambda=0\), y el triángulo normalizado es
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
con perímetro primitivo \(\Pi_{+}=5\).
La rama negativa parte de \((8,6,1)\). Aquí hace falta una duplicación, por lo que \(\lambda=1\). Tras la normalización obtenemos
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
con perímetro primitivo \(\Pi_{-}=9\).
Si el límite de perímetro fuera \(20\) en lugar de \(10^7\), el primer triángulo aportaría \(5\cdot 4\cdot 5/2=50\) y el segundo \(9\cdot 2\cdot 3/2=27\). Este ejemplo único muestra las dos ramas, la normalización por potencias de \(2\) y la suma en progresión aritmética de todos los múltiplos.
Las implementaciones recorren primero las ocho familias de coeficientes y después los pares coprimos de parámetros \((m,n)\). El bucle exterior se detiene cuando \(\kappa m^2>4P_{\max}\), porque incluso el perímetro más pequeño posible ya sería demasiado grande. El bucle interior termina cuando \(\ell n^2\ge \kappa m^2\); exactamente en ese punto \(q\le 0\) y ningún triángulo positivo puede sobrevivir.
Para cada par restante, la implementación reconstruye \(p\), \(q\) y \(t\), impone la condición de paridad, verifica la relación cuadrática con una raíz cuadrada entera exacta y descarta los datos cuadráticos no primitivos antes de ramificar.
Cada una de las dos ramas pasa por la misma cadena: comprobación de positividad de la segunda rama, normalización por potencias de \(2\), prueba de primitividad del triple final de lados, test de desigualdad triangular y la restricción de orden que elimina duplicados simétricos. Cuando se acepta un perímetro primitivo \(\Pi\), la implementación calcula \(Q=\lfloor P_{\max}/\Pi\rfloor\) y añade \(\Pi\,Q(Q+1)/2\) al acumulador.
Las versiones en C++, Python y Java solo difieren en sintaxis y llamadas de biblioteca. Los objetos matemáticos, los filtros y el orden de acumulación son los mismos en las tres.
Para una familia fija de coeficientes, la cota \(\kappa m^2\le 4P_{\max}\) da \(m=O(\sqrt{P_{\max}})\). Para cada \(m\) fijo, la desigualdad \(\ell n^2<\kappa m^2\) da \(n=O(m)\). Por tanto, cada familia examina \(O(P_{\max})\) pares de parámetros, y el número de familias es la constante \(8\).
Cada candidato solo usa aritmética entera de tiempo constante, cálculos de mcd, pruebas de paridad, una verificación exacta de raíz cuadrada y unos pocos tests locales de rama. El tiempo total es entonces \(O(P_{\max})\), y la memoria adicional es \(O(1)\).
目标是求出所有周长不超过 \(P_{\max}=10^7\) 的 Fortunate 三角形的周长总和。C++、Python 和 Java 实现都不是按边长去暴力枚举三角形，而是先枚举一个等价二次条件的原始解，再从这些二次数据恢复出真正的三角形边长，最后把所有放大倍数的贡献用一次等差求和直接加入答案。
因此整个计算分成两层。第一层是用一个参数化的丢番图曲面刻画原始 Fortunate 三角形。第二层是在知道某个原始周长 \(\Pi\) 之后，不再逐个生成 \(\Pi,2\Pi,3\Pi,\dots\) 这些倍数，而是一次性统计所有满足 \(k\Pi\le P_{\max}\) 的相似三角形。
三种语言的实现使用的是同一套推导。它们把问题压缩到二次恒等式 \(p^2-q^2=15t^2\)，再把其中允许出现的无平方因子分布分类，最后从每一个互素参数对中恢复出至多两个原始三角形。
把实现所依据的定义关系改写之后，每个原始候选都可以表示为正整数 \(p>q>0\) 和 \(t>0\)，并满足
$$p^2-q^2=15t^2.$$
由于
$$p^2-q^2=(p+q)(p-q),$$
自然引入
$$S=p+q,\qquad D=p-q.$$
于是有
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
这一步已经解释了搜索中的两个硬性条件。首先必须有 \(D<S\)，否则 \(q\le 0\) 就不可能得到正边长。其次 \(S\) 和 \(D\) 必须同奇同偶，否则 \(p\) 和 \(q\) 就不是整数。
实现把因子对 \((S,D)\) 写成平方倍数
$$S=\kappa m^2,\qquad D=\ell n^2,$$
其中 \(m,n\ge 1\)，并且 \(\gcd(m,n)=1\)。代入 \(SD=15t^2\) 以后得到
$$15t^2=\kappa\ell\,m^2n^2.$$
因此 \(\kappa\ell\) 的无平方因子部分必须是 \(15\)。在奇数情形下，这就只剩下 \(15\) 的四个有序因子对：
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
但 \(S\) 与 \(D\) 必须同奇同偶。对这四个奇系数族来说，这又进一步强迫 \(m\) 和 \(n\) 都是奇数。偶数情形则通过把两个系数同时乘以 \(2\) 来得到；把必要的 \(2\) 因子提出之后，无平方因子部分并没有改变，于是得到四个配套族
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
实现里固定写死的，正是这八个有序系数对。
它们还会把 \(t\) 直接确定下来。如果 \(\kappa\ell=15\)，那么 \(t=mn\)；如果 \(\kappa\ell=60\)，那么 \(t=2mn\)。不过程序并不只依赖这个符号推导，而是仍然用一次精确的整数平方根检查来确认结果。
一旦 \(p\)、\(q\)、\(t\) 已知，二次数据就会给出两个可能的边长种子：
$$ (p,\ q+t,\ t) \qquad\text{和}\qquad (p,\ q-t,\ t). $$
第二个分支只有在 \(q>t\) 时才成立，否则其中一条边会变成零或负数。此时这些量还不是最终三角形的边。实现会做一个固定的 \(2\)-adic 归一化：选择最小的 \(\lambda\in\{0,1,2\}\)，使得把整个种子乘上 \(2^\lambda\) 之后，前两个坐标都能被 \(4\) 整除。最终边长写成
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right) $$
这与程序的行为完全一致：不断把种子整体乘以 \(2\)，直到前两项都能除以 \(4\)，然后只把这两项除以 \(4\)。
由于 \(p+q=S\)，两条分支的周长公式可以直接写成
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
正是这两个闭式表达式使得周长上界可以很早截断搜索。特别地，每个被接受的三角形都满足 \(\Pi\ge S/4\)，所以一旦 \(S>4P_{\max}\)，外层循环就可以立即停止。
并不是每一个参数种子都会被接受。条件 \(\gcd(m,n)=1\) 用来去掉参数层上的重复平方倍数，\(\gcd(p,q,t)=1\) 用来在分支展开之前剔除二次曲面上的非原始点。归一化之后，最终边长三元组 \((a,b,c)\) 仍然必须满足 \(\gcd(a,b,c)=1\)。
几何部分通过
$$a+b+c>2\max(a,b,c)$$
来检查，这只是三角不等式的一种紧凑写法。额外的顺序条件
$$b\ge c$$
则用来避免把镜像对称的副本重复计算。内层循环也会在 \(D\ge S\) 时立刻结束，因为这时 \(q\le 0\)，两个分支都不可能再产生正三角形。
如果某个原始三角形通过了所有过滤，周长为 \(\Pi\)，那么所有满足 \(k\Pi\le P_{\max}\) 的相似三角形也都要计入。记
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor,$$
则这一整个原始家族的总贡献为
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
这就是为什么程序从来不会逐个枚举非原始三角形：一个原始周长已经决定了所有合法倍数构成的整条等差序列。
取系数族 \((\kappa,\ell)=(15,1)\)，参数取互素对 \((m,n)=(1,1)\)。这时
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
由于 \(\kappa\ell=15\)，所以
$$t=mn=1.$$
正号分支从 \((8,8,1)\) 开始。前两项本来就能被 \(4\) 整除，因此 \(\lambda=0\)，归一化后得到
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
对应原始周长 \(\Pi_{+}=5\)。
负号分支从 \((8,6,1)\) 开始。这里需要先整体乘一次 \(2\)，也就是 \(\lambda=1\)。归一化后得到
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
对应原始周长 \(\Pi_{-}=9\)。
如果周长上界不是 \(10^7\) 而是 \(20\)，那么第一个三角形的贡献为 \(5\cdot 4\cdot 5/2=50\)，第二个三角形的贡献为 \(9\cdot 2\cdot 3/2=27\)。这个例子把两条重建分支、\(2\)-adic 归一化以及“用等差求和一次性加入所有倍数”的方法连在了一起。
实现首先遍历八个系数族，然后遍历互素参数对 \((m,n)\)。外层循环在 \(\kappa m^2>4P_{\max}\) 时停止，因为连最小可能周长都已经超出范围。内层循环在 \(\ell n^2\ge \kappa m^2\) 时停止，这正对应 \(q\le 0\) 的情形，也就不再可能产生正三角形。
对每个保留下来的参数对，程序恢复 \(p\)、\(q\) 与 \(t\)，检查奇偶条件，用精确整数平方根验证二次关系，并在分支展开之前丢掉非原始的二次数据。
两个分支都会经过同一条处理链：第二分支的正性检查、\(2\)-adic 归一化、最终边长三元组的原始性检查、三角不等式检查，以及消除对称重复的顺序条件。一旦某个原始周长 \(\Pi\) 被接受，程序就计算 \(Q=\lfloor P_{\max}/\Pi\rfloor\)，并把 \(\Pi\,Q(Q+1)/2\) 加入累积答案。
C++、Python 和 Java 版本的区别只在语法和库函数调用。数学对象、过滤规则和累加顺序是完全一致的。
对于固定的系数族，条件 \(\kappa m^2\le 4P_{\max}\) 给出 \(m=O(\sqrt{P_{\max}})\)。对每个固定的 \(m\)，不等式 \(\ell n^2<\kappa m^2\) 给出 \(n=O(m)\)。因此每个系数族会检查 \(O(P_{\max})\) 个参数对，而系数族总数只是常数 \(8\)。
每个候选只需要常数时间的整数运算、最大公因数计算、奇偶性测试、一次精确平方根验证以及少量局部分支判断。因此总时间复杂度是 \(O(P_{\max})\)，额外空间复杂度是 \(O(1)\)。
Нужно найти сумму периметров всех треугольников Fortunate с периметром не больше \(P_{\max}=10^7\). Реализации на C++, Python и Java не перебирают треугольники напрямую по сторонам. Вместо этого они перечисляют примитивные решения эквивалентного квадратичного условия, восстанавливают из этих данных реальные длины сторон, а затем одним арифметическим шагом добавляют вклад всех масштабированных копий.
Значит, вычисление состоит из двух уровней. Сначала примитивные треугольники Fortunate описываются через параметризованную диофантову поверхность. Затем, как только найден примитивный периметр \(\Pi\), сразу учитываются все треугольники с периметрами \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\), без явного перечисления этих кратных.
Все три реализации опираются на одну и ту же схему. Задача сводится к квадратичному тождеству \(p^2-q^2=15t^2\), затем классифицируются допустимые квадратно-свободные пары множителей, и из каждой взаимно простой пары параметров восстанавливаются не более двух примитивных треугольников.
После преобразования определяющего соотношения, используемого реализациями, каждый примитивный кандидат задается положительными целыми \(p>q>0\) и \(t>0\), удовлетворяющими равенству
$$p^2-q^2=15t^2.$$
Поскольку
$$p^2-q^2=(p+q)(p-q),$$
естественно ввести
$$S=p+q,\qquad D=p-q.$$
Тогда
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
Это сразу объясняет два жестких фильтра в переборе. Нужно \(D<S\), чтобы оставалось \(q>0\), и \(S\) с \(D\) обязаны иметь одинаковую четность, иначе \(p\) и \(q\) не будут целыми.
Реализации записывают пару множителей \((S,D)\) в виде квадратных множителей
$$S=\kappa m^2,\qquad D=\ell n^2,$$
где \(m,n\ge 1\) и \(\gcd(m,n)=1\). Подстановка в \(SD=15t^2\) дает
$$15t^2=\kappa\ell\,m^2n^2.$$
Следовательно, квадратно-свободная часть \(\kappa\ell\) должна быть равна \(15\). В нечетном случае остаются ровно четыре упорядоченные пары делителей числа \(15\):
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
Но \(S\) и \(D\) должны иметь одинаковую четность. Для этих четырех нечетных семейств это заставляет \(m\) и \(n\) быть нечетными. Четная альтернатива получается удвоением обоих коэффициентов; после выделения нужной степени двойки квадратно-свободное ядро остается тем же. Так появляются четыре сопутствующих семейства
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
Именно эти восемь упорядоченных пар и зашиты в реализациях.
Они также явно определяют \(t\). Если \(\kappa\ell=15\), то \(t=mn\). Если \(\kappa\ell=60\), то \(t=2mn\). Тем не менее программы дополнительно подтверждают это точной целочисленной проверкой квадратного корня, а не полагаются только на символическое рассуждение.
Когда \(p\), \(q\) и \(t\) уже известны, квадратические данные дают две возможные стартовые тройки сторон:
$$ (p,\ q+t,\ t) \qquad\text{и}\qquad (p,\ q-t,\ t). $$
Вторая ветвь существует только при \(q>t\), иначе одна из сторон станет нулевой или отрицательной. На этом этапе это еще не окончательные стороны треугольника. Реализации применяют фиксированную нормализацию степенями двойки: выбирается наименьшее \(\lambda\in\{0,1,2\}\), при котором после умножения всей тройки на \(2^\lambda\) первые две координаты делятся на \(4\). Настоящие стороны равны
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $$
Это буквально совпадает с кодом: стартовая тройка последовательно удваивается, пока первые два элемента не станут делиться на \(4\), а затем только эти два элемента делятся на \(4\).
Так как \(p+q=S\), формулы периметра принимают вид
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
Именно эти замкнутые выражения делают отсечение по периметру таким сильным. В частности, любой принятый треугольник удовлетворяет \(\Pi\ge S/4\), поэтому при \(S>4P_{\max}\) внешний цикл можно немедленно завершить.
Принимается не каждая параметризованная заготовка. Условие \(\gcd(m,n)=1\) убирает повторные квадратные множители на уровне параметров, а \(\gcd(p,q,t)=1\) устраняет непримитивные точки на квадратической поверхности еще до ветвления. После нормализации итоговая тройка сторон \((a,b,c)\) тоже обязана удовлетворять \(\gcd(a,b,c)=1\).
Геометрия проверяется через
$$a+b+c>2\max(a,b,c),$$
что является компактной формой неравенства треугольника. Дополнительное условие
$$b\ge c$$
не дает считать зеркальные копии дважды. Внутренний цикл также останавливается при \(D\ge S\), потому что тогда \(q\le 0\), и ни одна из двух ветвей уже не может породить положительный треугольник.
Если примитивный треугольник проходит все фильтры и имеет периметр \(\Pi\), то вклад дают и все подобные треугольники, для которых \(k\Pi\le P_{\max}\). Обозначим
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor.$$
Тогда полный вклад этой примитивной семьи равен
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
Поэтому реализации никогда не перебирают непримитивные треугольники по отдельности: один примитивный периметр уже задает всю арифметическую прогрессию допустимых кратных.
Возьмем семейство \((\kappa,\ell)=(15,1)\) и взаимно простую пару \((m,n)=(1,1)\). Тогда
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
Поскольку \(\kappa\ell=15\), имеем
$$t=mn=1.$$
Плюсовая ветвь начинается с \((8,8,1)\). Первые два элемента уже делятся на \(4\), значит \(\lambda=0\), и после нормализации получается
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
с примитивным периметром \(\Pi_{+}=5\).
Минусовая ветвь начинается с \((8,6,1)\). Здесь требуется одно удвоение, то есть \(\lambda=1\). После нормализации имеем
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
с примитивным периметром \(\Pi_{-}=9\).
Если бы ограничение по периметру было равно \(20\), а не \(10^7\), то первый треугольник дал бы вклад \(5\cdot 4\cdot 5/2=50\), а второй - вклад \(9\cdot 2\cdot 3/2=27\). Этот пример одновременно показывает обе ветви, нормализацию степенями двойки и суммирование всех кратных через арифметическую прогрессию.
Реализации сначала перебирают восемь семейств коэффициентов, а затем взаимно простые пары параметров \((m,n)\). Внешний цикл заканчивается при \(\kappa m^2>4P_{\max}\), потому что даже минимально возможный периметр уже слишком велик. Внутренний цикл останавливается при \(\ell n^2\ge \kappa m^2\); именно здесь \(q\le 0\), и положительный треугольник уже невозможен.
Для каждой оставшейся пары программа восстанавливает \(p\), \(q\) и \(t\), проверяет условие четности, подтверждает квадратическое равенство точной целочисленной квадратной корневой проверкой и отбрасывает непримитивные квадратические данные еще до ветвления.
Каждая из двух ветвей проходит одну и ту же цепочку: проверка положительности для второй ветви, нормализация степенями двойки, проверка примитивности итоговой тройки сторон, проверка неравенства треугольника и условие порядка, убирающее симметричные дубликаты. Когда примитивный периметр \(\Pi\) принят, реализация вычисляет \(Q=\lfloor P_{\max}/\Pi\rfloor\) и добавляет \(\Pi\,Q(Q+1)/2\) к накопленной сумме.
Версии на C++, Python и Java различаются только синтаксисом и библиотечными вызовами. Математические объекты, фильтры и порядок накопления у них полностью совпадают.
Для фиксированного семейства коэффициентов ограничение \(\kappa m^2\le 4P_{\max}\) дает \(m=O(\sqrt{P_{\max}})\). Для каждого фиксированного \(m\) неравенство \(\ell n^2<\kappa m^2\) дает \(n=O(m)\). Значит, каждое семейство рассматривает \(O(P_{\max})\) пар параметров, а число семейств равно постоянной \(8\).
На каждый кандидат требуется только константное число целочисленных операций, вычислений НОД, проверок четности, одна точная проверка квадратного корня и несколько локальных ветвлений. Поэтому суммарное время равно \(O(P_{\max})\), а дополнительная память - \(O(1)\).
المطلوب هو حساب مجموع محيطات جميع مثلثات Fortunate التي لا يتجاوز محيطها \(P_{\max}=10^7\). تنفيذات C++ و Python و Java لا تعدد المثلثات مباشرة من خلال اطوال اضلاعها. بدلا من ذلك فهي تعدد الحلول البدائية لشرط تربيعي مكافئ، ثم تعيد بناء الاضلاع الحقيقية من هذه البيانات، ثم تضيف مساهمة جميع النسخ المكبرة بخطوة واحدة تعتمد على مجموع متتالية حسابية.
لذلك يتكون الحساب من مستويين. اولا يجري توصيف مثلثات Fortunate البدائية عبر سطح ديوفانتي بارامتري. ثم ما ان يعرف محيط بدائي \(\Pi\)، حتى تحسب دفعة واحدة جميع المثلثات ذات المحيط \(\Pi,2\Pi,3\Pi,\dots\le P_{\max}\) من غير توليد هذه المضاعفات واحدا واحدا.
تستخدم اللغات الثلاث الاشتقاق نفسه. فالمسألة تختزل إلى المتطابقة التربيعية \(p^2-q^2=15t^2\)، ثم تصنف ازواج العوامل الممكنة الخالية من المربعات، ثم يستعاد من كل زوج بارامترات اولي فيما بينه ما يصل إلى مثلثين بدائيين.
بعد اعادة كتابة العلاقة التعريفية التي تعتمد عليها التنفيذات، يوصف كل مرشح بدائي باعداد صحيحة موجبة \(p>q>0\) و \(t>0\) تحقق
$$p^2-q^2=15t^2.$$
وبما ان
$$p^2-q^2=(p+q)(p-q),$$
فمن الطبيعي تعريف
$$S=p+q,\qquad D=p-q.$$
وعندئذ نحصل على
$$SD=15t^2,\qquad p=\frac{S+D}{2},\qquad q=\frac{S-D}{2}.$$
وهذا يفسر فورا مرشحين اساسيين في البحث. يجب ان يكون \(D<S\) حتى يبقى \(q>0\)، كما يجب ان يملك \(S\) و \(D\) التكافؤ نفسه حتى يكون \(p\) و \(q\) عددين صحيحين.
تكتب التنفيذات زوج العوامل \((S,D)\) على صورة مضاعفات مربعة:
$$S=\kappa m^2,\qquad D=\ell n^2,$$
حيث \(m,n\ge 1\) و \(\gcd(m,n)=1\). وبالتعويض في \(SD=15t^2\) نحصل على
$$15t^2=\kappa\ell\,m^2n^2.$$
اذن لا بد ان يكون الجزء الخالي من المربعات في \(\kappa\ell\) هو \(15\). في الحالة الفردية لا يبقى الا ازواج القواسم الاربعة للعدد \(15\):
$$ (1,15),\ (3,5),\ (5,3),\ (15,1). $$
لكن \(S\) و \(D\) يجب ان يملكا التكافؤ نفسه. وفي هذه العائلات الفردية الاربع يفرض ذلك ان يكون \(m\) و \(n\) فرديين معا. اما البديل الزوجي فينتج من مضاعفة المعاملين كليهما بالعدد \(2\)؛ وبعد استخراج قوة الاثنين اللازمة يبقى اللب الخالي من المربعات كما هو. وهكذا تظهر العائلات الاربع المرافقة
$$ (2,30),\ (6,10),\ (10,6),\ (30,2). $$
وهذه هي بالضبط الازواج الثمانية المرتبة المثبتة داخل التنفيذات.
كما انها تحدد \(t\) صراحة. اذا كان \(\kappa\ell=15\) فلدينا \(t=mn\)، واذا كان \(\kappa\ell=60\) فلدينا \(t=2mn\). ومع ذلك تعيد البرامج التحقق من هذه النتيجة بجذر تربيعي صحيح دقيق بدلا من الاعتماد على الاشتقاق الرمزي وحده.
بعد معرفة \(p\) و \(q\) و \(t\)، تنتج البيانات التربيعية بذرتين محتملتين للاضلاع:
$$ (p,\ q+t,\ t) \qquad (p,\ q-t,\ t). $$
الفرع الثاني لا يوجد الا اذا تحقق \(q>t\)، والا اصبح احد الاضلاع صفرا او سالبا. وفي هذه المرحلة لا تكون القيم بعد هي اضلاع المثلث النهائية. تطبق التنفيذات تطبيعا ثابتا بقوى العدد \(2\): نختار اصغر \(\lambda\in\{0,1,2\}\) بحيث تصبح القيمتان الاوليان قابلتين للقسمة على \(4\) بعد ضرب البذرة كلها في \(2^\lambda\). وعندئذ تصبح الاضلاع الفعلية
$$ \left(2^{\lambda-2}p,\ 2^{\lambda-2}(q\pm t),\ 2^\lambda t\right). $$
وهذا يطابق ما يفعله الكود حرفيا: تضاعف البذرة تكرارا حتى يمكن قسمة المدخلين الاولين على \(4\)، ثم يقسم هذان المدخلان فقط على \(4\).
وبما ان \(p+q=S\)، فان صيغتي المحيط تصبحان
$$ \Pi_{+}=2^{\lambda-2}(S+5t),\qquad \Pi_{-}=2^{\lambda-2}(S+3t). $$
وهاتان الصيغتان المغلقتان هما ما يجعل قطع البحث بواسطة حد المحيط فعالا جدا. وعلى وجه الخصوص يحقق كل مثلث مقبول الشرط \(\Pi\ge S/4\)، ولذلك ما ان يصبح \(S>4P_{\max}\) حتى يمكن ايقاف الحلقة الخارجية مباشرة.
ليست كل بذرة بارامترية مقبولة. فالشرط \(\gcd(m,n)=1\) يزيل مضاعفات المربعات المكررة على مستوى البارامترات، والشرط \(\gcd(p,q,t)=1\) يزيل النقاط غير البدائية على السطح التربيعي قبل التفريع. وبعد التطبيع يجب ان يحقق ثلاثي الاضلاع النهائي \((a,b,c)\) ايضا الشرط \(\gcd(a,b,c)=1\).
اما الفحص الهندسي فيتم عبر
$$a+b+c>2\max(a,b,c),$$
وهي صيغة مضغوطة لمتباينة المثلث. والشرط الاضافي
$$b\ge c$$
يمنع عد النسخ المرآتية مرتين. كما ان الحلقة الداخلية تتوقف فور تحقق \(D\ge S\)، لأن ذلك يعني \(q\le 0\)، وعندها لا يعود اي من الفرعين قادرا على انتاج مثلث موجب.
اذا نجا مثلث بدائي من جميع المرشحات وكان محيطه \(\Pi\)، فان كل مثلث مشابه يحقق \(k\Pi\le P_{\max}\) يسهم هو ايضا في الناتج. لنكتب
$$Q=\left\lfloor\frac{P_{\max}}{\Pi}\right\rfloor.$$
عندئذ تكون مساهمة هذه العائلة البدائية كلها
$$ \Pi(1+2+\cdots+Q)=\Pi\,\frac{Q(Q+1)}{2}. $$
ولهذا لا تعدد التنفيذات المثلثات غير البدائية على نحو منفصل: فمحيط بدائي واحد يحدد مسبقا المتتالية الحسابية الكاملة لجميع المضاعفات الصالحة.
لنأخذ العائلة \((\kappa,\ell)=(15,1)\) مع الزوج الاولي فيما بينه \((m,n)=(1,1)\). عندئذ نحصل على
$$ S=15,\qquad D=1,\qquad p=\frac{15+1}{2}=8,\qquad q=\frac{15-1}{2}=7. $$
ولأن \(\kappa\ell=15\)، فان
$$t=mn=1.$$
فرع الجمع يبدأ من \((8,8,1)\). المدخلان الاولان قابلان للقسمة على \(4\) من البداية، ولذلك \(\lambda=0\)، وبعد التطبيع يصبح لدينا
$$ \left(\frac{8}{4},\frac{8}{4},1\right)=(2,2,1), $$
ومحيطه البدائي هو \(\Pi_{+}=5\).
اما فرع الطرح فيبدأ من \((8,6,1)\). هنا نحتاج الى مضاعفة واحدة، اي \(\lambda=1\). وبعد التطبيع نحصل على
$$ \left(\frac{16}{4},\frac{12}{4},2\right)=(4,3,2), $$
ومحيطه البدائي هو \(\Pi_{-}=9\).
ولو كان حد المحيط \(20\) بدلا من \(10^7\)، لكانت مساهمة المثلث الاول \(5\cdot 4\cdot 5/2=50\)، ومساهمة المثلث الثاني \(9\cdot 2\cdot 3/2=27\). هذا المثال الواحد يوضح الفرعين، وتطبيع قوى الاثنين، وجمع جميع المضاعفات بواسطة متتالية حسابية في آن واحد.
تمر التنفيذات اولا على عائلات المعاملات الثماني، ثم على ازواج البارامترات المتباينة اوليا \((m,n)\). تتوقف الحلقة الخارجية عندما يصبح \(\kappa m^2>4P_{\max}\)، لأن اصغر محيط ممكن يكون عندها قد تجاوز الحد بالفعل. وتتوقف الحلقة الداخلية عندما يتحقق \(\ell n^2\ge \kappa m^2\)، وهو الموضع الذي يصبح فيه \(q\le 0\) فلا يبقى اي مثلث موجب.
لكل زوج يبقى بعد هذه الحدود، يعيد التنفيذ بناء \(p\) و \(q\) و \(t\)، ويفرض شرط التكافؤ، ويتحقق من العلاقة التربيعية بجذر تربيعي صحيح دقيق، ثم يستبعد البيانات التربيعية غير البدائية قبل الانتقال إلى التفريع.
كل واحد من الفرعين يمر بالسلسلة نفسها: فحص الايجابية للفرع الثاني، ثم تطبيع قوى الاثنين، ثم اختبار بدائية ثلاثي الاضلاع النهائي، ثم فحص متباينة المثلث، ثم شرط الترتيب الذي يزيل النسخ المتناظرة. وعندما يقبل محيط بدائي \(\Pi\)، يحسب التنفيذ \(Q=\lfloor P_{\max}/\Pi\rfloor\) ويضيف \(\Pi\,Q(Q+1)/2\) إلى المجموع الجاري.
الفرق بين نسخ C++ و Python و Java هو في الصياغة البرمجية واستدعاءات المكتبة فقط. اما البنية الرياضية والمرشحات وترتيب الجمع فهي متطابقة.
بالنسبة إلى عائلة معاملات ثابتة، يعطي القيد \(\kappa m^2\le 4P_{\max}\) التقدير \(m=O(\sqrt{P_{\max}})\). ولكل \(m\) ثابت، تعطي المتباينة \(\ell n^2<\kappa m^2\) التقدير \(n=O(m)\). لذلك تفحص كل عائلة \(O(P_{\max})\) من ازواج البارامترات، وعدد العائلات نفسه هو الثابت \(8\).
كل مرشح يحتاج فقط إلى عدد ثابت من العمليات الصحيحة، وحسابات القاسم المشترك الاكبر، وفحوص التكافؤ، واختبار واحد دقيق للجذر التربيعي، وعدة اختبارات محلية داخل الفرع. لذا يكون الزمن الكلي \(O(P_{\max})\)، اما الذاكرة الاضافية فهي \(O(1)\).