Maximal pythagorean triplet that sums to n

Question

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));
    }

}

Answer 1

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.