DescriptionFrom Project Euler:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
SolutionCreating 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
a2 + b2 = c2
b2 = c2
b = c
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 = m2 - n2Given these equations, we can easily work out what the range of m and n are that we need to search to find our answer.
b = 2mn
c = m2 + n2
a + b + c = 1000Since 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.
m2 - n2 + 2mn + m2 + n2 = 1000
2m2 + 2mn = 1000
if n = 0 (which will maximize m in this equation), then
2m2 = 1000
m2 = 500
m = 22.360...
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.