Project Euler - Rust Problem 9

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.

Pythagorean triplets are whole numbers that work with the right triangle formula.  They also increase in value so none of them are the same. 

There's a whole system of mathematics that deals with equations like this where there are multiple unknowns and various answers that once known will solve all equations present.  These equations are known as Diophantine equations.  

Thanks wikipedia... but that doesn't help me.  However, there's some juicy information on PT's.

Here are some properties that must be satisfied that we can use.

a^2 + b^2 = c^2
a < b < c
((c * a)(c*b))/2 is always a square
(3,4,5) is the smallest known PT
At most only one of a,b,c is a square (more than 1 square they're not a set)
a or b is divisible by 3
a or b is divisible by 4
a or b or c is divisible by 5
the largest number that always divides abc is 60

Ok, so there's a few things that we can increment by and check by. as well as a starting point.

We could always do the brute force method.

for i in 1..1000, for j in 2..1000, for k in 3..1000 if i+j+k = 1000, check if i^2 + j^2 = k^2, if true return i,j,k

Psudo code but that's the basic brute force. I mean if only one of them is equal to 1000 and satisfies the formula then great. 

However, I wanted to try a different approach.  There's a relation to PT's and Fibonacci sequences that is pretty interesting.  The downside to our current problem is that while the Fib numbers do follow a predictive pattern, they do not encompass all the PT's in that range.  They skip quite a few.

Kind of a "all buicks are cars but not all cars are buicks".

I've been working on this for about a week now.  I've been distracted with my family.  However, I think I've been trying to reinvent the wheel.  I got sucked into a tangent with the Fibonacci sequence trying to use that to determine the answer.  It won't hit the numbers that we're looking for.

So I went ahead and brute forced it.  I'm not proud but I am tired of this problem.