Integer Right Triangles

Question: If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120: {20,48,52}, {24,45,51}, and {30,40,50}.

Related Tags:

Brute force

We could write a triple for-loop and try out all possible values for a, b and c, but with a little math we can reduce this complexity from O(n2) to O(n2).

Writing out the math

Before we jump straight into coding, let's write out some math.

We know that the total perimeter is p, so we can write:

a + b + c = p

Equation 1

Furthermore, we know from the pythagorean theorem that this equation holds true for right triangles:

a2 + b2 = c2

Equation 2

Now if we plug in c = p - (a + b) into the Pythagorean theorem, we get:

b = (p2 - 2pa) / 2(p - a)

Equation 3

More analysis

Consider the following scenarios and correlaries.

a and b are even
c is even by Equation 2, and p is even by Equation 1.
a and b are odd
c is even by Equation 2, and p is even by Equation 1.
a or b is odd (not both)
c is odd by Equation 2. In this case, p is still even.

Thus we know that p is even, so we only need to check every other p.

Furthermore, we can say that a < c and b < c and a <= b < c (we can switch a and b around as needed. Thus, we know that a is at most p/3 from Equation 1.

Implementation in Java

public class IntegerRightTriangles {
	public static void main(String[] args) {

		System.out.println(maxNumPossible(1000));

	}

	static int maxNumPossible(int upperBound) {

		// max number of possible values
		int numMax = 0;
		// maximum value for p
		int maxIndex = 0;

		for (int p = 3; p <= upperBound; p +=2) {

			// number of possible values for this i 
			int numPossible = numPossible(p);

			if (numPossible > numMax)  {
				numMax = numPossible;
				maxIndex = p;
			}
		}

		return maxIndex;
		
	}

	static int numPossible(int p) {

		int numPos = 0;

		for (int a = 2; a < p/3; a++) {

			// Only integer values
			if ((p*p - 2*p*a) % (2*(p-a)) == 0 ){
				numPos++;
			}

		}

		return numPos;
	}

}

Came up with a better solution or have a question? Comment below!

Next Challenge: FizzBuzz