Problem 039


Project Euler

Integer right triangles

Problem 39

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximized?


 Again, the larger the number, the number of solutions should also increase in general. Therefore, we’ll start will the maximum number ( p ≤ 1000) and count backward.

We can cut the search space smaller by recognize the following triangle with a, b, c.

a + b < c
a + b + c = p
Therefore, search a between 1 to \frac{p}{2} and search b between a+1 to \frac{p}{2} in a nested loop to ensure no repeat combination of a and b. Then, increment the number of solution for a specific c by solving c base on a and b using the equations from above. Since p ≤ 1000, then c ≤ 998. At the end, find the c with the most solution.
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