In Problem 91 of Project Euler we are dealing with a geometry problem which reads

The points P (x_{1},y_{1}) and Q (x_{2},y_{2}) are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,

0≤x_{1},y_{1},x_{2},y_{2}≤2.

Given that 0 ≤x_{1},y_{1},x_{2},y_{2}≤50, how many right triangles can be formed?

The brute force solution for solving this would be to test all combinations of P and Q which is along the lines of 51^{4} which is approximately 7.000.000 solutions to check. So we will take another approach here.

There are three possibilities to make a right angled triangle. Either the right angle is at O, P and Q. O is fixed but P and Q can be interchanged so we will start by treating the regular case of the right angle being at P and 0 < x_{1}, y_{1}. You will see later on that the other cases are special cases which we can solve rather easily.

## Regular case

I will do this by using the example illustrated to the right where P is in the point (4,6). That means the slope of the line leading to P is 6/4. If we want to make a line orthogonal to that (meaning the will make a right angle) we will end up with a slope of that line of -4/6 or if we reduce it with the greatest common divisor the slope is -2/3.

Or in other words for every 3 we move out of the x-axis we fall exactly 2 on the y-axis. Since we are starting in an integer point after moving 3 out of the x-axis we reach a new integer point. We can keep finding solutions in this way until we either reach the maximum value for x or reach 0 on the y-axis. In our case it gives us the minimum of (x_{max}-4)/3 and 6/2 solutions depending on which constraint we will meet first.

This can be generalised as with the following formula. Let us define dx = y_{1}/gcd(x,_{1}, y_{1}) and dy = x_{1}/gcd(x,_{1}, y_{1}) where gcd is the greatest common divisor function.

This gives us min((x_{max}-x_{1)}/dx, y_{1}/dy) solutions downwards for a given point P.

In order to find all solutions to the in the upwards direction we can mirror this solution in the line y=x and that will give us the solutions for that.

## Special cases

Let us first treat the special case where the right angle in in O. This means that the P should be on the x-axis and Q should be on the y-axis such that y_{1} = x_{2} = 0 and thus we have solutions for every combination of y_{2} and x_{1} which is the same as x_{max}^{2}.

The reason I wanted to treat the case of P being on the x or y-axis as special cases as well is that we end up dividing by 0 if we use the regular case. However, if y_{1}=0 we get an integer solution for x_{2}=x_{1} and any integer value of y_{2}. Or in other words for each value of the x_{max} different values of x_{2} there are x_{max} valid solutions.

The same goes for P being on the y-axis. So the special cases gives us a total of 3*x_{max}^{2} solutions.

## Implementing the solution

Given the formulas above we can rather easily make a solution where we iterate through all possible positions of P and then add the special cases. My implementation looks like

int size = 50; int result = size*size*3; for (int x = 1; x <= size; x++) { for (int y = 1; y <= size; y++) { int fact = gcd(x, y); result += Math.Min(y*fact /x, (size - x)*fact /y) * 2; } }

where the gcd implementation is copied from earlier solutions.

This gives us the result

There are 14234 triangles Solution took 0,2134 ms

and to be honest, I don’t think this can be done much faster.

## Wrapping up

I think this problem was a fun and challenging little exercise in geometry. The derived solution was as I see it pretty efficient in providing the solution.

My only doubt is whether I have expressed my thoughts well enough, so don’t hesitate on asking questions or making comments below the post. If you want the full implementation of the problem code including the gcd function it is available here.

A comparison of the rate of increase of the grid area and the rate of increase of the number of specific rectangular triangles described in the article is shown in Fig. 1 and Fig. 2.

The illustration in the article and Table 1 and 2 show that the simplest grid area (i.e. 1×1) can contain 3 rectangular triangles with one vertex having coordinates (0, 0). The next grid in size (2×2), can accomodate 14 of these rectangular triangles, etc…

A first estimation of the equation of these parabolic functions would be: y = a*(x^2), a<=0.01.

A more accurate determination of these equations might be obtained from a curve-fitting application such as XLfit.

http://www.excelcurvefitting.com

___

Table 1

Comparison of rate of increase:

Grid area (in blue), range: 1 @ 10 000; number of specific rectangular triangles (in red) described in the article,range: 3 @ 62 848.

[re: Project Euler 91].

http://img4.hostingpics.net/pics/880101pe91table1.jpg

___

Table 2

Comparison of rate of increase:

Grid area (in blue), range: 1 @ 100; number of specific rectangular triangles (in red) described in the article, range: 3 @ 448.

[re: Project Euler 91].

http://img4.hostingpics.net/pics/553354pe91tab2.jpg

Thanks again to Kristian for the code.

🙂

___

Sources:

1) Project Euler 91

Kristian’s algorithm

http://www.mathblog.dk/files/euler/Problem91.cs

2) Microsoft Visual C# 2010 Express

3) Microsoft Office Excel (2007)