Project Euler Problem 91 Statement
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 $\triangle 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 \le x_1, y_1, x_2, y_2 \le 2$.
Given that $0 \le x_1, y_1, x_2, y_2 \le 50$, how many right triangles can be formed?
Solution
Let's start with the example using point P(4,6). We find the Greatest Common Divisor (GCD) of 4 and 6, which equals 2. This tells us that our point (4,6) can be reduced to the primitive vector (2,3), represented by the purple dot.
When finding perpendicular vectors, we start with the primitive vector (2,3). From there, we can determine that our perpendicular vector will be (-3,2), which we'll scale appropriately to find valid points.
The code performs two crucial calculations using the code min(x*m//y, m*(N-y)//x). The first term, x*m//y, determines how far we can extend in the direction (-3,2), while the second term, m*(N-y)//x, calculates how far we can go in the opposite direction (3,-2). N-y accounts for the remaining space between our point and the grid boundary.
Looking at the diagram, we can see several key points. The blue point O represents the origin (0,0), while the red point P shows our chosen point (4,6). The green point Q indicates one possible point using the perpendicular vector, and there's a right angle marker showing where our 90° angle occurs.
The importance of using GCD becomes clear when we consider what might happen without it. If we didn't use GCD, we could miss point Q because we'd only be looking at larger steps. By using GCD, we can find ALL possible right triangles by working with the smallest possible steps. For instance, if we only used vector (4,6) instead of reducing it to (2,3), we would miss some valid triangles.
In summary, the code systematically finds all possible triangles through a comprehensive process. It considers every point P(x,y) in the grid, uses GCD to find the primitive vector, calculates perpendicular vectors, and determines how many valid triangles can be formed with each point. This methodical approach ensures we don't miss any possible right triangles within our grid.
One last detail, the expression (2*t + 3*N*N). The factor of 2 accounts for symmetrical cases and 3*N*N accounts for the trivial cases where the right angle is at one of the three points (origin or on either axis). See "Last Word" for a probably uneccessary deep dive on this simple expression.
HackerRank version
HackerRank Project Euler 91 increases the limit from 50 to 2500
Python Source Code
import math
N = int(input())
t = sum(min(x*m//y, m*(N - y)//x)
for x in range(1, N+1)
for y in range(1, N)
for m in [math.gcd(x, y)])
print(2*t + 3*N*N) Last Word
Let's start with the 2*t part. The variable t represents the sum of all the right triangles we found using our perpendicular vector method. We multiply this by 2 because for most triangles we find, there's actually a mirror image that's also valid. Think of it like this: when we find a right triangle with a right angle at point P, we could often create another valid right triangle by reflecting P across the line between O and Q. This doubling captures these symmetric cases.
Now for the 3*N*N part, which accounts for what we call the "trivial cases"—these are right triangles that are aligned with our coordinate axes. There are three types of these triangles:
First, consider right triangles where the right angle is at the origin (0,0). For any point P in our N×N grid, we can form a right triangle by using that point and another point directly above or to the right of it. This gives us N*N triangles, since each point in the grid can be used as P.
Second, think about right triangles where the right angle sits on the x-axis (but not at the origin). For any point on the x-axis and any point above it in the grid, we can form a right triangle. Again, this gives us N*N possibilities.
Third, we have the similar case where the right angle sits on the y-axis (but not at the origin). Just like with the x-axis, this gives us N*N more triangles.
Adding these three cases together gives us 3*N*N total "trivial" triangles. These are special because they don't follow the same pattern as the other triangles we found using perpendicular vectors—they're simpler and can be counted directly.