notes.html

problem 91 · 24 lines

<article>
<h3>Problem Analysis</h3>
<p>
I need to count right triangles OPQ where O is the origin and P, Q are distinct lattice points - points with integer coordinates - in the square grid [0, N] x [0, N] with N = 50. A triangle has a right angle when two of its edges meet at exactly 90 degrees. The cleanest perpendicularity test is the <a class="reference-source" href="https://en.wikipedia.org/wiki/Dot_product" rel="noopener noreferrer" target="_blank">dot product</a>: two vectors are orthogonal precisely when their dot product is zero. The brute-force route enumerates every pair of points - an O(N^4) loop over the four coordinates - and checks all three vertices for a right angle. For N = 50 that is a few million pairs, tolerable but wasteful and not generalizable. A far better idea is to classify each triangle by *where* its right angle sits, which collapses the four-dimensional search into a two-dimensional sum.
</p>
<p>
There are exactly three places the right angle can live: at the origin O, at P, or at Q. The right angle at O is easy: vectors OP and OQ both leave the first-quadrant origin, and two such vectors are perpendicular only when one runs along the x-axis and the other along the y-axis. Counting those axis-aligned combinations gives exactly 3*N^2 triangles. The interesting case is a right angle at a non-origin vertex, say P = (x, y). The edge OP points in direction (x, y); the perpendicular direction is (-y, x). To enumerate the lattice points Q lying on that perpendicular line through P, I reduce (-y, x) to its primitive - shortest integer - form by dividing both components by m = <a class="reference-source" href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="noopener noreferrer" target="_blank">gcd</a>(x, y). Each integer step along that primitive direction lands on a lattice point, and I just count how many such steps stay inside the grid. Computing a gcd at each of the O(N^2) grid points costs O(log N), so the whole algorithm runs in O(N^2 log N) - a dramatic improvement over O(N^4).
</p>
<h3>Solution Approach</h3>
<h4>Analytical Counting via Primitive Perpendicular Vectors</h4>
<p>
The Python and C files implement the same algorithm; the C version is a direct translation for speed. I split the total into two additive pieces.
</p>
<p>
<strong>Right angle at the origin.</strong> By the axis argument above, these contribute exactly <code>3 * N^2</code> triangles. I encode this directly as <code>triangles_at_origin = 3 * coordinate_limit**2</code>. I checked this constant against the N = 2 example: it accounts for the axis-aligned right triangles among the fourteen shown.
</p>
<p>
<strong>Right angle at P (and by symmetry at Q).</strong> I iterate over every candidate vertex P = (x, y) with <code>x</code> from 1 to N and <code>y</code> from 1 to N-1. Keeping <code>x, y &gt;= 1</code> holds OP off the axes, so the perpendicular case stays genuinely distinct from the origin case. For each P, I compute <code>m = gcd(x, y)</code>. The primitive perpendicular step is <code>(-y/m, x/m)</code>. Stepping from P along that direction, Q moves by <code>y/m</code> horizontally and <code>x/m</code> vertically per step. The number of steps before leaving the grid is bounded two ways: by horizontal room, giving <code>x * m / y</code>, and by remaining vertical room, giving <code>m * (N - y) / x</code>. Both divisions are exact because m divides both x and y. I take the minimum of the two bounds - whichever boundary I hit first - and add it. Stepping in the opposite perpendicular direction mirrors this count, and the right angle can equally sit at Q rather than P; both effects are captured by the final <code>*= 2</code>.
</p>
<p>
The C code stores the gcd in a local <code>int m</code> and casts to <code>long long</code> before multiplying, so <code>x * m</code> cannot overflow 32 bits if N grows. The Python code expresses the whole sum as one generator passed to <code>sum</code>, using <code>math.gcd</code> from the standard library. The only structural difference is how each language binds the gcd to a name, discussed below.
</p>
</article>