# Project Euler 39

We’re looking at Pythagorean triplets, that is equations where a, b and c are integers, and:

a^{2} + b^{2} = c^{2}

The triangle defined by a,b,c has a perimeter.

The triplet 20,48,52 fulfills the equation, 20^{2} + 48^{2} = 52^{2.} And the perimeter of the triangle is 20 + 48 + 52 = 120

Which perimeter p, smaller than 1000, has the most solutions?

So, we have two equations:

a^{2} + b^{2} = c^{2}

p = a + b + c

We can write

c = p – a – b

And substitute that into the first equation:

a^{2} + b^{2} = (p – a -b)^{2}

Expanding the paranthesis:

a^{2} + b^{2} = p^{2} – ap – bp – ap + a^{2} + ab – bp + ab + b^{2}

Cancelling:

0 = p^{2} – 2ap – 2bp + 2ab

Isolating b:

0 = p^{2} – 2ap – b(2p – 2a)

b(2p – 2a) = p^{2} – 2ap

b = (p^{2} – 2ap)/(2p – 2a)

So. For a given value of p, we can run through all possible values of a and get b. If b is integer, we have a solution that satisfies the constraints.

The smallest value of a we need to check is 1. But what is the largest value of a for a given value of p?

We can see from the pythagorean equation, that a =< b < c. a might be larger than b, but we can then just switch a and b. So it holds. What follows from that, is that a =< p/3.

What else? If a and b are both even, a^{2} and b^{2} are also even, then c^{2} is even, and then c is even, and therefore p = a + b + c is also even.

If a and b are both uneven, a^{2} and b^{2} are also uneven, and c^{2} is then even. c is then even. And therefore p = a + b + c must be even.

If either a or b are uneven, either a^{2} or b^{2} is uneven. Then c^{2} is uneven, and c is then uneven. Therefore p = a + b + c must be even.

So. I only need to check even values of p. That halves the number of values to check.

Allright, time to write some code:

```
current_best_number_of_solutions <- 0
for(p in seq(2,1000,by=2)){
solutions_for_current_p <- 0
for(a in 1:ceiling(p/3)){
if(!(p**2-2*a*p)%%(2*p-2*a)){
solutions_for_current_p <- solutions_for_current_p + 1
}
}
if(solutions_for_current_p > current_best_number_of_solutions){
current_best_p <- p
current_best_number_of_solutions <- solutions_for_current_p
}
}
answer <- current_best_p
```

current_best_number_of_solutions is initialized to 0.

For every p from 2 to 1000, in steps of 2 (only checking even values of p), I set the number of solutions_for_current_p to 0.

For every value a from 1 to p/3 – rounded to to an integer: If !(p**2-2*a*p)%%(2*p-2*a) is true, that is, if the remainder of (p**2-2*a*p)/(2*p-2*a) is 0, I increment the solutions_for_current_p.

After running through all possible values of a for the value of p we have reached in the for-loop:

If the number of solutions for this value of p is larger, than the previous current_best_number_of_solutions, we have found a value of p that has a higher number of solutions than any previous value of p we have examined. In that case, set the current_best_p to the current value of p. And the current_best_number_of_solutions to the number of solutions we have found for the value of p.

If not, dont change anything, reset solutions_for_current_p and check a new value of p.