Exact Counting of Right Triangles with Vertices at the Nodes of an n x n Grid: Algorithms of Complexity O(n^(3/2+eps)) and O(n log^2 n).

Abstract

This paper considers the exact computation of the number R(n) of right triangles with vertices at the nodes of an n x n grid (sequence A077435 in the OEIS). A formula is obtained in the form of a fourfold sum, R(n) = 4S^2 + 4W, over p,q,g,mu >= 1 with gcd(p,q)=1. The summand is symmetric under the exchange of the pairs (g,mu) and (p,q); from this an algorithm of complexity O(n^(3/2+eps)) is derived. Next, the coprimality condition is removed by means of the Mobius function, the sum is split into layers, and the remaining two-dimensional sums over polygons are computed by a kernel of floor sums with moments in O(log n); the overall complexity is O(n log^2 n) arithmetic operations. Both Python implementations coincided with direct enumeration for n <= 7, with all OEIS values for n <= 35, and with the OEIS b-file up to n=10,000. In the measurements, the near-linear algorithm turned out to be faster at n=12,800 (9.35 s versus 11.55 s), yielding the previously unknown exact value of R(12800).