A Pythagorean triplet is a triple of positive integers \((a,b,c)\) satisfying
$$a^2+b^2=c^2.$$
In this problem we also impose the fixed-perimeter condition
$$a+b+c=S,$$
with the sides ordered as \(a \lt b \lt c\). The Project Euler target is \(S=1000\), but the implementations are slightly more general: for any positive perimeter \(S\), they search for an ordered triple and return the corresponding product \(abc\), or \(0\) when no such triple exists.
The core simplification is that the perimeter condition removes one degree of freedom. Once \(a\) and \(b\) are chosen, the hypotenuse is no longer independent, so the search is really over a constrained region in the \((a,b)\)-plane rather than over arbitrary triples.
From the fixed sum we immediately have
$$c=S-a-b.$$
Substitute this into the Pythagorean equation:
$$a^2+b^2=(S-a-b)^2.$$
Expanding and cancelling \(a^2+b^2\) gives
$$0=S^2-2S(a+b)+2ab.$$
Collecting the terms that contain \(b\),
$$2b(S-a)=S(S-2a),$$
so any valid triple must satisfy
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
This identity is useful for two reasons. First, for each fixed \(a\) there is at most one possible value of \(b\). Second, a candidate value of \(a\) works only when the denominator \(2(S-a)\) divides the numerator \(S(S-2a)\). The implementations do not use this closed form directly, but it explains why the brute-force search is so tightly constrained.
The inequalities \(a \lt b \lt c\) combine with \(a+b+c=S\) to produce immediate bounds.
Because \(a\) is the smallest side, we must have
$$3a \lt a+b+c=S,$$
hence
$$a \lt \frac{S}{3}.$$
Likewise, since \(b \lt c=S-a-b\), we get
$$2b \lt S-a,$$
or equivalently
$$b \lt \frac{S-a}{2}.$$
These bounds are exactly what make the direct enumeration practical. The implementation scans \(a\) upward, then scans \(b\) starting at \(a+1\), and it discards any pair for which \(c=S-a-b\) has already dropped to \(b\) or below. Once that happens, the order \(a \lt b \lt c\) is impossible for that pair.
There is also a classical number-theoretic description of all integer right triangles. Every Pythagorean triple can be written in the form
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
with integers \(m \gt n \gt 0\) and \(k \ge 1\). Therefore the perimeter is always
$$S=2km(m+n).$$
This immediately implies that every admissible perimeter is even. So an odd value of \(S\) can never work. The implementations do not special-case odd inputs, but the formula explains in advance why such searches would end with no solution.
For the Euler target \(S=1000\), the perimeter equation becomes
$$500=km(m+n).$$
One successful choice is \(m=4\), \(n=1\), \(k=25\). Then the two legs are \(25(4^2-1^2)=375\) and \(25(2\cdot4\cdot1)=200\), while the hypotenuse is \(25(4^2+1^2)=425\). After ordering the two legs, the triple is
$$\boxed{(200,375,425)},$$
and its product is
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
The small checkpoint case is \(S=12\). The familiar triple \((3,4,5)\) works because
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
The product is therefore \(60\), which is why the implementations use this perimeter as a validation case before evaluating the main target.
The derivation above also shows a more structural viewpoint: once \(a\) is chosen, \(b\) is forced by the rational formula, and then \(c\) is forced by the perimeter. So the mathematical problem has only one real free variable, even though the code keeps the simpler two-loop enumeration.
The C++, Python, and Java implementations all use the same strategy. They iterate through candidate values of \(a\) from \(1\) upward. For each such \(a\), they iterate through candidate values of \(b\) starting from \(a+1\), so the inequality \(a \lt b\) is built directly into the loop structure.
For each pair \((a,b)\), the implementation computes
$$c=S-a-b.$$
If \(c \le b\), the order \(a \lt b \lt c\) has already failed, so that pair is skipped immediately. Otherwise the code checks the single remaining invariant
$$a^2+b^2=c^2.$$
As soon as that equation holds, the implementation returns the product \(abc\). For the Project Euler perimeter this is enough, because the ordered solution is unique. If the loops finish without finding a valid triple, the return value is \(0\).
Before handling the main perimeter, the implementations also verify themselves on the sample perimeter \(12\), where the correct product is \(60\). That small check confirms that the arithmetic, the ordering logic, and the return value convention are all consistent.
The nested search examines \(O(S^2)\) candidate pairs \((a,b)\) in the worst case. Each candidate requires only constant-time arithmetic: one subtraction to form \(c\), a comparison for the order test, and a fixed number of multiplications and additions for the Pythagorean check. The running time is therefore \(O(S^2)\).
The memory usage is \(O(1)\), because the implementation stores only a handful of integers regardless of the perimeter. For the Euler target \(S=1000\), this straightforward approach is already comfortably fast.
The closed-form relation for \(b\) shows that one could reduce the search to \(O(S)\) by scanning only over \(a\) and testing divisibility. The given implementations deliberately prefer the simpler double loop, which keeps the code short and still solves the target instance immediately.
Ein pythagoreisches Tripel ist ein Tripel positiver ganzer Zahlen \((a,b,c)\) mit
$$a^2+b^2=c^2.$$
Hier kommt zusätzlich die feste Umfangsbedingung
$$a+b+c=S$$
hinzu, und die Seiten sollen als \(a \lt b \lt c\) geordnet sein. Das Ziel der Euler-Aufgabe ist \(S=1000\). Die Implementierungen sind jedoch etwas allgemeiner: Für ein beliebiges positives \(S\) suchen sie ein geordnetes Tripel und geben das Produkt \(abc\) zurück, beziehungsweise \(0\), falls kein solches Tripel existiert.
Die entscheidende Vereinfachung ist, dass die Umfangsbedingung einen Freiheitsgrad entfernt. Sobald \(a\) und \(b\) feststehen, ist \(c\) nicht mehr unabhängig. Dadurch wird aus einer scheinbaren Dreifachsuche ein stark eingeschränkter Suchraum in der \((a,b)\)-Ebene.
Aus dem festen Umfang folgt sofort
$$c=S-a-b.$$
Setzt man dies in die pythagoreische Gleichung ein, erhält man
$$a^2+b^2=(S-a-b)^2.$$
Ausmultiplizieren und Kürzen von \(a^2+b^2\) liefert
$$0=S^2-2S(a+b)+2ab.$$
Fasst man die \(b\)-Terme zusammen, so folgt
$$2b(S-a)=S(S-2a),$$
also für jede gültige Lösung
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
Diese Formel ist in zweierlei Hinsicht wichtig. Erstens gibt es zu jedem festen \(a\) höchstens einen möglichen Wert von \(b\). Zweitens funktioniert ein Kandidat \(a\) nur dann, wenn der Nenner \(2(S-a)\) den Zähler \(S(S-2a)\) teilt. Die Implementierungen verwenden diese geschlossene Form nicht direkt, aber sie erklärt, warum selbst der einfache Brute-Force-Ansatz nur einen engen Raum durchsucht.
Die Ungleichungen \(a \lt b \lt c\) ergeben zusammen mit \(a+b+c=S\) sofort nützliche Schranken.
Da \(a\) die kleinste Seite ist, gilt
$$3a \lt a+b+c=S,$$
also
$$a \lt \frac{S}{3}.$$
Außerdem folgt aus \(b \lt c=S-a-b\)
$$2b \lt S-a,$$
und damit
$$b \lt \frac{S-a}{2}.$$
Genau diese Abschätzungen machen die direkte Enumeration praktikabel. Die Implementierung lässt \(a\) aufsteigend laufen, beginnt für jedes \(a\) den zweiten Lauf bei \(b=a+1\), und verwirft jedes Paar sofort, sobald \(c=S-a-b\) nicht mehr echt größer als \(b\) ist. Dann kann die Ordnung \(a \lt b \lt c\) ohnehin nicht mehr erfüllt werden.
Alle ganzzahligen rechtwinkligen Dreiecke besitzen eine klassische Parametrisierung. Jedes pythagoreische Tripel hat die Form
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
wobei \(m \gt n \gt 0\) und \(k \ge 1\) ganze Zahlen sind. Damit ist der Umfang immer
$$S=2km(m+n).$$
Insbesondere muss jeder mögliche Umfang gerade sein. Ein ungerades \(S\) kann daher prinzipiell keine Lösung besitzen. Die Implementierungen behandeln diesen Fall nicht gesondert, aber die Zahlentheorie erklärt im Voraus, warum die Suche dann zwangsläufig leer bleibt.
Für das Euler-Ziel \(S=1000\) wird daraus
$$500=km(m+n).$$
Eine passende Wahl ist \(m=4\), \(n=1\), \(k=25\). Dann sind die beiden Katheten \(25(4^2-1^2)=375\) und \(25(2\cdot4\cdot1)=200\), während die Hypotenuse \(25(4^2+1^2)=425\) ist. Nach Sortierung der Katheten erhält man also
$$\boxed{(200,375,425)},$$
mit dem Produkt
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
Der kleine Prüfpunkt ist \(S=12\). Das bekannte Tripel \((3,4,5)\) erfüllt beide Bedingungen:
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
Das Produkt ist also \(60\). Deshalb prüfen die Implementierungen diese Perimetergröße zuerst, bevor sie den Zielwert behandeln.
Die Herleitung zeigt außerdem den eigentlichen Kern der Aufgabe: Sobald \(a\) gewählt ist, erzwingt die rationale Formel einen eindeutigen Kandidaten für \(b\), und der Umfang erzwingt dann \(c\). Mathematisch gibt es also nur eine echte freie Variable, obwohl der Code die bewusst einfachere Doppelschleife verwendet.
Die C++-, Python- und Java-Implementierungen verwenden dieselbe Suchstrategie. Zuerst wird \(a\) von \(1\) an aufwärts durchlaufen. Für jedes solche \(a\) wird \(b\) ab \(a+1\) getestet, sodass die Bedingung \(a \lt b\) bereits durch die Schleifenstruktur garantiert ist.
Zu jedem Paar \((a,b)\) berechnet die Implementierung
$$c=S-a-b.$$
Wenn \(c \le b\) gilt, ist die Ordnung \(a \lt b \lt c\) bereits verletzt und das Paar wird sofort verworfen. Andernfalls bleibt nur noch die Invariante
$$a^2+b^2=c^2$$
zu prüfen. Beim ersten Treffer wird \(abc\) zurückgegeben. Für die Euler-Eingabe genügt das, weil es dort genau eine geordnete Lösung gibt. Wenn kein Treffer gefunden wird, liefern die Implementierungen \(0\).
Vor dem eigentlichen Zielumfang wird außerdem der Beispielumfang \(12\) kontrolliert, bei dem das richtige Produkt \(60\) ist. Damit werden Arithmetik, Ordnungslogik und Rückgabekonvention an einem kleinen, leicht überprüfbaren Fall abgesichert.
Die verschachtelte Suche betrachtet im Worst Case \(O(S^2)\) Kandidatenpaare \((a,b)\). Pro Paar fallen nur konstante viele ganzzahlige Operationen an: eine Subtraktion für \(c\), ein Vergleich für die Ordnungsbedingung und einige Multiplikationen und Additionen für den pythagoreischen Test. Die Laufzeit ist daher \(O(S^2)\).
Der Speicherbedarf ist \(O(1)\), weil unabhängig vom Umfang nur wenige Ganzzahlen gehalten werden. Für das Euler-Ziel \(S=1000\) ist dieser direkte Ansatz bereits völlig ausreichend.
Die geschlossene Formel für \(b\) zeigt, dass man den Suchaufwand theoretisch auf \(O(S)\) reduzieren könnte, indem man nur über \(a\) iteriert und Teilbarkeit prüft. Die gegebenen Implementierungen bevorzugen bewusst die kürzere Doppelschleife, weil sie den Zielwert trotzdem sofort findet.
Bir Pisagor üçlüsü,
$$a^2+b^2=c^2$$
eşitliğini sağlayan pozitif tamsayılar \((a,b,c)\) üçlüsüdür. Bu problemde buna ek olarak
$$a+b+c=S$$
çevre koşulu ve \(a \lt b \lt c\) sıralaması da istenir. Project Euler hedefi \(S=1000\) olsa da uygulamalar daha geneldir: herhangi bir pozitif \(S\) için sıralı bir üçlü arar, bulursa \(abc\) çarpımını döndürür, çözüm yoksa \(0\) verir.
Asıl sadeleşme, çevre eşitliğinin bir serbestlik derecesini ortadan kaldırmasından gelir. \(a\) ve \(b\) seçildiğinde \(c\) artık bağımsız değildir. Böylece rastgele üçlüler arasında arama yapmak yerine, \((a,b)\) düzleminde dar bir bölge incelenir.
Sabit çevreden hemen
$$c=S-a-b$$
elde edilir. Bunu Pisagor denklemine yazarsak
$$a^2+b^2=(S-a-b)^2$$
olur. Açıp \(a^2+b^2\) terimlerini sadeleştirince
$$0=S^2-2S(a+b)+2ab$$
kalır. \(b\) içeren terimleri bir araya getirince
$$2b(S-a)=S(S-2a),$$
dolayısıyla her geçerli üçlü için
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}$$
zorunludur. Bu formül iki önemli şey söyler. Birincisi, sabit bir \(a\) için en fazla bir tane uygun \(b\) olabilir. İkincisi, aday bir \(a\) değeri ancak \(2(S-a)\) sayısı \(S(S-2a)\)'yı bölüyorsa işe yarar. Uygulamalar bu kapalı biçimi doğrudan kullanmaz, fakat basit görünen aramanın neden aslında çok dar bir alanda gerçekleştiğini açıklar.
\(a \lt b \lt c\) eşitsizlikleri ile \(a+b+c=S\) birlikte çok güçlü sınırlar verir.
\(a\) en küçük kenar olduğundan
$$3a \lt a+b+c=S,$$
yani
$$a \lt \frac{S}{3}.$$
Ayrıca \(b \lt c=S-a-b\) olduğundan
$$2b \lt S-a,$$
ve dolayısıyla
$$b \lt \frac{S-a}{2}.$$
Doğrudan taramayı pratik kılan şey tam olarak bu sınırlardır. Uygulama \(a\)'yı küçükten büyüğe dener, her \(a\) için \(b\)'yi \(a+1\)'den başlatır ve \(c=S-a-b\) değeri \(b\)'ye eşit veya daha küçük olur olmaz o çifti anında eler. Çünkü o noktadan sonra \(a \lt b \lt c\) düzeni zaten imkansızdır.
Tüm tam sayılı dik üçgenler için klasik bir parametrizasyon vardır:
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
burada \(m \gt n \gt 0\) ve \(k \ge 1\) tamsayılardır. Bu durumda çevre daima
$$S=2km(m+n)$$
şeklindedir. Demek ki çözüm gelebilecek her çevre mutlaka çifttir. Bu yüzden tek bir \(S\) değeri ilke olarak hiç çalışamaz. Uygulamalar bunu ayrıca kontrol etmez, ama sayı kuramı neden böyle girdilerin sonunda çözümsüz kalacağını önceden açıklar.
Euler hedefi \(S=1000\) için denklem
$$500=km(m+n)$$
olur. Başarılı bir seçim \(m=4\), \(n=1\), \(k=25\)'tir. Bu durumda iki dik kenar \(25(4^2-1^2)=375\) ve \(25(2\cdot4\cdot1)=200\), hipotenüs ise \(25(4^2+1^2)=425\) olur. Kenarları sıralayınca
$$\boxed{(200,375,425)}$$
üçlüsünü elde ederiz; çarpımı da
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000}$$
çıkar.
Küçük kontrol örneği \(S=12\)'dir. Bilinen \((3,4,5)\) üçlüsü iki koşulu da sağlar:
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
Dolayısıyla çarpım \(60\) olur. Uygulamaların önce bu çevreyi doğrulamasının nedeni budur.
Bu türetim aynı zamanda problemin özünü gösterir: \(a\) seçildiğinde rasyonel formül \(b\)'yi zorlar, çevre eşitliği de \(c\)'yi zorlar. Yani matematiksel olarak aslında tek gerçek serbest değişken vardır; kod ise sadelik adına bunu iki döngülü bir tarama olarak bırakır.
C++, Python ve Java uygulamalarının mantığı aynıdır. Önce \(a\) değeri \(1\)'den başlayarak artırılır. Her sabit \(a\) için \(b\), \(a+1\)'den başlayarak denenir; böylece \(a \lt b\) koşulu ayrı bir kontrol yerine döngü yapısının içine yerleşmiş olur.
Her \((a,b)\) çifti için uygulama
$$c=S-a-b$$
hesabını yapar. Eğer \(c \le b\) ise \(a \lt b \lt c\) düzeni bozulmuştur ve çift hemen atılır. Aksi halde geriye sadece
$$a^2+b^2=c^2$$
değişmezi kalır; kod bunu test eder. Eşitlik sağlanır sağlanmaz \(abc\) çarpımı döndürülür. Project Euler çevresi için bu yeterlidir, çünkü sıralı çözüm tektir. Hiç eşleşme bulunmazsa sonuç \(0\) olur.
Ana çevreye geçmeden önce uygulamalar \(S=12\) örneğini de doğrular. Doğru çarpımın \(60\) olduğu bu küçük test, aritmetiğin, sıralama mantığının ve dönüş kuralının yerinde olduğunu gösterir.
İç içe arama en kötü durumda \(O(S^2)\) kadar \((a,b)\) adayı inceler. Her aday için sabit sayıda işlem yapılır: \(c\) için bir çıkarma, sıra koşulu için bir karşılaştırma ve Pisagor kontrolü için birkaç çarpma ile toplama. Bu yüzden çalışma süresi \(O(S^2)\)'dir.
Ek bellek kullanımı \(O(1)\)'dir; çünkü çevre ne olursa olsun sadece birkaç tamsayı tutulur. Euler hedefi \(S=1000\) için bu doğrudan yaklaşım fazlasıyla hızlıdır.
\(b\) için elde edilen kapalı biçim, sadece \(a\) üzerinde gezip bölünebilirlik testi yaparak aramanın teorik olarak \(O(S)\)'ye indirilebileceğini gösterir. Verilen uygulamalar ise daha kısa ve daha açık olduğu için bilinçli olarak çift döngülü sürümü tercih eder.
Un triple pitagórico es un trío de enteros positivos \((a,b,c)\) que satisface
$$a^2+b^2=c^2.$$
En este problema además se impone el perímetro fijo
$$a+b+c=S,$$
con el orden \(a \lt b \lt c\). El objetivo de Project Euler corresponde a \(S=1000\), aunque las implementaciones son algo más generales: para cualquier perímetro positivo \(S\), buscan un triple ordenado y devuelven el producto \(abc\), o bien \(0\) si no existe ninguna solución de ese tipo.
La simplificación decisiva es que la condición sobre el perímetro elimina un grado de libertad. Una vez elegidos \(a\) y \(b\), la hipotenusa ya no es independiente. Por eso el problema real no es explorar triples arbitrarios, sino una región muy restringida del plano \((a,b)\).
Del perímetro fijo se obtiene inmediatamente
$$c=S-a-b.$$
Al sustituir en la ecuación pitagórica, resulta
$$a^2+b^2=(S-a-b)^2.$$
Desarrollando y cancelando \(a^2+b^2\), queda
$$0=S^2-2S(a+b)+2ab.$$
Si agrupamos los términos que contienen \(b\), obtenemos
$$2b(S-a)=S(S-2a),$$
y por tanto toda solución válida debe cumplir
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
Esta identidad es importante por dos motivos. Primero, para cada valor fijo de \(a\) puede existir como mucho un valor de \(b\). Segundo, un candidato \(a\) solo funciona cuando el denominador \(2(S-a)\) divide al numerador \(S(S-2a)\). Las implementaciones no usan esta fórmula cerrada de manera directa, pero sí explica por qué incluso la búsqueda exhaustiva está muy restringida.
Las desigualdades \(a \lt b \lt c\), combinadas con \(a+b+c=S\), producen cotas inmediatas.
Como \(a\) es el lado más pequeño, se tiene
$$3a \lt a+b+c=S,$$
de donde
$$a \lt \frac{S}{3}.$$
Además, de \(b \lt c=S-a-b\) se deduce
$$2b \lt S-a,$$
y por ello
$$b \lt \frac{S-a}{2}.$$
Estas cotas son exactamente las que hacen viable la enumeración directa. La implementación recorre \(a\) en orden ascendente, inicia el segundo recorrido en \(b=a+1\), y descarta de inmediato cualquier par para el cual \(c=S-a-b\) ya no sea estrictamente mayor que \(b\). En ese punto, el orden \(a \lt b \lt c\) ya es imposible.
Existe además una descripción clásica de todos los triángulos rectángulos con lados enteros. Todo triple pitagórico puede escribirse como
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
con enteros \(m \gt n \gt 0\) y \(k \ge 1\). En consecuencia, el perímetro siempre es
$$S=2km(m+n).$$
Así se ve de inmediato que todo perímetro admisible debe ser par. Un valor impar de \(S\) nunca puede producir una solución. Las implementaciones no tratan ese caso por separado, pero la parametrización muestra de antemano por qué la búsqueda terminaría sin encontrar nada.
Para el objetivo \(S=1000\), la ecuación del perímetro pasa a ser
$$500=km(m+n).$$
Una elección válida es \(m=4\), \(n=1\), \(k=25\). Entonces los dos catetos son \(25(4^2-1^2)=375\) y \(25(2\cdot4\cdot1)=200\), mientras que la hipotenusa es \(25(4^2+1^2)=425\). Al ordenar los catetos, se obtiene
$$\boxed{(200,375,425)},$$
cuyo producto es
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
El pequeño caso de control es \(S=12\). El triple conocido \((3,4,5)\) satisface ambas condiciones:
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
Por eso el producto correcto es \(60\), y precisamente esa es la validación preliminar que realizan las implementaciones antes de evaluar el perímetro principal.
La derivación también deja claro el núcleo matemático del problema: una vez fijado \(a\), la fórmula racional fuerza \(b\), y el perímetro fuerza \(c\). Desde el punto de vista matemático solo queda una verdadera variable libre, aunque el código prefiera la enumeración más simple con dos bucles.
Las implementaciones en C++, Python y Java siguen exactamente la misma idea. Recorren valores candidatos de \(a\) desde \(1\) hacia arriba. Para cada \(a\), recorren valores de \(b\) a partir de \(a+1\), de modo que la desigualdad \(a \lt b\) queda incorporada en la propia estructura de los bucles.
Para cada par \((a,b)\), la implementación calcula
$$c=S-a-b.$$
Si \(c \le b\), el orden \(a \lt b \lt c\) ya ha fallado y ese par se descarta de inmediato. En caso contrario, solo queda comprobar la invariante
$$a^2+b^2=c^2.$$
En cuanto esta igualdad se cumple, se devuelve el producto \(abc\). Para el perímetro de Project Euler esto basta, porque la solución ordenada es única. Si el recorrido completo no encuentra ninguna coincidencia, el valor devuelto es \(0\).
Antes de resolver el caso objetivo, las implementaciones también se verifican con el perímetro \(12\), cuyo producto correcto es \(60\). Esa comprobación pequeña confirma que la aritmética, la lógica de orden y la convención de retorno son coherentes.
La búsqueda anidada examina \(O(S^2)\) pares candidatos \((a,b)\) en el peor caso. Cada par requiere solo trabajo constante: una resta para obtener \(c\), una comparación para la condición de orden y unas pocas multiplicaciones y sumas para el test pitagórico. Por tanto, el tiempo total es \(O(S^2)\).
El uso adicional de memoria es \(O(1)\), ya que solo se mantienen unos pocos enteros independientemente del perímetro. Para el objetivo \(S=1000\), este método directo es más que suficiente.
La fórmula cerrada para \(b\) muestra que, teóricamente, el recorrido podría reducirse a \(O(S)\) si se iterara solo sobre \(a\) y se comprobara divisibilidad. Las implementaciones dadas prefieren deliberadamente el doble bucle porque es más corto, más claro y sigue siendo instantáneo para el tamaño de entrada del problema.
勾股数组是满足
$$a^2+b^2=c^2$$
的正整数三元组 \((a,b,c)\)。本题还额外要求固定周长
$$a+b+c=S,$$
并且边长按 \(a \lt b \lt c\) 排序。Project Euler 的目标周长是 \(S=1000\)，不过这些实现稍微更一般一些：对于任意正整数周长 \(S\)，它们都会搜索满足条件的有序三元组，找到后返回乘积 \(abc\)，若不存在则返回 \(0\)。
最关键的简化在于：固定周长这个条件直接消掉了一个自由度。一旦 \(a\) 和 \(b\) 给定，\(c\) 就不再独立。因此真正的问题不是在所有整数三元组里盲目搜索，而是在 \((a,b)\) 平面中一个很窄的可行区域里寻找解。
由周长条件立刻得到
$$c=S-a-b.$$
代回勾股方程：
$$a^2+b^2=(S-a-b)^2.$$
展开并消去两边共同的 \(a^2+b^2\) 之后，有
$$0=S^2-2S(a+b)+2ab.$$
把含 \(b\) 的项整理到一起，可得
$$2b(S-a)=S(S-2a),$$
因此任何合法解都必须满足
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
这个式子有两个直接后果。第一，对于固定的 \(a\)，最多只可能对应一个 \(b\)。第二，一个候选 \(a\) 只有在分母 \(2(S-a)\) 整除分子 \(S(S-2a)\) 时才可能形成整数解。实现本身并没有直接使用这个闭式，但它清楚地说明了为什么看似朴素的穷举其实搜索空间非常受限。
不等式 \(a \lt b \lt c\) 与 \(a+b+c=S\) 结合后会给出立即可用的上界。
因为 \(a\) 是最短边，所以必有
$$3a \lt a+b+c=S,$$
也就是
$$a \lt \frac{S}{3}.$$
又因为 \(b \lt c=S-a-b\)，所以
$$2b \lt S-a,$$
从而
$$b \lt \frac{S-a}{2}.$$
这正是直接枚举仍然足够高效的原因。实现会让 \(a\) 从小到大递增，对每个 \(a\)，令 \(b\) 从 \(a+1\) 开始尝试；一旦 \(c=S-a-b\) 已经小于或等于 \(b\)，那么 \(a \lt b \lt c\) 的顺序就不可能成立，这一对候选值会立刻被丢弃。
所有整边直角三角形都可以用经典参数化来描述：
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
其中 \(m \gt n \gt 0\)，\(k \ge 1\) 为整数。于是周长必然写成
$$S=2km(m+n).$$
这马上说明任何可能出现解的周长都一定是偶数，所以奇数周长从原理上就不可能对应勾股数组。实现虽然没有专门对奇数输入做快速返回，但这个数论结构解释了为什么那样的搜索最终只能失败。
对本题目标 \(S=1000\) 来说，上式变成
$$500=km(m+n).$$
一个可行选择是 \(m=4\)、\(n=1\)、\(k=25\)。此时两条直角边分别为 \(25(4^2-1^2)=375\) 与 \(25(2\cdot4\cdot1)=200\)，斜边为 \(25(4^2+1^2)=425\)。把两条直角边按大小排序后，就得到
$$\boxed{(200,375,425)},$$
其乘积为
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
较小的检验周长是 \(S=12\)。众所周知，\((3,4,5)\) 满足两项条件：
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
所以对应乘积是 \(60\)。这也正是实现先用来做自检的样例。
从推导角度看，这个问题的本质也已经非常清楚：一旦 \(a\) 固定，闭式关系就把 \(b\) 几乎完全钉死，而周长条件又立即确定 \(c\)。因此数学上真正自由的变量只有一个，只是代码为了保持结构简单，仍然采用了两层循环的写法。
C++、Python 和 Java 实现使用的是同一套思路。它们先从 \(1\) 开始递增枚举候选值 \(a\)。对于每个固定的 \(a\)，再从 \(a+1\) 开始枚举 \(b\)，这样 \(a \lt b\) 这个条件就直接体现在循环结构里，而不需要额外分支。
对每一对 \((a,b)\)，实现都会先计算
$$c=S-a-b.$$
如果 \(c \le b\)，那么顺序 \(a \lt b \lt c\) 已经失败，这一对候选值会被立刻跳过。否则只剩下最后一个不变量需要检查：
$$a^2+b^2=c^2.$$
一旦该等式成立，实现就返回乘积 \(abc\)。对 Project Euler 的目标周长来说，这样做完全足够，因为有序解只有一个。如果所有循环都结束仍未找到满足条件的三元组，则返回 \(0\)。
在处理主目标之前，这些实现还会先验证周长 \(12\) 的样例，其正确乘积是 \(60\)。这个小检查可以确认整数运算、顺序判断以及返回规则都没有偏差。
两层枚举在最坏情况下会检查 \(O(S^2)\) 个候选对 \((a,b)\)。每一对只需要常数次整数运算：一次减法得到 \(c\)，一次比较判断顺序，再加上若干次乘法和加法验证勾股关系。因此总时间复杂度是 \(O(S^2)\)。
额外空间复杂度是 \(O(1)\)，因为无论周长多大，实现都只保留少量整数变量。对目标输入 \(S=1000\) 而言，这种直接方法已经完全足够快。
前面推出的 \(b\) 的闭式也说明，理论上可以只枚举 \(a\) 并检查整除性，从而把搜索压到 \(O(S)\)。不过给出的实现有意保留更短、更直观的双重循环，因为对本题规模来说它已经几乎瞬间完成。
Пифагорова тройка, это тройка положительных целых чисел \((a,b,c)\), для которой выполняется
$$a^2+b^2=c^2.$$
В этой задаче дополнительно задан фиксированный периметр
$$a+b+c=S,$$
а стороны упорядочены как \(a \lt b \lt c\). Целевой случай Project Euler соответствует \(S=1000\), однако реализации написаны немного шире: для любого положительного \(S\) они ищут упорядоченную тройку и возвращают произведение \(abc\), а если решения нет, возвращают \(0\).
Главное упрощение состоит в том, что условие на периметр убирает одну степень свободы. Как только выбраны \(a\) и \(b\), число \(c\) определяется автоматически. Поэтому фактический поиск ведётся не по всем тройкам целых чисел, а по сильно ограниченной области на плоскости \((a,b)\).
Из фиксированного периметра немедленно следует
$$c=S-a-b.$$
Подставим это в уравнение Пифагора:
$$a^2+b^2=(S-a-b)^2.$$
После раскрытия скобок и сокращения \(a^2+b^2\) получаем
$$0=S^2-2S(a+b)+2ab.$$
Если собрать вместе члены с \(b\), получится
$$2b(S-a)=S(S-2a),$$
то есть любая допустимая тройка обязана удовлетворять формуле
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
Это равенство важно по двум причинам. Во-первых, для каждого фиксированного \(a\) возможен не более чем один кандидат на роль \(b\). Во-вторых, число \(a\) годится только тогда, когда знаменатель \(2(S-a)\) делит числитель \(S(S-2a)\). Реализации не используют эту формулу напрямую, но именно она объясняет, почему даже полный перебор на деле исследует очень узкую область.
Неравенства \(a \lt b \lt c\), вместе с \(a+b+c=S\), дают немедленные верхние границы.
Так как \(a\) является наименьшей стороной, имеем
$$3a \lt a+b+c=S,$$
следовательно,
$$a \lt \frac{S}{3}.$$
Кроме того, из \(b \lt c=S-a-b\) следует
$$2b \lt S-a,$$
а значит
$$b \lt \frac{S-a}{2}.$$
Именно эти оценки делают прямой перебор разумным. Реализация увеличивает \(a\) снизу вверх, для каждого \(a\) начинает второй проход с \(b=a+1\), а затем немедленно отбрасывает пары, у которых \(c=S-a-b\) уже не больше \(b\). После этого упорядочение \(a \lt b \lt c\) всё равно невозможно.
Существует и классическое число-теоретическое описание всех целочисленных прямоугольных треугольников:
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
где \(m \gt n \gt 0\) и \(k \ge 1\) являются целыми числами. Тогда периметр всегда равен
$$S=2km(m+n).$$
Отсюда сразу видно, что любой допустимый периметр обязан быть чётным. Поэтому нечётное \(S\) не может дать решение в принципе. Реализации не добавляют для этого отдельную ветку, но параметризация заранее объясняет, почему такой поиск завершится безуспешно.
Для целевого значения \(S=1000\) условие на периметр превращается в
$$500=km(m+n).$$
Один подходящий выбор, это \(m=4\), \(n=1\), \(k=25\). Тогда катеты равны \(25(4^2-1^2)=375\) и \(25(2\cdot4\cdot1)=200\), а гипотенуза равна \(25(4^2+1^2)=425\). После упорядочения катетов получаем
$$\boxed{(200,375,425)},$$
и произведение
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
Малый проверочный случай, это \(S=12\). Знаменитая тройка \((3,4,5)\) удовлетворяет обеим требованиям:
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
Следовательно, произведение равно \(60\). Именно поэтому реализации сначала проверяют этот периметр, а уже потом переходят к основному значению.
Из всей этой схемы хорошо видно и математическое ядро задачи: стоит зафиксировать \(a\), как рациональная формула почти полностью определяет \(b\), а затем условие на периметр определяет \(c\). То есть по существу свободной остаётся только одна переменная, хотя код сознательно сохраняет более простой вариант с двумя циклами.
Реализации на C++, Python и Java используют один и тот же алгоритм. Они перебирают возможные значения \(a\), начиная с \(1\). Для каждого такого \(a\) перебираются значения \(b\), начиная с \(a+1\), так что неравенство \(a \lt b\) сразу встроено в структуру циклов.
Для каждой пары \((a,b)\) сначала вычисляется
$$c=S-a-b.$$
Если оказывается, что \(c \le b\), порядок \(a \lt b \lt c\) уже нарушен, и пара сразу пропускается. В противном случае остаётся проверить единственный основной инвариант
$$a^2+b^2=c^2.$$
Как только равенство выполняется, возвращается произведение \(abc\). Для периметра из Project Euler этого достаточно, потому что упорядоченное решение единственно. Если перебор завершается без находки, результатом становится \(0\).
Перед основным запуском реализации также проверяют пример с периметром \(12\), где правильный ответ равен \(60\). Такая маленькая проверка подтверждает корректность арифметики, логики порядка и соглашения о возвращаемом значении.
Вложенный перебор рассматривает \(O(S^2)\) кандидатных пар \((a,b)\) в худшем случае. Для каждой пары выполняется лишь константное число операций: одна разность для вычисления \(c\), одно сравнение для проверки порядка и несколько умножений с сложениями для проверки уравнения Пифагора. Поэтому время работы равно \(O(S^2)\).
Дополнительная память равна \(O(1)\), поскольку независимо от значения периметра хранятся только несколько целых чисел. Для целевого случая \(S=1000\) такого прямого подхода более чем достаточно.
Полученная выше формула для \(b\) показывает, что теоретически перебор можно сократить до \(O(S)\), если проходить только по \(a\) и проверять делимость. Однако данные реализации намеренно выбирают более короткий и прозрачный двойной цикл, потому что для размера этой задачи он и так работает мгновенно.
ثلاثية فيثاغورس هي ثلاثية من الأعداد الصحيحة الموجبة \((a,b,c)\) تحقق
$$a^2+b^2=c^2.$$
وفي هذه المسألة يضاف أيضاً شرط المحيط الثابت
$$a+b+c=S,$$
مع ترتيب الأضلاع على الصورة \(a \lt b \lt c\). قيمة المسألة المستهدفة في Project Euler هي \(S=1000\)، لكن التنفيذات أكثر عمومية بقليل: فهي تبحث لأي محيط موجب \(S\) عن ثلاثية مرتبة تحقق الشرطين، ثم تعيد حاصل الضرب \(abc\)، أو تعيد \(0\) إذا لم توجد ثلاثية مناسبة.
أهم تبسيط هنا أن شرط المحيط يزيل درجة حرية كاملة. فبمجرد اختيار \(a\) و\(b\)، يصبح \(c\) محدداً تلقائياً. لذلك فالمسألة الحقيقية ليست فحص كل الثلاثيات الممكنة، بل البحث داخل منطقة ضيقة جداً في مستوى \((a,b)\).
من شرط المحيط نحصل مباشرة على
$$c=S-a-b.$$
وبالتعويض في معادلة فيثاغورس نجد
$$a^2+b^2=(S-a-b)^2.$$
وبعد التوسيع وحذف \(a^2+b^2\) من الطرفين نحصل على
$$0=S^2-2S(a+b)+2ab.$$
وبجمع الحدود التي تحتوي على \(b\) في طرف واحد يظهر أن
$$2b(S-a)=S(S-2a),$$
ولذلك فإن أي حل صحيح لا بد أن يحقق
$$\boxed{b=\frac{S(S-2a)}{2(S-a)}}.$$
هذه الصيغة مهمة لسببين. أولاً، لكل قيمة ثابتة من \(a\) يوجد على الأكثر مرشح واحد للقيمة \(b\). وثانياً، لا يمكن أن ينجح مرشح ما إلا إذا كان المقام \(2(S-a)\) يقسم البسط \(S(S-2a)\). التنفيذات لا تستخدم هذه الصيغة المغلقة مباشرة، لكنها تفسر لماذا يبقى حتى البحث الشامل محصوراً في مجال صغير جداً.
الشرطان \(a \lt b \lt c\) مع \(a+b+c=S\) يعطيان حدوداً مباشرة ومفيدة.
بما أن \(a\) هو أصغر ضلع، فلا بد أن
$$3a \lt a+b+c=S,$$
ومن ثم
$$a \lt \frac{S}{3}.$$
وكذلك من \(b \lt c=S-a-b\) نستنتج
$$2b \lt S-a,$$
أي
$$b \lt \frac{S-a}{2}.$$
وهذه الحدود هي بالضبط ما يجعل التعداد المباشر عملياً. فالتنفيذ يزيد \(a\) تصاعدياً، ثم يبدأ \(b\) من \(a+1\)، ويهمل أي زوج فوراً عندما تصبح القيمة \(c=S-a-b\) أصغر من \(b\) أو مساوية لها. عند تلك اللحظة يصبح ترتيب \(a \lt b \lt c\) مستحيلاً أصلاً.
هناك أيضاً الوصف الكلاسيكي لكل المثلثات القائمة ذات الأضلاع الصحيحة:
$$\{a,b\}=\{k(m^2-n^2),\,2kmn\}, \qquad c=k(m^2+n^2),$$
حيث \(m \gt n \gt 0\) و\(k \ge 1\) عددان صحيحان. وعندئذ يكون المحيط دائماً
$$S=2km(m+n).$$
وهذا يبين فوراً أن أي محيط يسمح بحل يجب أن يكون زوجياً. لذلك فكل قيمة فردية لـ \(S\) يستحيل أن تعطي ثلاثية فيثاغورس. التنفيذات لا تضيف فرعاً خاصاً لهذا الأمر، لكن البنية العددية تشرح مسبقاً لماذا ينتهي البحث في هذه الحالة بلا نتيجة.
في المسألة المستهدفة \(S=1000\) تصبح المعادلة
$$500=km(m+n).$$
واختيار ناجح هو \(m=4\)، و\(n=1\)، و\(k=25\). عندها يكون الضلعان القائمان \(25(4^2-1^2)=375\) و\(25(2\cdot4\cdot1)=200\)، أما الوتر فهو \(25(4^2+1^2)=425\). وبعد ترتيب الضلعين القائمين نحصل على
$$\boxed{(200,375,425)},$$
ويكون حاصل الضرب
$$\boxed{200 \cdot 375 \cdot 425 = 31{,}875{,}000.}$$
حالة التحقق الصغيرة هي \(S=12\). فالثلاثية المعروفة \((3,4,5)\) تحقق الشرطين معاً:
$$3^2+4^2=9+16=25=5^2, \qquad 3+4+5=12.$$
إذن حاصل الضرب هو \(60\)، ولهذا تستعمل التنفيذات هذا المحيط كاختبار أولي قبل التعامل مع القيمة الأساسية.
كما يوضح الاشتقاق جوهر المسألة أيضاً: بمجرد تثبيت \(a\)، فإن الصيغة الكسرية تكاد تحدد \(b\) بالكامل، ثم يحدد شرط المحيط \(c\) مباشرة. أي إن المشكلة الرياضية تمتلك متغيراً حراً حقيقياً واحداً فقط، رغم أن الكود يحتفظ بالتعداد الأبسط ذي الحلقتين.
تنفيذات C++ وPython وJava تعتمد الفكرة نفسها. فهي تمر على القيم المرشحة لـ \(a\) ابتداءً من \(1\). ولكل قيمة من \(a\)، تبدأ تجربة \(b\) من \(a+1\)، وبذلك يصبح الشرط \(a \lt b\) مضمناً داخل بنية الحلقات نفسها.
لكل زوج \((a,b)\) يحسب التنفيذ أولاً
$$c=S-a-b.$$
فإذا كان \(c \le b\)، فهذا يعني أن ترتيب \(a \lt b \lt c\) قد فشل بالفعل، فيُهمل الزوج فوراً. وإلا فلا يبقى إلا اختبار الثابت الأساسي
$$a^2+b^2=c^2.$$
وعندما تتحقق هذه المساواة يعاد حاصل الضرب \(abc\) مباشرة. وهذا كافٍ في حالة Project Euler لأن الحل المرتب وحيد. وإذا انتهى التعداد من غير العثور على ثلاثية صالحة، تكون القيمة المعادة هي \(0\).
وقبل معالجة المحيط الهدف، تتحقق التنفيذات أيضاً من المثال ذي المحيط \(12\)، حيث يكون حاصل الضرب الصحيح \(60\). هذا الفحص الصغير يؤكد سلامة الحسابات ومنطق الترتيب واتفاقية الإرجاع.
يفحص البحث المتداخل في أسوأ الأحوال \(O(S^2)\) من الأزواج المرشحة \((a,b)\). وكل زوج يحتاج فقط إلى عمل ثابت: طرح واحد لحساب \(c\)، ومقارنة واحدة لاختبار الترتيب، وعدد محدود من الضرب والجمع للتحقق من معادلة فيثاغورس. لذلك فإن الزمن الكلي هو \(O(S^2)\).
أما الذاكرة الإضافية فهي \(O(1)\)، لأن التنفيذ يحتفظ بعدد قليل فقط من القيم الصحيحة مهما كان المحيط. وبالنسبة إلى \(S=1000\)، فهذا الأسلوب المباشر سريع بما يكفي تماماً.
الصيغة المغلقة الخاصة بـ \(b\) تبين أن من الممكن نظرياً تقليص البحث إلى \(O(S)\) بالاكتفاء بالمرور على \(a\) وفحص القابلية للقسمة. لكن التنفيذات المعطاة تتعمد اختيار النسخة الأبسط ذات الحلقتين لأنها أوضح، وأقصر، ولا تزال فورية تقريباً على حجم الإدخال المطلوب.