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.
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.
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.
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.
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.
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.
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.
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.
Definiere die Menge rationaler Koordinaten durch
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$$
Die im Problem verwendete Punktmenge ist dann
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$$
also eine endliche Teilmenge der offenen Einheitskreisscheibe im Poincare-Modell. Gesucht ist \(T(n)\), die Anzahl geordneter Tripel verschiedener Punkte aus \(S_n\), die auf derselben hyperbolischen Geraden liegen.
Ein naiver Dreifachtest würde dieselben Geodäten immer wieder neu erkennen. Die Implementierungen umgehen das, indem sie die Bedingung „liegt auf derselben hyperbolischen Geraden“ in eine ganzzahlige lineare Bedingung für gehobene Punkte umformulieren und anschließend gleiche Geodäten-Signaturen gruppieren.
Zuerst werden Nenner beseitigt. Setze
$$L=\operatorname{lcm}(1,2,\dots,n).$$
Dann lässt sich jedes \(\xi\in R_n\) als \(\xi=x/L\) mit ganzzahligem \(x\) schreiben. Die im Code erzeugte ganzzahlige Liste ist
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$$
wobei nach dem Sortieren Dubletten entfernt werden. Das ist genau die Menge aller rationalen Zahlen in \((-1,1)\), deren vollständig gekürzter Nenner höchstens \(n\) ist, nur auf einen gemeinsamen Maßstab gebracht.
Im Poincare-Modell ist eine hyperbolische Gerade entweder ein Durchmesser oder ein Bogen eines euklidischen Kreises, der den Randkreis \(\xi^2+\eta^2=1\) orthogonal schneidet. Ein solcher orthogonaler Kreis besitzt die Gleichung
$$\xi^2+\eta^2+a\xi+b\eta+1=0,$$
denn Orthogonalität zum Einheitskreis erzwingt den konstanten Term \(1\). Durchmesser erscheinen als Grenzfall \(a\xi+b\eta=0\). Beide Fälle werden durch die homogene Form
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0$$
vereinigt. Für \(C=0\) erhält man einen Durchmesser, für \(C\ne 0\) einen orthogonalen Kreis. Genau diese Vereinheitlichung macht die Lösung effizient.
Führe den Lift
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr)$$
ein. Eine hyperbolische Gerade wird dadurch zu einer gewöhnlichen Ebene durch den Ursprung, denn ihre Gleichung lautet nun einfach
$$AX+BY+CZ=0.$$
Um vollständig ganzzahlig zu bleiben, verwenden die Implementierungen den skalierten Lift
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$$
also lediglich \(L^2\Phi(\xi,\eta)\). Damit liegen drei Punkte der Scheibe genau dann auf derselben hyperbolischen Geraden, wenn ihre gehobenen ganzzahligen Vektoren koplanar sind, also genau dann, wenn
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
Der geometrische Teil ist damit vollständig in ein algebraisches Koplanaritätskriterium überführt.
Fixiere einen gehobenen Punkt \(P\). Für jeden späteren Punkt \(Q\) entspricht die hyperbolische Gerade durch \(P\) und \(Q\) der von \(P\) und \(Q\) aufgespannten Ebene; ihr Normalenvektor ist
$$N(P,Q)=P\times Q.$$
Zwei Punkte \(Q\) und \(R\) liegen zusammen mit \(P\) auf derselben hyperbolischen Geraden genau dann, wenn \(N(P,Q)\) und \(N(P,R)\) proportional sind. Da alle Koordinaten ganzzahlig sind, genügt es, durch den ggT der gespeicherten Komponenten zu teilen und ein Vorzeichen zu normieren; so erhält jede Geodätenrichtung einen eindeutigen reduzierten Schlüssel.
Für festes \(P=(P_x,P_y,P_z)\) ist eine Komponente von \(P\times Q\) redundant, weil der Normalenvektor stets \(A P_x+B P_y+C P_z=0\) erfüllen muss. Deshalb speichern die Implementierungen nur zwei Zahlen. Für \(P_x\ne 0\) verwenden sie
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$$
und für \(P_x=0\) wechseln sie zu
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$$
Nach der Normierung bedeuten gleiche Schlüssel dieselbe hyperbolische Gerade durch den Basispunkt. Wenn ein Schlüssel \(c\)-mal vorkommt, liefert er
$$\binom{c}{2}$$
ungeordnete Tripel mit diesem Basispunkt als zuerst verarbeitetem Punkt. Über alle Basispunkte aufsummiert wird jedes ungeordnete kollineare Tripel genau einmal gezählt; die abschließende Multiplikation mit \(6\) macht daraus geordnete Tripel.
Für \(n=2\) gilt
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
Alle neun Gitterpunkte mit diesen Koordinaten liegen in der Einheitskreisscheibe, also ist \(S_2\) ein \(3\times 3\)-Gitter um den Ursprung. Die einzigen hyperbolischen Geraden, die drei dieser Punkte enthalten, sind die vier Durchmesser
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
Jeder Durchmesser enthält genau drei Punkte und liefert daher \(3!=6\) geordnete Tripel. Folglich
$$T(2)=4\cdot 6=24,$$
genau wie in der kleinen Kontrollrechnung der Implementierungen.
Die C++-, Python- und Java-Implementierungen folgen dieser Herleitung direkt. Zunächst berechnen sie \(L=\operatorname{lcm}(1,\dots,n)\), erzeugen daraus die skalierte Koordinatenmenge \(X_n\) und filtern anschließend alle Paare \((\xi,\eta)\) mit \(\xi^2+\eta^2<1\). Gespeichert wird jeder Punkt nur über seinen ganzzahligen Lift \(P(\xi,\eta)\), sodass alle weiteren Rechnungen exakt mit ganzen Zahlen ablaufen.
Danach wird über die gehobenen Punkte in fester Reihenfolge iteriert. Für einen Basispunkt \(P\) berechnet die Implementierung zu jedem späteren Punkt \(Q\) den reduzierten Geodätenschlüssel, sortiert diese Schlüssel und zählt die Längen gleicher Läufe. Ein Lauf der Länge \(c\) trägt \(\binom{c}{2}\) ungeordnete Tripel bei. Nachdem alle Basispunkte verarbeitet sind, wird das Ergebnis mit \(6\) multipliziert. Die kleinen Kontrollwerte \(T(2)=24\), \(T(3)=1296\) und \(T(4)=5052\) prüfen, dass die Umsetzung der Geometrie in Algebra korrekt ist. Die C++-Version benutzt an den kritischen Stellen 128-Bit-Zwischenwerte, Python verwendet eingebaute große Ganzzahlen, und Java greift in der Kreuzproduktphase auf Ganzzahlen mit beliebiger Präzision zurück.
Sei \(M=|S_n|\). Die Erzeugung der Koordinatenmenge ist kleiner als die eigentliche Zählphase: Sie baut die rationalen Koordinaten einmal auf und filtert dann das kartesische Produkt mit der Kreisscheiben-Ungleichung. Dominierend ist die wiederholte Gruppierung nach Geodäten. Für jeden Basispunkt werden \(O(M)\) Schlüssel erzeugt und sortiert, also beträgt die gesamte Laufzeit
$$O(M^2\log M).$$
Der Zusatzspeicher ist linear in der Punktanzahl, weil nur die Punktliste und eine temporäre Schlüsselliste für den aktuellen Basispunkt gehalten werden:
$$O(M).$$
Genau darin liegt der Gewinn gegenüber Brute Force: Statt jedes Tripel einzeln zu prüfen, bündelt der Algorithmus alle Punkte auf derselben hyperbolischen Geraden durch einen gewählten Basispunkt in einem einzigen Sortier-und-Zähl-Schritt.
Rasyonel koordinat kümesini
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}$$
olarak tanımlayalım. Problemde kullanılan sonlu nokta kümesi ise
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\}$$
şeklindedir; yani Poincare disk modelinin açık birim diski içindeki rasyonel noktalarda çalışıyoruz. İstenen \(T(n)\), \(S_n\) içindeki birbirinden farklı noktaların aynı hiperbolik doğru üzerinde bulunan sıralı üçlülerinin sayısıdır.
Saf kaba kuvvet yaklaşımı her üçlü için yeniden aynı geodezikleri keşfeder. Uygulamalar bunu yapmak yerine “aynı hiperbolik doğru üzerinde olma” koşulunu yükseltilmiş tamsayı noktaları üzerinde lineer bir bağımlılık testine dönüştürüyor ve sonra aynı doğruyu temsil eden anahtarları gruplayarak sayımı yapıyor.
İlk adım paydaları ortadan kaldırmaktır. Bunun için
$$L=\operatorname{lcm}(1,2,\dots,n)$$
tanımlanır. Böylece her \(\xi\in R_n\) değeri \(\xi=x/L\) olacak biçimde bir tam sayı \(x\) ile temsil edilebilir. Kodun ürettiği ölçeklenmiş tam sayı koordinat listesi
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\}$$
olup sıralamadan sonra tekrarlar silinir. Bu küme, indirgenmiş paydası en fazla \(n\) olan \((-1,1)\) içindeki bütün rasyonel sayıların ortak bir tamsayı ölçeğine taşınmış halidir.
Poincare disk modelinde bir hiperbolik doğru ya bir çap ya da sınır çemberi \(\xi^2+\eta^2=1\) ile dik kesişen bir Öklid çember yaydır. Böyle bir dik çemberin denklemi
$$\xi^2+\eta^2+a\xi+b\eta+1=0$$
şeklindedir; çünkü birim çembere diklik sabit terimi \(1\) yapar. Çaplar ise limit durumda \(a\xi+b\eta=0\) denklemleriyle ortaya çıkar. Bu iki durum birlikte
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0$$
homojen formunda yazılabilir. \(C=0\) olduğunda bir çap, \(C\ne 0\) olduğunda sınırla dik bir çember elde ederiz. Çözümün merkezi gözlemi budur.
Şimdi
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr)$$
yükseltmesini tanımlayalım. O zaman bir hiperbolik doğru, bu yükseltilmiş uzayda orijinden geçen sıradan bir düzleme dönüşür; çünkü denklemi artık
$$AX+BY+CZ=0$$
olur. Hesapların tamamen tamsayılarla yapılabilmesi için uygulamalar ölçeklenmiş yükseltmeyi kullanır:
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta.$$
Bu aslında sadece \(L^2\Phi(\xi,\eta)\) ifadesidir. Dolayısıyla diskteki üç nokta aynı hiperbolik doğru üzerindeyse ve ancak o zaman, yükseltilmiş tamsayı vektörleri eşdüzlemseldir; yani
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
Böylece çemberlerle ilgili bütün geometri, doğrudan cebirsel bir eşdüzlemsellik testine indirgenmiş olur.
Bir yükseltilmiş \(P\) noktasını sabitleyelim. Daha sonraki her \(Q\) noktası için, \(P\) ve \(Q\) üzerinden geçen hiperbolik doğru, bu iki vektörün gerdiği düzlemdir; normal vektörü
$$N(P,Q)=P\times Q$$
olur. \(Q\) ve \(R\) noktaları, \(P\) ile birlikte aynı hiperbolik doğru üzerindeyse ve ancak o zaman \(N(P,Q)\) ile \(N(P,R)\) orantılıdır. Bütün koordinatlar tam sayı olduğundan, uygun bileşenlerin ebobuna bölüp işareti standart hale getirerek her doğru yönü için tekil bir indirgenmiş anahtar elde edebiliriz.
Sabit \(P=(P_x,P_y,P_z)\) için \(P\times Q\) vektörünün bir bileşeni gereksizdir; çünkü normal vektör her zaman \(A P_x+B P_y+C P_z=0\) koşulunu sağlamalıdır. Bu yüzden uygulamalar yalnızca iki tam sayı saklar. \(P_x\ne 0\) ise
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr)$$
kullanılır; \(P_x=0\) ise
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr)$$
saklanır. Normalizasyondan sonra eşit anahtarlar, taban noktadan geçen aynı hiperbolik doğruyu ifade eder. Bir anahtar \(c\) kez görülüyorsa bu, taban noktası sabitken
$$\binom{c}{2}$$
adet sırasız üçlü katkısı demektir. Bütün taban noktalar üzerinden toplandığında her sırasız doğrudaş üçlü tam bir kez sayılır; son aşamadaki \(6\) ile çarpma ise bunu sıralı üçlü sayısına dönüştürür.
\(n=2\) için
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
Bu koordinatlarla elde edilen dokuz noktanın tamamı birim diskin içindedir; dolayısıyla \(S_2\), merkezde duran \(3\times 3\) bir ızgaradır. Bu noktaların üç tanesini içeren tek hiperbolik doğrular, dört çaptır:
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
Her çap tam üç nokta içerdiği için \(3!=6\) sıralı üçlü verir. Sonuç olarak
$$T(2)=4\cdot 6=24$$
elde edilir ve bu değer uygulamalardaki doğrulama kontrolüyle birebir aynıdır.
C++, Python ve Java uygulamaları bu türetmeyi doğrudan uygular. Önce \(L=\operatorname{lcm}(1,\dots,n)\) hesaplanır, sonra ölçeklenmiş koordinat kümesi \(X_n\) oluşturulur ve \(\xi^2+\eta^2<1\) koşulunu sağlayan bütün nokta çiftleri taranır. Her nokta yalnızca tamsayı yükseltmesi \(P(\xi,\eta)\) ile saklandığı için sonraki bütün işlemler tam sayılarla ve hatasız yapılır.
Daha sonra yükseltilmiş noktalar sabit bir sırayla gezilir. Bir taban noktası \(P\) için, sonraki her \(Q\) noktasına karşılık indirgenmiş doğru anahtarı hesaplanır, bu anahtarlar sıralanır ve eşit blokların uzunlukları sayılır. Uzunluğu \(c\) olan bir blok \(\binom{c}{2}\) adet sırasız üçlü üretir. Tüm taban noktalar işlendiğinde toplam \(6\) ile çarpılır. Küçük doğrulama değerleri \(T(2)=24\), \(T(3)=1296\) ve \(T(4)=5052\), geometriden cebire geçişin doğru kodlandığını gösterir. C++ sürümü gerekli yerlerde 128 bit ara değerler kullanır, Python sürümü doğal büyük tamsayılara dayanır, Java sürümü ise çapraz çarpım aşamasında keyfi hassasiyetli tamsayılar kullanır.
\(M=|S_n|\) olsun. Koordinat üretim aşaması ana sayıma göre daha küçüktür: rasyonel koordinat kümesini bir kez kurar ve sonra Kartezyen çarpımı disk eşitsizliğiyle filtreler. Baskın maliyet, aynı doğruya düşen noktaları tekrar tekrar gruplama aşamasıdır. Her taban noktası için \(O(M)\) anahtar üretilip sıralandığından toplam çalışma süresi
$$O(M^2\log M)$$
olur. Ek bellek ise nokta listesi ve tek bir geçici anahtar listesi ile sınırlıdır:
$$O(M).$$
Asıl hızlanma burada gelir. Bütün üçlüleri tek tek sınamak yerine, algoritma seçilen bir taban noktadan geçen aynı hiperbolik doğru üzerindeki tüm noktaları tek bir sıralama ve tarama adımında toplar.
Definamos el conjunto de coordenadas racionales
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$$
El conjunto finito de puntos del problema es
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$$
es decir, trabajamos dentro del disco unidad abierto del modelo de Poincare. La cantidad buscada \(T(n)\) es el numero de ternas ordenadas de puntos distintos de \(S_n\) que pertenecen a una misma recta hiperbolica.
Un barrido ingenuo sobre todas las ternas volveria a detectar las mismas geodesicas una y otra vez. Las implementaciones lo evitan transformando la condicion “estos puntos estan en la misma recta hiperbolica” en una condicion lineal sobre puntos elevados con coordenadas enteras, y despues agrupan firmas iguales de geodesicas.
El primer paso consiste en eliminar denominadores. Sea
$$L=\operatorname{lcm}(1,2,\dots,n).$$
Entonces cada \(\xi\in R_n\) puede escribirse como \(\xi=x/L\) con \(x\) entero. La lista entera construida por el codigo es
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$$
y luego se eliminan duplicados tras ordenar. Esto coincide exactamente con los racionales de \((-1,1)\) cuyo denominador reducido es a lo sumo \(n\), todos expresados en una escala comun.
En el disco de Poincare, una recta hiperbolica es o bien un diametro o bien un arco de una circunferencia euclidea ortogonal a la circunferencia frontera \(\xi^2+\eta^2=1\). Una circunferencia ortogonal tiene ecuacion
$$\xi^2+\eta^2+a\xi+b\eta+1=0,$$
porque la ortogonalidad con la circunferencia unidad fuerza el termino constante a ser \(1\). Los diametros aparecen como el caso limite \(a\xi+b\eta=0\). Ambas posibilidades quedan unificadas por
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0.$$
Si \(C=0\), tenemos un diametro; si \(C\ne 0\), una circunferencia ortogonal. Esta forma homogenea es la observacion central que vuelve tratable el problema.
Introduzcamos la elevacion
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr).$$
Con ella, una recta hiperbolica se convierte en un plano ordinario que pasa por el origen, porque su ecuacion toma la forma
$$AX+BY+CZ=0.$$
Para mantener aritmetica entera exacta, las implementaciones usan la elevacion escalada
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$$
que no es mas que \(L^2\Phi(\xi,\eta)\). Por tanto, tres puntos del disco estan en una misma recta hiperbolica si y solo si sus vectores enteros elevados son coplanares, es decir, si y solo si
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
La geometria de circunferencias desaparece del paso de conteo y queda reemplazada por una prueba algebraica de coplanaridad.
Fijemos un punto elevado \(P\). Para cualquier punto posterior \(Q\), la recta hiperbolica que pasa por ambos corresponde al plano generado por \(P\) y \(Q\), cuyo vector normal es
$$N(P,Q)=P\times Q.$$
Dos puntos \(Q\) y \(R\) estan en la misma recta hiperbolica con \(P\) exactamente cuando \(N(P,Q)\) y \(N(P,R)\) son proporcionales. Como todas las coordenadas son enteras, basta dividir por el mcd de los componentes almacenados y fijar una convencion de signo para obtener una clave reducida unica por direccion geodesica.
Para un punto fijo \(P=(P_x,P_y,P_z)\), una componente de \(P\times Q\) es redundante porque el normal siempre satisface \(A P_x+B P_y+C P_z=0\). Por eso las implementaciones almacenan solo dos enteros. Cuando \(P_x\ne 0\), usan
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$$
y cuando \(P_x=0\), cambian a
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$$
Tras la normalizacion, claves iguales significan la misma recta hiperbolica a traves del punto base. Si una clave aparece \(c\) veces, aporta
$$\binom{c}{2}$$
ternas no ordenadas cuyo primer punto descubierto es el punto base. Al sumar sobre todos los puntos base, cada terna colineal no ordenada se cuenta exactamente una vez; la multiplicacion final por \(6\) la convierte en una terna ordenada.
Para \(n=2\),
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
Los nueve puntos de la cuadricula con esas coordenadas quedan dentro del disco unidad, de modo que \(S_2\) es una cuadricula \(3\times 3\) centrada en el origen. Las unicas rectas hiperbolicas que contienen tres de esos puntos son los cuatro diametros
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
Cada diametro contiene exactamente tres puntos, asi que aporta \(3!=6\) ternas ordenadas. Por tanto,
$$T(2)=4\cdot 6=24,$$
que coincide con el punto de control usado por las implementaciones.
Las implementaciones en C++, Python y Java siguen esta derivacion paso a paso. Primero calculan \(L=\operatorname{lcm}(1,\dots,n)\), generan el conjunto escalado \(X_n\) y enumeran todos los pares \((\xi,\eta)\) que satisfacen \(\xi^2+\eta^2<1\). Cada punto se guarda unicamente mediante su elevacion entera \(P(\xi,\eta)\), de modo que el resto del algoritmo trabaja con aritmetica exacta.
Despues, la implementacion recorre los puntos elevados en un orden fijo. Para un punto base \(P\), calcula la clave geodesica reducida para cada punto posterior \(Q\), ordena esas claves y cuenta los bloques iguales. Un bloque de longitud \(c\) aporta \(\binom{c}{2}\) ternas no ordenadas. Al final se multiplica el total por \(6\). Los pequeños controles \(T(2)=24\), \(T(3)=1296\) y \(T(4)=5052\) comprueban que la traduccion de la geometria a algebra se hizo correctamente. La version en C++ usa enteros intermedios de 128 bits cuando hace falta, Python aprovecha enteros grandes nativos y Java utiliza aritmetica de precision arbitraria en la etapa del producto cruzado.
Sea \(M=|S_n|\). La fase de generacion de coordenadas es menor que la fase principal de conteo: construye una sola vez el conjunto racional y despues filtra el producto cartesiano con la desigualdad del disco. El coste dominante es la agrupacion repetida por geodesica. Para cada punto base se crean \(O(M)\) claves y se ordenan, asi que el tiempo total es
$$O(M^2\log M).$$
La memoria adicional es lineal en el numero de puntos, porque solo se mantienen la lista de puntos y una lista temporal de claves para el punto base actual:
$$O(M).$$
Ese es el ahorro esencial frente a la fuerza bruta. En vez de verificar cada terna por separado, el algoritmo agrupa en una sola pasada de ordenar y recorrer todos los puntos que caen en la misma recta hiperbolica a traves de un punto base dado.
先定义有理坐标集合
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$$
题目使用的有限点集是
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$$
也就是 Poincare 圆盘模型中开单位圆盘里的那些有理点。目标量 \(T(n)\) 是：从 \(S_n\) 中取三个互不相同的点，要求它们位于同一条双曲直线上，并且三点的顺序有区别，问这样的有序三元组有多少个。
如果直接枚举所有三元组，再逐个判断是否共双曲直线，会反复识别同一条测地线，代价很高。实现采用的关键做法是：把“位于同一条双曲直线”这个几何条件，改写成整数提升向量之间的线性相关条件，然后按同一条测地线对应的标准化键值分组统计。
第一步是统一分母。设
$$L=\operatorname{lcm}(1,2,\dots,n).$$
这样每个 \(\xi\in R_n\) 都可以写成 \(\xi=x/L\)，其中 \(x\) 是整数。代码实际构造的是整数坐标集合
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$$
排序之后去重。这个集合恰好对应于区间 \((-1,1)\) 内所有约分后分母不超过 \(n\) 的有理数，只不过全部放到了同一个整数尺度上。
在 Poincare 圆盘模型里，双曲直线要么是穿过原点的直径，要么是与边界圆 \(\xi^2+\eta^2=1\) 正交的欧氏圆弧。与单位圆正交的圆可以写成
$$\xi^2+\eta^2+a\xi+b\eta+1=0,$$
因为正交条件会把常数项固定成 \(1\)。而直径可以看成 \(a\xi+b\eta=0\) 这个极限情形。这两类对象可以统一写成一个齐次方程
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0.$$
当 \(C=0\) 时，它就是一条直径；当 \(C\ne 0\) 时，它对应一条与边界圆正交的圆。整个算法最重要的数学观察，就是这一步把双曲直线统一成了一个线性形式。
定义提升映射
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr).$$
在这个提升空间里，一条双曲直线就变成了一个经过原点的普通平面，因为其方程变成
$$AX+BY+CZ=0.$$
为了全程使用精确整数运算，实现采用缩放后的提升
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$$
它只不过是 \(L^2\Phi(\xi,\eta)\)。因此，圆盘中的三个点落在同一条双曲直线上，当且仅当它们对应的整数提升向量共面，也就是
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
到这里为止，原先关于正交圆弧的几何问题已经完全变成了一个整数行列式为零的判定问题。
现在固定一个提升点 \(P\)。对于任何后面的点 \(Q\)，经过 \(P\) 和 \(Q\) 的双曲直线对应于由 \(P\) 与 \(Q\) 张成的那个平面，它的法向量是
$$N(P,Q)=P\times Q.$$
如果 \(Q\) 和 \(R\) 与 \(P\) 位于同一条双曲直线，那么 \(N(P,Q)\) 与 \(N(P,R)\) 必须成比例；反过来也成立。由于所有坐标都是整数，只要把所存储分量同时除以它们的最大公约数，再统一符号约定，就能得到这条测地线方向的唯一标准化键值。
对固定的 \(P=(P_x,P_y,P_z)\) 而言，\(P\times Q\) 的三个分量里有一个其实是冗余的，因为法向量必然满足 \(A P_x+B P_y+C P_z=0\)。所以实现只存两个整数。当 \(P_x\ne 0\) 时，存的是
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$$
而当 \(P_x=0\) 时，改存
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$$
归一化之后，键值相同就表示通过该基点的同一条双曲直线。如果某个键值出现了 \(c\) 次，那么它贡献的无序三元组数量就是
$$\binom{c}{2}.$$
对所有基点求和时，每个无序的三点共线组恰好只会被数一次；最后再乘以 \(6\)，就把无序三元组转成了有序三元组。
当 \(n=2\) 时，
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
这时所有 \(3\times 3\) 的网格点都落在单位圆盘内部，所以 \(S_2\) 正好是一个以原点为中心的九点格子。能够包含其中三个点的双曲直线只有四条直径：
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
每条直径恰好包含三个点，因此贡献 \(3!=6\) 个有序三元组。于是
$$T(2)=4\cdot 6=24,$$
这正好对应实现里的第一个校验值，也很好地说明了乘 \(6\) 的来源。
C++、Python 和 Java 三个实现都严格按照上面的推导来做。它们先计算 \(L=\operatorname{lcm}(1,\dots,n)\)，再构造缩放后的坐标集合 \(X_n\)，然后枚举所有满足 \(\xi^2+\eta^2<1\) 的点对。每个点只以整数提升向量 \(P(\xi,\eta)\) 的形式保存，因此后续所有计算都不需要浮点数。
接着，程序按固定顺序扫描这些提升点。对每个基点 \(P\)，它会为每个后续点 \(Q\) 计算归一化后的测地线键值，把这些键值排序，并统计每段相同键值的长度。长度为 \(c\) 的一段就贡献 \(\binom{c}{2}\) 个无序三元组。全部基点处理完以后，再把总数乘以 \(6\)。实现还包含小规模校验 \(T(2)=24\)、\(T(3)=1296\)、\(T(4)=5052\)，用来确认几何到代数的转换没有写错。C++ 版本在必要处使用 128 位中间整数，Python 版本直接依赖原生大整数，Java 版本则在叉积相关阶段使用任意精度整数。
记 \(M=|S_n|\)。坐标构造阶段的成本低于主计数阶段：它只需建立一次有理坐标集合，并用圆盘不等式筛选笛卡尔积。真正占主导的是反复按测地线分组的过程。对于每个基点，要生成 \(O(M)\) 个键并排序，因此总时间复杂度是
$$O(M^2\log M).$$
额外空间复杂度是线性的，因为程序只需要保存点表，以及当前基点对应的一份临时键值表：
$$O(M).$$
这就是它比暴力枚举快三元组得多的原因。算法并不是逐个检查三点是否共双曲直线，而是一次性把通过同一基点且落在同一条双曲直线上的点归并起来，再统一计数。
Введем множество рациональных координат
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$$
Тогда конечное множество точек из задачи равно
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$$
то есть речь идет о рациональных точках внутри открытого единичного диска в модели Пуанкаре. Величина \(T(n)\) считает упорядоченные тройки различных точек из \(S_n\), лежащих на одной гиперболической прямой.
Прямой перебор всех троек был бы неэффективен: одна и та же геодезическая распознавалась бы снова и снова. Реализации обходят это, переводя условие “точки лежат на одной гиперболической прямой” в целочисленное условие линейной зависимости для поднятых точек, а затем группируют одинаковые сигнатуры геодезических.
Сначала устраняются знаменатели. Положим
$$L=\operatorname{lcm}(1,2,\dots,n).$$
Тогда каждое \(\xi\in R_n\) можно записать в виде \(\xi=x/L\) с целым \(x\). Целочисленный список, который строит код, имеет вид
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$$
после чего одинаковые значения удаляются. Это в точности множество рациональных чисел из интервала \((-1,1)\), у которых сокращенный знаменатель не превосходит \(n\), только записанных на общем масштабе.
В модели Пуанкаре гиперболическая прямая является либо диаметром, либо дугой евклидовой окружности, ортогональной граничной окружности \(\xi^2+\eta^2=1\). Такая ортогональная окружность имеет уравнение
$$\xi^2+\eta^2+a\xi+b\eta+1=0,$$
потому что ортогональность к единичной окружности фиксирует свободный член равным \(1\). Диаметры возникают как предельный случай \(a\xi+b\eta=0\). Обе ситуации объединяются одной однородной формой
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0.$$
При \(C=0\) получаем диаметр, при \(C\ne 0\) — ортогональную окружность. Именно это объединение и позволяет перейти от геометрии к вычислимой алгебре.
Рассмотрим подъем
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr).$$
После него гиперболическая прямая превращается в обычную плоскость, проходящую через начало координат, потому что ее уравнение становится
$$AX+BY+CZ=0.$$
Чтобы всюду работать с точными целыми числами, реализации используют масштабированный подъем
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$$
то есть просто \(L^2\Phi(\xi,\eta)\). Поэтому три точки диска лежат на одной гиперболической прямой тогда и только тогда, когда их поднятые целочисленные векторы компланарны, то есть
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
Геометрическое условие на ортогональные окружности тем самым превращается в обычную проверку равенства нулю детерминанта.
Зафиксируем поднятую точку \(P\). Для любой более поздней точки \(Q\) гиперболическая прямая через \(P\) и \(Q\) соответствует плоскости, натянутой на \(P\) и \(Q\), а ее нормаль равна
$$N(P,Q)=P\times Q.$$
Точки \(Q\) и \(R\) лежат вместе с \(P\) на одной гиперболической прямой тогда и только тогда, когда \(N(P,Q)\) и \(N(P,R)\) пропорциональны. Поскольку координаты целые, можно разделить сохраненные компоненты на их общий делитель и затем зафиксировать знак; так получается единственный нормализованный ключ для каждого направления геодезической.
Для фиксированного \(P=(P_x,P_y,P_z)\) одна компонента вектора \(P\times Q\) избыточна, потому что нормаль всегда удовлетворяет равенству \(A P_x+B P_y+C P_z=0\). Поэтому реализации хранят только две величины. Если \(P_x\ne 0\), используется пара
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$$
а если \(P_x=0\), то
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$$
После нормализации одинаковые ключи означают одну и ту же гиперболическую прямую через базовую точку. Если некоторый ключ встретился \(c\) раз, то он дает
$$\binom{c}{2}$$
неупорядоченных троек с данным базовым элементом как первым обнаруженным. При суммировании по всем базовым точкам каждая неупорядоченная коллинеарная тройка считается ровно один раз, а итоговое умножение на \(6\) переводит счет в упорядоченные тройки.
При \(n=2\)
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
Все девять точек соответствующей сетки лежат внутри единичного диска, так что \(S_2\) — это сетка \(3\times 3\) с центром в начале координат. Единственные гиперболические прямые, содержащие по три такие точки, — это четыре диаметра
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
Каждый диаметр содержит ровно три точки и потому дает \(3!=6\) упорядоченных троек. Следовательно,
$$T(2)=4\cdot 6=24,$$
что совпадает с первым контрольным значением в реализациях.
Реализации на C++, Python и Java следуют этой схеме буквально. Сначала они вычисляют \(L=\operatorname{lcm}(1,\dots,n)\), строят масштабированное координатное множество \(X_n\), а затем перебирают все пары \((\xi,\eta)\), удовлетворяющие условию \(\xi^2+\eta^2<1\). Каждая точка хранится только через свой целочисленный подъем \(P(\xi,\eta)\), поэтому дальнейшие вычисления выполняются без ошибок округления.
Далее программа проходит по поднятым точкам в фиксированном порядке. Для базовой точки \(P\) она вычисляет нормализованный ключ геодезической для каждой более поздней точки \(Q\), сортирует ключи и считает длины одинаковых серий. Серия длины \(c\) дает вклад \(\binom{c}{2}\) в число неупорядоченных троек. После обработки всех базовых точек суммарное значение умножается на \(6\). Проверки \(T(2)=24\), \(T(3)=1296\) и \(T(4)=5052\) служат подтверждением того, что геометрическая идея корректно переведена в алгебраический алгоритм. В версии на C++ используются 128-битные промежуточные значения там, где это нужно, Python опирается на встроенные большие целые, а Java применяет арифметику произвольной точности на этапе, связанном с векторными произведениями.
Пусть \(M=|S_n|\). Построение координатного множества меньше по стоимости, чем основной этап подсчета: рациональные координаты строятся один раз, после чего декартово произведение фильтруется неравенством диска. Доминирует повторяющаяся группировка по геодезическим. Для каждой базовой точки создается \(O(M)\) ключей и выполняется их сортировка, поэтому полное время работы равно
$$O(M^2\log M).$$
Дополнительная память линейна по числу точек, поскольку нужно хранить список точек и один временный список ключей для текущей базовой точки:
$$O(M).$$
Именно здесь достигается ускорение по сравнению с грубым перебором. Вместо проверки каждой тройки по отдельности алгоритм за один проход сортировки и подсчета собирает все точки, лежащие на одной гиперболической прямой через выбранную базовую точку.
لنعرّف مجموعة الإحداثيات الكسرية بالعلاقة
$$R_n=\left\{\frac{a}{b}\in\mathbb{Q}: \gcd(a,b)=1,\ 0<b\le n,\ |a|<b\right\}.$$
وعندئذ تكون مجموعة النقاط المنتهية المستخدمة في المسألة هي
$$S_n=\{(\xi,\eta)\in R_n^2:\xi^2+\eta^2<1\},$$
أي إننا نعمل داخل القرص الواحدي المفتوح في نموذج Poincare. والكمية المطلوبة \(T(n)\) هي عدد الثلاثيات المرتبة من النقاط المختلفة في \(S_n\) التي تقع كلها على خط هذلولي واحد.
الفحص المباشر لكل الثلاثيات يهدر الوقت في اكتشاف الخطوط الجيوديسية نفسها مرارًا. لذلك تحول التطبيقات الشرط الهندسي “هذه النقاط على الخط الهذلولي نفسه” إلى شرط جبر خطي على نقاط مرفوعة بإحداثيات صحيحة، ثم تجمع النقاط التي تشترك في المفتاح نفسه لذلك الخط.
الخطوة الأولى هي إزالة المقامات. نضع
$$L=\operatorname{lcm}(1,2,\dots,n).$$
وبذلك يمكن كتابة كل \(\xi\in R_n\) على الصورة \(\xi=x/L\) حيث \(x\) عدد صحيح. والقائمة الصحيحة التي يبنيها التنفيذ هي
$$X_n=\left\{\frac{mL}{d}:1\le d\le n,\ -d<m<d\right\},$$
ثم تزال القيم المكررة بعد الترتيب. هذه هي بالضبط جميع الأعداد الكسرية في المجال \((-1,1)\) التي لا يتجاوز مقامها بعد الاختزال \(n\)، لكنها ممثلة كلها على مقياس صحيح واحد.
في نموذج Poincare يكون الخط الهذلولي إما قطرًا أو قوسًا من دائرة إقليدية متعامدة مع دائرة الحد \(\xi^2+\eta^2=1\). ويمكن كتابة مثل هذه الدائرة المتعامدة على الصورة
$$\xi^2+\eta^2+a\xi+b\eta+1=0,$$
لأن شرط التعامد مع الدائرة الواحدة يفرض أن يكون الحد الثابت مساويًا لـ \(1\). أما الأقطار فتظهر بوصفها الحالة الحدية \(a\xi+b\eta=0\). ويمكن جمع الحالتين في معادلة متجانسة واحدة هي
$$A\xi+B\eta+C(\xi^2+\eta^2+1)=0.$$
إذا كان \(C=0\) حصلنا على قطر، وإذا كان \(C\ne 0\) حصلنا على دائرة متعامدة مع الحد. هذه الصياغة الموحدة هي الفكرة الرياضية الأساسية في الحل.
نعرّف الرفع
$$\Phi(\xi,\eta)=\bigl(\xi,\eta,\xi^2+\eta^2+1\bigr).$$
بعد هذا الرفع يصبح الخط الهذلولي مستوىً عاديًا يمر بنقطة الأصل، لأن معادلته تتحول إلى
$$AX+BY+CZ=0.$$
ولكي تبقى كل العمليات حسابات صحيحة تمامًا، تستخدم التطبيقات الرفع المقاس
$$P(\xi,\eta)=\bigl(xL,\ yL,\ x^2+y^2+L^2\bigr),\qquad x=L\xi,\ y=L\eta,$$
وهو ليس إلا \(L^2\Phi(\xi,\eta)\). لذلك فإن ثلاث نقاط من القرص تقع على خط هذلولي واحد إذا وفقط إذا كانت متجهاتها الصحيحة المرفوعة تقع في مستوى واحد، أي إذا وفقط إذا تحقق
$$\det\begin{pmatrix} X_1 & Y_1 & Z_1\\ X_2 & Y_2 & Z_2\\ X_3 & Y_3 & Z_3 \end{pmatrix}=0.$$
وهكذا تختفي هندسة الأقواس المتعامدة من خطوة العد، ويتبقى اختبار جبري صريح للتواسط في مستوى واحد.
لنثبت نقطة مرفوعة \(P\). ولكل نقطة لاحقة \(Q\)، فإن الخط الهذلولي المار بهما يقابل المستوى المولَّد بواسطة \(P\) و\(Q\)، ومتجه العمود عليه هو
$$N(P,Q)=P\times Q.$$
وتقع النقطتان \(Q\) و\(R\) مع \(P\) على الخط الهذلولي نفسه إذا وفقط إذا كان المتجهان \(N(P,Q)\) و\(N(P,R)\) متناسبين. وبما أن جميع الإحداثيات صحيحة، فيكفي أن نقسم المركبات المخزنة على القاسم المشترك الأكبر ونثبت إشارة موحدة، فنحصل على مفتاح مختزل وحيد لكل اتجاه جيوديسي.
وبالنسبة إلى \(P=(P_x,P_y,P_z)\)، فإن إحدى مركبات \(P\times Q\) زائدة لأن المتجه العمودي يحقق دائمًا العلاقة \(A P_x+B P_y+C P_z=0\). لذلك لا تخزن التطبيقات إلا عددين صحيحين. عندما يكون \(P_x\ne 0\) تستعمل
$$\bigl(P_yQ_x-P_xQ_y,\ P_zQ_x-P_xQ_z\bigr),$$
وعندما يكون \(P_x=0\) تتحول إلى
$$\bigl(Q_x,\ P_zQ_y-P_yQ_z\bigr).$$
بعد التطبيع، فإن تساوي المفتاحين يعني تساوي الخطين الهذلوليين المارين بنقطة الأساس. وإذا ظهر مفتاح ما \(c\) مرة فإنه يساهم بعدد
$$\binom{c}{2}$$
من الثلاثيات غير المرتبة التي تكون نقطة الأساس فيها هي أول عنصر يُكتشف. وعند الجمع على جميع نقاط الأساس تُعد كل ثلاثية غير مرتبة على استقامة هذلولية مرة واحدة فقط، ثم يحول الضرب النهائي في \(6\) هذه القيمة إلى عدد الثلاثيات المرتبة.
عندما \(n=2\) يكون
$$R_2=\left\{-\frac12,0,\frac12\right\}.$$
وجميع نقاط الشبكة التسع الناتجة تقع داخل القرص الواحدي، ومن ثم فإن \(S_2\) شبكة \(3\times 3\) متمركزة عند الأصل. والخطوط الهذلولية الوحيدة التي تحتوي ثلاثًا من هذه النقاط هي الأقطار الأربعة
$$\eta=0,\qquad \xi=0,\qquad \eta=\xi,\qquad \eta=-\xi.$$
كل قطر يحتوي ثلاث نقاط بالضبط، ولذلك يضيف \(3!=6\) ثلاثيات مرتبة. ومن هنا نحصل على
$$T(2)=4\cdot 6=24,$$
وهو تمامًا مقدار نقطة التحقق الصغيرة في التطبيقات.
تتبع تطبيقات C++ وPython وJava هذا الاشتقاق مباشرة. فهي تبدأ بحساب \(L=\operatorname{lcm}(1,\dots,n)\)، ثم تبني مجموعة الإحداثيات المقاسة \(X_n\)، ثم تولد جميع الأزواج \((\xi,\eta)\) التي تحقق \(\xi^2+\eta^2<1\). وكل نقطة تحفظ فقط من خلال الرفع الصحيح \(P(\xi,\eta)\)، ولذلك تبقى الحسابات كلها دقيقة من دون أي أعداد فاصلة.
بعد ذلك يمر التنفيذ على النقاط المرفوعة بترتيب ثابت. ومن أجل نقطة أساس \(P\) يحسب المفتاح الجيوديسي المختزل لكل نقطة لاحقة \(Q\)، ثم يرتب هذه المفاتيح ويحصي أطوال المقاطع المتساوية. والمقطع ذو الطول \(c\) يضيف \(\binom{c}{2}\) ثلاثيات غير مرتبة. وبعد معالجة جميع نقاط الأساس يضرب المجموع في \(6\). كما تتضمن التطبيقات نقاط تحقق صغيرة هي \(T(2)=24\) و\(T(3)=1296\) و\(T(4)=5052\) للتأكد من أن الانتقال من الهندسة إلى الجبر طُبّق بصورة صحيحة. وتستخدم نسخة C++ قيَمًا وسيطة بعرض 128 بت عند الحاجة، بينما تعتمد Python على الأعداد الصحيحة الكبيرة المدمجة، وتستخدم Java حسابًا صحيحًا ذا دقة غير محدودة في مرحلة الضرب الاتجاهي.
لنكتب \(M=|S_n|\). إن مرحلة توليد الإحداثيات أصغر من مرحلة العد الأساسية: فهي تبني مجموعة الإحداثيات الكسرية مرة واحدة ثم تصفي الجداء الديكارتي بواسطة شرط القرص. أما الجزء المسيطر فهو التجميع المتكرر بحسب الخطوط الجيوديسية. فلكل نقطة أساس تُنشأ \(O(M)\) مفاتيح ثم تُرتب، ولذلك يكون زمن التنفيذ الكلي
$$O(M^2\log M).$$
أما الذاكرة الإضافية فهي خطية في عدد النقاط، لأن الخوارزمية تحتفظ بقائمة النقاط وبقائمة مؤقتة واحدة من المفاتيح خاصة بنقطة الأساس الحالية:
$$O(M).$$
وهنا يأتي التفوق على العد العنيف. فبدل فحص كل ثلاثية على حدة، تجمع الخوارزمية جميع النقاط الواقعة على الخط الهذلولي نفسه عبر نقطة أساس معينة في خطوة واحدة من الترتيب ثم المسح.