Project Euler 75: Find the number of different lengths of wire that can form a right angle triangle in only one way.

Project Euler 75: Find the number of different lengths of wire that can form a right angle triangle in only one way.

Written by on 17 December 2011

Topics: Project Euler

Assuming we have solved the problems from one end, we are now at Problem 75 of Project Euler which should unlock the 75 problem achievement as well as the Pythagorean Triplet achievement. The problem description reads

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

Note: This problem has been changed recently, please check that you are using the right parameters.

I have already noted that we should unlock the Pythagorean triplet achievement, and that is for a reason. In order to get a good solution we need to revisit the theory we used in Problem 9 about Pythagorean triples.

Pythagorean Triplets

The theory on Pythagorean triplets as given on Wikipedia states that we can generate every primitive triplet by iterating over the integers m, n such that m > n, and m+n is odd and gcd(n,m) ) 1 then the triplets are generated by

a = m2 – n2
b = 2mn
c = m2 + n2

Based on this we can generate all triplets by taking multiples of the primitive triplets such that

a = k(m2 – n2)
b = 2kmn
c = k(m2 + n2)

So now we have a method to generate all possible triplets. Now we just need to iterate over all m and n which fits the properties.

Tracking the number of ways a length can be generated

I have chosen a method based on an array which stores the number of ways a certain length of wire can be generated. So I basically increase the count of the array by one for the result of a+b+c.

Since we have one side which is generated by m2 + n2 we only need to check for m up to . I have implemented the function as

int limit = 1500000;
int[] triangles = new int[limit+1];

int result =0;
int mlimit = (int)Math.Sqrt(limit / 2);

for (long m = 2; m < mlimit; m++) {
    for (long n = 1; n < m; n++) {
        if (((n + m) % 2) == 1 && gcd(n, m) == 1) {
            long a = m * m + n * n;
            long b = m * m - n * n;
            long c = 2 * m * n;
            long p = a + b + c;
            while(p <= limit){
                triangles[p]++;
                if (triangles[p] == 1) result++;
                if (triangles[p] == 2) result--;
                p += a+b+c;
            }
        }
    }
}

Which results in the code executing in

There are 161667 triangles which can be bent one way
Solution took 45 ms

Compared to the first few tries I took at the algorithm, I am pretty satisfied with execution time. After all we need to check quite a few number of triangles.

Wrapping up

We could have modified the code from Problem 39 or Problem 9. I tried that but the presented the solution is just faster.

As usual you can find the source code for the solution here. Comments, other solutions and questions are as always welcome in the comment section, and I will do what I can to reply to them.

The blog awesome image being the most artistic image illustrating a piece of wire I could find is kindly shared by Chris and Laura Pawluk under the creative commons license.

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

  1. Thanks Kristian for another great post. Very clear explanation. I was having trouble with this one – and your array structure (incrementing and decrementing a list was really great).

    I had a question about the 18th line of code – p += a.

    I think that p should be incremented by a step value equal to the original p. When I rewrote the code to be p += p, this was also a problem because it changes the incremental step function, so I had to assign a step variable to the original value of p, and then use p += step.

  2. Kristian says:

    Hi Robert

    Thanks for the comment. To be honest, I have no idea why I made that mistake. I must have been trying something else and then forgot to correct it again.

    You are of course right, Line 18 should be changed to p += a+b+c. The result I posted is even wrong due to this mistake. Thanks for coming up with the correct fix for the problem. I have made the corrections in the post as well as in the source code.

    /Kristian

  3. Mike says:

    I took a different approach, and found the primatives in a tree like fashion.
    Given:
    a^2+b^2=c^2
    a=q+m
    b=q+n
    c=q+m+n

    we get
    q=sqrt(2mn) || q=-sqrt(x)
    m=c-b
    n=c-a
    q=a+b-c

    Using this, given a Pythagorean triplet, we can find m,n,q. We also know that inverting the sign on q, then solving for a,b,c will yield another triplet (with a and/or b being negative)

    Given a triplet, inverting the signs of a and or b, will produce another set satisfying the Pythagorean,equation. By applying the above process to these points, we get 3 other Pythagorean triplets. While applying it to the original appears to give us the previous triplet. We can reapply this approach to those to generate another 3 for each of the ones we found.

    For each triplet we find, we can multiply each value by an integer to get a ‘simmilar’ triplet, or divide by a common factor. Originally, I was going to explicitly prevent duplicates by recording ones I found, but in running my code I found that no duplicates were generated, and that starting with (3,4,5) produced only primitive triplets (Obviously I only checked a finite portion of the tree, and have not found a proof saying either of these will always be the case)

    I can somewhat justify starting with 3,4,5 because its ‘parent’ is -1,0,1 whose parent is itself. and whose children are 1,0,1; and 3,4,5.

    The only evidence I have that this works out to find all of them is that it gave me the correct answer.

    Below is the code that pops a triplet off a stack, then pushes its three children on:

    cursor=triplets.pop();
    int[][] sppt=new int[3][3];
    sppt[0]=cursor.clone();
    sppt[1]=cursor.clone();
    sppt[2]=cursor.clone();
    sppt[0][0]*=-1;
    sppt[1][1]*=-1;
    sppt[2][0]*=-1;
    sppt[2][1]*=-1;
    for (int [] p : sppt){
    	int m=p[2]-p[1];
    	int n=p[2]-p[0];
    	int q=p[0]+p[1]-p[2];
    	int[] child=new int[3];
    	child[0]=m-q;
    	child[1]=n-q;
    	child[2]=m+n-q;
    	triplets.push(child);
    }
    
  4. Kristian says:

    Hi Mike

    That is certainly an interesting approach. Your approach seems similar to the one described on wikipedia under the parent/child relationship.

    This early in the morning I can’t figure out if it is indeed the same transform as made there. If this is true, then you have your proof that your method does generate all primitive triplets.

    Well done.
    Kristian

  5. Christian says:

    If we must multiply by a variable ‘k’ to obtain all unique triples, how come you didn’t include that factor in your code? You somehow (correctly) assumed that if a primitive triple shared a perimeter with a composite triple, that it must too share a perimeter with a different primitive triple, but I don’t see how one could prove that.

  6. Kristian says:

    The while loop starting on line 14, is actually where I multiply with k. So I am using k, just a bit disguised.

  7. Susanne Rynders says:

    Your program gives the wrong solution for limit = 120.

  8. Kristian says:

    You might be right, but what is the correct solution, and what solution does the program give?

  9. Jean-Marie Hachey says:

    Table 1
    Number of different integer sided right angle triangles
    generated by different int limits using algorithm (1).
    [Re: Project Euler 75]

    http://img15.hostingpics.net/pics/806648pe75tab1.jpg

    ___

    Sources:
    1) Project Euler 75
    Kristian’s algorithm
    http://www.mathblog.dk/files/euler/Problem75.cs
    2) Microsoft Visual C# 2010 Express
    3) Microsoft Office Excel (2007)

  10. Babak Sairafi says:

    Hello
    This is my code that same your code but conditions in my loops are different with your conditions. Hence code is faster.

    int gcd(int n, int m)
    {
    if (n % m == 0)
    return m;
    else
    return gcd(m, n % m);
    }

    void euler75()
    {
    long max = 1500000;
    int[] l = new int[max + 1];

    for (int n = 1; n <= Math.Sqrt(max) / 2; n++)
    for (int m = n + 1; 2 * m * m + 2 * m * n <= max; m++)
    {
    if ((m – n) % 2 == 1 && gcd(m, n) == 1)
    {
    long a = m * m – n * n;
    long b = 2 * m * n;
    long c = m * m + n * n;
    long p = a + b + c;
    for (long k = 1; k * p <= max; k++)
    l[k * p]++;
    }
    }

    int cnt = 0;
    for (int i = 0; i <= max; i++)
    if (l[i] == 1)
    cnt++;
    textBox1.Text = cnt.ToString();
    }

  11. Kristian says:

    Could you elaborate a bit more on the different conditions and why they hold?

  12. BabakSairafi says:

    1. clearly n=1 and cause m>n then m=n+1.

    2. condition loop n:
    a+b+c<=max therefor m*m-n*n+2*m*n+m*m+n*n<=max
    2*m*m+2*m*n<=max and m=n+1:
    2*(n+1)*(n+1)+2*(n+1)*n<=max and n~n+1:
    4*(n+1)*(n+1)<=max
    (n+1)*(n+1)<=max/4
    n+1<=sqrt(max)/2
    n<sqrt(max)/2

    3. condition loop m
    a+b+c<=max therefore 2*m*m+2*m*n<=max

  13. Jeremy says:

    I think the Tree of Pythagorean triples might be faster than using Euler’s formula: every node on the tree is a primitive triple, vs Euler’s formula where you have to calculate the gcd of every m,n before proceeding.

  14. W.Bruechle says:

    The code could be faster because you are not interested in a,b,c, but only the sum. So one does not need +n*n and -n*n:
    long a = m * m + n * n;
    long b = m * m – n * n;
    long c = 2 * m * n;
    long p = a + b + c;
    Instead of the 4 lines, long p=2*m*(m+n) does the business faster.

  15. Martin says:

    Thanks for your nice blog. I do not understand how you assure that not only primitive triples are calculated. I am missing the extra parameter k and don’t get line 18. Could you please clarify this a bit?

Trackbacks For This Post

  1. Project Euler 75 – Investigating Pythagorean triples

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.