Project Euler

A Taste of Number Theory

Problem 9: Special Pythagorean Triplet

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2. For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

The Catch

How to generate Pythagorean triplets.

The Light

Utilize the Euclid's Formula to create Pythagorean triplets: given an arbitrary pair of positive integers m and n with m > n, the formula states that:

  • a = m2 - n2
  • b = 2 * m * n
  • c = m2 + n2

Check when their sum equals 1,000 and find their product.

The Code

public class Problem9
{
  public static void main(String[] args)
  {
    for(int m = 2;; m++) 
    {
      for(int n = 1; n < m; n++)
      {
        int a = m * m - n * n;
        int b = 2 * m * n;
        int c = m * m + n * n;

        int sum = a + b + c;
        if( sum == 1000 )
        {
          System.out.println("a = " + a);
          System.out.println("b = " + b);
          System.out.println("c = " + c);
          System.out.println(a * b * c );
          return;
        }
      }
    }
  }
}