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 (a,b,c) 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 lengthc.

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.

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.

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]

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

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

If you consider a primitive triple (a,b,c) such that b-a divides c, then it is not hard to see that b-a = 1. Indeed, any common prime factor of b-a and c divides b^2-a^2 and therefore 2a^2 and 2b^2. Since a and b are coprime, we find that p divides 2. Now, if b-a is even and c is even then all a,b,c are even so the triple is not primitive.

Once we find that b=a+1 there are simple recursive formulas to do the rest. See the following link: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Pythag/pythag.html#section3.2

This makes the computation instant since there are only about 11 primitive triangles with perimeter below the limit.