Project Euler 39: If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?

Written by on 3 May 2011

Topics: Project Euler

Even though the title nor the description of Problem 39 of Project Euler mentions Pythagorean Triplets, this is the topic we are revisiting. The problem description reads

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 maximised?

The answer is certainly not p = 1000 which I can state so boldly since we in Problem 9 was given the fact that there only exists 1 triplet with that property.

I have found three different approaches to solving this problem. We can brute force it, we can take an arithmetic approach where we rewrite the equations so we only have to work two parameters and check if an equation has an integer solution, and last but not least we can reuse all the work we derived in solving Problem 9 yielding a very efficient solution to the problem.

I wont cover the brute force method in this post, but I have included it in the source code for reference to timing. The brute force implementation took 348 ms to run.

Arithmetic Approach

We are given two equations to work with

a2 + b2 = c2 (1)

a + b+ c = p (2)

Thus we can rewrite (2) as c = p  – a – b and insert it into (1) yielding

a2 + b2 = (p-a-b)2 = p2 + a2 + b2 -2pa – 2pb + 2ab

Isolating b on one side of that equation yields

b = (p2 -2pa) / (2p-2a)

So for all values of p and a where b is an integer is a Pythagorean triplet with the perimeter p.

We can further make a bit of analysis on (1)

if a and b is even so is c and thus p is even

if a or b (but not both) is odd then c is odd and thus p is even

if both a and b is odd then c is even and thus p is even

Therefore we only need to check the numbers where p is even.

Furthermore we know a < c and b < c and without loss of generality we can assume that ab (otherwise we could switch them) which gives us that ab < c.  That implies  a < p/3 and thus we don’t need to check values higher than that.

This can be implemented in C# as

long result = 0, resultSolutions = 0;

for (long p = 2; p <= 1000; p += 2) {
    int numberOfSolutions = 0;
    for (long a = 2; a < (p/3); a++) {
          if(p*(p-2*a) % (2*(p-a)) == 0){
              numberOfSolutions++;
          }
      }
      if(numberOfSolutions > resultSolutions){
        resultSolutions = numberOfSolutions;
        result = p;
    }
}

The result we get out of this will give us the right number, but it wont give us all the ordered triplets. However, for the rather small number p < 1000 we get a fast solution yielding

The number of solutions is maximized for p=840
Solution took 2 ms

Number Theoretic approach

In the solution of Problem 9 we derived a rather intricate solution to finding a Pythagorean triplet for a specific p. I would suggest you read the deduction of that algorithm in order to understand the how to exploit coprimability and primitive Pythagorean triplets.

Once you understand that the solution, the modification to solve this problem is trivial and can be implemented in C# as

int pMax = 0, tMax = 0;
int m = 0, k = 0;

for (int s = 1; s <= 1000; s++) {
    int t = 0;
    int mlimit = (int)Math.Sqrt(s / 2);
    for (m = 2; m <= mlimit; m++) {
        if ((s / 2) % m == 0) { // m found
            if (m % 2 == 0) { // ensure that we find an odd number for k
                k = m + 1;
            } else {
                k = m + 2;
            }
            while (k < 2 * m && k <= s / (2 * m)) {
                 if (s / (2 * m) % k == 0 && gcd(k, m) == 1) {
                     t++;
                 }
                 k += 2;
             }
         }
     }
     if (t > tMax) {
        tMax = t;
        pMax = s;
    }
}

This code runs in 0ms for p ≤ 1000 and if we increase the the maximum of p, this is significantly faster than any of the other solutions I have tried.

Wrapping up

In the available source code you will find 3 solutions, the two presented here and a brute force solution. The last presented solution scales rather well and can solve the problem in less than 4 seconds.

As usual I would like to hear from you if you have another solution strategy, comments or questions.

5 Comments For This Post I'd Love to Hear Yours!

  1. Googol says:

    Nice work, although I’ve found an error in the arithmetic approach. This error does not affect the final result, so 840 is the answer for the project Euler question.

    But the way for counting the number of triangles fails because of the limit. Your for goes from 2 to p/3. But this could in fact be too high. For some triangles, both cathetus can be less than p/3. For example, with perimeter equal 70, only one triangle exists {29, 21, 20} but your for will inform about two, that are the same {29, 21, 20} and {29, 20, 21}.

  2. I wrote this code for Project Euler problem 75 , which asks how many integers ? 1500000 exist, where the integer is a perimeter length that can be divided into three integer-length sides of a right triangle in one unique way.

  3. Jacky Tang says:

    For the code in the arithmetic approach, b has to be checked if it is bigger than or equal to a, otherwise some solutions will be double counted.
    So that e.g. when p=70, only {20, 21, 29} is emitted.

  4. Maxime says:

    You can actually do this problem without any computations.

    All pythagorean triples can be generated using the following formula:
    a=m²-n², b=2mn, c=m²+n² with 0<m<n
    All the triples (ka, kb, kc) with k integer are Pythagorean triples.
    From this results the fact that the perimeter of a right angle triangle with integer length must be of the form 2km(m+n) (I simply summed a, b and c).

    The problem is therefore equivalent to finding the value s below 1000 so that s can be written as s=2*km(m+n) with the most different triples (k, m, m+n).

    In other words, we are looking for the value below 1000 which has the most distinct triples of factors. Since those triples are directly related to the number of factors or the number, we are simply looking for the number below 1000 with the most factors. Looking up a table of highly composite numbers under 1000 gives a maximum value of 840, which is our solution.

  5. Michael says:

    The Number Theoretic code has an error
    If “if (t > tMax)” is changed to “if (t >= tMax)”
    the answer will become 841 – revealing the error

    Every s and s+1 will give same result on line
    if ((s / 2) % m == 0) { // m found

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

This site uses cookies.