Euler Problem 9 -Special Pythagorean triplet

Special Pythagorean triplet

Problem 9

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.

I took a lot of time thinking about the possible shortcuts that i can use to reduce this problem. I knew a straightforward approach however, that approach was going to be computationally very expensive. So was trying to find something which takes less of time. However, after investing lot of time I could not find anything better so here is my straightforward approach.

getTripletForSum = function(x) {
gotit = FALSE
for (a in 1:x) {
  for (b in 1:x) {
    for (c in 1:x) {
      if (a+b+c == x && !gotit) {
        lhs = (a*a) + (b*b)
        rhs = (c*c)
        if (lhs == rhs) {
          cat("The pythagorean triplets are ", a, b, c, 
              "and the product is ", a*b*c)
          gotit = TRUE
        }
      }
    }
  }
}
If (!gotit) {
cat(“No triplet with sum “, x)
}
}

The logic here is we pass the input as the sum of three numbers. For example , here, the sum of three numbers is 1000 (a+b+c). Then we write 3 for loops one each for a, b and c check if sum of those three numbers is equal to the number which we have passed. Also we maintain a flag to check if we have already got the triplets or not.

Once we get the combination where a + b+ c = x, we check if a2 + b2 is equal to c2. Once we get the correct triplet we print the result along with the flag.

getTripletForSum(12)
The pythagorean triplets are  3 4 5 and the product is  60

getTripletForSum(24)
The pythagorean triplets are  6 8 10 and the product is  480

getTripletForSum(1000)
The pythagorean triplets are  200 375 425 and the product is 31875000

getTripletForSum(25)
No triplet with sum 25

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s