Pythagorean Triples Formula in Javascript - Project Euler Prob 9

Question

I'm trying to solve the Project Euler 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 looked on Wikipedia for the formula to find Pythagorean triples and tried to translate it into code. The problem is that the code is outputting the wrong answer, but I think that the code is correct.

var a, b, c;
var pos1, pos2, pos3;
var ans1, ans2, ans3;

for(var n=2; n<=20000; n++) {
  a = 2 * n + 1;
  b = 2 * n * (n +1);
  c = 2 * n * (n +1) + 1;
  if(a<b<c) {
  if(a^2 + b^2 === c^2) {
      pos1 = a;
      pos2 = b;
      pos3 = c;
  }
  if(a + b + c ===1000) {
      ans1 = a;
      ans2 = b;
      ans3 = c;
  }
}
}
console.log(ans1 + " " + ans2 + " " + ans3);

Answer 1

This is a solution

var a;
var c;

for (var b = 1; b < 1000; b += 1) {
    a = (500000 - 1000 * b) / (1000 - b);

    if (Math.floor(a) === a) {
        c = 1000 - a - b;

        break;
    }
}

console.log(a, b, c);

Result is 375 200 425

on jsfiddle

Pythagoras
a² + b² = c²

Also we have
a + b + c = 1000

algebra, rearrange c to left
c = 1000 - (a + b)

insert c back in pythagoras
a² + b² = (1000 - (a + b))²

multiply out
a² + b² = 1000000 - 2000 * (a + b) + (a + b)²

multiply out
a² + b² = 1000000 - 2000 * (a + b) + a² + 2 * a * b + b²

rearrange a² + b² to simplify
0 = 1000000 - 2000 * (a + b) + 2 * a * b

rearrange unknowns to left
2000 * (a + b) - 2 * a * b = 1000000

simplify, / 2
1000 * (a + b) - a * b = 500000

factorsize
a(1000 - b) + 1000 * b = 500000

rearrange
a(1000 - b) = 500000 - 1000 * b

a = (500000 - 1000 * b) / (1000 - b)

now input b, calculate a and test if a is an integer as required by Pythagorean Triples

Answer 2

TGarr, here is an explanation to Xotic750's answer.

I don't really understand how you created the algorithm. Why is a = to (500000 - 1000 * b) / (1000 - b) ...

He started with a^2 + b^2 = c^2, and a + b + c = 1000, and combined them because the problem on projecteuler states that there is only 1 set of numbers where both of these statments will be true. Here's how he combined them. He solved the second equation for c to be c = 1000 - (a + b). Then he plugged that into the first equation so that it became a^2 + b^2 = (1000 - (a + b))^2. He continued until he was able to solve the entire equation for a. Once he was able to do that, he was able to make a single for loop that increases b, which is much simpler and more elegant than many other options.

why is the if statement's conditions set to Math.floor(a) === a?

This just means "is a, rounded down to its nearest integer, the same as a?" In other words, is a an integer? (copy his code, and add console.log ( a ); above the if statement. That might help you understand that bit of code) Since he was able to solve the equation for a, all he had to do was plug in different numbers for b, and as soon as the outcome was an integer, he'd have the answer. Or at least he'd know what a and b c = 1000 - a - b; tells him what c is, and that's all she wrote.

Answer 3

Here is another solution with less code:

for(var a = 1; a < 500; a++){
  for(var b = a; b < 1000; b++){
    var c = Math.sqrt(a * a + b * b);
    if(c > b && Number.isInteger(c) && a + b + c == 1000){
      console.log(a * b * c);
    }
  }
}

The result is: 31875000 :)

Answer 4

You can't calculate powers like that.

Use Math.pow(a,2) to calculate a^2

var a, b, c;
var pos1, pos2, pos3;
var ans1, ans2, ans3;

for(var n=2; n<=20000; n++) {
  a = 2 * n + 1;
  b = 2 * n * (n +1);
  c = 2 * n * (n +1) + 1;
  if(a<b<c) {
  if(Math.pow(a,2) + Math.pow(b,2) === Math.pow(c,2)) {
      pos1 = a;
      pos2 = b;
      pos3 = c;
  }
  if(a + b + c ===1000) {
      ans1 = a;
      ans2 = b;
      ans3 = c;
  }
}
}
console.log(ans1 + " " + ans2 + " " + ans3);

Answer 5

eq 1 : a² + b² = c²

eq 2 : a + b + c = 1000

From eq 1 and eq 2 we can have

eq 3 : c = 1000 - a - b

Substitute the value of c from eq 3 into eq 1 we get :

eq 4 : a² + b² = (1000 - a - b)²

R.H.S of eq 4 is a trinomial squared. We know that square of a trinomial of such kind is

(a - b - c)² = a² + b² + c² – 2ab + 2bc – 2ca

We get :

a² + b² = 1000² + a² + b² – 2*1000*a + 2*a*b – 2*b*1000

Now we simplify to get a to the L.H.S

a = (1000² - 2*1000*b)/(2*1000*b)

Now I can use this to find out value of a where it is an integer and then use Math.sqrt( aa + bb ) to calculate the value of c. Then I can check if a+b+c==1000 holds to be true.

My solution:

public class ProjectEuler9 {
    public static void main(String[] args) {
        long start = System.nanoTime();
        double a;
        for(int b=1; b<1000; b++){
            a = ( (Math.pow(1000, 2) - 2000*b ) / (2000- 2*b) );
            if(Math.floor(a) == a) {
                // a is an integer
                double c = Math.sqrt((a*a + b*b));
                System.out.println("a : " + a + " b :" + b + " c : " + c);
                long product = (long) (a*b*c);
                System.out.println("product abc : " + product);
                break;
            } else {
               //a is not an integer.
            }
        }
        long stop = System.nanoTime();
        System.out.println("\nTime: " + (stop - start) / 1000 + " ns");
    }
}

Output :

a : 375.0 b :200 c : 425.0
product abc : 31875000

Time: 3714 ns