#### Description

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

For example, 3a^{2}+b^{2}=c^{2}^{2}+ 4^{2}= 9 + 16 = 25 = 5^{2}.

There exists exactly one Pythagorean triplet for whicha+b+c= 1000.

Find the productabc.

#### 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:

ifa= 0 (which will maximizebin this equation, thena^{2}+b^{2}=c^{2}b^{2}=c^{2}b=c

and

a+b+c= 1000

2b= 1000b= 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:

Given these equations, we can easily work out what the range ofa=m^{2}-n^{2}b= 2mnc=m^{2}+n^{2}

`m`and

`n`are that we need to search to find our answer.

Sincea+b+c= 1000m^{2}-n^{2}+ 2mn+m^{2}+n^{2}= 1000

2m^{2}+ 2mn= 1000

ifn= 0 (which will maximizemin this equation), then

2m^{2}= 1000m^{2}= 500m= 22.360...

`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.

## No comments:

Post a Comment