Detailed mathematical approach

Problem Summary

Let \(O=(0,0)\), and let \(P\) and \(Q\) be distinct lattice points in the square \(0 \le x,y \le 50\), excluding the origin itself. Every unordered pair \(\{P,Q\}\) determines a candidate triangle \(OPQ\). The task is to count how many of those triangles are right triangles.

The C++, Python, and Java implementations do not rely on a closed formula. They use an exact geometric invariant: a right angle is detected by a zero dot product. Because the grid is still small enough, every unordered pair of non-origin lattice points can be tested directly.

Mathematical Approach

Write \(P=(x_1,y_1)\) and \(Q=(x_2,y_2)\). Since the origin is fixed, the whole search space is just the set of unordered pairs of distinct non-origin lattice points. The central question is therefore not how to draw the triangles, but how to recognize efficiently whether a given pair \(\{P,Q\}\) produces a right angle at \(O\), at \(P\), or at \(Q\).

The state space is a pair of lattice points

There are \((50+1)^2-1=2600\) lattice points in the square other than the origin. Choosing two of them gives

$\binom{2600}{2}=3{,}378{,}700$

candidate triangles. That is too many to reason about one by one by hand, but still small enough for a direct computer sweep. Using unordered pairs is essential, because \(OPQ\) and \(OQP\) are the same triangle.

A non-degenerate triangle can have at most one right angle, so once the three possible vertices have been tested, the decision is complete.

Three exact orthogonality tests

The right angle can occur at exactly one of the three vertices. Using vectors based at the candidate vertex gives three equivalent dot-product tests:

$\vec{OP}\cdot\vec{OQ}=x_1x_2+y_1y_2=0,$

$\vec{PO}\cdot\vec{PQ}=(-x_1,-y_1)\cdot(x_2-x_1,y_2-y_1)=x_1(x_1-x_2)+y_1(y_1-y_2)=0,$

$\vec{QO}\cdot\vec{QP}=(-x_2,-y_2)\cdot(x_1-x_2,y_1-y_2)=x_2(x_2-x_1)+y_2(y_2-y_1)=0.$

These are exactly the three scalar quantities computed by the implementations. Everything is done with integer arithmetic, so there is no floating-point ambiguity and no geometric approximation.

What the origin case looks like

Because all coordinates lie in the first quadrant, every coordinate is nonnegative. Therefore the equation

$x_1x_2+y_1y_2=0$

can hold only when one point lies on the positive \(x\)-axis and the other lies on the positive \(y\)-axis. So the right-angle-at-\(O\) triangles contribute exactly \(50^2\) in the full problem, and more generally \(n^2\) on an \(n\times n\) grid.

This observation is not required for the brute-force algorithm, but it is a useful invariant: the origin case is completely characterized by the sign pattern of the coordinates.

The geometric meaning of a right angle at \(P\) or \(Q\)

If the right angle is at \(P=(x_1,y_1)\), then the segment from \(P\) to \(Q\) must be perpendicular to the segment from \(P\) to the origin. In vector form, \(\vec{PQ}\) must be perpendicular to \(\vec{OP}\). Let

$g=\gcd(x_1,y_1).$

A primitive lattice direction perpendicular to \((x_1,y_1)\) is

$\left(\frac{y_1}{g},-\frac{x_1}{g}\right),$

and the opposite direction is its negative. So any lattice point \(Q\) producing a right angle at \(P\) must lie on one of the two rays

$Q=P\pm k\left(\frac{y_1}{g},-\frac{x_1}{g}\right)\qquad (k\in\mathbb{Z}_{>0}),$

as long as the coordinates stay inside the square \(0 \le x,y \le n\). The same picture, with the roles reversed, explains the right-angle-at-\(Q\) test. The implementation does not march along these rays explicitly, but the dot-product conditions are simply the algebraic form of this perpendicular-line description.

Worked example: the \(n=2\) checkpoint

The smallest interesting grid is \(n=2\), where the correct answer is 14. The dot-product viewpoint makes the breakdown easy to see.

There are \(n^2=4\) triangles with the right angle at the origin: choose one point on the \(x\)-axis and one on the \(y\)-axis. There are \(2n^2=8\) more with the right angle on an axis point away from the origin. For example, \(O=(0,0)\), \(P=(1,0)\), and \(Q=(1,1)\) give a right angle at \(P\).

The remaining two come from the interior point \(P=(1,1)\). Here \(g=\gcd(1,1)=1\), so a primitive perpendicular step is \((1,-1)\). Inside the \(2\times2\) square, the valid partners are \(Q=(2,0)\) and \(Q=(0,2)\). For \(Q=(2,0)\),

$\vec{PO}\cdot\vec{PQ}=(-1,-1)\cdot(1,-1)=0.$

Thus the total is \(4+8+2=14\). This is exactly the sample value used as a correctness checkpoint in the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same counting strategy. First they enumerate the lattice points in the square and exclude the origin. Then they examine each unordered pair exactly once, either by storing the points in a list first or by iterating over the coordinate grid and skipping pairs that would repeat an earlier triangle.

For each candidate pair, the implementation computes the three dot products corresponding to a right angle at \(O\), at \(P\), and at \(Q\). If at least one of them is zero, the counter is incremented. Because the pair ordering is one-way only, no triangle is counted twice. Because the calculations use integer arithmetic, the test is exact.

The C++ and Java implementations promote the products to 64-bit integers before adding them, which keeps the arithmetic safe even when \(n\) is changed. The Python implementation gets the same safety automatically from Python's integer model.

Complexity Analysis

Let \(M=(n+1)^2-1\) be the number of non-origin lattice points. The algorithm checks all unordered pairs, so the running time is

$\Theta\!\left(\binom{M}{2}\right)=\Theta(M^2)=\Theta(n^4).$

For \(n=50\), this means \(3{,}378{,}700\) candidate pairs, and each pair requires only a constant amount of arithmetic. That is why the straightforward method is entirely practical for this problem.

Auxiliary space depends on the implementation style. The direct nested-loop versions use \(O(1)\) extra space beyond the counters, while the version that first materializes the lattice points uses \(O(n^2)\) space for that list. In both cases the memory footprint is small.

Footnotes and References

1. Problem page: Project Euler 91
2. Dot product: Wikipedia - Dot product
3. Right triangle: Wikipedia - Right triangle
4. Lattice point: Wikipedia - Lattice point
5. Greatest common divisor: Wikipedia - Greatest common divisor