Sublinear Exact Counting of Acute, Right and Obtuse Integer Triangles with Given Perimeter

This paper considers the exact number of integer-sided triangles with perimeter p that are acute, right or obtuse. The formulas listed in the OEIS for these counts use double sums, requiring O(p^2) operations, and a single sum over the shortest side gives O(p). It is shown that, with u=p-a and v=p-b for the two shorter sides a <= b, the type of the triangle is decided by the sign of 2uv-p^2, so the acute triangles are the lattice points of a polygon lying under the hyperbola uv=p^2/2. The count reduces to one hyperbolic sum over a band of ratio sqrt(2), a few closed-form sums, and the number of divisor pairs of p^2/2 for the right triangles. With a hull-walk kernel for hyperbolic sums, this gives O(p^(2/3)) operations. The Python 3.12 implementation coincided with direct enumeration and baseline evaluations. At p=10^9+7 the linear method took 319.6 s, while the new method took only 3.2 s (100x speedup), enabling exact partition counts up to p=10^11+7.