Counting integer right triangles by perimeter in time $O(N^{2/3}\log^2N)$: an exact formula without gcd conditions, a hull walk under the hyperbola, and new terms of the sequence A299706

Let T(N) be the number of integer right triangles with perimeter at most N (A299706 for N=10^n). We prove the exact formula T(N) = sum_{r >= 1, r odd, squarefree} R(floor(floor(N/2)/r)), where R(M) = #{(a,b) in N^2 : a < b < 2a, ab <= M}, in which neither a coprimality condition nor a parity condition appears. The function R(M) reduces to a sum sum floor(M/a) over an interval of length ~ sqrt(M), and the dual form involves the counting function Q of odd squarefree integers. A Dirichlet hyperbola split gives an algorithm with O(N^{3/4}) operations. Replacing the sums of integer parts by a walk along the convex hull of the lattice points above the hyperbola (a descent in the Stern-Brocot tree with batched steps), and the evaluation of Q by blocks of equal floor(z/d^2), lowers the cost to O(N^{2/3} log^2 N) operations and O(N^{1/2}) memory, against Theta(N) for the enumeration of primitive triples used for the entry. The method reproduces the ten listed terms of A299706 and computes T(10^n) for n=11,...,17; for example T(10^{17}) = 258777325927633181. The C implementation evaluates T(10^{14}) in 8.2 s, against 35 s for the O(N^{3/4}) version, and T(10^{17}) in 863 s; the measured growth between 10^{14} and 10^{17} is N^{0.67}. The increments of T(10^n)/10^n agree with the constant ln(2)*ln(10)/pi^2 of the classical asymptotics T(N) ~ (ln(2)/pi^2)*N*ln(N) to 9 digits.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-17
DOI
https://doi.org/10.5281/zenodo.24298133
Primary Topic
Analytic Number Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Counting integer right triangles by perimeter in time $O(N^{2/3}\log^2N)$: an exact formula without gcd conditions, a hull walk under the hyperbola, and new terms of the sequence A299706

Mark Kim
7 links
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

Counting integer right triangles by perimeter in time $O(N^{2/3}\log^2N)$: an exact formula without gcd conditions, a hull walk under the hyperbola, and new terms of the sequence A299706

Mark Kim
preprint en

Abstract

Let T(N) be the number of integer right triangles with perimeter at most N (A299706 for N=10^n). We prove the exact formula T(N) = sum_{r >= 1, r odd, squarefree} R(floor(floor(N/2)/r)), where R(M) = #{(a,b) in N^2 : a < b < 2a, ab <= M}, in which neither a coprimality condition nor a parity condition appears. The function R(M) reduces to a sum sum floor(M/a) over an interval of length ~ sqrt(M), and the dual form involves the counting function Q of odd squarefree integers. A Dirichlet hyperbola split gives an algorithm with O(N^{3/4}) operations. Replacing the sums of integer parts by a walk along the convex hull of the lattice points above the hyperbola (a descent in the Stern-Brocot tree with batched steps), and the evaluation of Q by blocks of equal floor(z/d^2), lowers the cost to O(N^{2/3} log^2 N) operations and O(N^{1/2}) memory, against Theta(N) for the enumeration of primitive triples used for the entry. The method reproduces the ten listed terms of A299706 and computes T(10^n) for n=11,...,17; for example T(10^{17}) = 258777325927633181. The C implementation evaluates T(10^{14}) in 8.2 s, against 35 s for the O(N^{3/4}) version, and T(10^{17}) in 863 s; the measured growth between 10^{14} and 10^{17} is N^{0.67}. The increments of T(10^n)/10^n agree with the constant ln(2)*ln(10)/pi^2 of the classical asymptotics T(N) ~ (ln(2)/pi^2)*N*ln(N) to 9 digits.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon