The implementations count integer triples \((a,b,c)\) with
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
A direct search over \((a,b,c)\) is far too slow for the actual limit. The key reduction is to convert the Diophantine condition into a rational point on a conic, classify primitive solutions once, and then count every scaled multiple in one floor division.
Start from
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$$
After rearranging and dividing by \(b^2c^2\), we obtain
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
So if we define
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
then \((X,Y)\) is a rational point on the conic \(X^2+Y^2=5\). The ordering \(a<b<c<2a\) translates into
$$1<Y<X<2.$$
This is the geometric core of the fast solution: the original triple-counting problem becomes a count of rational points in one canonical region of the conic.
Write the rational point in lowest terms as
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
Then
$$U^2+V^2=5W^2.$$
Because \(1<Y<X<2\), the reduced integers satisfy
$$W<V<U<2W.$$
Any common divisor of two of \(U,V,W\) would also divide the third, so primitiveness implies pairwise coprimality. Also \(U\) and \(V\) cannot both be odd, hence exactly one of them is even and \(UV/2\) is an integer.
From \(X=2a/b=U/W\) and \(Y=2a/c=V/W\), we get
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
Since \(\gcd(U,W)=\gcd(V,W)=1\), integrality forces \(U\mid 2a\) and \(V\mid 2a\). Because \(\gcd(U,V)=1\), we must have
$$UV\mid 2a.$$
Therefore every solution in this primitive family is obtained by writing
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
The primitive family generator is thus
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
and its contribution to \(F(N)\) is exactly
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
The implementations enumerate coprime pairs \(m>n>m/2\) and define
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
A direct expansion shows
$$X_0^2+Y_0^2=5W_0^2.$$
So \((|X_0|,Y_0,W_0)\) is an integer solution of the same quadratic form. Let
$$g=\gcd(|X_0|,Y_0,W_0).$$
The reduced primitive data is
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
Cases with \(5\mid g\) are discarded by the implementations because they are non-canonical \(5\)-lifts of smaller primitive families and would otherwise be counted twice.
The condition \(n>m/2\) is exactly what puts the parameterization into the correct region. Indeed,
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
Hence both \(|X_0|\) and \(Y_0\) lie strictly between \(W_0\) and \(2W_0\). After dividing by \(g\) and sorting the two numerators, we obtain
$$W<V<U<2W,$$
which is exactly the reduced form corresponding to \(a<b<c<2a\).
Suppose an odd prime \(p\) divides all of \(|X_0|,Y_0,W_0\). Then \(p\) divides
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
Because \(p\) is odd and \(\gcd(m,n)=1\), the only possible shared cause is
$$m\equiv 2n \pmod p.$$
Substituting this into \(W_0=m^2+n^2\) gives \(5n^2\equiv 0\pmod p\), so \(p=5\). Thus the only odd common prime factor is \(5\). For the factor \(2\), if \(m\) and \(n\) are both odd then \(|X_0|,Y_0,W_0\) are even but not divisible by \(4\); otherwise at least one of them is odd. Therefore
$$g\in\{1,2,5,10\},$$
and once the duplicate \(5\)-lifts are skipped, the surviving cases have \(g=1\) or \(g=2\).
Take \((m,n)=(3,2)\). Then
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
Here \(g=1\), so after ordering we get
$$U=22,\qquad V=19,\qquad W=13.$$
The primitive triple generated by this family is
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
Thus the whole family is
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
and it contributes \(\lfloor N/209\rfloor\) solutions. In particular, this already explains why \(F(100)=0\): the first primitive family starts above \(100\).
The C++, Python, and Java implementations all follow the same mathematics. They first compute a safe upper bound for \(m\), then iterate every coprime pair \(m>n>m/2\). For each pair they build the quadratic forms above, divide out the common factor, reject the duplicate \(5\)-lift cases, sort the two reduced numerators into the canonical order, and finally add
$$\left\lfloor\frac{N}{UV/2}\right\rfloor.$$
The C++ and Java implementations parallelize the outer loop over \(m\), while the Python implementation uses the same arithmetic sequentially.
Let \(M\) be the largest \(m\) that can still contribute. Using \(g\le 2\) after the \(5\)-lift filter, we have
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
Write \(r=n/m\), so \(r\in(1/2,1)\). Then
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
hence
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
The factor on the right is increasing on \((1/2,1)\), so its minimum occurs at \(r=1/2\) and equals \(25/16\). Therefore
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
So no value \(m>(4N)^{1/4}\) can contribute, which matches the fourth-root cutoff used by the implementations. The enumeration therefore visits \(O(M^2)=O(N^{1/2})\) candidate pairs, with a constant amount of arithmetic and one gcd test per pair. Memory usage is \(O(1)\) apart from thread-local accumulators.
Die Implementierungen zählen ganzzahlige Tripel \((a,b,c)\) mit
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
Ein direkter Suchlauf über \((a,b,c)\) ist für die echte Schranke viel zu teuer. Der entscheidende Schritt besteht darin, die diofantische Bedingung in einen rationalen Punkt auf einer Kegelschnittgleichung umzuschreiben, primitive Familien nur einmal zu erzeugen und danach alle Skalierungen mit einer einzigen Ganzzahldivision zu zählen.
Aus
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}$$
folgt nach Umformen und Division durch \(b^2c^2\)
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
Setzt man
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
dann ist \((X,Y)\) ein rationaler Punkt auf \(X^2+Y^2=5\). Aus \(a<b<c<2a\) wird
$$1<Y<X<2.$$
Damit ist das ursprüngliche Zählproblem auf rationale Punkte in einem kanonischen Bereich derselben quadratischen Kurve reduziert.
Schreibe den rationalen Punkt in gekürzter Form als
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
Dann gilt
$$U^2+V^2=5W^2.$$
Wegen \(1<Y<X<2\) erhält man automatisch
$$W<V<U<2W.$$
Aus der Primitivität folgt sogar Paarweise-Teilerfremdheit. Außerdem können \(U\) und \(V\) nicht beide ungerade sein; daher ist genau einer von beiden gerade und \(UV/2\) eine ganze Zahl.
Aus \(X=2a/b=U/W\) und \(Y=2a/c=V/W\) folgt
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
Da \(\gcd(U,W)=\gcd(V,W)=1\), muss \(U\mid 2a\) und \(V\mid 2a\) gelten. Mit \(\gcd(U,V)=1\) folgt
$$UV\mid 2a.$$
Somit hat jede Lösung dieser primitiven Familie die Form
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
Der primitive Grundbaustein ist also
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
und sein Beitrag zu \(F(N)\) ist
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
Die Implementierungen durchlaufen teilerfremde Paare \(m>n>m/2\) und definieren
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
Durch direktes Ausmultiplizieren erhält man
$$X_0^2+Y_0^2=5W_0^2.$$
Also ist \((|X_0|,Y_0,W_0)\) bereits eine ganzzahlige Lösung derselben Form. Mit
$$g=\gcd(|X_0|,Y_0,W_0)$$
wird reduziert zu
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
Fälle mit \(5\mid g\) werden verworfen, weil sie keine neuen primitiven Familien liefern, sondern nur nichtkanonische \(5\)-Lifts bereits vorhandener Lösungen sind.
Aus \(n>m/2\) folgt
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
Damit liegen sowohl \(|X_0|\) als auch \(Y_0\) strikt zwischen \(W_0\) und \(2W_0\). Nach der Division durch \(g\) und dem Sortieren der beiden Zähler erhält man also
$$W<V<U<2W,$$
genau die reduzierte Region, die zu \(a<b<c<2a\) gehört.
Sei \(p\) ein ungerader Primteiler von \(|X_0|,Y_0,W_0\). Dann teilt \(p\) auch
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
Da \(p\) ungerade ist und \(\gcd(m,n)=1\) gilt, bleibt nur
$$m\equiv 2n \pmod p.$$
In \(W_0=m^2+n^2\) eingesetzt ergibt das \(5n^2\equiv 0\pmod p\), also \(p=5\). Der einzige mögliche ungerade gemeinsame Primteiler ist daher \(5\). Für die Zweierpotenz gilt: Sind \(m\) und \(n\) beide ungerade, dann sind \(|X_0|,Y_0,W_0\) zwar gerade, aber nicht durch \(4\) teilbar; andernfalls ist mindestens einer der drei Werte ungerade. Also
$$g\in\{1,2,5,10\},$$
und nach dem Entfernen der doppelten \(5\)-Lifts bleiben nur \(g=1\) oder \(g=2\).
Für \((m,n)=(3,2)\) erhält man
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
Hier ist \(g=1\), also nach Sortierung
$$U=22,\qquad V=19,\qquad W=13.$$
Der primitive Grundbaustein der Familie lautet damit
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
Die gesamte Familie ist also
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
und trägt \(\lfloor N/209\rfloor\) Lösungen bei. Insbesondere erklärt dieses erste primitive Beispiel bereits den Kontrollwert \(F(100)=0\).
Die C++-, Python- und Java-Implementierungen setzen exakt diese Herleitung um. Zuerst wird eine sichere Obergrenze für \(m\) berechnet. Danach werden alle teilerfremden Paare \(m>n>m/2\) durchlaufen, die quadratischen Formen ausgewertet, der gemeinsame Teiler entfernt, die doppelten \(5\)-Lifts verworfen und schließlich
$$\left\lfloor\frac{N}{UV/2}\right\rfloor$$
zum Ergebnis addiert. C++ und Java parallelisieren die äußere Schleife über \(m\), Python verwendet dieselbe Arithmetik seriell.
Sei \(M\) die größte relevante \(m\)-Schranke. Nach dem \(5\)-Lift-Filter gilt \(g\le 2\), also
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
Mit \(r=n/m\in(1/2,1)\) hat man
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
und damit
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
Der Faktor rechts ist auf \((1/2,1)\) wachsend und nimmt sein Minimum bei \(r=1/2\) an. Somit
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
Also kann kein \(m>(4N)^{1/4}\) mehr beitragen. Die Enumeration besucht daher \(O(M^2)=O(N^{1/2})\) Kandidatenpaare, jeweils mit konstant viel Arithmetik und einem ggT-Test. Der Speicherbedarf ist \(O(1)\), abgesehen von thread-lokalen Summen.
Uygulamalar şu koşulları sağlayan tamsayı üçlülerini \((a,b,c)\) sayar:
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
\((a,b,c)\) uzayında doğrudan arama yapmak gerçek sınır için çok pahalıdır. Hızlı çözüm, diofantik koşulu bir konik üzerindeki rasyonel noktaya dönüştürür, primitif aileleri bir kez üretir ve her aileden gelen tüm ölçekleri tek bir taban bölümle sayar.
Başlangıç denklemi
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$$
Bunu düzenleyip \(b^2c^2\) ile bölersek
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5$$
elde edilir. Şimdi
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c}$$
tanımını yapalım. Böylece \((X,Y)\), \(X^2+Y^2=5\) koniği üzerinde rasyonel bir noktadır. Ayrıca \(a<b<c<2a\) eşitsizlikleri
$$1<Y<X<2$$
şeklinde yazılır. Yani problem, konik üzerindeki rasyonel noktaların tek bir kanonik bölgesini sayma problemine indirgenir.
Rasyonel noktayı sadeleştirilmiş biçimde
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1$$
olarak yazalım. O zaman
$$U^2+V^2=5W^2$$
olur. \(1<Y<X<2\) koşulu da
$$W<V<U<2W$$
şeklini alır. İki bileşenin ortak böleni olsaydı üçüncüyü de bölerdi; dolayısıyla bu üç sayı ikili olarak da aralarında asaldır. Ayrıca \(U\) ve \(V\) aynı anda tek olamaz; bu yüzden tam olarak biri çifttir ve \(UV/2\) tam sayıdır.
\(X=2a/b=U/W\) ve \(Y=2a/c=V/W\) olduğundan
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}$$
yazabiliriz. \(\gcd(U,W)=\gcd(V,W)=1\) olduğuna göre \(U\mid 2a\) ve \(V\mid 2a\) olmalıdır. \(\gcd(U,V)=1\) ile birlikte bu
$$UV\mid 2a$$
sonucunu verir. Dolayısıyla bu primitif ailedeki tüm çözümler
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1$$
şeklindedir. Ailenin primitif çekirdeği
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW$$
olur ve bu ailenin toplam katkısı
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor$$
şeklindedir.
Uygulamalar \(\gcd(m,n)=1\) olmak üzere \(m>n>m/2\) çiftlerini gezer ve
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2$$
tanımlarını kullanır. Doğrudan açarsak
$$X_0^2+Y_0^2=5W_0^2$$
özdeşliği elde edilir. Yani \((|X_0|,Y_0,W_0)\) zaten aynı kuadratik formun bir tamsayı çözümüdür. Şimdi
$$g=\gcd(|X_0|,Y_0,W_0)$$
alınır ve sadeleştirilmiş veri
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}$$
olarak oluşturulur. \(5\mid g\) olan durumlar, daha küçük primitif ailelerin kanonik olmayan \(5\)-kat kaldırımları olduğundan atılır.
\(n>m/2\) koşulu tam olarak doğru bölgeyi seçer. Gerçekten
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
Böylece hem \(|X_0|\) hem de \(Y_0\), \(W_0\) ile \(2W_0\) arasında kalır. \(g\) ile böldükten ve iki payı sıraladıktan sonra
$$W<V<U<2W$$
elde edilir; bu da doğrudan \(a<b<c<2a\) bölgesine karşılık gelir.
\(|X_0|,Y_0,W_0\) sayılarını bölen tek bir tek asal \(p\) düşünelim. O halde \(p\) aynı zamanda
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n)$$
ifadelerini de böler. \(p\) tek ve \(\gcd(m,n)=1\) olduğundan, tek tutarlı seçenek
$$m\equiv 2n \pmod p$$
olur. Bunu \(W_0=m^2+n^2\) içine koyarsak \(5n^2\equiv 0\pmod p\) bulunur; dolayısıyla \(p=5\). Yani olası tek tek ortak asal çarpan \(5\)'tir. İkilik kısım için, \(m\) ve \(n\) ikisi de tekse üç ifade çift ama \(4\)'e bölünmez; aksi halde en az biri tektir. Sonuç olarak
$$g\in\{1,2,5,10\}$$
ve \(5\)-kat tekrarları atıldıktan sonra geriye yalnızca \(g=1\) veya \(g=2\) kalır.
\((m,n)=(3,2)\) alalım. O zaman
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
Burada \(g=1\) olduğundan sıralanmış primitif çözüm
$$U=22,\qquad V=19,\qquad W=13$$
şeklindedir. Bu ailenin primitif üçlüsü
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286$$
olur. Yani tüm aile
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1 $$
şeklindedir ve katkısı \(\lfloor N/209\rfloor\)'dur. Özellikle bu ilk primitif aile bile \(F(100)=0\) kontrolünü açıklar.
C++, Python ve Java uygulamaları aynı matematiği uygular. Önce \(m\) için güvenli bir üst sınır hesaplanır. Sonra tüm aralarında asal \(m>n>m/2\) çiftleri gezilir; kuadratik formlar hesaplanır, ortak bölen kaldırılır, yinelenen \(5\)-kat temsiller atılır ve son olarak
$$\left\lfloor\frac{N}{UV/2}\right\rfloor$$
sonuca eklenir. C++ ve Java dıştaki \(m\) döngüsünü paralelleştirirken, Python aynı aritmetiği tek iş parçacığında uygular.
\(M\), katkı verebilecek en büyük \(m\) olsun. \(5\)-kat filtrelemesinden sonra \(g\le 2\) olduğundan
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
\(r=n/m\in(1/2,1)\) yazarsak
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
ve dolayısıyla
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
Sağdaki çarpan \((1/2,1)\) aralığında artandır; minimumu \(r=1/2\) noktasında \(25/16\) olur. Bu yüzden
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
Böylece \(m>(4N)^{1/4}\) ise katkı gelmez; bu, uygulamaların kullandığı dördüncü kök kesmesini açıklar. Toplam aday sayısı \(O(M^2)=O(N^{1/2})\) düzeyindedir ve her aday için sabit sayıda aritmetik işlem ile bir ebob hesabı yapılır. Bellek kullanımı, iş parçacığı yerel toplamları dışında \(O(1)\)'dir.
Las implementaciones cuentan ternas enteras \((a,b,c)\) tales que
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
Un barrido directo sobre \((a,b,c)\) es demasiado lento para el límite real. La reducción clave consiste en convertir la condición diofántica en un punto racional sobre una cónica, generar una sola vez cada familia primitiva y después contar todas sus escalas válidas mediante una división entera.
Partimos de
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$$
Al reorganizar y dividir por \(b^2c^2\), obtenemos
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
Si definimos
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
entonces \((X,Y)\) es un punto racional de la cónica \(X^2+Y^2=5\). Además, la condición \(a<b<c<2a\) se traduce en
$$1<Y<X<2.$$
Así, el problema original se convierte en contar puntos racionales de una región canónica de esa cónica.
Escribimos el punto racional en forma reducida como
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
Entonces
$$U^2+V^2=5W^2.$$
La desigualdad \(1<Y<X<2\) implica
$$W<V<U<2W.$$
Si dos de \(U,V,W\) compartieran un divisor, el tercero también lo compartiría; por tanto, la primitividad implica coprimalidad por pares. Además, \(U\) y \(V\) no pueden ser ambos impares, de modo que exactamente uno es par y \(UV/2\) es entero.
De \(X=2a/b=U/W\) y \(Y=2a/c=V/W\) se sigue que
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
Como \(\gcd(U,W)=\gcd(V,W)=1\), la integridad de \(b\) y \(c\) obliga a que \(U\mid 2a\) y \(V\mid 2a\). Dado que \(\gcd(U,V)=1\), resulta
$$UV\mid 2a.$$
Por tanto, toda solución de esa familia se escribe como
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
El bloque primitivo es
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
y su contribución a \(F(N)\) es
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
Las implementaciones recorren pares coprimos \(m>n>m/2\) y forman
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
Al expandir se verifica que
$$X_0^2+Y_0^2=5W_0^2.$$
Luego \((|X_0|,Y_0,W_0)\) ya es una solución entera de la misma forma cuadrática. Si
$$g=\gcd(|X_0|,Y_0,W_0),$$
la solución reducida es
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
Los casos con \(5\mid g\) se descartan porque corresponden a duplicados obtenidos por un levantamiento no canónico por factor \(5\).
La condición \(n>m/2\) coloca automáticamente la parametrización en la región correcta. En efecto,
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
Por lo tanto, tanto \(|X_0|\) como \(Y_0\) quedan estrictamente entre \(W_0\) y \(2W_0\). Tras dividir por \(g\) y ordenar los dos numeradores, obtenemos
$$W<V<U<2W,$$
que es exactamente la región reducida asociada a \(a<b<c<2a\).
Supongamos que un primo impar \(p\) divide simultáneamente \(|X_0|,Y_0,W_0\). Entonces también divide
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
Como \(p\) es impar y \(\gcd(m,n)=1\), la única posibilidad consistente es
$$m\equiv 2n \pmod p.$$
Sustituyendo en \(W_0=m^2+n^2\) resulta \(5n^2\equiv 0\pmod p\), así que \(p=5\). Es decir, el único posible primo impar común es \(5\). Para el factor \(2\), si \(m\) y \(n\) son ambos impares, las tres formas son pares pero no múltiplos de \(4\); en caso contrario, al menos una de ellas es impar. Por tanto,
$$g\in\{1,2,5,10\},$$
y tras eliminar los duplicados por factor \(5\), solo quedan \(g=1\) o \(g=2\).
Tomemos \((m,n)=(3,2)\). Entonces
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
Aquí \(g=1\), así que tras ordenar obtenemos
$$U=22,\qquad V=19,\qquad W=13.$$
La terna primitiva asociada es
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
Por tanto, toda la familia es
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
y aporta \(\lfloor N/209\rfloor\) soluciones. Esto explica de inmediato por qué \(F(100)=0\).
Las implementaciones en C++, Python y Java siguen exactamente esta derivación. Primero calculan una cota superior segura para \(m\); después recorren todos los pares coprimos \(m>n>m/2\), evalúan las formas cuadráticas, eliminan el divisor común, descartan los levantamientos duplicados por \(5\) y acumulan
$$\left\lfloor\frac{N}{UV/2}\right\rfloor.$$
Las versiones en C++ y Java paralelizan el bucle exterior sobre \(m\); la versión en Python realiza la misma aritmética de forma secuencial.
Sea \(M\) el mayor valor de \(m\) que todavía puede contribuir. Después de filtrar los duplicados por factor \(5\), se cumple \(g\le 2\), de modo que
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
Escribiendo \(r=n/m\in(1/2,1)\), tenemos
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
y por tanto
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
El factor de la derecha es creciente en \((1/2,1)\), así que su mínimo está en \(r=1/2\) y vale \(25/16\). En consecuencia,
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
Luego ningún \(m>(4N)^{1/4}\) puede contribuir, lo que coincide con el corte por cuarta raíz usado por las implementaciones. La enumeración visita \(O(M^2)=O(N^{1/2})\) pares candidatos, con aritmética constante y una prueba de coprimalidad por par. La memoria adicional es \(O(1)\), aparte de acumuladores locales por hilo.
这些实现要统计满足下式的整数三元组 \((a,b,c)\)：
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
如果直接枚举 \((a,b,c)\)，在真实上界下完全不可行。高效做法先把这个丢番图条件改写成圆锥曲线上的有理点问题，再只生成一次每个原始族，最后用一个下取整计入该族的全部缩放倍数。
从
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}$$
出发，整理并除以 \(b^2c^2\)，得到
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
令
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
那么 \((X,Y)\) 就是圆锥曲线 \(X^2+Y^2=5\) 上的一个有理点。由 \(a<b<c<2a\) 可知
$$1<Y<X<2.$$
也就是说，原问题可以转化为统计这条曲线某个规范区域中的有理点。
把有理点约分后写成
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
于是有
$$U^2+V^2=5W^2.$$
又因为 \(1<Y<X<2\)，所以自动满足
$$W<V<U<2W.$$
如果其中两个数还有公共因子，那么第三个数也会被同一个因子整除，因此原始性意味着它们两两互素。另外 \(U\) 与 \(V\) 不可能同时为奇数，所以恰有一个是偶数，从而 \(UV/2\) 一定是整数。
由 \(X=2a/b=U/W\) 与 \(Y=2a/c=V/W\) 可得
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
因为 \(\gcd(U,W)=\gcd(V,W)=1\)，要使 \(b,c\) 为整数，就必须有 \(U\mid 2a\) 且 \(V\mid 2a\)。再结合 \(\gcd(U,V)=1\)，得到
$$UV\mid 2a.$$
因此，这个原始族中的所有解都可写成
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
所以对应的原始基元是
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
该族对 \(F(N)\) 的贡献正好是
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
实现枚举满足 \(\gcd(m,n)=1\) 的参数对 \(m>n>m/2\)，并构造
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
直接展开可以验证
$$X_0^2+Y_0^2=5W_0^2.$$
因此 \((|X_0|,Y_0,W_0)\) 本身就是同一二次型的整数解。记
$$g=\gcd(|X_0|,Y_0,W_0),$$
再把它约成
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
如果 \(5\mid g\)，实现会直接丢弃该情况，因为这只是更小原始族的非规范 \(5\)-提升，会造成重复计数。
条件 \(n>m/2\) 恰好保证参数点落在正确区域。确实有
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
所以 \(|X_0|\) 与 \(Y_0\) 都严格落在 \(W_0\) 和 \(2W_0\) 之间。除以 \(g\) 并重新排序后，就得到
$$W<V<U<2W,$$
这正是与 \(a<b<c<2a\) 完全对应的规范区域。
设某个奇素数 \(p\) 同时整除 \(|X_0|,Y_0,W_0\)。那么它也整除
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
由于 \(p\) 为奇素数且 \(\gcd(m,n)=1\)，唯一可能的一致结论是
$$m\equiv 2n \pmod p.$$
代回 \(W_0=m^2+n^2\) 得到 \(5n^2\equiv 0\pmod p\)，因此 \(p=5\)。也就是说，可能出现的奇公共素因子只有 \(5\)。至于因子 \(2\)，若 \(m,n\) 都是奇数，则三项都为偶数但都不被 \(4\) 整除；否则三项中至少有一项是奇数。因此
$$g\in\{1,2,5,10\},$$
滤掉重复的 \(5\)-提升以后，只剩下 \(g=1\) 或 \(g=2\)。
取 \((m,n)=(3,2)\)。此时
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
这里 \(g=1\)，排序后得到
$$U=22,\qquad V=19,\qquad W=13.$$
于是对应的原始三元组为
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
整族解为
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
因此该族贡献 \(\lfloor N/209\rfloor\)。这也立刻解释了为什么 \(F(100)=0\)。
C++、Python 和 Java 实现都遵循同一套数学结构。它们先计算 \(m\) 的安全上界，然后枚举所有满足 \(m>n>m/2\) 且互素的参数对，构造上面的二次型，去掉公共因子，过滤重复的 \(5\)-提升表示，最后累加
$$\left\lfloor\frac{N}{UV/2}\right\rfloor.$$
C++ 与 Java 会把外层 \(m\) 循环并行化，而 Python 版本使用完全相同的整数算术顺序执行。
记 \(M\) 为仍可能产生贡献的最大 \(m\)。过滤 \(5\)-提升后有 \(g\le 2\)，因此
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
令 \(r=n/m\in(1/2,1)\)，则
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
于是
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
右侧因子在区间 \((1/2,1)\) 上递增，最小值出现在 \(r=1/2\)，等于 \(25/16\)。因此
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
所以当 \(m>(4N)^{1/4}\) 时，原始面积已经超过 \(N\)，不可能再有贡献。这与实现中的四次根截断完全一致。总共访问的候选参数对数量为 \(O(M^2)=O(N^{1/2})\)，每对只需要常数次整数运算和一次 gcd 检查；除线程局部累加器外，额外空间为 \(O(1)\)。
Реализации считают целочисленные тройки \((a,b,c)\), удовлетворяющие условию
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
Прямой перебор по \((a,b,c)\) слишком дорог для настоящего ограничения. Быстрый метод переводит диофантово условие в задачу о рациональных точках на конике, строит каждое примитивное семейство один раз, а затем сразу учитывает все его масштабы с помощью одной целочисленной части.
Начинаем с равенства
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$$
После преобразования и деления на \(b^2c^2\) получаем
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
Если положить
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
то \((X,Y)\) является рациональной точкой коники \(X^2+Y^2=5\). Неравенства \(a<b<c<2a\) переходят в
$$1<Y<X<2.$$
Тем самым исходная задача о тройках сводится к рациональным точкам в одной канонической области этой кривой.
Запишем рациональную точку в несократимом виде:
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
Тогда выполняется
$$U^2+V^2=5W^2.$$
Из \(1<Y<X<2\) сразу следует
$$W<V<U<2W.$$
Если бы два числа из \(U,V,W\) имели общий делитель, то он делил бы и третье, поэтому примитивность даёт попарную взаимную простоту. Кроме того, \(U\) и \(V\) не могут быть одновременно нечётными, так что ровно одно из них чётно, а значит \(UV/2\) целое.
Из \(X=2a/b=U/W\) и \(Y=2a/c=V/W\) имеем
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
Так как \(\gcd(U,W)=\gcd(V,W)=1\), целочисленность \(b\) и \(c\) требует, чтобы \(U\mid 2a\) и \(V\mid 2a\). С учётом \(\gcd(U,V)=1\) получаем
$$UV\mid 2a.$$
Следовательно, все решения данного примитивного семейства имеют вид
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
Примитивный базовый элемент равен
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
а вклад семейства в \(F(N)\) равен
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
Реализации перебирают взаимно простые пары \(m>n>m/2\) и задают
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
Непосредственное раскрытие скобок даёт
$$X_0^2+Y_0^2=5W_0^2.$$
Значит, \((|X_0|,Y_0,W_0)\) уже является целочисленным решением той же квадратичной формы. Пусть
$$g=\gcd(|X_0|,Y_0,W_0).$$
Тогда после сокращения получаем
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
Случаи с \(5\mid g\) отбрасываются, потому что они соответствуют неканоническим \(5\)-подъёмам уже учтённых меньших примитивных семейств.
Условие \(n>m/2\) ровно и помещает параметризацию в нужную область. Действительно,
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
Следовательно, и \(|X_0|\), и \(Y_0\) лежат строго между \(W_0\) и \(2W_0\). После деления на \(g\) и сортировки двух числителей получаем
$$W<V<U<2W,$$
то есть именно ту редуцированную область, которая эквивалентна \(a<b<c<2a\).
Пусть нечётное простое \(p\) делит одновременно \(|X_0|,Y_0,W_0\). Тогда \(p\) делит и
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
Поскольку \(p\) нечётно и \(\gcd(m,n)=1\), единственная согласованная возможность такова:
$$m\equiv 2n \pmod p.$$
Подстановка в \(W_0=m^2+n^2\) даёт \(5n^2\equiv 0\pmod p\), значит \(p=5\). Итак, единственный возможный нечётный общий простой делитель равен \(5\). Для двойки: если \(m\) и \(n\) оба нечётны, то \(|X_0|,Y_0,W_0\) чётные, но не делятся на \(4\); иначе хотя бы одно из трёх чисел нечётно. Следовательно,
$$g\in\{1,2,5,10\},$$
а после удаления дубликатов с фактором \(5\) остаются только случаи \(g=1\) или \(g=2\).
Возьмём \((m,n)=(3,2)\). Тогда
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
Здесь \(g=1\), и после упорядочивания получаем
$$U=22,\qquad V=19,\qquad W=13.$$
Соответствующая примитивная тройка равна
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
Значит всё семейство имеет вид
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
и даёт вклад \(\lfloor N/209\rfloor\). Уже это первое примитивное семейство объясняет контрольное значение \(F(100)=0\).
Реализации на C++, Python и Java используют одну и ту же математику. Сначала вычисляется безопасная верхняя граница для \(m\), затем перебираются все взаимно простые пары \(m>n>m/2\), строятся указанные квадратичные формы, убирается общий делитель, выбрасываются дубликаты вида \(5\)-lift и накапливается
$$\left\lfloor\frac{N}{UV/2}\right\rfloor.$$
Версии на C++ и Java распараллеливают внешний цикл по \(m\), а версия на Python выполняет те же вычисления последовательно.
Пусть \(M\) обозначает наибольшее значение \(m\), которое ещё может дать вклад. После фильтра \(5\)-lift имеем \(g\le 2\), поэтому
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
Положим \(r=n/m\in(1/2,1)\). Тогда
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
откуда
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
Множитель справа возрастает на \((1/2,1)\), поэтому минимум достигается при \(r=1/2\) и равен \(25/16\). Следовательно,
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
Значит, никакое \(m>(4N)^{1/4}\) уже не может внести вклад; именно такой срез по четвёртому корню и используют реализации. Всего посещается \(O(M^2)=O(N^{1/2})\) кандидатных пар, и на каждую пару приходится константное число арифметических операций и одна проверка взаимной простоты. Дополнительная память равна \(O(1)\), не считая потоковых частичных сумм.
تقوم التطبيقات بعدّ الثلاثيات الصحيحة \((a,b,c)\) التي تحقق
$$F(N)=\#\left\{(a,b,c)\in\mathbb{Z}_{>0}^3:\ a\le N,\ a<b<c<2a,\ c^2=\frac{4a^2b^2}{5b^2-4a^2}\right\}.$$
الفحص المباشر لجميع القيم \((a,b,c)\) غير عملي عند الحد الحقيقي للمسألة. الفكرة الحاسمة هي تحويل الشرط الديوفانتي إلى نقطة نسبية على قطع مخروطي، ثم توليد كل عائلة بدائية مرة واحدة فقط، وبعد ذلك عدّ جميع التمددات المسموح بها بواسطة قسمة صحيحة واحدة.
نبدأ من العلاقة
$$c^2=\frac{4a^2b^2}{5b^2-4a^2}.$$
وبعد إعادة الترتيب والقسمة على \(b^2c^2\) نحصل على
$$\left(\frac{2a}{b}\right)^2+\left(\frac{2a}{c}\right)^2=5.$$
إذا عرفنا
$$X=\frac{2a}{b},\qquad Y=\frac{2a}{c},$$
فإن \((X,Y)\) نقطة نسبية على القطع \(X^2+Y^2=5\). أما الترتيب \(a<b<c<2a\) فيصبح
$$1<Y<X<2.$$
وبذلك تتحول المسألة الأصلية إلى عدّ نقاط نسبية داخل منطقة معيارية واحدة على هذا القطع.
نكتب النقطة النسبية في الصورة المختزلة
$$X=\frac{U}{W},\qquad Y=\frac{V}{W},\qquad \gcd(U,V,W)=1.$$
عندئذٍ
$$U^2+V^2=5W^2.$$
ومن \(1<Y<X<2\) نحصل مباشرة على
$$W<V<U<2W.$$
لو كان لأي عددين من \(U,V,W\) قاسم مشترك لكان هذا القاسم يقسم الثالث أيضًا، لذا فالبداوة تعني أنها أولية فيما بينها زوجيًا. كما أن \(U\) و\(V\) لا يمكن أن يكونا كلاهما فرديين، ولذلك يكون أحدهما فقط زوجيًا ويكون \(UV/2\) عددًا صحيحًا.
من \(X=2a/b=U/W\) و\(Y=2a/c=V/W\) نحصل على
$$b=\frac{2aW}{U},\qquad c=\frac{2aW}{V}.$$
وبما أن \(\gcd(U,W)=\gcd(V,W)=1\)، فإن صحة \(b\) و\(c\) كأعداد صحيحة تفرض \(U\mid 2a\) و\(V\mid 2a\). ومع \(\gcd(U,V)=1\) نستنتج
$$UV\mid 2a.$$
إذن كل حل في هذه العائلة البدائية يكتب على الصورة
$$a=k\frac{UV}{2},\qquad b=kVW,\qquad c=kUW,\qquad k\ge 1.$$
ومن ثم يكون العنصر البدائي
$$a_0=\frac{UV}{2},\qquad b_0=VW,\qquad c_0=UW,$$
ومساهمته في \(F(N)\) هي
$$\left\lfloor\frac{N}{a_0}\right\rfloor=\left\lfloor\frac{2N}{UV}\right\rfloor.$$
تعدّ التطبيقات الأزواج الأولية \(m>n>m/2\) وتبني
$$X_0=m^2-4mn-n^2,\qquad Y_0=2(m^2+mn-n^2),\qquad W_0=m^2+n^2.$$
وبالتوسيع المباشر نجد
$$X_0^2+Y_0^2=5W_0^2.$$
إذًا فإن \((|X_0|,Y_0,W_0)\) حل صحيح لنفس الصيغة التربيعية. إذا أخذنا
$$g=\gcd(|X_0|,Y_0,W_0),$$
فإن البيانات المختزلة تصبح
$$U=\frac{\max(|X_0|,Y_0)}{g},\qquad V=\frac{\min(|X_0|,Y_0)}{g},\qquad W=\frac{W_0}{g}.$$
الحالات التي يحقق فيها \(5\mid g\) تُستبعد لأنّها تمثيلات مكررة من نوع رفع بعامل \(5\) لعائلات بدائية أصغر.
الشرط \(n>m/2\) هو بالضبط ما يضعنا في المنطقة الصحيحة. فعلًا لدينا
$$|X_0|-W_0=2m(2n-m)>0,$$
$$Y_0-W_0=(m-n)(m+3n)>0,$$
$$2W_0-|X_0|=3m^2+n^2-4mn>0,$$
$$2W_0-Y_0=2n(2n-m)>0.$$
وبالتالي فإن \(|X_0|\) و\(Y_0\) يقعان كلاهما بدقة بين \(W_0\) و\(2W_0\). وبعد القسمة على \(g\) وترتيب البسطين نحصل على
$$W<V<U<2W,$$
وهي بالضبط المنطقة المختزلة المطابقة للشرط \(a<b<c<2a\).
افترض أن عددًا أوليًا فرديًا \(p\) يقسم معًا \(|X_0|,Y_0,W_0\). عندئذٍ يقسم أيضًا
$$2W_0-Y_0=2n(2n-m),\qquad W_0+X_0=2m(m-2n).$$
وبما أن \(p\) فردي وأن \(\gcd(m,n)=1\)، فإن الاحتمال المتوافق الوحيد هو
$$m\equiv 2n \pmod p.$$
وبالتعويض في \(W_0=m^2+n^2\) نحصل على \(5n^2\equiv 0\pmod p\)، ومن ثم \(p=5\). أي إن العامل الأولي الفردي المشترك الوحيد الممكن هو \(5\). أما بالنسبة للعامل \(2\)، فإذا كان \(m\) و\(n\) كلاهما فرديين فإن \(|X_0|,Y_0,W_0\) زوجية لكنها غير قابلة للقسمة على \(4\)، وإلا فإن واحدًا منها على الأقل يكون فرديًا. لذا
$$g\in\{1,2,5,10\},$$
وبعد حذف حالات الرفع المكرر بعامل \(5\) لا يبقى إلا \(g=1\) أو \(g=2\).
خذ \((m,n)=(3,2)\). عندها
$$X_0=3^2-4\cdot 3\cdot 2-2^2=-19,\qquad Y_0=2(3^2+3\cdot 2-2^2)=22,\qquad W_0=3^2+2^2=13.$$
هنا \(g=1\)، وبعد الترتيب نحصل على
$$U=22,\qquad V=19,\qquad W=13.$$
إذن الثلاثية البدائية الموافقة هي
$$a_0=\frac{22\cdot 19}{2}=209,\qquad b_0=19\cdot 13=247,\qquad c_0=22\cdot 13=286.$$
وبالتالي تكون العائلة كلها
$$ (a,b,c)=k(209,247,286),\qquad k\ge 1,$$
ومساهمتها \(\lfloor N/209\rfloor\). وهذا يفسر مباشرةً لماذا تكون \(F(100)=0\).
تتبع تطبيقات C++ وPython وJava هذه المشتقة نفسها حرفيًا. فهي تحسب أولًا حدًا علويًا آمنًا لـ \(m\)، ثم تمرّ على كل زوج أولي \(m>n>m/2\)، وتبني الأشكال التربيعية السابقة، وتزيل القاسم المشترك، وتستبعد تمثيلات \(5\)-lift المكررة، ثم تجمع
$$\left\lfloor\frac{N}{UV/2}\right\rfloor.$$
تقوم نسختا C++ وJava بتوازي الحلقة الخارجية على \(m\)، بينما تنفذ Python الحسابات نفسها بشكل متسلسل.
ليكن \(M\) أكبر قيمة لـ \(m\) يمكن أن تساهم. بعد تطبيق مرشح \(5\)-lift لدينا \(g\le 2\)، ومن ثم
$$a_0=\frac{UV}{2}=\frac{|X_0|Y_0}{2g^2}\ge \frac{|X_0|Y_0}{8}.$$
إذا كتبنا \(r=n/m\) بحيث \(r\in(1/2,1)\)، فإن
$$|X_0|=m^2(4r+r^2-1),\qquad Y_0=2m^2(1+r-r^2),$$
ولذلك
$$a_0\ge \frac{m^4}{4}(4r+r^2-1)(1+r-r^2).$$
العامل في الطرف الأيمن متزايد على \((1/2,1)\)، لذا يتحقق حده الأدنى عند \(r=1/2\) ويساوي \(25/16\). ومن ثم
$$a_0\ge \frac{25}{64}m^4>\frac14 m^4.$$
إذن إذا كان \(m>(4N)^{1/4}\) فلن يبقى أي إسهام، وهذا يطابق حد الجذر الرابع المستخدم في التطبيقات. عدد الأزواج المرشحة هو \(O(M^2)=O(N^{1/2})\)، مع عدد ثابت من العمليات الحسابية واختبار gcd واحد لكل زوج. الذاكرة الإضافية هي \(O(1)\) باستثناء المجاميع المحلية للخيوط.