# Maximal pythagorean triplet that sums to n

Write a function maxPythagTriple that accepts an integer n and returns the maximum product of three numbers that are both a Pythagorean triplet and sum to the integer n. If no such pythagorean triplet exists, return -1.

i.e. maxPythagTriple(4) == -1 i.e. maxPythagTriple(12) == 60 {3,4,5} --> 3+4+5 = 12 --> 3^2+4^2= 5^2 --> 3*4*5 = 60

Below is my solution the preceeding challenge. I have been told there is a better solution. Any help would be much appreciated!

package challenges;

public class MathChallenges {

private static boolean isValidTriple(int i, int j, int k) {
return k > 0 && i != j && j != k && i > j && j > k;
}

private static boolean isPythagTriple(int i, int j, int k) {
return (i*i + j*j) == k*k;
}

public static int maxPythagTriple(int n) {
for (int i = n-1; i >= 1; i--) {
for (int j = i-1; j >= 1; j--) {
int k = n - (i + j);
if (isValidTriple(i, j, k) && isPythagTriple(k, j, i)) {
return i * j * k;
}
}
}
return -1;
}

public static void main(String[] args) {
System.out.println("maxPythagTriple(4) = " + maxPythagTriple(4));
System.out.println("maxPythagTriple(12) = " + maxPythagTriple(12));
}

}


The code returns the first product, not the maximum product. For example, it returns 6240 instead of 7500 on input 60:

(60)  10² + 24² = 26² ; 10 * 24 * 26 = 6240
(60)  15² + 20² = 25² ; 15 * 20 * 25 = 7500


This is easy to fix: loop and take the maximum.

I have been told there is a better solution.

There are solutions that take fewer steps. One could attempt to improve the current solution by shrinking the possible ranges. Given:

$c^2 = a^2 + b^2 ; sum = a + b + c$

Neither a nor b can be larger than c. This also means that neither a nor b can be larger than half the sum.

For c: it can't be smaller than any other term, and it must be at least one-third of the sum.

  // the "sum - 1" accounts for a being at least 1
for ( int b = (sum - 1) / 2; b >= 1; b-- ) {
for ( int c = Math.max(b, sum - 2*b); c < sum-b-1; c++ ) {
int a = n - b - c;
if ( a*a + b*b == c*c ) {
// found a triple
}
}
}


This is a little better, but it's still inefficient. If you're feeling brave, there is a formula to generate all Pythagorean triples.

# Euclid's Formula

Briefly, Euclid's formula involves two integers, $m > n > 0$, that generate Pythagorean triples:

$a = m^2 - n^2 ; b = 2mn ; c = m^2 + n^2$

(This doesn't generate all triples; we'll get to that in a minute.)

The sum of a, b, c becomes:

$sum = m^2 - n^2 + 2mn + m^2 + n^2 = (m - n)(m + n) + (m + n)^2 = 2m(m + n)$

Because sum, m, and n are integers, this means that both m and (m+n) divide sum.

For minimal n = 1, m is maximally $\sqrt{sum \over 2}$, so that's a good upper bound to start with. And given sum and m, we have $n = {sum \over {2m}} - m$

/* sum = 2m(m+n) ; m > n > 0 */
public static int maxPythagTriple_Euclid(int sum) {
// sum must be even; smallest triple has sum 12
if ( sum % 2 != 0 || sum < 12 ) return -1;
final int sumd2 = sum / 2; // divisible by 2
for ( int m = (int) Math.sqrt(sumd2); m > sumd2 / m - m; m-- ) {
if ( sum % m != 0 ) continue; // must be a divisor
final int n = sumd2 / m - m;
if ( n <= 0 ) continue; // rule out pathologicals
if ( sum % (m+n) != 0 ) continue; // must be a divisor
final int msq = m*m, nsq = n*n;
final int a = msq - nsq, b = 2*m*n, c = msq + nsq;
assert a * a + b * b == c * c;
return a * b * c;
}
return -1;
}

// Alternative implementation, pulling n into the for-loop
public static int maxPythagTriple_Euclid(int sum) {
if ( sum % 2 != 0 || sum < 12 ) return -1;
final int sumd2 = sum / 2; // divisible by 2
for ( int m = (int) Math.sqrt(sumd2), n = sumd2 / m - m;
m > n;
m--, n = sumd2 / m - m ) {
if ( n <= 0 || sum % m != 0 || sum % (m+n) != 0 ) {
continue;
}
final int msq = m*m, nsq = n*n;
final int a = msq - nsq, b = 2*m*n, c = msq + nsq;
assert a * a + b * b == c * c;
return a * b * c;
}
return -1;
}


We can return at our first hit because we maximize m; the product will be largest when the terms are closest, which is the case for minimal n (and thus maximal m).

To quote myself:

This doesn't generate all triples; we'll get to that in a minute.

Euclid's formula doesn't generate all triples, but it does generate at least all primitive triples.

An important property of Pythagorean triples is that, if $(a,b,c)$ is a triple, then so is $(k*a, k*b, k*c)$, for any integer k. Such a k is necessarily a divisor of the sum of a, b, c.

public static int maxPythagTriple_Euclid(int sum) {
int max = -1;
for ( int k = 1; k < sum / 2 && sum / k >= 12; k++ ) {
if ( sum % k != 0 ) continue;

// multiply by k^3
int prod = maxPythagTriple_Euclid_primitive(sum / k) * (k * k * k);
if ( prod > max ) {
max = prod;
}
}
return max;
}


Precomputing the divisors of sum may save some more steps, but I haven't looked into that.