Project Euler 91: Find the number of right angle triangles in the quadrant

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

The points P (x1, y1) and Q (x2, y2) 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,
x1, y1, x2, y2  2.

Given that 0 ≤ x1, y1, x2, y2  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 514 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 < x1, y1. 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  (xmax-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 = y1/gcd(x,1, y1) and dy = x1/gcd(x,1, y1) where gcd is the greatest common divisor function.

This gives us min((xmax-x1)/dx, y1/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  y1 = x2 = 0 and thus we have solutions for every combination of y2 and x1 which is the same as xmax2.

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 y1=0 we get an integer solution for x2=x1 and any integer value of y2. Or in other words for each value of the xmax different values of x2 there are xmax valid solutions.

The same goes for P being on the y-axis. So the special cases gives us a total of 3*xmax2 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.

Posted by Kristian

1 comment

Jean-Marie Hachey

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)

Leave a Reply