Project Euler-Problem 9

Description

From Project Euler:

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.

Solution

Creating all of the Pythagorean triplets can be done in one of two ways. The first is to simply pick arbitrary values for a and b and then compute the value of c. Using this tactic we can see that the following would hold true:

if a = 0 (which will maximize b in this equation, then
a² + b² = c²
b² = c²
b = c

and

a + b + c = 1000
2b = 1000
b = 500

Since a must be greater than 0, we can deduce that b must be less than 500. This means we need to search all of the pairs such that 1 <= a <= b < 500. Thankfully, there is a much easier solution. The astute reader may have noticed that a large number of the triplets (the vast majority in fact) will generate values of c that are irrational. Since we are only concerned with values of c that are natural numbers, there is an easy way to cut down the problem space.

The answer here is Euclid's formula for Pythagorean triples. This formula states that given an arbitrary pair of positive integers m and n such that m > n, a Pythagorean triple exists given by the equations:

a = m² - n²
b = 2mn
c = m² + n²

Given these equations, we can easily work out what the range of m and n are that we need to search to find our answer.

a + b + c = 1000
m² - n² + 2mn + m² + n² = 1000
2m² + 2mn = 1000
if n = 0 (which will maximize m in this equation), then
2m² = 1000
m² = 500
m = 22.360...

Since m and n must be positive integers, we know that the range we need to search is 1 <= n < m < 23. This is a much smaller search space than our first attempt.
With all of this theory out of the way, lets take a look at some code.

class Problem009
  def find_triplet
    max = Math.sqrt(500).floor
    2.upto(max) do |m|
      1.upto(m-1) do |n|
        a = m**2 - n**2
        b = 2*m*n
        c = m**2 + n**2
        return [a, b, c] if a + b + c == 1000
      end
    end
  end
end
Problem009.new.find_triplet.reduce(1, :*)

The full source and specifications can be seen on github. Next time, computing the sum of all prime numbers less than 2 million.