Detailed mathematical approach

Problem Summary

Define the rational coordinate set

$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$

The finite point set used in the problem is

$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$

so we are working inside the open unit disk of the Poincare model. The target quantity \(T(n)\) is the number of ordered triples of distinct points of \(S_n\) that lie on a single hyperbolic line.

A brute-force search over all triples would spend nearly all its time repeatedly rediscovering the same geodesics. The implementations avoid that by converting the geometric condition “these points lie on one hyperbolic line” into an integer linear-algebra condition on lifted points, and then grouping equal geodesic signatures.

Mathematical Approach

A Farey-Type Coordinate Set

The code first removes denominators. Let

$L=\operatorname{lcm}(1,2,\dots,n).$

Every \(\xi\in R_n\) can then be written as \(\xi=x/L\) for some integer \(x\). Equivalently, the coordinate list is

$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$

with duplicates removed after sorting. This is exactly the set of rationals in \((-1,1)\) whose reduced denominator is at most \(n\), represented on a common integer scale.

How Hyperbolic Lines Look in the Disk

In the Poincare disk, a hyperbolic line is either a diameter or an arc of a Euclidean circle orthogonal to the boundary circle \(\xi^2+\eta^2=1\). An orthogonal circle has equation

$\xi^2+\eta^2+a\xi+b\eta+1=0,$

because orthogonality to the unit circle forces the constant term to be \(1\). Diameters are the limiting case given by a linear equation \(a\xi+b\eta=0\). Both cases are unified by the homogeneous form

$A\xi+B\eta+C(\xi^2+\eta^2+1)=0,$

where \(C=0\) gives a diameter and \(C\ne 0\) gives an orthogonal circle. That single formula is the key observation behind the whole algorithm.

Linearizing the Geodesic Condition

Introduce the lift

$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr).$

Then a hyperbolic line becomes an ordinary plane through the origin in this lifted space, because its equation is simply

$AX+BY+CZ=0.$

To stay in integer arithmetic, the implementations use the scaled lift

$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$

which is just \(L^2\Phi(\xi,\eta)\). Therefore three disk points lie on one hyperbolic line exactly when their lifted integer vectors are coplanar, equivalently

$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$

This removes all circle geometry from the counting step: the problem becomes a collinearity test in projective coordinates.

Grouping Points by the Geodesic Through a Fixed Base Point

Fix one lifted point \(P\). For any later point \(Q\), the hyperbolic line through them corresponds to the plane spanned by \(P\) and \(Q\), whose normal vector is

$N(P,Q)=P\times Q.$

Two points \(Q\) and \(R\) lie with \(P\) on the same hyperbolic line if and only if \(N(P,Q)\) and \(N(P,R)\) are proportional. Since all coordinates are integers, we can divide by the gcd of the stored components and fix the sign convention to obtain a unique reduced key for each geodesic direction.

For a fixed \(P=(P_x,P_y,P_z)\), one coordinate of \(P\times Q\) is redundant because the normal must satisfy \(A P_x+B P_y+C P_z=0\). The implementations therefore store only two integers. When \(P_x\ne 0\), they use

$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$

and when \(P_x=0\), they switch to

$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$

After normalization, equal keys mean equal hyperbolic lines through the base point. If one normalized key appears \(c\) times, then it contributes

$\binom{c}{2}$

unordered triples having the chosen base point as their first discovered element. Summing this over all base points counts every unordered collinear triple exactly once, and the final multiplication by \(6\) converts unordered triples into ordered triples.

Worked Example: Why \(T(2)=24\)

For \(n=2\),

$R_2=\left\{-\frac12,0,\frac12\right\}.$

All nine grid points with these coordinates lie inside the unit disk, so \(S_2\) is a \(3\times 3\) grid centered at the origin. The only hyperbolic lines containing three of these points are the four diameters

$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$

Each diameter contains exactly three points, hence contributes \(3!=6\) ordered triples. Therefore

$T(2)=4\cdot 6=24,$

which matches the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations follow the derivation directly. They first compute \(L=\operatorname{lcm}(1,\dots,n)\), generate the scaled coordinate set \(X_n\), and then enumerate all disk points \((\xi,\eta)\) with \(\xi^2+\eta^2<1\). Each such point is stored only through its integer lift \(P(\xi,\eta)\), so every later computation stays in exact integer arithmetic.

Next, the implementation loops over the lifted points in a fixed order. For one base point \(P\), it computes the reduced geodesic key for every later point \(Q\), sorts those keys, and scans equal runs. A run of length \(c\) contributes \(\binom{c}{2}\) unordered triples. After all base points are processed, the total is multiplied by \(6\). The small checkpoints \(T(2)=24\), \(T(3)=1296\), and \(T(4)=5052\) verify that the geometry-to-algebra reduction has been implemented correctly. The C++ version uses 128-bit intermediate arithmetic where needed, the Python version relies on native big integers, and the Java version uses arbitrary-precision arithmetic in the cross-product stage.

Complexity Analysis

Let \(M=|S_n|\). The coordinate generation phase is smaller than the main counting phase: it builds the rational coordinate set once and then filters the Cartesian product by the disk inequality. The dominant work is the repeated geodesic grouping. For each base point, the implementation creates \(O(M)\) keys and sorts them, so the full running time is

$O(M^2\log M).$

The extra memory is linear in the number of points, because the algorithm stores the point list and one temporary key list for the current base point:

$O(M).$

This is the essential speedup over brute force. Instead of checking all triples separately, the algorithm groups all points on the same hyperbolic line through a chosen base point in one sort-and-scan pass.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=972
2. Poincare disk model: Wikipedia - Poincare disk model
3. Farey sequence: Wikipedia - Farey sequence
4. Cross product: Wikipedia - Cross product
5. Determinant and coplanarity: Wikipedia - Determinant