Project Euler 139: Pythagorean tiles

Project Euler 139: Pythagorean tiles

Written by on 9 March 2013

Topics: Project Euler

In Project Euler There are loads of problems that end up with a number theoretic solution. Problem 139 is no exception to that.  The problem reads

Let (abc) represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length c.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

Before going into a solution I have just pulled out the figure and named some of the line segments.

p_139

Such that we have the triangle a,b,c and then the have the square in the middle with the side length d. Since we have 4 similar triangles, you can name the rest of the line segments yourself. Based on the drawing it is rather easy to see that d = b – a. Therefore any combination og a,b and c that will solve the problem we have that the

This can also be rewritten such that we have that

For some integer value of y. Now that we have covered the basics, I will give you two different approaches to solving it.

Finding Primitive Triplets

In  the last problem I tried to make a solution which finds primitive triplets and then use that to generate a solution. I couldn’t get through with that within the given time limit.  However for this problem I will try it again. A primitive triplet is a right angled triangle with integer sides where the greatest common divisor of the sides are 1. Such that we cannot make it smallet.

A primitive triplet is a solution if it respects the first equation such that the areas fit. Furthermore if we have a primitive triplet we can multiply all sides with an integer k and it will still hold. And we will have still a solution to the problem that fulfills the first condition. That means for any primitive triplet we can find we have 100.000.000/(a+b+c) solutions.

So reusing the primitive triple generator we have build from previous problems we can solve the problem like this

long limit = 100000000;
long result = 0;
long mlimit = (long)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 = 2 * m * n;
long b = m * m - n * n;
long c = m * m + n * n;
long p = a + b + c;
if(c % (b-a) == 0)
result += limit / p;
        }
    }
}

I have put in a search limit for m, which can convince yourself is correct if you rewrite a+b+c in terms of m and n. The code takes a little more than 1.5seconds to run

Solving a Diophantine Equation

The alternative to find the primitive triplets is to manipulate the Pythagorean equation a bit until we arrive at something which can be treated as a Diophantine equation and then solve that.  So we have

And we can express b in form of b = a-d, and c in the form of dy such that we get

We can multiply both sides with 2, and then shorten the lefthand side such that

And then divide both sides with

Or rearranged

If we then substitute x = 2a/d – 1 then we have

Which is a classic Diophantine equation or Pell’s equation which we can solve.

We need to find solutions for the Pell equation until we have that a+b+c > 100.000.000. This means that we should check if

Since we have that xd = a + b and we have c = yd, and since solving the Pell’s equation corresponds to finding primitive triplets which fulfills the requirements we can conclude that d=1, since since a divisor of a, b and c is d. And since the greatest common divisor among a, b and c has to be one if it is a primitive Pythagorean triple.

Once again we have a  number of solutions based on the Pell equation corresponding to 100.000.000 / (x+y).

We can solve the Pell’s equation by heading over to Dario Alpern’s Generic Two integer variable  equation solver once again. Based on that we get the code

long result = 0;
long limit = 100000000;
long x = 1;
long y = 1;

while(x+y < limit){
    long xnew = 3 * x + 4 * y;
    long ynew = 2 * x + 3 * y;

    x = xnew;
    y = ynew;

    result += limit / (x + y);
}

This code gives us the same solution but in 0.0003 ms instead.

Wrapping up

As always you can find the source code here.

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

  1. Jean-Marie Hachey says:

    Table 1
    Primitive Pythagorean triads with c ≤ 100
    and the squares circumscribed by four identical rectangular triangles.
    [Re: Project Euler 139: Pythagorean tiles]

    http://img28.imageshack.us/img28/3161/pe139tablone.jpg

    ___

    In this limited series, we see that two consecutive Pythagorean triples with the same value of SCRT present one the following characteristics:
    1) a + (3 x k); b + (3 x k); c + (4 x k) (where k = 1); perimeters differences: 10. [EN: 2, 4; 13, 14]
    2) a + (3 x k); b + (3 x k); c + (4 x k) (where k = 7); perimeters differences: 7×10. [EN: 3, 11]
    3) a + 17; b + 17; c + (4 x k) (where k = 6) [EN: 15, 16]

  2. Kristian says:

    Interesting observation. can you elaborate more on that in order to generalize it?

  3. Jean-Marie Hachey says:

    Hi Kristian,
    Here is an example of calculations applied to
    the case where (b-a)=1; SCRT=1.

    http://img829.imageshack.us/img829/7814/pe139tabtwocalcn.jpg

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=""> <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

Notify me of comments via e-mail. You can also subscribe without commenting.