Let
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
be the \(k\)-th triangular number. The function \(G(n)\) counts ordered triples \((a,b,c)\) of nonnegative integers such that
$$T_a+T_b+T_c=n.$$
The task is to evaluate \(G(17526\cdot 10^9)\). Directly enumerating triangular triples is hopeless at that scale, so the solution converts the problem into counting representations by three squares and then uses a class-number formula.
The implementation turns the additive problem for triangular numbers into an arithmetic problem for quadratic forms.
The identity
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
shows that every triangular number corresponds to an odd square. Therefore
$$n=T_a+T_b+T_c$$
is equivalent to
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
If we write
$$N=8n+3,$$
then \(G(n)\) is the number of ordered representations of \(N\) as a sum of three positive odd squares.
Define
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
where order and signs are both counted. Since \(N\equiv 3 \pmod{8}\), each square in any representation must be congruent to \(1 \pmod{8}\), because the only way to obtain \(3\) from three quadratic residues modulo \(8\) is
$$1+1+1\equiv 3 \pmod{8}.$$
So every valid \(x,y,z\) is odd, and none of them can be zero. Each positive odd triple corresponds to exactly \(2^3=8\) signed triples in \(r_3(N)\). Hence
$$G(n)=\frac{r_3(8n+3)}{8}.$$
Factor \(N\) as
$$N=f^2m,$$
where \(m\) is squarefree. Because \(N\equiv 3\pmod{8}\), the squarefree part \(m\) is odd and satisfies \(m\equiv 3\pmod{4}\). Set
$$D=-m.$$
Then \(D\) is a negative fundamental discriminant, and the implementation evaluates
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
Here \(h(D)\) is the class number of discriminant \(D\), \(\mu\) is the Möbius function, \(\sigma\) is the sum-of-divisors function, \(\left(\frac{D}{d}\right)\) is the Jacobi or Kronecker character, and \(w(D)\) is the number of units in the quadratic order:
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{otherwise.} \end{cases}$$
The sum is multiplicative in the square part \(f\), which is why the factorization of \(N\) is the first major step of the program.
For a negative fundamental discriminant \(D\), the class number can be obtained by counting reduced positive definite binary quadratic forms
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D.$$
The reduced conditions used by the implementation are
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{when}\quad |b|=a\ \text{or}\ a=c.$$
Since \(D<0\), one only needs to scan
$$1\le a\le \sqrt{\frac{|D|}{3}}.$$
For each odd \(a\), the congruence condition coming from the discriminant is
$$b^2\equiv D \pmod{4a}.$$
The implementation factors \(a\), finds square roots of \(D\) modulo each prime power, lifts them to higher powers, combines the local roots with the Chinese remainder theorem, and then reconstructs the admissible values of \(b\) and \(c\). Every valid reduced form contributes exactly one class.
For \(n=9\), we have
$$N=8\cdot 9+3=75.$$
The positive odd-square representations of \(75\) are
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
The first pattern has \(3!=6\) orderings, and each ordering has \(8\) sign choices in \(r_3(75)\). The second pattern contributes \(1\cdot 8\). Therefore
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
so
$$G(9)=\frac{56}{8}=7.$$
In triangular-number language, those seven ordered representations are the six permutations of \(0+3+6\) and the single representation \(3+3+3\).
For the target input, the program forms
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
factors \(N\), extracts \(f\) and \(m\), computes \(h(-m)\), evaluates the divisor sum in the formula for \(r_3(N)\), and finally divides by \(8\) to obtain \(G(n)\). This avoids any search over triangular numbers themselves.
The C++, Python, and Java implementations follow the same pipeline. First they factor \(N=8n+3\) with a 64-bit primality test and Pollard-Rho splitting. From that factorization they separate the squarefree part \(m\) from the square part \(f^2\), which gives the discriminant \(D=-m\).
Next they compute the class number \(h(D)\). To do that efficiently, the implementation enumerates candidate values of \(a\), factors each \(a\) with a small-prime sieve, solves the modular square-root conditions prime-power by prime-power, merges the local solutions with the Chinese remainder theorem, and counts the reduced forms that satisfy the discriminant equation.
Once \(h(D)\) is known, the code evaluates the divisor sum
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
by iterating over the squarefree divisors encoded by the prime factors of \(f\). That produces \(r_3(N)\), and the final answer is \(r_3(N)/8\). The implementations also include checkpoint values such as \(G(9)=7\), \(G(1000)=78\), and \(G(10^6)=2106\).
The brute-force search space for three triangular numbers grows far too quickly, so the arithmetic method is essential. Integer factorization is handled by Miller-Rabin and Pollard-Rho, which are very fast in practice for a single 64-bit input. After factorization, the dominant deterministic work is the class-number computation.
If
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor,$$
then the sieve used inside the class-number computation requires \(O(A)\) memory and \(O(A\log\log A)\) preprocessing time. The subsequent enumeration scans odd \(a\le A\); each step performs a small factorization of \(a\), a few modular square-root lifts, and a small CRT merge. In practice this is easily manageable for a single target value and is incomparably faster than enumerating triangular triples directly.
Sei
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
die \(k\)-te Dreieckszahl. \(G(n)\) zählt geordnete Tripel \((a,b,c)\) nichtnegativer ganzer Zahlen mit
$$T_a+T_b+T_c=n.$$
Gesucht ist \(G(17526\cdot 10^9)\). Ein direktes Durchprobieren aller Dreieckszahltripel ist für diese Größenordnung völlig unrealistisch, deshalb übersetzt die Lösung das Problem in eine Zählung von Darstellungen durch drei Quadrate und wertet anschließend eine Klassenzahlformel aus.
Die Implementierung ersetzt die ursprüngliche additive Fragestellung durch eine arithmetische Fragestellung über quadratische Formen.
Aus der Identität
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
folgt, dass jede Dreieckszahl zu einem ungeraden Quadrat gehört. Daher ist
$$n=T_a+T_b+T_c$$
äquivalent zu
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
Setzt man
$$N=8n+3,$$
dann zählt \(G(n)\) genau die geordneten Darstellungen von \(N\) als Summe dreier positiver ungerader Quadrate.
Definiere
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
wobei Reihenfolge und Vorzeichen mitgezählt werden. Weil \(N\equiv 3 \pmod{8}\), muss in jeder Darstellung jedes Quadrat kongruent zu \(1 \pmod{8}\) sein, denn nur
$$1+1+1\equiv 3 \pmod{8}$$
liefert den Rest \(3\) aus drei quadratischen Resten modulo \(8\). Also sind alle \(x,y,z\) ungerade und insbesondere ungleich null. Jedes positive ungerade Tripel entspricht genau \(2^3=8\) signierten Tripeln in \(r_3(N)\). Somit gilt
$$G(n)=\frac{r_3(8n+3)}{8}.$$
Zerlege \(N\) in der Form
$$N=f^2m,$$
wobei \(m\) quadratfrei ist. Da \(N\equiv 3\pmod{8}\), ist \(m\) ungerade und erfüllt \(m\equiv 3\pmod{4}\). Setze
$$D=-m.$$
Dann ist \(D\) eine negative fundamentale Diskriminante, und die Implementierung verwendet
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
Dabei ist \(h(D)\) die Klassenzahl zur Diskriminante \(D\), \(\mu\) die Möbius-Funktion, \(\sigma\) die Teilersummenfunktion, \(\left(\frac{D}{d}\right)\) das Jacobi- beziehungsweise Kronecker-Symbol und \(w(D)\) die Anzahl der Einheiten:
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{sonst.} \end{cases}$$
Die Divisorensumme ist multiplikativ in dem quadratischen Anteil \(f\), weshalb die Faktorisierung von \(N\) der erste große Programmschritt ist.
Für negative fundamentale Diskriminanten erhält man die Klassenzahl, indem man reduzierte positiv definite binäre quadratische Formen
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D$$
zählt. Die in der Implementierung verwendeten Reduktionsbedingungen lauten
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{falls}\quad |b|=a\ \text{oder}\ a=c.$$
Wegen \(D<0\) genügt es,
$$1\le a\le \sqrt{\frac{|D|}{3}}$$
zu betrachten. Für jedes ungerade \(a\) entsteht aus der Diskriminantenbedingung die Kongruenz
$$b^2\equiv D \pmod{4a}.$$
Die Implementierung faktorisiert \(a\), bestimmt Quadratwurzeln von \(D\) modulo jeder Primzahlpotenz, hebt sie auf höhere Potenzen an, setzt die lokalen Lösungen per chinesischem Restsatz zusammen und rekonstruiert daraus die zulässigen Werte für \(b\) und \(c\). Jede gültige reduzierte Form liefert genau eine Klasse.
Für \(n=9\) gilt
$$N=8\cdot 9+3=75.$$
Die positiven ungeraden Quadratdarstellungen von \(75\) sind
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
Das erste Muster besitzt \(3!=6\) Anordnungen, und jede Anordnung liefert \(8\) Vorzeichenvarianten in \(r_3(75)\). Das zweite Muster trägt \(1\cdot 8\) bei. Also
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
und damit
$$G(9)=\frac{56}{8}=7.$$
In der Sprache der Dreieckszahlen sind das die sechs Permutationen von \(0+3+6\) sowie die einzelne Darstellung \(3+3+3\).
Für die eigentliche Aufgabe bildet das Programm
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
faktorisiert \(N\), bestimmt daraus \(f\) und \(m\), berechnet \(h(-m)\), wertet die Divisorensumme in der Formel für \(r_3(N)\) aus und dividiert am Ende durch \(8\). Dadurch wird jede brute-force-Suche über Dreieckszahlen vermieden.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Rechenkette. Zuerst wird \(N=8n+3\) mit einem 64-Bit-Primzahltest und Pollard-Rho faktorisiert. Aus der Primfaktorzerlegung werden der quadratfreie Anteil \(m\) und der quadratische Anteil \(f^2\) getrennt, woraus die Diskriminante \(D=-m\) entsteht.
Danach wird die Klassenzahl \(h(D)\) berechnet. Dafür enumeriert die Implementierung mögliche Werte von \(a\), faktorisiert jedes \(a\) mit einer kleinen Primzahlsieb-Tabelle, löst die modularen Quadratwurzelbedingungen primzahlpotenzweise, kombiniert die lokalen Lösungen mit dem chinesischen Restsatz und zählt genau die reduzierten Formen, die die Diskriminantengleichung erfüllen.
Sobald \(h(D)\) vorliegt, wertet der Code die Summe
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
über die quadratfreien Teiler von \(f\) aus. Daraus folgt \(r_3(N)\), und der Endwert ist \(r_3(N)/8\). Als Plausibilitätskontrollen werden unter anderem \(G(9)=7\), \(G(1000)=78\) und \(G(10^6)=2106\) überprüft.
Eine naive Suche über drei Dreieckszahlen wäre viel zu groß, daher ist der arithmetische Ansatz entscheidend. Die Faktorisierung von \(N\) wird mit Miller-Rabin und Pollard-Rho erledigt und ist für einen einzelnen 64-Bit-Wert in der Praxis sehr schnell. Der dominierende deterministische Teil ist danach die Klassenzahlberechnung.
Mit
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor$$
benötigt das Sieb in der Klassenzahlroutine \(O(A)\) Speicher und \(O(A\log\log A)\) Vorverarbeitungszeit. Anschließend werden die ungeraden \(a\le A\) durchlaufen; pro Schritt kommen eine kleine Faktorisierung, einige Quadratwurzelhebungen und eine kleine CRT-Zusammensetzung hinzu. Für einen einzelnen Zielwert ist das bequem praktikabel und um Größenordnungen schneller als direkte Enumeration.
Şunu tanımlayalım:
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
olsun. \(G(n)\),
$$T_a+T_b+T_c=n$$
eşitliğini sağlayan sıralı \((a,b,c)\) üçlülerinin sayısını verir; burada \(a,b,c\) negatif olmayan tam sayılardır. İstenen değer \(G(17526\cdot 10^9)\)'dur. Bu büyüklükte doğrudan üçgensel sayı denemesi yapmak mümkün değildir, bu yüzden çözüm problemi üç kare toplamına çevirip ardından sınıf sayısı formülü uygular.
Uygulama, üçgensel sayıların toplamsal yapısını ikili kuadratik formların aritmetiğine dönüştürür.
Kimlik
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
her üçgensel sayının bir tek kareyle bağlantılı olduğunu gösterir. Dolayısıyla
$$n=T_a+T_b+T_c$$
eşitliği
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2$$
ile denktir. Eğer
$$N=8n+3$$
dersek, \(G(n)\) tam olarak \(N\)'in üç pozitif tek karenin sıralı toplamı olarak yazılma sayısı olur.
Şimdi
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\}$$
tanımını yapalım; burada hem sıra hem işaret sayılır. \(N\equiv 3 \pmod{8}\) olduğundan, herhangi bir çözümdeki her kare \(1 \pmod{8}\) olmalıdır; çünkü mod \(8\)'de üç kare kalıntısının toplamı ancak
$$1+1+1\equiv 3 \pmod{8}$$
şeklinde \(3\) verebilir. Böylece tüm \(x,y,z\) tektir ve hiçbiri sıfır olamaz. Her pozitif tek üçlü, işaretler bakımından \(2^3=8\) farklı tam sayı üçlüsüne karşılık gelir. O halde
$$G(n)=\frac{r_3(8n+3)}{8}.$$
\(N\)'yi
$$N=f^2m$$
şeklinde yazalım; burada \(m\) karefree'dir. \(N\equiv 3\pmod{8}\) olduğu için karefree parça \(m\) tektir ve \(m\equiv 3\pmod{4}\) sağlar. Şimdi
$$D=-m$$
tanımını yapalım. Böylece \(D\) negatif temel diskriminant olur ve uygulama şu formülü kullanır:
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
Burada \(h(D)\) sınıf sayısıdır, \(\mu\) Möbius fonksiyonudur, \(\sigma\) bölenler toplamı fonksiyonudur, \(\left(\frac{D}{d}\right)\) Jacobi veya Kronecker karakteridir ve \(w(D)\) ilgili kuadratik düzenin birim sayısını gösterir:
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{diğer durumlarda.} \end{cases}$$
Toplam, \(f\)'nin asal çarpanlarına göre çarpımsal olduğu için programın ilk büyük işi \(N\)'yi çarpanlarına ayırmaktır.
Negatif temel diskriminantlar için sınıf sayısı,
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D$$
şeklindeki indirgenmiş pozitif belirli ikili kuadratik formların sayılmasıyla elde edilir. Uygulamanın kullandığı indirgenmişlik koşulları
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{eğer}\quad |b|=a\ \text{veya}\ a=c$$
şeklindedir. \(D<0\) olduğundan sadece
$$1\le a\le \sqrt{\frac{|D|}{3}}$$
aralığını taramak yeterlidir. Her tek \(a\) için diskriminant koşulu
$$b^2\equiv D \pmod{4a}$$
kongruansına dönüşür. Uygulama önce \(a\)'yı çarpanlarına ayırır, sonra \(D\)'nin her asal kuvvet modülündeki kareköklerini bulur, bunları daha yüksek kuvvetlere kaldırır, yerel çözümleri Çin kalan teoremiyle birleştirir ve son olarak geçerli \(b\) ile \(c\) değerlerini yeniden kurar. Her geçerli indirgenmiş form bir sınıf katkısı yapar.
\(n=9\) için
$$N=8\cdot 9+3=75$$
olur. \(75\)'in pozitif tek kare ayrışımları
$$75=1^2+5^2+7^2=5^2+5^2+5^2$$
şeklindedir. İlk örüntünün \(3!=6\) farklı sırası vardır ve her sıranın \(8\) işaret seçeneği bulunur. İkinci örüntü ise \(1\cdot 8\) katkı yapar. Böylece
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
dolayısıyla
$$G(9)=\frac{56}{8}=7$$
elde edilir. Üçgensel sayılar dilinde bunlar \(0+3+6\)'nın altı permütasyonu ile \(3+3+3\)'ün tek sıralı yazımıdır.
Hedef giriş için program
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003$$
değerini oluşturur; \(N\)'yi çarpanlarına ayırır, \(f\) ve \(m\)'yi çıkarır, \(h(-m)\)'yi hesaplar, \(r_3(N)\) formülündeki bölenler toplamını değerlendirir ve sonunda \(8\)'e bölerek \(G(n)\)'yi elde eder. Böylece üçgensel sayılar üzerinde hiçbir kaba kuvvet taraması yapılmaz.
C++, Python ve Java uygulamaları aynı akışı izler. İlk olarak \(N=8n+3\), 64 bitlik bir asal test ve Pollard-Rho tabanlı çarpan ayırma ile parçalanır. Sonra asal üslerinden karefree kısım \(m\) ile tam kare kısım \(f^2\) ayrılır ve diskriminant \(D=-m\) elde edilir.
Ardından sınıf sayısı \(h(D)\) hesaplanır. Bunun için uygulama olası \(a\) değerlerini dolaşır, her \(a\)'yı küçük asal süzgeciyle çarpanlarına ayırır, modüler karekök koşullarını asal kuvvet bazında çözer, yerel çözümleri Çin kalan teoremiyle birleştirir ve diskriminant denklemine uyan indirgenmiş formları sayar.
Son aşamada kod
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
toplamını değerlendirir, bundan \(r_3(N)\)'yi üretir ve cevabı \(r_3(N)/8\) olarak verir. Uygulama ayrıca \(G(9)=7\), \(G(1000)=78\) ve \(G(10^6)=2106\) gibi kontrol noktalarıyla yöntemi doğrular.
Üç üçgensel sayının kaba kuvvetle taranması son derece pahalıdır; bu yüzden aritmetik yaklaşım kritik önemdedir. Tamsayı çarpan ayırma kısmı Miller-Rabin ve Pollard-Rho ile yapılır ve tek bir 64 bitlik girdi için pratikte çok hızlıdır. Faktorizasyondan sonra baskın belirlenmiş maliyet sınıf sayısı hesabıdır.
Eğer
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor$$
ise, sınıf sayısı içindeki süzgeç \(O(A)\) bellek ve \(O(A\log\log A)\) ön işlem zamanı kullanır. Sonraki tarama tek \(a\le A\) değerleri üzerinde ilerler; her adımda küçük bir çarpan ayırma, birkaç karekök kaldırması ve küçük bir CRT birleştirmesi vardır. Tek hedef değer için bu yöntem rahatlıkla uygulanabilir ve doğrudan enumerasyondan kat kat üstündür.
Sea
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
el \(k\)-ésimo número triangular. La función \(G(n)\) cuenta los ternas ordenadas \((a,b,c)\) de enteros no negativos que cumplen
$$T_a+T_b+T_c=n.$$
Se pide calcular \(G(17526\cdot 10^9)\). Probar ternas triangulares una por una es inviable para ese tamaño, así que la solución traduce el problema a representaciones por tres cuadrados y luego evalúa una fórmula basada en números de clase.
La implementación sustituye el problema aditivo original por un problema aritmético sobre formas cuadráticas.
La identidad
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
muestra que cada número triangular produce un cuadrado impar. Por tanto,
$$n=T_a+T_b+T_c$$
es equivalente a
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
Si escribimos
$$N=8n+3,$$
entonces \(G(n)\) es exactamente el número de representaciones ordenadas de \(N\) como suma de tres cuadrados impares positivos.
Definimos
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
donde se cuentan tanto el orden como los signos. Como \(N\equiv 3 \pmod{8}\), en cualquier representación cada cuadrado debe ser congruente con \(1 \pmod{8}\), porque la única forma de obtener \(3\) como suma de tres residuos cuadráticos módulo \(8\) es
$$1+1+1\equiv 3 \pmod{8}.$$
Así, todos los \(x,y,z\) son impares y ninguno puede ser cero. Cada terna positiva impar corresponde exactamente a \(2^3=8\) ternas con signos en \(r_3(N)\). En consecuencia,
$$G(n)=\frac{r_3(8n+3)}{8}.$$
Factorizamos \(N\) como
$$N=f^2m,$$
donde \(m\) es libre de cuadrados. Como \(N\equiv 3\pmod{8}\), la parte libre de cuadrados \(m\) es impar y satisface \(m\equiv 3\pmod{4}\). Definimos
$$D=-m.$$
Entonces \(D\) es un discriminante fundamental negativo, y la implementación evalúa
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
Aquí \(h(D)\) es el número de clase de discriminante \(D\), \(\mu\) es la función de Möbius, \(\sigma\) es la suma de divisores, \(\left(\frac{D}{d}\right)\) es el carácter de Jacobi o de Kronecker, y \(w(D)\) es el número de unidades:
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{en otro caso.} \end{cases}$$
La suma sobre divisores es multiplicativa respecto a la parte cuadrática \(f\), por lo que la factorización de \(N\) es el primer bloque importante del algoritmo.
Para un discriminante fundamental negativo, el número de clase se obtiene contando las formas cuadráticas binarias positivas definidas y reducidas
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D.$$
Las condiciones de reducción usadas por la implementación son
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{cuando}\quad |b|=a\ \text{o}\ a=c.$$
Como \(D<0\), basta recorrer
$$1\le a\le \sqrt{\frac{|D|}{3}}.$$
Para cada \(a\) impar, la condición del discriminante se convierte en
$$b^2\equiv D \pmod{4a}.$$
La implementación factoriza \(a\), busca raíces cuadradas de \(D\) módulo cada potencia prima, las levanta a potencias superiores, combina las soluciones locales mediante el teorema chino del resto y reconstruye después los valores admisibles de \(b\) y \(c\). Cada forma reducida válida aporta una clase.
Para \(n=9\), tenemos
$$N=8\cdot 9+3=75.$$
Las representaciones de \(75\) por cuadrados impares positivos son
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
El primer patrón tiene \(3!=6\) ordenaciones, y cada una tiene \(8\) elecciones de signo dentro de \(r_3(75)\). El segundo patrón aporta \(1\cdot 8\). Por tanto,
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
y así
$$G(9)=\frac{56}{8}=7.$$
En términos de números triangulares, eso corresponde a las seis permutaciones de \(0+3+6\) y a la representación única \(3+3+3\).
Para la entrada pedida, el programa forma
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
factoriza \(N\), extrae \(f\) y \(m\), calcula \(h(-m)\), evalúa la suma de divisores de la fórmula de \(r_3(N)\) y divide el resultado entre \(8\) para obtener \(G(n)\). Así se evita cualquier enumeración directa de números triangulares.
Las implementaciones en C++, Python y Java siguen la misma cadena de pasos. Primero factorizar \(N=8n+3\) mediante una prueba de primalidad de 64 bits y descomposición Pollard-Rho. A partir de esa factorización separan la parte libre de cuadrados \(m\) y la parte cuadrática \(f^2\), lo que fija el discriminante \(D=-m\).
Después calculan el número de clase \(h(D)\). Para ello, la implementación enumera los posibles valores de \(a\), factoriza cada \(a\) con una criba pequeña, resuelve las condiciones de raíces cuadradas módulo potencias primas, fusiona las soluciones locales con el teorema chino del resto y cuenta exactamente las formas reducidas que satisfacen la ecuación del discriminante.
Con \(h(D)\) ya disponible, el código evalúa
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
recorriendo los divisores libres de cuadrados determinados por los primos de \(f\). Eso produce \(r_3(N)\), y la salida final es \(r_3(N)/8\). Además se comprueban valores de control como \(G(9)=7\), \(G(1000)=78\) y \(G(10^6)=2106\).
Un barrido directo sobre ternas triangulares sería totalmente impracticable, así que el método aritmético es indispensable. La factorización entera se resuelve con Miller-Rabin y Pollard-Rho, muy rápidos en la práctica para una sola entrada de 64 bits. Una vez factorado \(N\), el coste determinista dominante es el cálculo del número de clase.
Si
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor,$$
entonces la criba dentro de la rutina del número de clase usa \(O(A)\) memoria y \(O(A\log\log A)\) tiempo de preprocesado. Luego se recorren los valores impares \(a\le A\); cada paso requiere una pequeña factorización, unos pocos levantamientos de raíces cuadradas y una combinación CRT pequeña. Para un único valor objetivo, todo ello es perfectamente manejable y enormemente mejor que la fuerza bruta.
设
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
为第 \(k\) 个三角数。函数 \(G(n)\) 统计满足
$$T_a+T_b+T_c=n$$
的有序三元组 \((a,b,c)\) 的个数，其中 \(a,b,c\) 都是非负整数。题目要求计算 \(G(17526\cdot 10^9)\)。如果直接枚举三角数三元组，规模会大得完全不可行，因此实现采用“先转化为三平方表示，再用类数公式求值”的路线。
实现的核心思想，是把原来的加法计数问题改写成一个关于二元二次型的算术问题。
恒等式
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
说明每个三角数都天然对应一个奇平方。因此
$$n=T_a+T_b+T_c$$
等价于
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
若记
$$N=8n+3,$$
那么 \(G(n)\) 就变成了“\(N\) 表成三个正奇平方有序和的方式数”。这一变换是整个算法的起点。
定义
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
这里同时区分顺序和符号。由于 \(N\equiv 3 \pmod{8}\)，任何表示中的三个平方在模 \(8\) 下都必须等于 \(1\)，因为三个平方剩余之和得到 \(3\) 的唯一方式就是
$$1+1+1\equiv 3 \pmod{8}.$$
这立刻推出所有 \(x,y,z\) 都是奇数，而且没有一个可以为零。于是，每个“正的奇数三元组”在 \(r_3(N)\) 中会因为三个坐标的独立符号选择而出现 \(2^3=8\) 次。因此
$$G(n)=\frac{r_3(8n+3)}{8}.$$
也就是说，只要能够高效求出 \(r_3(N)\)，原问题就解决了。
把 \(N\) 分解为
$$N=f^2m,$$
其中 \(m\) 是平方自由数。因为 \(N\equiv 3\pmod{8}\)，所以平方自由部分 \(m\) 一定是奇数，并且满足 \(m\equiv 3\pmod{4}\)。令
$$D=-m.$$
这样 \(D\) 就是一个负的基本判别式。实现使用的表示数公式是
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
其中 \(h(D)\) 是判别式 \(D\) 的类数，\(\mu\) 是 Möbius 函数，\(\sigma\) 是因子和函数，\(\left(\frac{D}{d}\right)\) 表示 Jacobi 或 Kronecker 特征，\(w(D)\) 表示对应二次整环中的单位数：
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{其他情况。} \end{cases}$$
这个公式的结构非常适合程序实现：先分解 \(N\)，再把平方部分 \(f\) 和平方自由部分 \(m\) 分开，最后分别处理类数与除数和。
对于负的基本判别式，类数可以通过统计约化的正定二元二次型得到，也就是统计满足
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D$$
的约化形式。实现采用的约化条件是
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{当}\quad |b|=a\ \text{或}\ a=c.$$
由于 \(D<0\)，只需要枚举
$$1\le a\le \sqrt{\frac{|D|}{3}}$$
即可。对于每个奇数 \(a\)，判别式方程转化为同余条件
$$b^2\equiv D \pmod{4a}.$$
实现会先分解 \(a\)，然后分别求出 \(D\) 在各个素数幂模数下的平方根，把这些局部解提升到更高幂次，再通过中国剩余定理合并，最后还原出合法的 \(b\) 和 \(c\)。每找到一个满足约化条件的形式，就对应类数中的一个类。
当 \(n=9\) 时，
$$N=8\cdot 9+3=75.$$
\(75\) 的正奇平方表示只有两种模式：
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
第一种模式 \((1,5,7)\) 有 \(3!=6\) 种排列，每一种排列又有 \(8\) 种独立符号选择，所以一共贡献 \(48\)。第二种模式 \((5,5,5)\) 只有一种排列，但仍有 \(8\) 种符号选择，因此贡献 \(8\)。于是
$$r_3(75)=48+8=56,$$
从而
$$G(9)=\frac{56}{8}=7.$$
换回三角数语言，这七种表示正好就是 \(0+3+6\) 的六个排列，再加上 \(3+3+3\) 这一种。
对题目的目标输入，程序先构造
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
然后分解 \(N\)，取出 \(f\) 与 \(m\)，计算 \(h(-m)\)，代入上面的类数公式求出 \(r_3(N)\)，最后除以 \(8\) 得到 \(G(n)\)。整个过程中完全不需要在三角数空间中暴力搜索。
C++、Python 和 Java 三份实现走的是同一条计算链。第一步是对 \(N=8n+3\) 做 64 位整数范围内的素性测试与 Pollard-Rho 分解。得到素因子之后，把平方自由部分 \(m\) 和平方部分 \(f^2\) 分开，于是判别式 \(D=-m\) 也就确定了。
接下来是类数计算。实现会枚举候选的 \(a\)，借助小素数筛快速分解每个 \(a\)，求解模素数幂的平方根条件，再用中国剩余定理合并这些局部信息，最后验证哪些 \((a,b,c)\) 真正构成约化二元二次型。这样就能得到 \(h(D)\)。
有了 \(h(D)\) 之后，代码再计算
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
这一项。实现方式是遍历由 \(f\) 的不同素因子决定的平方自由除数，再把它们代入公式，最终得到 \(r_3(N)\)，最后输出 \(r_3(N)/8\)。程序还会用 \(G(9)=7\)、\(G(1000)=78\)、\(G(10^6)=2106\) 这样的检查点确认整个推导和实现是一致的。
如果直接枚举三角数三元组，复杂度会随目标值迅速失控，因此算术化简是必要的。整数分解部分使用 Miller-Rabin 与 Pollard-Rho，对单个 64 位输入来说实践中非常快。分解完成后，主要的确定性开销来自类数计算。
记
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor,$$
则类数过程中的筛法需要 \(O(A)\) 内存和 \(O(A\log\log A)\) 的预处理时间。随后对所有奇数 \(a\le A\) 逐个检查；每一步包含一次小规模分解、少量模平方根提升以及一次规模很小的 CRT 合并。对题目这种单次大输入，这样的成本完全可接受，也远远优于直接搜索三角数表示。
Пусть
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
обозначает \(k\)-е треугольное число. Функция \(G(n)\) считает количество упорядоченных троек \((a,b,c)\) неотрицательных целых чисел, для которых
$$T_a+T_b+T_c=n.$$
Нужно вычислить \(G(17526\cdot 10^9)\). Прямой перебор всех троек треугольных чисел здесь невозможен, поэтому решение переводит задачу к представлениям числа в виде суммы трёх квадратов, а затем использует формулу через класс-число.
Реализация заменяет исходную аддитивную задачу арифметической задачей о квадратичных формах.
Тождество
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
показывает, что каждому треугольному числу соответствует нечётный квадрат. Поэтому равенство
$$n=T_a+T_b+T_c$$
эквивалентно равенству
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
Если обозначить
$$N=8n+3,$$
то \(G(n)\) становится числом упорядоченных представлений \(N\) в виде суммы трёх положительных нечётных квадратов.
Введём
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
где учитываются и порядок, и знаки. Поскольку \(N\equiv 3 \pmod{8}\), в любом представлении каждый квадрат обязан давать остаток \(1 \pmod{8}\): только
$$1+1+1\equiv 3 \pmod{8}$$
может дать остаток \(3\) как сумму трёх квадратичных вычетов modulo \(8\). Значит, все \(x,y,z\) нечётны и ни один из них не равен нулю. Каждая положительная нечётная тройка даёт ровно \(2^3=8\) знаковых троек в \(r_3(N)\). Следовательно,
$$G(n)=\frac{r_3(8n+3)}{8}.$$
Разложим \(N\) в виде
$$N=f^2m,$$
где \(m\) свободно от квадратов. Так как \(N\equiv 3\pmod{8}\), квадратсвободная часть \(m\) нечётна и удовлетворяет \(m\equiv 3\pmod{4}\). Положим
$$D=-m.$$
Тогда \(D\) является отрицательным фундаментальным дискриминантом, и реализация вычисляет
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
Здесь \(h(D)\) — класс-число дискриминанта \(D\), \(\mu\) — функция Мёбиуса, \(\sigma\) — сумма делителей, \(\left(\frac{D}{d}\right)\) — символ Якоби или Кронекера, а \(w(D)\) — число единиц в соответствующем квадратичном порядке:
$$w(D)=\begin{cases} 6,& D=-3,\\ 4,& D=-4,\\ 2,& \text{иначе.} \end{cases}$$
Сумма по делителям мультипликативна по квадратной части \(f\), поэтому факторизация \(N\) является первым ключевым шагом алгоритма.
Для отрицательного фундаментального дискриминанта класс-число можно получить, считая приведённые положительно определённые формы
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D.$$
Условия приведённости, используемые в реализации, таковы:
$$|b|\le a\le c,$$
$$b\ge 0\quad\text{если}\quad |b|=a\ \text{или}\ a=c.$$
Поскольку \(D<0\), достаточно перебирать
$$1\le a\le \sqrt{\frac{|D|}{3}}.$$
Для каждого нечётного \(a\) условие на дискриминант превращается в сравнение
$$b^2\equiv D \pmod{4a}.$$
Реализация факторизует \(a\), находит квадратные корни числа \(D\) по модулям простых степеней, поднимает их на большие степени, затем сшивает локальные решения при помощи китайской теоремы об остатках и восстанавливает допустимые значения \(b\) и \(c\). Каждая найденная приведённая форма даёт ровно один класс.
Для \(n=9\) получаем
$$N=8\cdot 9+3=75.$$
Положительные нечётные квадратные разложения числа \(75\) таковы:
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
Первый шаблон имеет \(3!=6\) перестановок, и каждая перестановка даёт \(8\) выборов знаков в \(r_3(75)\). Второй шаблон даёт \(1\cdot 8\). Значит,
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
а потому
$$G(9)=\frac{56}{8}=7.$$
На языке треугольных чисел это шесть перестановок суммы \(0+3+6\) и единственная запись \(3+3+3\).
Для нужного входа программа строит число
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
факторизует его, выделяет \(f\) и \(m\), вычисляет \(h(-m)\), подставляет всё в формулу для \(r_3(N)\), а затем делит результат на \(8\), получая \(G(n)\). Никакого перебора треугольных чисел при этом не требуется.
Реализации на C++, Python и Java следуют одной и той же схеме. Сначала число \(N=8n+3\) раскладывается на множители с помощью 64-битного теста на простоту и метода Полларда rho. По факторизации отделяются квадратсвободная часть \(m\) и квадратная часть \(f^2\), после чего фиксируется дискриминант \(D=-m\).
Затем вычисляется класс-число \(h(D)\). Для этого программа перебирает допустимые значения \(a\), раскладывает каждое \(a\) с помощью маленького решета, решает условия на квадратные корни по модулям простых степеней, объединяет локальные решения китайской теоремой об остатках и подсчитывает ровно те приведённые формы, которые удовлетворяют уравнению дискриминанта.
После этого код вычисляет сумму
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right),$$
проходя по квадратсвободным делителям, определяемым простыми множителями числа \(f\). Так получается \(r_3(N)\), а окончательный ответ равен \(r_3(N)/8\). В реализации также есть контрольные значения \(G(9)=7\), \(G(1000)=78\) и \(G(10^6)=2106\).
Прямой перебор троек треугольных чисел слишком дорог, поэтому арифметический подход здесь принципиален. Целочисленная факторизация выполняется при помощи Miller-Rabin и Pollard-Rho и на практике очень быстра для одного 64-битного входа. После факторизации основной детерминированный вклад даёт вычисление класс-числа.
Если обозначить
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor,$$
то решето внутри процедуры класс-числа использует \(O(A)\) памяти и \(O(A\log\log A)\) времени предварительной обработки. Затем перебираются нечётные \(a\le A\); на каждом шаге выполняются небольшая факторизация, несколько подъёмов квадратных корней и маленькая сборка CRT. Для одной целевой точки такой объём вычислений вполне практичен и на порядки лучше наивного поиска.
لتكن
$$T_k=\frac{k(k+1)}{2}\qquad (k\ge 0)$$
هي العدد المثلثي ذي الرتبة \(k\). الدالة \(G(n)\) تعدّ الثلاثيات المرتبة \((a,b,c)\) من الأعداد الصحيحة غير السالبة التي تحقق
$$T_a+T_b+T_c=n.$$
المطلوب هو حساب \(G(17526\cdot 10^9)\). الفحص المباشر لجميع الثلاثيات المثلثية مستحيل عملياً عند هذا الحجم، لذلك يحوّل الحل المسألة إلى تمثيل بعدد من ثلاثة مربعات ثم يستخدم صيغة تعتمد على عدد الفئات.
الفكرة الأساسية في التنفيذ هي استبدال مسألة الجمع الأصلية بمسألة عددية مرتبطة بالأشكال التربيعية الثنائية.
من الهوية
$$8T_k+1=4k(k+1)+1=(2k+1)^2$$
نرى أن كل عدد مثلثي يرتبط مباشرة بمربع فردي. لذلك فإن
$$n=T_a+T_b+T_c$$
تكافئ
$$8n+3=(2a+1)^2+(2b+1)^2+(2c+1)^2.$$
إذا وضعنا
$$N=8n+3,$$
فإن \(G(n)\) تصبح عدد الطرق المرتبة لكتابة \(N\) كمجموع ثلاثة مربعات فردية موجبة.
نعرّف
$$r_3(N)=\#\left\{(x,y,z)\in\mathbb{Z}^3:x^2+y^2+z^2=N\right\},$$
حيث يُحسب كل من الترتيب والإشارات. بما أن \(N\equiv 3 \pmod{8}\)، فإن كل مربع في أي تمثيل يجب أن يكون مساوياً لـ \(1 \pmod{8}\)، لأن الطريقة الوحيدة للحصول على \(3\) كمجموع ثلاثة بواقي تربيعية modulo \(8\) هي
$$1+1+1\equiv 3 \pmod{8}.$$
إذن كل من \(x,y,z\) فردي، ولا يمكن أن يساوي أي منها الصفر. كل ثلاثية موجبة فردية تقابل بالضبط \(2^3=8\) ثلاثيات مختلفة بالإشارات داخل \(r_3(N)\). ومن ثم
$$G(n)=\frac{r_3(8n+3)}{8}.$$
نكتب \(N\) على الصورة
$$N=f^2m,$$
حيث إن \(m\) خالٍ من المربعات. وبما أن \(N\equiv 3\pmod{8}\)، فإن الجزء الخالي من المربعات \(m\) يكون فردياً ويحقق \(m\equiv 3\pmod{4}\). ثم نضع
$$D=-m.$$
عندئذ يكون \(D\) مميزاً أساسياً سالباً، ويحسب التنفيذ
$$r_3(N)=\frac{12\cdot 2h(D)\left(1-\left(\frac{D}{2}\right)\right)}{w(D)}\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right).$$
هنا \(h(D)\) هو عدد الفئات للمميز \(D\)، و\(\mu\) هي دالة موبيوس، و\(\sigma\) هي دالة مجموع القواسم، و\(\left(\frac{D}{d}\right)\) هو رمز ياكوبي أو كرونيكر، أما \(w(D)\) فهو عدد الوحدات في الترتيب التربيعي الموافق:
$$w(D)=6 \quad (D=-3),\qquad w(D)=4 \quad (D=-4),\qquad w(D)=2 \quad (D\ne -3,-4).$$
هذه الصيغة تجعل تحليل \(N\) إلى عوامله الخطوة البرمجية الأولى، لأن المجموع على القواسم يعتمد على الجزء التربيعي \(f\).
عندما يكون \(D\) مميزاً أساسياً سالباً، يمكن إيجاد عدد الفئات عن طريق عدّ الأشكال التربيعية الثنائية الموجبة المختزلة
$$ax^2+bxy+cy^2,\qquad b^2-4ac=D.$$
شروط الاختزال المستخدمة في التنفيذ هي
$$|b|\le a\le c,$$
$$b\ge 0$$
عندما \( |b|=a \) أو \( a=c \).
وبما أن \(D<0\)، يكفي فحص القيم
$$1\le a\le \sqrt{\frac{|D|}{3}}.$$
ولكل \(a\) فردي يتحول شرط المميز إلى علاقة التطابق
$$b^2\equiv D \pmod{4a}.$$
يقوم التنفيذ بتفكيك \(a\) إلى قوى أولية، ثم يجد الجذور التربيعية لـ \(D\) modulo كل قوة أولية، ويرفع هذه الجذور إلى القوى الأعلى، ثم يجمع الحلول المحلية بواسطة مبرهنة البواقي الصينية، وبعد ذلك يعيد بناء القيم الممكنة لـ \(b\) و\(c\). كل شكل مختزل صالح يضيف فئة واحدة.
عند \(n=9\) نحصل على
$$N=8\cdot 9+3=75.$$
والتمثيلات بالمربعات الفردية الموجبة هي
$$75=1^2+5^2+7^2=5^2+5^2+5^2.$$
النمط الأول يملك \(3!=6\) ترتيبات، ولكل ترتيب \(8\) اختيارات للإشارات داخل \(r_3(75)\). أما النمط الثاني فيعطي \(1\cdot 8\). لذلك
$$r_3(75)=6\cdot 8+1\cdot 8=56,$$
ومن ثم
$$G(9)=\frac{56}{8}=7.$$
وبلغة الأعداد المثلثية فإن هذه الطرق السبع هي التبديلات الستة للمجموع \(0+3+6\) بالإضافة إلى الحالة الوحيدة \(3+3+3\).
للقيمة المطلوبة في المسألة، يُنشئ البرنامج
$$N=8\cdot (17526\cdot 10^9)+3=140208000000003,$$
ثم يفكك \(N\)، ويستخرج \(f\) و\(m\)، ويحسب \(h(-m)\)، ويقيّم مجموع القواسم في صيغة \(r_3(N)\)، ثم يقسم على \(8\) للحصول على \(G(n)\). بهذه الطريقة لا يحتاج التنفيذ إلى أي بحث مباشر في فضاء الأعداد المثلثية.
تنفذ نسخ C++ وPython وJava سلسلة الخطوات نفسها. أولاً يُفكك العدد \(N=8n+3\) باستخدام اختبار أولية مناسب لـ 64 بت مع خوارزمية Pollard-Rho. ومن هذا التفكيك يُفصل الجزء الخالي من المربعات \(m\) عن الجزء التربيعي \(f^2\)، فيتحدد المميز \(D=-m\).
بعد ذلك يُحسب عدد الفئات \(h(D)\). ولتحقيق ذلك، يعدد التنفيذ القيم المرشحة لـ \(a\)، ويفكك كل \(a\) بواسطة غربال صغير، ويحل شروط الجذور التربيعية modulo القوى الأولية، ثم يدمج الحلول المحلية بوساطة مبرهنة البواقي الصينية، وأخيراً يعدّ فقط الأشكال المختزلة التي تحقق معادلة المميز.
ثم يقيّم الكود المقدار
$$\sum_{d\mid f}\mu(d)\left(\frac{D}{d}\right)\sigma\left(\frac{f}{d}\right)$$
عن طريق المرور على القواسم الخالية من المربعات الناتجة من العوامل الأولية لـ \(f\). من هذا نحصل على \(r_3(N)\)، ثم تكون الإجابة النهائية هي \(r_3(N)/8\). كما تتضمن التطبيقات نقاط تحقق مثل \(G(9)=7\) و\(G(1000)=78\) و\(G(10^6)=2106\).
العدّ المباشر لثلاثيات الأعداد المثلثية مكلف جداً، لذلك فإن الصياغة العددية ضرورية. تفكيك الأعداد الصحيحة يُنجز باستخدام Miller-Rabin وPollard-Rho، وهو سريع عملياً لمدخل واحد من فئة 64 بت. بعد التفكيك، تصبح كلفة حساب عدد الفئات هي الجزء الحتمي الأكبر.
إذا كتبنا
$$A=\left\lfloor\sqrt{\frac{|D|}{3}}\right\rfloor,$$
فإن الغربال داخل روتين عدد الفئات يحتاج إلى ذاكرة \(O(A)\) وزمن تمهيدي \(O(A\log\log A)\). بعد ذلك يجري فحص جميع القيم الفردية \(a\le A\)، وكل خطوة تتضمن تفكيكاً صغيراً، وعدداً قليلاً من عمليات رفع الجذور التربيعية، ودمج CRT صغيراً. بالنسبة إلى قيمة هدف واحدة، فهذا عملي جداً وأفضل بمراحل من البحث الساذج المباشر.