For an integer-sided triangle \(\Delta\), let \(s(\Delta)\) be the side length of the smallest square that can contain \(\Delta\) after the triangle is rotated and translated in the plane. Project Euler 998 asks for the sum of the perimeters of all distinct integer-sided triangles whose minimum enclosing square has side length at most \(10^6\). The examples \(T(40)=346\), \(T(400)=76402\), and \(T(2000)=3237036\) are used as checkpoints.
Fix a square of side length \(L\), and rotate the whole configuration so the square is axis-aligned. A triangle that is tight for this square has vertices on the boundary. If one of its sides crosses the square with horizontal or vertical span \(L\), that side is the hypotenuse of a right triangle whose legs are \(L\) and some offset \(p\). Therefore its length is integral exactly when
\[ h^2=L^2+p^2. \]
This is the first major reduction: instead of searching arbitrary triangles, we enumerate Pythagorean segments attached to each possible square side \(L\). For every \(L\), the program stores pairs \((p,h)\), where \(0\le p\le L\) and \(h=\sqrt{L^2+p^2}\) is an integer. The restriction \(p\le L\) loses nothing because the complementary orientation is symmetric.
The enumeration rests on a normal-form statement. Let \(Q\) be a minimum square for a triangle. After rotating the plane, \(Q=[0,L]\times[0,L]\). A non-degenerate minimum cannot have all vertices strictly inside a smaller homothetic square, so at least two opposite supporting lines or two adjacent supporting lines are active. For a triangle, the supporting vertices can change only when a side direction becomes parallel to a square side. Thus every critical placement can be represented by boundary chords whose coordinate spans are determined by the side length \(L\) and by one boundary offset.
Lemma 1. If a side of a critical placement connects two boundary lines separated by \(L\), then its integral length is equivalent to a Pythagorean condition \(h^2=L^2+p^2\). This follows immediately from orthogonal projection: the side vector has components \(L\) and \(p\), up to sign. Conversely, every such Pythagorean segment can be placed on the square boundary and is therefore a legitimate building block for a candidate triangle.
Lemma 2. Pairing two boundary segments of the same square side \(L\) leaves only two combinatorial closures. Either the remaining side lies on a square boundary and has length \(p+q\), or it joins the two opposite residual endpoints and has squared length \((L-p)^2+(L-q)^2\). These are exactly the two families tested in the program. No third closure exists because the three vertices of the triangle occupy three chosen boundary endpoints, and after the first two side chords are fixed the last side is determined by which pair of residual endpoints is joined.
The inequality \(pq\ge L(L-p-q)\) is the algebraic form of the first closure's inside-square condition. It is obtained by writing the two boundary chords in coordinates, intersecting the two supporting rays from the boundary endpoints, and requiring the intersection coordinate to remain inside the square. This converts the geometric feasibility statement into one integer comparison, avoiding any floating-point decision in the first family.
The offsets are generated with Euclid's formula. Primitive triples are
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
with \(\gcd(m,n)=1\) and \(m-n\) odd. Each primitive triple is then scaled by \(k\). Either leg may play the role of the square side \(L\), and the other leg becomes the offset. Hence the code inserts both \((L, p, h)=(ka,kb,kc)\) and \((kb,ka,kc)\) whenever the offset is not larger than the side. Since the relevant leg is at most \(L\le 10^6\), the Euclid parameters only need to be tested up to \(\sqrt{2L}+2\). Duplicates are removed after sorting each list for a fixed \(L\).
Choose two Pythagorean boundary segments for the same square side \(L\): \((p,h_p)\) and \((q,h_q)\). The first family is obtained when the remaining side of the triangle lies along one side of the square. Its length is
\[ b=p+q. \]
For the endpoints to lie on the boundary segment, we require \(b\le L\). The third vertex must also be on the correct side of the square rather than outside the \(L\times L\) box. In the boundary coordinates used by the implementation, this feasibility condition simplifies to
\[ pq\ge L(L-b). \]
When both inequalities hold, \((b,h_p,h_q)\) is a valid integer-sided triangle whose enclosing square has side length \(L\). Its perimeter is added after sorting the three side lengths into a canonical key.
The same two Pythagorean segments can also close through the opposite pair of endpoints. The remaining displacement has legs \(L-p\) and \(L-q\), so the third side is integral exactly when
\[ r^2=(L-p)^2+(L-q)^2. \]
This gives a candidate triangle \((h_p,h_q,r)\). Unlike the first family, the construction alone does not prove that \(L\) is the minimum enclosing square side. The same side triple might fit into a smaller square after a different rotation. Therefore every candidate from this family is passed to an independent minimum-square verifier, and it is accepted only when the verified value is at least \(L\), up to a small floating-point tolerance.
For a triangle with side lengths \(a\le b\le c\), place the side \(c\) on the \(x\)-axis and compute the third vertex by the law of cosines:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
For a rotation angle \(\theta\), project the three vertices onto the rotated axes \(u\) and \(v\). The side length of the smallest axis-aligned square at that angle is
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
The vertices that realize the maxima and minima change only when an edge becomes parallel to one of the square axes. Thus the interval \([0,\pi/2)\) is split at the edge directions. Inside each interval, both widths are fixed sinusoidal expressions. The optimum is found either at a boundary or at an interior angle where the two widths are equal. The routine minimum_square evaluates exactly these candidates, which is the standard rotating-calipers idea specialized to three points.
A triangle may be produced by several square sides, by both endpoint orderings, or by both geometric families. The problem asks for distinct triangles, so the program sorts every side triple and packs it into one integer key. The side lengths are below \(2^{21}\), so the key
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
is collision-free for the target range. The perimeter is added only the first time a key appears.
Soundness. Every accepted triangle is integer-sided by construction. In the first family, the side lengths are \(p+q\), \(h_p\), and \(h_q\), with the Pythagorean equations ensuring integral hypotenuses and the feasibility inequality ensuring a placement inside the square. In the second family, the extra square test ensures that \(r\) is integral, and minimum_square verifies that the side triple does not belong to a smaller enclosing square. Therefore every inserted triangle satisfies \(s(\Delta)\le L\le n\).
Completeness. Take any integer-sided triangle with \(s(\Delta)\le n\), and place it in a minimum square of side \(L=s(\Delta)\). By the normal-form discussion, at least two of the tight side chords are Pythagorean boundary segments for the same \(L\). Their remaining endpoints close in one of the two possible combinatorial ways described in Lemma 2. Hence the triangle is generated by the corresponding iteration of the algorithm. If it appears through several placements, the canonical key keeps only one copy.
Numerical robustness. The enumeration, square tests, perimeter sums, and deduplication keys are exact integer operations. Floating point is used only in the secondary verifier for the second family. That verifier evaluates all critical angles of a three-point set and compares against \(L\) with a small tolerance; the published checkpoints provide an end-to-end guard against both missed candidates and false positives.
pythagorean_offsets builds the list of all admissible Pythagorean boundary segments for every \(L\le n\). The main solve loop then considers all unordered pairs of segments attached to the same \(L\). It tests the first family with the algebraic inequality above, tests the second family with a square check and minimum_square, and inserts every accepted side triple into the global set. The three published checkpoints are asserted before the target value is printed.
Let \(d_L\) be the number of Pythagorean offsets stored for side \(L\). The running time after triple generation is
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
because every unordered pair of offsets for the same \(L\) is tested once. The memory usage is \(O(\sum d_L+u)\), where \(u\) is the number of distinct accepted triangles. In practice the lists \(d_L\) are sparse, so \(n=10^6\) is feasible in compiled code.
Für ein Dreieck \(\Delta\) mit ganzzahligen Seiten sei \(s(\Delta)\) die Seitenlänge des kleinsten Quadrats, das \(\Delta\) nach Rotation und Translation in der Ebene enthalten kann. Project Euler 998 verlangt die Summe der Umfänge aller verschiedenen ganzzahligen Dreiecke, deren minimales umschließendes Quadrat Seitenlänge höchstens \(10^6\) hat. Die Werte \(T(40)=346\), \(T(400)=76402\) und \(T(2000)=3237036\) dienen als Kontrollpunkte.
Fixiere ein Quadrat der Seitenlänge \(L\) und drehe die gesamte Figur so, dass das Quadrat achsenparallel ist. Ein Dreieck, das für dieses Quadrat straff sitzt, berührt den Rand. Wenn eine seiner Seiten das Quadrat mit horizontaler oder vertikaler Spannweite \(L\) überquert, ist diese Seite die Hypotenuse eines rechtwinkligen Dreiecks mit Katheten \(L\) und einem Versatz \(p\). Ihre Länge ist also genau dann ganzzahlig, wenn
\[ h^2=L^2+p^2. \]
Das ist die erste wesentliche Reduktion: Statt beliebige Dreiecke zu durchsuchen, enumerieren wir pythagoreische Randsegmente zu jeder möglichen Quadratseite \(L\). Für jedes \(L\) speichert das Programm Paare \((p,h)\), wobei \(0\le p\le L\) und \(h=\sqrt{L^2+p^2}\) ganzzahlig ist. Die Einschränkung \(p\le L\) ist ohne Verlust, da die komplementäre Orientierung symmetrisch ist.
Die Enumeration beruht auf einer Normalform. Sei \(Q\) ein minimales Quadrat für ein Dreieck. Nach einer Drehung gilt \(Q=[0,L]\times[0,L]\). In einem nicht entarteten Minimum können nicht alle Eckpunkte in einem kleineren homothetischen Quadrat liegen; daher sind mindestens zwei gegenüberliegende oder zwei benachbarte Stützgeraden aktiv. Bei einem Dreieck ändern sich die stützenden Eckpunkte nur dann, wenn eine Dreiecksseite parallel zu einer Quadratseite wird. Jede kritische Lage kann also durch Randsehnen beschrieben werden, deren Koordinatenspannen durch \(L\) und einen Randversatz bestimmt sind.
Lemma 1. Verbindet eine Seite einer kritischen Lage zwei Randgeraden mit Abstand \(L\), so ist ihre ganzzahlige Länge äquivalent zur Bedingung \(h^2=L^2+p^2\). Dies folgt direkt aus der orthogonalen Projektion: Der Seitenvektor besitzt, bis auf Vorzeichen, die Komponenten \(L\) und \(p\). Umgekehrt kann jedes solche pythagoreische Segment auf den Rand des Quadrats gelegt werden und ist damit ein zulässiger Baustein für ein Kandidatendreieck.
Lemma 2. Werden zwei Randsegmente derselben Quadratseite \(L\) kombiniert, bleiben nur zwei kombinatorische Abschlüsse. Entweder liegt die letzte Dreiecksseite auf dem Quadratrand und hat Länge \(p+q\), oder sie verbindet die beiden gegenüberliegenden Restendpunkte und hat Quadrat \((L-p)^2+(L-q)^2\). Genau diese zwei Familien prüft das Programm. Ein dritter Abschluss existiert nicht, weil nach Fixierung der ersten beiden Randsehnen die drei Dreiecksecken bereits durch die gewählten Randendpunkte bestimmt sind.
Die Ungleichung \(pq\ge L(L-p-q)\) ist die algebraische Form der Innenbedingung für den ersten Abschluss. Man erhält sie, indem man die beiden Randsehnen in Koordinaten schreibt, die von den Randendpunkten ausgehenden Stützstrahlen schneidet und verlangt, dass die Schnittkoordinate im Quadrat bleibt. Dadurch wird die geometrische Zulässigkeit zu einem einzigen ganzzahligen Vergleich.
Die Versätze werden mit der euklidischen Formel erzeugt. Primitive Tripel sind
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
mit \(\gcd(m,n)=1\) und ungeradem \(m-n\). Danach wird jedes primitive Tripel mit \(k\) skaliert. Jede Kathete kann die Quadratseite \(L\) sein, die andere Kathete ist dann der Versatz. Daher fügt der Code sowohl \((L,p,h)=(ka,kb,kc)\) als auch \((kb,ka,kc)\) ein, sofern der Versatz nicht größer als die Seite ist. Da die relevante Kathete höchstens \(L\le10^6\) ist, genügt es, die euklidischen Parameter bis \(\sqrt{2L}+2\) zu testen. Duplikate werden pro festem \(L\) nach Sortierung entfernt.
Wähle zwei pythagoreische Randsegmente derselben Quadratseite \(L\): \((p,h_p)\) und \((q,h_q)\). Die erste Familie entsteht, wenn die verbleibende Dreiecksseite auf einer Quadratseite liegt. Ihre Länge ist
\[ b=p+q. \]
Damit die Endpunkte auf dem Randsegment liegen, muss \(b\le L\) gelten. Außerdem darf der dritte Eckpunkt nicht außerhalb des \(L\times L\)-Quadrats liegen. In den Randkoordinaten der Implementierung reduziert sich diese Zulässigkeitsbedingung auf
\[ pq\ge L(L-b). \]
Gelten beide Ungleichungen, ist \((b,h_p,h_q)\) ein gültiges ganzzahliges Dreieck mit umschließendem Quadrat der Seitenlänge \(L\). Sein Umfang wird nach kanonischer Sortierung der Seiten addiert.
Dieselben zwei Randsegmente können auch über das gegenüberliegende Endpunktpaar geschlossen werden. Die verbleibende Verschiebung hat Katheten \(L-p\) und \(L-q\), also ist die dritte Seite genau dann ganzzahlig, wenn
\[ r^2=(L-p)^2+(L-q)^2. \]
Das ergibt den Kandidaten \((h_p,h_q,r)\). Anders als bei der ersten Familie beweist die Konstruktion allein nicht, dass \(L\) die minimale Quadratseite ist. Dasselbe Seitentripel könnte nach anderer Rotation in ein kleineres Quadrat passen. Deshalb wird jeder Kandidat dieser Familie mit einem unabhängigen Minimum-Quadrat-Prüfer getestet und nur akzeptiert, wenn der geprüfte Wert bis auf numerische Toleranz mindestens \(L\) ist.
Für ein Dreieck mit Seiten \(a\le b\le c\) wird die Seite \(c\) auf die \(x\)-Achse gelegt. Der dritte Punkt folgt aus dem Kosinussatz:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
Bei einem Drehwinkel \(\theta\) werden die drei Eckpunkte auf die gedrehten Achsen \(u\) und \(v\) projiziert. Die kleinste achsenparallele Quadratseite für diesen Winkel ist
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
Die stützenden Eckpunkte für Maxima und Minima ändern sich nur, wenn eine Dreiecksseite parallel zu einer Quadratseite wird. Daher wird \([0,\pi/2)\) an den Kantenrichtungen zerlegt. Innerhalb eines Intervalls sind beide Breiten feste sinusförmige Ausdrücke. Das Optimum liegt an einer Grenze oder an einem inneren Winkel, bei dem beide Breiten gleich sind. minimum_square prüft genau diese Kandidaten; das ist die Rotating-Calipers-Idee für drei Punkte.
Ein Dreieck kann über mehrere Quadratseiten, beide Endpunktordnungen oder beide geometrischen Familien entstehen. Gezählt werden aber verschiedene Dreiecke. Deshalb sortiert das Programm jedes Seitentripel und packt es in einen ganzzahligen Schlüssel. Alle Seitenlängen liegen unter \(2^{21}\), also ist
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
für den Zielbereich kollisionsfrei. Der Umfang wird nur beim ersten Auftreten eines Schlüssels addiert.
Korrektheit der erzeugten Kandidaten. Jedes akzeptierte Dreieck ist konstruktionsbedingt ganzzahlig. In der ersten Familie sind die Seiten \(p+q\), \(h_p\) und \(h_q\); die pythagoreischen Gleichungen liefern ganzzahlige Hypotenusen, und die Zulässigkeitsungleichung garantiert eine Lage im Quadrat. In der zweiten Familie macht der Quadrattest \(r\) ganzzahlig, und minimum_square prüft, dass das Seitentripel nicht zu einem kleineren umschließenden Quadrat gehört. Somit erfüllt jedes eingefügte Dreieck \(s(\Delta)\le L\le n\).
Vollständigkeit. Sei umgekehrt ein ganzzahliges Dreieck mit \(s(\Delta)\le n\) gegeben, und lege es in ein minimales Quadrat mit \(L=s(\Delta)\). Nach der Normalform gibt es mindestens zwei straffe Seiten-Sehnen, die pythagoreische Randsegmente derselben Quadratseite \(L\) sind. Die verbleibenden Endpunkte schließen sich auf eine der beiden in Lemma 2 beschriebenen Arten. Daher wird das Dreieck von der entsprechenden Iteration des Algorithmus erzeugt. Mehrfach erzeugte Lagen werden durch den kanonischen Schlüssel zusammengeführt.
Numerische Robustheit. Enumeration, Quadrattests, Umfangssummen und Schlüsselbildung sind exakte Ganzzahloperationen. Gleitkommazahlen treten nur im sekundären Prüfer der zweiten Familie auf. Dieser Prüfer wertet alle kritischen Winkel einer Drei-Punkte-Menge aus und vergleicht mit \(L\) unter kleiner Toleranz; die veröffentlichten Kontrollwerte sichern zusätzlich gegen verpasste Kandidaten und falsche Annahmen ab.
pythagorean_offsets erzeugt alle zulässigen pythagoreischen Randsegmente für jedes \(L\le n\). Die Hauptschleife in solve betrachtet danach alle ungeordneten Segmentpaare zum selben \(L\). Sie testet die erste Familie mit der algebraischen Ungleichung, die zweite Familie mit Quadrattest und minimum_square, und trägt jedes akzeptierte Seitentripel in die globale Menge ein. Die drei veröffentlichten Kontrollwerte werden vor der Ausgabe des Zielwertes geprüft.
Sei \(d_L\) die Anzahl der gespeicherten Versätze zur Seite \(L\). Nach der Tripelerzeugung ist die Laufzeit
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
weil jedes ungeordnete Paar gleicher Quadratseite einmal geprüft wird. Der Speicherbedarf ist \(O(\sum d_L+u)\), wobei \(u\) die Anzahl der akzeptierten verschiedenen Dreiecke ist. In der Praxis sind die Listen \(d_L\) dünn besetzt, sodass \(n=10^6\) in kompilierter Sprache gut machbar ist.
Kenarları tamsayı olan bir üçgen \(\Delta\) için \(s(\Delta)\), üçgen düzlemde döndürülüp ötelenebildikten sonra onu içine alabilen en küçük karenin kenar uzunluğu olsun. Project Euler 998, minimum çevreleyen karesi en fazla \(10^6\) olan tüm farklı tamsayı kenarlı üçgenlerin çevreleri toplamını soruyor. \(T(40)=346\), \(T(400)=76402\) ve \(T(2000)=3237036\) değerleri doğrulama noktaları olarak kullanılıyor.
Kenar uzunluğu \(L\) olan bir kare sabitleyelim ve tüm şekli kare eksenlere paralel olacak şekilde döndürelim. Bu kare için sıkı oturan bir üçgenin köşeleri sınır üzerindedir. Üçgenin bir kenarı kareyi yatay veya düşey açıklığı \(L\) olacak şekilde kesiyorsa, bu kenar dik üçgenin hipotenüsüdür; dik kenarlar \(L\) ve bir \(p\) ofsetidir. Dolayısıyla uzunluk tam sayı ise
\[ h^2=L^2+p^2 \]
olmalıdır. İlk büyük indirgeme budur: Rastgele üçgenleri aramak yerine her olası kare kenarı \(L\) için Pisagor sınır parçalarını listeleriz. Program her \(L\) için \((p,h)\) çiftleri saklar; burada \(0\le p\le L\) ve \(h=\sqrt{L^2+p^2}\) tamsayıdır. \(p\le L\) kısıtı bilgi kaybettirmez, çünkü tamamlayıcı yönelim simetriktir.
Sayımın dayanağı bir normal form ifadesidir. \(Q\), bir üçgen için minimum kare olsun. Düzlemi döndürdükten sonra \(Q=[0,L]\times[0,L]\) yazabiliriz. Dejenere olmayan bir minimumda tüm köşeler daha küçük benzer bir karenin içinde kalamaz; bu nedenle en az iki karşıt destek doğrusu veya iki komşu destek doğrusu aktiftir. Üçgende maksimum ve minimum izdüşümü veren köşeler yalnızca bir kenar kare kenarına paralel olduğunda değişir. Böylece her kritik yerleşim, koordinat açıklıkları \(L\) ve bir sınır ofsetiyle belirlenen sınır kirişleriyle temsil edilebilir.
Lemma 1. Kritik yerleşimdeki bir kenar, aralarında \(L\) mesafe bulunan iki sınır doğrusunu bağlıyorsa, bu kenarın tamsayı uzunlukta olması \(h^2=L^2+p^2\) koşuluna denktir. Çünkü kenar vektörünün dik izdüşüm bileşenleri, işaretler dışında, \(L\) ve \(p\)'dir. Ters yönde de böyle bir Pisagor parçası kare sınırına yerleştirilebilir; dolayısıyla aday üçgenler için geçerli bir yapı taşıdır.
Lemma 2. Aynı kare kenarı \(L\)'ye ait iki sınır parçası eşleştirildiğinde yalnızca iki kapanış kalır. Ya son üçgen kenarı kare sınırı üzerinde yer alır ve uzunluğu \(p+q\) olur, ya da iki karşı artık uç noktayı bağlar ve karesi \((L-p)^2+(L-q)^2\) olur. Programın test ettiği iki aile tam olarak bunlardır. Üçüncü bir kapanış yoktur; çünkü ilk iki sınır kirişi sabitlendiğinde üçgenin üç köşesi seçilen sınır uçlarıyla belirlenmiştir.
\(pq\ge L(L-p-q)\) eşitsizliği, birinci kapanışın kare içinde kalma şartının cebirsel biçimidir. İki sınır kirişi koordinatlarla yazılıp sınır uçlarından çıkan destek ışınları kesiştirildiğinde, kesişim koordinatının karenin içinde kalması bu eşitsizliğe dönüşür. Böylece geometrik uygunluk, kayan nokta kullanmadan tek bir tamsayı karşılaştırmasıyla denetlenir.
Ofsetler Öklid formülüyle üretilir. İlkel üçlüler
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2 \]
şeklindedir; \(\gcd(m,n)=1\) ve \(m-n\) tek olmalıdır. Sonra her ilkel üçlü \(k\) ile ölçeklenir. Dik kenarlardan herhangi biri kare kenarı \(L\) olabilir, diğer dik kenar ofset olur. Bu yüzden kod, ofset kenardan büyük olmadığı sürece hem \((L,p,h)=(ka,kb,kc)\) hem de \((kb,ka,kc)\) ekler. İlgili dik kenar en fazla \(L\le10^6\) olduğundan Öklid parametrelerini \(\sqrt{2L}+2\) sınırına kadar denemek yeterlidir. Aynı \(L\) için tekrar eden çiftler sıralanıp silinir.
Aynı kare kenarı \(L\) için iki Pisagor sınır parçası seçelim: \((p,h_p)\) ve \((q,h_q)\). Birinci aile, üçgenin kalan kenarı karenin bir kenarı üzerinde yer aldığında elde edilir. Bu kenarın uzunluğu
\[ b=p+q \]
olur. Uç noktaların sınır parçası üzerinde kalması için \(b\le L\) gerekir. Üçüncü köşenin de \(L\times L\) karenin dışına taşmaması gerekir. Uygulamada kullanılan sınır koordinatlarında bu uygunluk koşulu
\[ pq\ge L(L-b) \]
eşitsizliğine indirgenir. İki koşul da sağlanıyorsa \((b,h_p,h_q)\), çevreleyen karesi \(L\) olan geçerli bir tamsayı kenarlı üçgendir. Kenarlar sıralanarak kanonik anahtar oluşturulur ve çevre buna göre eklenir.
Aynı iki Pisagor parçası, karşı uç noktalar üzerinden de kapanabilir. Kalan yer değiştirme vektörünün dik kenarları \(L-p\) ve \(L-q\) olur. Bu durumda üçüncü kenarın tamsayı olması için
\[ r^2=(L-p)^2+(L-q)^2 \]
gerekir. Böylece \((h_p,h_q,r)\) adayı doğar. Birinci aileden farklı olarak bu inşa tek başına minimum kare kenarının \(L\) olduğunu kanıtlamaz. Aynı kenar üçlüsü başka bir döndürmeyle daha küçük kareye sığabilir. Bu yüzden bu aileden gelen her aday bağımsız minimum_square denetiminden geçer ve doğrulanan değer küçük sayısal toleransla en az \(L\) ise kabul edilir.
Kenarları \(a\le b\le c\) olan bir üçgende \(c\) kenarı \(x\)-ekseni üzerine yerleştirilir. Üçüncü köşe kosinüs teoreminden bulunur:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
\(\theta\) kadar döndürülmüş bir kare için üç köşe döndürülmüş \(u\) ve \(v\) eksenlerine izdüşürülür. Bu açıda gereken en küçük eksenlere paralel kare kenarı
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\} \]
olur. Maksimum ve minimum izdüşümleri veren köşeler yalnızca bir üçgen kenarı kare eksenlerinden birine paralel olduğunda değişebilir. Bu yüzden \([0,\pi/2)\) aralığı kenar yönlerine göre bölünür. Her aralık içinde iki genişlik de sabit destek köşelerine sahip sinüzoidal ifadelerdir. En iyi açı ya aralık sınırındadır ya da iki genişliğin eşit olduğu iç noktadadır. minimum_square tam olarak bu adayları dener; bu, üç nokta için özelleştirilmiş rotating-calipers yaklaşımıdır.
Aynı üçgen farklı kare kenarlarından, iki uç nokta sıralamasından veya iki geometrik aileden üretilebilir. Problem ise farklı üçgenleri sayar. Bu nedenle program her kenar üçlüsünü sıralayıp tek bir tamsayı anahtara paketler. Hedef aralıkta kenarlar \(2^{21}\)'den küçük olduğundan
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
anahtarı çakışmasızdır. Çevre yalnızca anahtar ilk kez görüldüğünde toplam değere eklenir.
Sağlamlık. Kabul edilen her üçgen inşa gereği tamsayı kenarlıdır. Birinci ailede kenarlar \(p+q\), \(h_p\) ve \(h_q\)'dur; Pisagor denklemleri hipotenüsleri tamsayı yapar, uygunluk eşitsizliği de yerleşimin kare içinde kaldığını garanti eder. İkinci ailede ek kare testi \(r\)'yi tamsayı yapar; minimum_square ise aynı kenar üçlüsünün daha küçük bir çevreleyen kareye ait olmadığını doğrular. Dolayısıyla eklenen her üçgen \(s(\Delta)\le L\le n\) koşulunu sağlar.
Tamlık. Tersine, \(s(\Delta)\le n\) olan herhangi bir tamsayı kenarlı üçgeni alıp \(L=s(\Delta)\) kenarlı minimum karesine yerleştirelim. Normal formdan, aynı \(L\) için en az iki sıkı kenar kirişinin Pisagor sınır parçası olduğu çıkar. Kalan uç noktalar Lemma 2'deki iki kapanıştan biriyle birleşir. Bu yüzden üçgen algoritmanın ilgili yinelemesinde üretilir. Birden çok yerleşimden gelirse kanonik anahtar tek kopyayı tutar.
Sayısal güvenilirlik. Üretim, kare testleri, çevre toplamları ve tekilleştirme anahtarları tamamen tamsayı işlemleridir. Kayan nokta yalnızca ikinci ailedeki bağımsız doğrulayıcıda kullanılır. Bu doğrulayıcı üç noktalı kümenin tüm kritik açılarını değerlendirir ve \(L\) ile küçük tolerans altında karşılaştırır; yayınlanan kontrol değerleri de kaçan adaylara ve hatalı kabullere karşı uçtan uca güvence sağlar.
pythagorean_offsets, her \(L\le n\) için tüm uygun Pisagor sınır parçalarını oluşturur. Ana solve döngüsü aynı \(L\)'ye bağlı sırasız tüm parça çiftlerini gezer. Birinci aileyi yukarıdaki cebirsel eşitsizlikle, ikinci aileyi kare kontrolü ve minimum_square ile test eder; kabul edilen her kenar üçlüsünü küresel kümeye ekler. Yayınlanan üç doğrulama değeri hedef sonuç basılmadan önce assert edilir.
\(d_L\), \(L\) kenarı için saklanan Pisagor ofsetlerinin sayısı olsun. Üçlü üretiminden sonra çalışma süresi
\[ O\!\left(\sum_{L\le n} d_L^2\right) \]
çünkü aynı kare kenarına ait her sırasız ofset çifti bir kez test edilir. Bellek kullanımı \(O(\sum d_L+u)\) düzeyindedir; burada \(u\), kabul edilen farklı üçgenlerin sayısıdır. Pratikte \(d_L\) listeleri seyrektir, bu yüzden \(n=10^6\) derlenmiş dilde rahatça işlenir.
Para un triángulo \(\Delta\) con lados enteros, sea \(s(\Delta)\) la longitud del lado del menor cuadrado que puede contener a \(\Delta\) después de rotarlo y trasladarlo en el plano. Project Euler 998 pide la suma de los perímetros de todos los triángulos enteros distintos cuyo cuadrado envolvente mínimo tiene lado como máximo \(10^6\). Los valores \(T(40)=346\), \(T(400)=76402\) y \(T(2000)=3237036\) se usan como puntos de control.
Fijemos un cuadrado de lado \(L\) y rotemos toda la configuración para que el cuadrado quede alineado con los ejes. Un triángulo ajustado a ese cuadrado tiene vértices sobre la frontera. Si uno de sus lados cruza el cuadrado con anchura horizontal o vertical \(L\), ese lado es la hipotenusa de un triángulo rectángulo con catetos \(L\) y un desplazamiento \(p\). Por tanto su longitud es entera exactamente cuando
\[ h^2=L^2+p^2. \]
Esta es la primera reducción importante: en lugar de buscar triángulos arbitrarios, enumeramos segmentos pitagóricos asociados a cada posible lado \(L\) del cuadrado. Para cada \(L\), el programa guarda pares \((p,h)\), donde \(0\le p\le L\) y \(h=\sqrt{L^2+p^2}\) es entero. La restricción \(p\le L\) no pierde casos, porque la orientación complementaria es simétrica.
La enumeración se basa en una forma normal. Sea \(Q\) un cuadrado mínimo para un triángulo. Tras rotar el plano podemos escribir \(Q=[0,L]\times[0,L]\). En un mínimo no degenerado no pueden quedar todos los vértices dentro de un cuadrado homotético menor; por tanto, al menos dos rectas de soporte opuestas o dos rectas de soporte adyacentes están activas. En un triángulo, los vértices que realizan las proyecciones extremas solo cambian cuando una arista se vuelve paralela a un lado del cuadrado. Así, cada colocación crítica puede representarse por cuerdas de frontera cuyas componentes están determinadas por \(L\) y por un desplazamiento de borde.
Lema 1. Si un lado de una colocación crítica conecta dos líneas de frontera separadas por \(L\), entonces que su longitud sea entera equivale a la condición pitagórica \(h^2=L^2+p^2\). Esto se obtiene por proyección ortogonal: el vector del lado tiene componentes \(L\) y \(p\), salvo signos. Recíprocamente, todo segmento pitagórico de este tipo puede colocarse en la frontera del cuadrado y por tanto es un bloque válido para un triángulo candidato.
Lema 2. Al emparejar dos segmentos de frontera del mismo lado \(L\), solo quedan dos cierres combinatorios. O bien el lado restante del triángulo está sobre la frontera del cuadrado y mide \(p+q\), o bien une los dos extremos residuales opuestos y tiene cuadrado \((L-p)^2+(L-q)^2\). Estas son exactamente las dos familias probadas por el programa. No existe un tercer cierre, porque una vez fijadas las dos primeras cuerdas de frontera los tres vértices del triángulo quedan determinados por los extremos elegidos.
La desigualdad \(pq\ge L(L-p-q)\) es la forma algebraica de la condición de estar dentro del cuadrado para el primer cierre. Se obtiene escribiendo las dos cuerdas de frontera en coordenadas, intersectando los rayos de soporte que salen de los extremos de frontera y exigiendo que la coordenada de intersección permanezca en el cuadrado. Esto convierte la factibilidad geométrica en una sola comparación entera.
Los desplazamientos se generan con la fórmula de Euclides. Las ternas primitivas son
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
con \(\gcd(m,n)=1\) y \(m-n\) impar. Después cada terna primitiva se escala por \(k\). Cualquiera de los dos catetos puede ser el lado del cuadrado \(L\), y el otro cateto se convierte en desplazamiento. Por eso el código inserta tanto \((L,p,h)=(ka,kb,kc)\) como \((kb,ka,kc)\) siempre que el desplazamiento no supere al lado. Como el cateto relevante es a lo sumo \(L\le10^6\), basta probar los parámetros de Euclides hasta \(\sqrt{2L}+2\). Los duplicados se eliminan después de ordenar la lista de cada \(L\).
Tomemos dos segmentos pitagóricos de frontera para el mismo lado \(L\): \((p,h_p)\) y \((q,h_q)\). La primera familia aparece cuando el lado restante del triángulo queda sobre un lado del cuadrado. Su longitud es
\[ b=p+q. \]
Para que los extremos estén dentro del segmento de frontera necesitamos \(b\le L\). Además, el tercer vértice debe quedar dentro del cuadrado \(L\times L\). En las coordenadas de frontera utilizadas por la implementación, esta condición de factibilidad se simplifica a
\[ pq\ge L(L-b). \]
Cuando ambas desigualdades se cumplen, \((b,h_p,h_q)\) es un triángulo entero válido cuyo cuadrado envolvente tiene lado \(L\). Su perímetro se suma después de ordenar los tres lados y formar una clave canónica.
Los mismos dos segmentos pitagóricos también pueden cerrarse usando el par opuesto de extremos. El desplazamiento restante tiene catetos \(L-p\) y \(L-q\), de modo que el tercer lado es entero exactamente cuando
\[ r^2=(L-p)^2+(L-q)^2. \]
Esto da el candidato \((h_p,h_q,r)\). A diferencia de la primera familia, la construcción no demuestra por sí sola que \(L\) sea el lado mínimo del cuadrado envolvente. El mismo triple de lados podría caber en un cuadrado menor tras otra rotación. Por ello cada candidato de esta familia se envía a un verificador independiente de cuadrado mínimo y se acepta solo si el valor verificado es al menos \(L\), con una pequeña tolerancia numérica.
Para un triángulo con lados \(a\le b\le c\), colocamos el lado \(c\) sobre el eje \(x\) y calculamos el tercer vértice mediante la ley de cosenos:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
Para un ángulo de rotación \(\theta\), proyectamos los tres vértices sobre los ejes rotados \(u\) y \(v\). El lado del menor cuadrado alineado con esos ejes es
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
Los vértices que realizan máximos y mínimos solo cambian cuando una arista queda paralela a uno de los ejes del cuadrado. Por tanto el intervalo \([0,\pi/2)\) se divide por las direcciones de las aristas. Dentro de cada intervalo, las dos anchuras son expresiones sinusoidales fijas. El óptimo está en una frontera o en un ángulo interior donde las dos anchuras son iguales. minimum_square evalúa exactamente esos candidatos, que es la idea de rotating calipers especializada a tres puntos.
Un triángulo puede aparecer por varios lados de cuadrado, por ambos órdenes de extremos o por las dos familias geométricas. El problema cuenta triángulos distintos. Por eso el programa ordena cada triple de lados y lo empaqueta en una clave entera. En el rango objetivo todos los lados son menores que \(2^{21}\), así que
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
no tiene colisiones. El perímetro se añade únicamente la primera vez que aparece una clave.
Solidez. Cada triángulo aceptado tiene lados enteros por construcción. En la primera familia, los lados son \(p+q\), \(h_p\) y \(h_q\); las ecuaciones pitagóricas garantizan hipotenusas enteras y la desigualdad de factibilidad garantiza una colocación dentro del cuadrado. En la segunda familia, la prueba de cuadrado hace que \(r\) sea entero, y minimum_square verifica que el triple de lados no pertenece a un cuadrado envolvente menor. Por tanto, cada triángulo insertado cumple \(s(\Delta)\le L\le n\).
Completitud. Tomemos cualquier triángulo entero con \(s(\Delta)\le n\) y coloquémoslo en un cuadrado mínimo de lado \(L=s(\Delta)\). Por la forma normal, al menos dos cuerdas tensas son segmentos pitagóricos de frontera para el mismo \(L\). Sus extremos restantes se cierran de una de las dos formas descritas en el Lema 2. Así, el triángulo se genera en la iteración correspondiente del algoritmo. Si aparece por varias colocaciones, la clave canónica conserva una sola copia.
Robustez numérica. La enumeración, las pruebas de cuadrados, las sumas de perímetros y las claves de deduplicación son operaciones enteras exactas. Los números de punto flotante solo se usan en el verificador secundario de la segunda familia. Ese verificador evalúa todos los ángulos críticos de un conjunto de tres puntos y compara con \(L\) usando una pequeña tolerancia; los puntos de control publicados proporcionan una prueba integral contra candidatos omitidos y falsos positivos.
pythagorean_offsets construye la lista de todos los segmentos pitagóricos admisibles para cada \(L\le n\). El bucle principal de solve considera después todos los pares no ordenados de segmentos asociados al mismo \(L\). Prueba la primera familia con la desigualdad algebraica, prueba la segunda con una comprobación de cuadrado y minimum_square, e inserta cada triple aceptado en el conjunto global. Los tres puntos de control publicados se verifican antes de imprimir el valor objetivo.
Sea \(d_L\) el número de desplazamientos pitagóricos guardados para el lado \(L\). Tras generar las ternas, el tiempo es
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
porque cada par no ordenado de desplazamientos para el mismo \(L\) se prueba una vez. La memoria es \(O(\sum d_L+u)\), donde \(u\) es el número de triángulos distintos aceptados. En la práctica las listas \(d_L\) son dispersas, por lo que \(n=10^6\) es viable en código compilado.
对于边长均为整数的三角形 \(\Delta\)，令 \(s(\Delta)\) 表示在平面内允许旋转和平移后，能够包含 \(\Delta\) 的最小正方形边长。Project Euler 998 要求把所有满足 \(s(\Delta)\le10^6\) 的不同整数边三角形的周长求和。已知的 \(T(40)=346\)、\(T(400)=76402\)、\(T(2000)=3237036\) 用作程序校验点。
固定一个边长为 \(L\) 的正方形，并把整个构型旋转到正方形与坐标轴平行。对于一个被这个正方形紧包住的三角形，它的顶点会落在边界上。若三角形的一条边以水平或竖直跨度 \(L\) 穿过正方形，则这条边是一个直角三角形的斜边，两个直角边分别为 \(L\) 和某个偏移量 \(p\)。因此它的长度为整数当且仅当
\[ h^2=L^2+p^2. \]
这给出了第一个关键降维：我们不枚举任意三角形，而是对每个可能的正方形边长 \(L\) 枚举对应的毕达哥拉斯边界线段。程序为每个 \(L\) 保存 \((p,h)\)，其中 \(0\le p\le L\)，且 \(h=\sqrt{L^2+p^2}\) 为整数。限制 \(p\le L\) 不会丢失情况，因为互补方向由对称性覆盖。
枚举的基础是一个规范形命题。设 \(Q\) 是某个三角形的最小外包正方形。旋转平面后，可令 \(Q=[0,L]\times[0,L]\)。在非退化最小情形中，所有顶点不可能同时位于更小的相似正方形内部；因此至少有两条相对支撑线或两条相邻支撑线处于紧约束状态。对于三角形，给出极值投影的支撑顶点只有在某条边与正方形边平行时才会变化。因此每个临界位置都可由边界弦表示，其坐标跨度由 \(L\) 和一个边界偏移量确定。
引理 1。 若临界位置中的一条边连接两条相距 \(L\) 的边界直线，那么这条边长度为整数等价于毕达哥拉斯条件 \(h^2=L^2+p^2\)。这是正交投影的直接结果：该边向量的两个分量在符号外分别为 \(L\) 和 \(p\)。反过来，每个这样的毕达哥拉斯线段都能放在正方形边界上，因此是合法的候选三角形构件。
引理 2。 对同一个正方形边长 \(L\) 配对两个边界线段后，只剩两种组合闭合方式。剩余边要么位于正方形边界上且长度为 \(p+q\)，要么连接两个相对的剩余端点且平方长度为 \((L-p)^2+(L-q)^2\)。程序检测的正是这两类。不存在第三种闭合，因为前两条边界弦固定后，三角形的三个顶点已经由所选边界端点决定。
不等式 \(pq\ge L(L-p-q)\) 是第一种闭合位于正方形内部的代数形式。把两条边界弦写成坐标形式，求从边界端点出发的支撑射线交点，并要求交点坐标仍在正方形内，即可得到该不等式。这样几何可行性被转化成一次精确整数比较。
偏移量通过欧几里得公式生成。原始三元组为
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
其中 \(\gcd(m,n)=1\)，并且 \(m-n\) 为奇数。随后将每个原始三元组乘以比例 \(k\)。两个直角边中的任意一个都可以作为正方形边长 \(L\)，另一个成为偏移量。因此代码在偏移量不大于边长时同时插入 \((L,p,h)=(ka,kb,kc)\) 和 \((kb,ka,kc)\)。由于相关直角边最多为 \(L\le10^6\)，欧几里得参数只需测试到 \(\sqrt{2L}+2\)。每个固定 \(L\) 的列表排序后去重。
对同一个正方形边长 \(L\)，选取两个毕达哥拉斯边界线段 \((p,h_p)\) 和 \((q,h_q)\)。当三角形的剩余边位于正方形的一条边上时，得到第一类三角形。该边长度为
\[ b=p+q. \]
为了让端点落在边界线段内，需要 \(b\le L\)。同时第三个顶点也必须位于 \(L\times L\) 正方形内。在实现使用的边界坐标中，这个可行性条件化简为
\[ pq\ge L(L-b). \]
当两个不等式都成立时，\((b,h_p,h_q)\) 是一个有效的整数边三角形，其外包正方形边长为 \(L\)。程序将三条边排序为规范键后加入周长。
同样的两个毕达哥拉斯线段也可以通过另一对相对端点闭合。剩余位移的两个直角边为 \(L-p\) 和 \(L-q\)，所以第三边为整数当且仅当
\[ r^2=(L-p)^2+(L-q)^2. \]
于是得到候选三角形 \((h_p,h_q,r)\)。与第一类不同，这个构造本身不能证明 \(L\) 就是最小外包正方形边长；同一个边长三元组经过另一种旋转可能放入更小的正方形。因此这类候选都会交给独立的最小正方形验证器，只有验证值在小的浮点容差内不小于 \(L\) 时才被接受。
给定边长 \(a\le b\le c\) 的三角形，把边 \(c\) 放在 \(x\) 轴上，第三个顶点由余弦定理给出：
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
对于旋转角 \(\theta\)，将三个顶点投影到旋转后的 \(u\)、\(v\) 轴上。该角度下所需的最小轴对齐正方形边长为
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
决定最大和最小投影的支撑顶点只会在某条三角形边与正方形轴平行时发生变化。因此区间 \([0,\pi/2)\) 按边方向分割。在每个区间内部，两种宽度都是支撑顶点固定的正弦表达式。最优值要么在区间边界，要么在两种宽度相等的内部角度处。minimum_square 正是评估这些候选角度，这是 rotating calipers 思想在三个点上的特化。
同一个三角形可能来自多个正方形边长、两种端点顺序，或两类几何构造。题目要求按不同三角形计数，所以程序将每个边长三元组排序并打包成一个整数键。目标范围内所有边长都小于 \(2^{21}\)，因此
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
在该范围内不会碰撞。只有第一次看到某个键时，才把对应周长加入总和。
可靠性。 每个被接受的三角形按构造都有整数边。第一类的边长为 \(p+q\)、\(h_p\)、\(h_q\)，毕达哥拉斯等式保证两个斜边为整数，可行性不等式保证该放置在正方形内。第二类先用平方数检查保证 \(r\) 为整数，再用 minimum_square 验证这个边长三元组不属于更小的外包正方形。因此每个插入的三角形都满足 \(s(\Delta)\le L\le n\)。
完备性。 任取一个满足 \(s(\Delta)\le n\) 的整数边三角形，并把它放入边长 \(L=s(\Delta)\) 的最小正方形。由规范形可知，至少两条紧边界弦是同一 \(L\) 的毕达哥拉斯边界线段。剩余端点只能以引理 2 中的两种方式之一闭合。因此该三角形会在算法对应的迭代中生成。若它由多个位置生成，规范键只保留一份。
数值稳定性。 枚举、平方数检查、周长求和和去重键都是精确整数运算。浮点数只在第二类的辅助验证器中使用。该验证器枚举三点集的所有临界角并以小容差与 \(L\) 比较；公开校验值进一步为漏掉候选和误接收提供端到端保护。
pythagorean_offsets 为每个 \(L\le n\) 构造所有可用的毕达哥拉斯边界线段。主函数 solve 随后枚举同一 \(L\) 下所有无序线段对。第一类用上述代数不等式测试；第二类先检查平方数，再调用 minimum_square；每个通过的边长三元组插入全局集合。三个公开校验值在输出目标答案前都会被断言验证。
设 \(d_L\) 为边长 \(L\) 对应的毕达哥拉斯偏移数量。三元组生成之后，运行时间为
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
因为同一 \(L\) 的每个无序偏移对只测试一次。内存为 \(O(\sum d_L+u)\)，其中 \(u\) 是被接受的不同三角形数量。实际中 \(d_L\) 列表很稀疏，所以 \(n=10^6\) 在编译语言中可行。
Для треугольника \(\Delta\) с целыми сторонами обозначим через \(s(\Delta)\) длину стороны наименьшего квадрата, который может содержать \(\Delta\) после поворота и переноса на плоскости. Project Euler 998 просит найти сумму периметров всех различных целочисленных треугольников, для которых минимальный охватывающий квадрат имеет сторону не больше \(10^6\). Значения \(T(40)=346\), \(T(400)=76402\) и \(T(2000)=3237036\) используются как контрольные проверки.
Зафиксируем квадрат со стороной \(L\) и повернём всю конфигурацию так, чтобы квадрат был параллелен координатным осям. Треугольник, плотно помещённый в такой квадрат, имеет вершины на границе. Если одна из его сторон пересекает квадрат с горизонтальным или вертикальным размахом \(L\), то эта сторона является гипотенузой прямоугольного треугольника с катетами \(L\) и некоторым смещением \(p\). Поэтому её длина целая тогда и только тогда, когда
\[ h^2=L^2+p^2. \]
Это первое важное сокращение: вместо перебора произвольных треугольников мы перечисляем пифагоровы граничные отрезки для каждой возможной стороны квадрата \(L\). Для каждого \(L\) программа хранит пары \((p,h)\), где \(0\le p\le L\), а \(h=\sqrt{L^2+p^2}\) целое. Ограничение \(p\le L\) не теряет решений, потому что дополнительная ориентация покрывается симметрией.
Перечисление опирается на нормальную форму. Пусть \(Q\) - минимальный квадрат для треугольника. После поворота плоскости можно считать, что \(Q=[0,L]\times[0,L]\). В невырожденном минимуме все вершины не могут лежать внутри меньшего гомотетичного квадрата; следовательно, активны как минимум две противоположные или две соседние опорные прямые. Для треугольника вершины, задающие экстремальные проекции, меняются только тогда, когда сторона становится параллельной стороне квадрата. Поэтому каждое критическое положение можно описать граничными хордами, чьи координатные размахи задаются \(L\) и одним граничным смещением.
Лемма 1. Если сторона критического положения соединяет две граничные прямые на расстоянии \(L\), то её целая длина эквивалентна пифагорову условию \(h^2=L^2+p^2\). Это следует из ортогональной проекции: вектор стороны имеет компоненты \(L\) и \(p\), с точностью до знаков. Обратно, любой такой пифагоров отрезок можно разместить на границе квадрата, значит он является допустимым строительным блоком кандидата.
Лемма 2. Если выбрать два граничных отрезка для одной и той же стороны квадрата \(L\), остаются только два комбинаторных замыкания. Либо последняя сторона лежит на границе квадрата и имеет длину \(p+q\), либо она соединяет два противоположных остаточных конца и имеет квадрат длины \((L-p)^2+(L-q)^2\). Именно эти две семьи проверяются в программе. Третьего замыкания нет, потому что после фиксации первых двух граничных хорд три вершины треугольника уже определены выбранными граничными концами.
Неравенство \(pq\ge L(L-p-q)\) является алгебраической формой условия нахождения внутри квадрата для первого замыкания. Оно получается, если записать две граничные хорды в координатах, пересечь опорные лучи из граничных концов и потребовать, чтобы координата пересечения оставалась внутри квадрата. Так геометрическая допустимость становится одной точной целочисленной проверкой.
Смещения строятся по формуле Евклида. Примитивные тройки имеют вид
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
где \(\gcd(m,n)=1\), а \(m-n\) нечётно. Затем каждая примитивная тройка умножается на \(k\). Любой из двух катетов может быть стороной квадрата \(L\), а другой становится смещением. Поэтому код добавляет и \((L,p,h)=(ka,kb,kc)\), и \((kb,ka,kc)\), если смещение не превосходит сторону. Поскольку нужный катет не больше \(L\le10^6\), параметры Евклида достаточно проверять до \(\sqrt{2L}+2\). Дубликаты для каждого фиксированного \(L\) удаляются после сортировки.
Выберем два пифагоровых граничных отрезка для одной и той же стороны квадрата \(L\): \((p,h_p)\) и \((q,h_q)\). Первое семейство получается, когда оставшаяся сторона треугольника лежит на стороне квадрата. Её длина равна
\[ b=p+q. \]
Чтобы концы оставались на граничном отрезке, нужно \(b\le L\). Третья вершина также должна находиться внутри квадрата \(L\times L\). В граничных координатах реализации это условие допустимости упрощается до
\[ pq\ge L(L-b). \]
Если оба неравенства выполнены, \((b,h_p,h_q)\) является допустимым целочисленным треугольником с охватывающим квадратом стороны \(L\). Периметр добавляется после сортировки сторон в канонический ключ.
Те же два пифагоровых отрезка можно замкнуть через противоположную пару концов. Оставшееся смещение имеет катеты \(L-p\) и \(L-q\), поэтому третья сторона целая тогда и только тогда, когда
\[ r^2=(L-p)^2+(L-q)^2. \]
Так получается кандидат \((h_p,h_q,r)\). В отличие от первого семейства, сама конструкция не доказывает, что \(L\) является минимальной стороной охватывающего квадрата. Тот же набор сторон может поместиться в меньший квадрат после другого поворота. Поэтому каждый кандидат этого семейства проверяется независимой процедурой минимального квадрата и принимается только если проверенное значение не меньше \(L\) с малым численным допуском.
Для треугольника со сторонами \(a\le b\le c\) кладём сторону \(c\) на ось \(x\), а третью вершину находим по теореме косинусов:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
Для угла поворота \(\theta\) три вершины проецируются на повернутые оси \(u\) и \(v\). Требуемая сторона наименьшего осевого квадрата при этом угле равна
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
Вершины, задающие максимумы и минимумы проекций, меняются только тогда, когда сторона треугольника становится параллельной одной из осей квадрата. Значит, интервал \([0,\pi/2)\) разбивается направлениями сторон. Внутри каждого интервала обе ширины являются фиксированными синусоидальными выражениями. Оптимум находится либо на границе, либо в внутреннем угле, где две ширины равны. minimum_square проверяет ровно эти кандидаты; это идея rotating calipers, специализированная для трёх точек.
Один и тот же треугольник может быть получен из разных сторон квадрата, из двух порядков концов или из обоих геометрических семейств. Задача считает различные треугольники, поэтому программа сортирует каждую тройку сторон и упаковывает её в целочисленный ключ. В целевом диапазоне стороны меньше \(2^{21}\), следовательно
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
не даёт столкновений. Периметр добавляется только при первом появлении ключа.
Корректность принятых кандидатов. Каждый принятый треугольник имеет целые стороны по построению. В первой семье стороны равны \(p+q\), \(h_p\) и \(h_q\); пифагоровы уравнения дают целые гипотенузы, а неравенство допустимости гарантирует размещение внутри квадрата. Во второй семье проверка квадрата делает \(r\) целым, а minimum_square подтверждает, что тройка сторон не помещается в меньший охватывающий квадрат. Значит, каждый добавленный треугольник удовлетворяет \(s(\Delta)\le L\le n\).
Полнота. Возьмём любой целочисленный треугольник с \(s(\Delta)\le n\) и поместим его в минимальный квадрат стороны \(L=s(\Delta)\). Из нормальной формы следует, что как минимум две натянутые граничные хорды являются пифагоровыми граничными отрезками для того же \(L\). Оставшиеся концы замыкаются одним из двух способов Леммы 2. Следовательно, треугольник будет порождён соответствующей итерацией алгоритма. Если он возникает из нескольких положений, канонический ключ оставляет одну копию.
Численная устойчивость. Перечисление, проверки квадратов, суммы периметров и ключи дедупликации являются точными целочисленными операциями. Вещественная арифметика используется только во вторичном проверяющем для второй семьи. Он перебирает все критические углы трёхточечного множества и сравнивает с \(L\) с малым допуском; опубликованные контрольные значения дают дополнительную сквозную защиту от пропущенных кандидатов и ложных включений.
pythagorean_offsets строит список всех допустимых пифагоровых граничных отрезков для каждого \(L\le n\). Основной цикл solve затем перебирает все неупорядоченные пары отрезков, связанные с одним и тем же \(L\). Первое семейство проверяется алгебраическим неравенством, второе - проверкой на квадрат и вызовом minimum_square; каждая принятая тройка сторон вставляется в глобальное множество. Три опубликованные контрольные точки проверяются перед печатью целевого значения.
Пусть \(d_L\) - число сохранённых пифагоровых смещений для стороны \(L\). После генерации троек время работы равно
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
поскольку каждая неупорядоченная пара смещений для одного \(L\) проверяется один раз. Память равна \(O(\sum d_L+u)\), где \(u\) - число различных принятых треугольников. На практике списки \(d_L\) разрежены, поэтому \(n=10^6\) достижимо в компилируемом коде.
لأي مثلث \(\Delta\) أضلاعه أعداد صحيحة، ليكن \(s(\Delta)\) طول ضلع أصغر مربع يمكن أن يحتوي \(\Delta\) بعد السماح بالدوران والإزاحة في المستوى. تطلب Project Euler 998 مجموع محيطات كل المثلثات الصحيحة المختلفة التي لا يزيد طول ضلع مربعها الحاوي الأدنى عن \(10^6\). القيم \(T(40)=346\)، و \(T(400)=76402\)، و \(T(2000)=3237036\) تستعمل كنقاط تحقق.
نثبت مربعاً طول ضلعه \(L\)، وندير الشكل كله حتى يصبح المربع موازياً للمحاور. المثلث المشدود داخل هذا المربع تكون رؤوسه على الحدود. إذا قطع أحد أضلاع المثلث المربع بامتداد أفقي أو رأسي مقداره \(L\)، فهذا الضلع يكون وتر مثلث قائم ضلعاه القائمان هما \(L\) وإزاحة ما \(p\). لذلك يكون طوله صحيحاً تماماً عندما
\[ h^2=L^2+p^2. \]
هذا هو الاختزال الأول: بدلاً من البحث في مثلثات عشوائية، نعدد القطع الفيثاغورية المرتبطة بكل طول ضلع مربع ممكن \(L\). لكل \(L\) يخزن البرنامج الأزواج \((p,h)\)، حيث \(0\le p\le L\) و \(h=\sqrt{L^2+p^2}\) عدد صحيح. الشرط \(p\le L\) لا يفقد حالات، لأن الاتجاه المكمل مغطى بالتماثل.
يعتمد التعداد على صيغة معيارية. ليكن \(Q\) مربعاً أدنى لمثلث. بعد تدوير المستوى نستطيع كتابة \(Q=[0,L]\times[0,L]\). في حد أدنى غير متدهور لا يمكن أن تقع كل الرؤوس داخل مربع مشابه أصغر؛ لذلك تكون على الأقل مستقيمان داعمان متقابلان أو متجاوران نشطين. في المثلث لا تتغير الرؤوس التي تحقق الإسقاطات القصوى إلا عندما يصبح ضلع موازياً لضلع من أضلاع المربع. لذلك يمكن تمثيل كل وضع حرج بأوتار حدودية تحدد امتداداتها الإحداثية بواسطة \(L\) وإزاحة حدودية واحدة.
اللمّة 1. إذا وصل ضلع في وضع حرج بين مستقيمين حدوديين تفصل بينهما مسافة \(L\)، فإن كونه ذا طول صحيح يكافئ الشرط الفيثاغوري \(h^2=L^2+p^2\). هذا ينتج مباشرة من الإسقاط المتعامد: مركبتا متجه الضلع هما \(L\) و \(p\) حتى الإشارة. وبالعكس، يمكن وضع كل قطعة فيثاغورية من هذا الشكل على حد المربع، ومن ثم فهي لبنة صحيحة لمثلث مرشح.
اللمّة 2. عند إقران قطعتين حدوديتين لنفس ضلع المربع \(L\)، لا يبقى إلا نوعان من الإغلاق. إما أن يقع الضلع الباقي على حد المربع ويكون طوله \(p+q\)، أو أن يصل بين النهايتين المتبقيتين المتقابلتين ويكون مربع طوله \((L-p)^2+(L-q)^2\). هاتان هما العائلتان اللتان يختبرهما البرنامج. لا يوجد إغلاق ثالث، لأن تثبيت الوترين الحدوديين الأولين يحدد رؤوس المثلث الثلاثة بواسطة النهايات المختارة.
المتباينة \(pq\ge L(L-p-q)\) هي الصيغة الجبرية لشرط البقاء داخل المربع في الإغلاق الأول. نحصل عليها بكتابة الوترين الحدوديين بالإحداثيات، وتقاطع الشعاعين الداعمين الخارجين من نهايتي الحد، ثم اشتراط بقاء إحداثي التقاطع داخل المربع. بذلك تتحول القابلية الهندسية إلى مقارنة صحيحة واحدة.
تولد الإزاحات بصيغة إقليدس. الثلاثيات الأولية هي
\[ a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2, \]
مع \(\gcd(m,n)=1\) وأن يكون \(m-n\) فردياً. بعد ذلك تضرب كل ثلاثية أولية في عامل \(k\). يمكن لأي من الضلعين القائمين أن يكون ضلع المربع \(L\)، ويصبح الضلع الآخر هو الإزاحة. لذلك يضيف الكود الحالتين \((L,p,h)=(ka,kb,kc)\) و \((kb,ka,kc)\) متى لم تتجاوز الإزاحة طول الضلع. بما أن الضلع القائم المعني لا يتجاوز \(L\le10^6\)، يكفي اختبار معاملات إقليدس حتى \(\sqrt{2L}+2\). تزال التكرارات بعد فرز قائمة كل \(L\).
نختار قطعتين فيثاغوريتين حدوديتين لنفس ضلع المربع \(L\): \((p,h_p)\) و \((q,h_q)\). تظهر العائلة الأولى عندما يقع الضلع المتبقي من المثلث على أحد أضلاع المربع. طوله هو
\[ b=p+q. \]
حتى تبقى النهايتان داخل قطعة الحد يجب أن يكون \(b\le L\). ويجب أيضاً أن يكون الرأس الثالث داخل مربع \(L\times L\). في إحداثيات الحدود التي يستعملها التنفيذ، تختصر هذه القابلية إلى
\[ pq\ge L(L-b). \]
عند تحقق الشرطين يكون \((b,h_p,h_q)\) مثلثاً صحيح الأضلاع صالحاً، ومربعه الحاوي له ضلع \(L\). يضاف محيطه بعد ترتيب الأضلاع في مفتاح قياسي.
يمكن للقطعتين الفيثاغوريتين نفسيهما أن تغلقا المثلث عبر زوج النهايات المقابل. الإزاحة المتبقية لها ضلعان قائمان \(L-p\) و \(L-q\)، ولذلك يكون الضلع الثالث صحيحاً تماماً عندما
\[ r^2=(L-p)^2+(L-q)^2. \]
ينتج عن ذلك المرشح \((h_p,h_q,r)\). بخلاف العائلة الأولى، لا يثبت البناء وحده أن \(L\) هو ضلع المربع الأدنى. فقد تلائم ثلاثية الأضلاع نفسها مربعاً أصغر بعد دوران آخر. لذلك يمر كل مرشح من هذه العائلة على مدقق مستقل لأصغر مربع، ولا يقبل إلا إذا كانت القيمة المتحققة لا تقل عن \(L\) ضمن سماحية عددية صغيرة.
لمثلث أضلاعه \(a\le b\le c\)، نضع الضلع \(c\) على محور \(x\)، ونحسب الرأس الثالث بقانون جيب التمام:
\[ x=\frac{a^2+c^2-b^2}{2c},\qquad y=\sqrt{a^2-x^2}. \]
عند زاوية دوران \(\theta\)، تسقط الرؤوس الثلاثة على المحورين المدورين \(u\) و \(v\). طول ضلع أصغر مربع موازي لهذين المحورين هو
\[ w(\theta)=\max\{\max u-\min u,\ \max v-\min v\}. \]
الرؤوس التي تحقق القيم العظمى والصغرى لا تتغير إلا عندما يصبح ضلع من أضلاع المثلث موازياً لأحد محوري المربع. لذلك يقسم المجال \([0,\pi/2)\) عند اتجاهات الأضلاع. داخل كل مجال تكون العرضان تعبيرين جيبيين بداعمين ثابتين. تقع القيمة المثلى إما على حد المجال، أو عند زاوية داخلية يتساوى فيها العرضان. الدالة minimum_square تقيم هذه المرشحات بالضبط، وهي فكرة rotating calipers مخصصة لثلاث نقاط.
قد ينتج المثلث نفسه من أطوال مربعات متعددة، أو من ترتيبي نهايات مختلفين، أو من العائلتين الهندسيتين. المسألة تعد المثلثات المختلفة فقط، لذلك يرتب البرنامج كل ثلاثية أضلاع ويضعها في مفتاح صحيح واحد. في مجال الهدف كل الأضلاع أصغر من \(2^{21}\)، وبالتالي فإن
\[ (a\ll 42)\,|\,(b\ll 21)\,|\,c \]
لا يسبب تصادماً. يضاف المحيط فقط عند ظهور المفتاح أول مرة.
سلامة المرشحات. كل مثلث مقبول صحيح الأضلاع بالبناء. في العائلة الأولى تكون الأضلاع \(p+q\)، و \(h_p\)، و \(h_q\)؛ تضمن المعادلات الفيثاغورية أن الوترين صحيحان، وتضمن متباينة القابلية وجود الوضع داخل المربع. في العائلة الثانية يجعل اختبار المربع \(r\) عدداً صحيحاً، وتؤكد minimum_square أن ثلاثية الأضلاع لا تنتمي إلى مربع حاو أصغر. لذلك كل مثلث مدخل يحقق \(s(\Delta)\le L\le n\).
الاكتمال. خذ أي مثلث صحيح الأضلاع له \(s(\Delta)\le n\)، وضعه في مربع أدنى طول ضلعه \(L=s(\Delta)\). من الصيغة المعيارية توجد على الأقل وتران حدوديان مشدودان هما قطعتان فيثاغوريتان لنفس \(L\). النهايات المتبقية تغلق بإحدى الطريقتين في اللمّة 2. ومن ثم سينتج المثلث في التكرار الموافق من الخوارزمية. إذا ظهر من أوضاع متعددة، فإن المفتاح القياسي يحتفظ بنسخة واحدة فقط.
المتانة العددية. التعداد، واختبارات المربعات، وجمع المحيطات، ومفاتيح إزالة التكرار كلها عمليات صحيحة دقيقة. لا تستعمل الفاصلة العائمة إلا في المدقق الثانوي للعائلة الثانية. هذا المدقق يقيم كل الزوايا الحرجة لمجموعة من ثلاث نقاط ويقارن مع \(L\) بسماحية صغيرة؛ كما توفر نقاط التحقق المنشورة اختباراً شاملاً ضد المرشحات المفقودة والقبول الخاطئ.
تبني pythagorean_offsets قائمة كل القطع الفيثاغورية الحدودية المسموحة لكل \(L\le n\). بعد ذلك تمر الحلقة الأساسية في solve على كل أزواج القطع غير المرتبة المرتبطة بنفس \(L\). تختبر العائلة الأولى بالمتباينة الجبرية السابقة، وتختبر العائلة الثانية بفحص مربع كامل ثم minimum_square، وتدخل كل ثلاثية مقبولة في المجموعة العامة. تتحقق نقاط الاختبار المنشورة الثلاث قبل طباعة قيمة الهدف.
ليكن \(d_L\) عدد الإزاحات الفيثاغورية المخزنة للضلع \(L\). بعد توليد الثلاثيات يكون زمن التنفيذ
\[ O\!\left(\sum_{L\le n} d_L^2\right), \]
لأن كل زوج غير مرتب من إزاحات نفس \(L\) يختبر مرة واحدة. الذاكرة هي \(O(\sum d_L+u)\)، حيث \(u\) عدد المثلثات المختلفة المقبولة. عملياً تكون قوائم \(d_L\) متناثرة، ولذلك يكون \(n=10^6\) قابلاً للتنفيذ في لغة مترجمة.