Pythagorean triples
No. 80
Q: 
Pythagorean triples are integer combinations of three values being related by the Pythagorean theorem: Find all Pythagorean triples $\left(a,b,c\right)$ of nonzero integer values which simultaneously obey the additional constraint $a+b+c=840$. TipThink of creating all possible triples $\left(a,b,c\right)$ not yet obeying any restrictions at all:
Why does an upper value of 838 rather then the proposed sum value of 840 appears here? This list mostly contains values like $\left(1,3,4\right)$ failing both our restrictions ${1}^{2}+{3}^{2}\ne {4}^{2}$ and $1+3+4\ne \mathrm{840}$. These triples have thus to be filtered retaining only the desired combinations simultaneously obeying both ${a}^{2}+{b}^{2}={c}^{2}$ and $a+b+c=\mathrm{840}$. This might be accomplished by implementing three nested loops: for (int a = 1; a <= 838; a++) { for (int b = 1; b <= 838; b++) { for (int c = 1; c <= 838; c++) { if (a*a + b*b == c*c && // Pythagorean condition a + b + c == 840) { // sum constraint System.out.println(" Found (" + a + ", " + b + ", " + c + ")"); } } } } The above code generating $838\times 838\times 838=588480472$ combinations will run quite some time! Thus we are looking for a better (more efficient) solution. There are several issues with the above code. It creates a great number of combinations like $\left(1,4,3\right)$ which could be ruled out beforehand easily rather then creating and filtering them. Do we really need three nested loops? Also triples having identical values but in a
different order like So the problem can be stated to find the set of all triples $\left(a,b,c\right)\in {\left[1,\mathrm{838}\right]}^{3}$ which simultaneously obey:


A: 
Since each variable value must be greater than zero the maximum possible value is 840  1  1 = 838. The “last” triple obeying both restrictions
1 and 2 is (280, 280,
280). Due to the restriction
$a+b+c=\mathrm{840}$ two variable values already determine the
third one: For a given value of variable a from the outer
We thus only need two nested loops for generating all possible triples: If the value of b is being incremented by 1 then c has to be decremented by 1 as well and is thus completely determined. For convenience reasons we introduce a variable final int sum = 840; for (int a = 1; a <= sum / 3; a++) { final int aSquare = a * a; // Calculate square of variable a // outside subsequent loop. for (int b = a, c = sum  a  b; b < c; b++, c) { if (aSquare + b * b == c * c) { // Filter for pythagorean triples System.out.println("(" + a + ", " + b + ", " + c + ")"); } } } This leaves us with eight triples: (40, 399, 401) (56, 390, 394) (105, 360, 375) (120, 350, 370) (140, 336, 364) (168, 315, 357) (210, 280, 350) (240, 252, 348) The above code can be simplified even further. We
introduce the variable s being shorthand for Regarding the nth step of the inner
${a}^{2}+\underset{\underset{{b}^{2}}{\ufe38}}{{\left(a+n\right)}^{2}}=\underset{\underset{{c}^{2}}{\ufe38}}{{\left(s2an\right)}^{2}}$
Solving this equation for n results in:
$n=\frac{{\left(s2a\right)}^{2}2{a}^{2}}{2\left(sa\right)}$
So for each given value of a there is either no or
exactly one possible solution (since The above equation must hold for integer arithmetic
leaving no fractional remainder. We introduce two variables
final int sum = 840; for (int a = 1; a <= sum / 3; a++) { final int numerator = (sum  2 * a) * (sum  2 * a)  2 * a * a, denominator = 2 * (sum  a); final int remainder = numerator % denominator; if (0 == remainder) { final int n = numerator / denominator; System.out.println("(" + a + ", " + (a + n) + ", " + (sum  2 * a  n) + ")"); } } This yields the same result as before but execution is
(again) ways faster paying off when looking for larger values
of 