For a given bound \(n\), we count distinct real values of
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
where \(y\) and \(z\) are non-squares and the outer radical can be denested into a finite signed sum of simple square roots. Different triples \((x,y,z)\) may represent the same real number, but that value must be counted only once. The implementations evaluate this count at \(n=5{,}000{,}000\).
The program organizes the denestable values into two structural families. The first family comes from denestings with two simple roots. The second family comes from denestings with four simple roots and one minus sign. The final formula counts both families and then removes the four-root cases that collapse back to a value already counted in the two-root family.
Let \(F(n)\) denote the number of distinct denestable values with integer part \(x\le n\). The implementation builds \(F(n)\) from an arithmetic kernel \(f(s)\) and three counting terms \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\), and \(C_3(n)\).
Start with a value of the form
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
Squaring gives
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
If \(\alpha\beta\) is not a square, then \(V^2\) has exactly one irrational square-root direction, and it fits the required pattern because
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
with \(k^2\alpha\beta\) still non-square. So each primitive pair \((\alpha,\beta)\) produces one infinite scaling family of admissible values, and the integer part is
$$x=k(\alpha+\beta).$$
For a fixed primitive sum
$$s=\alpha+\beta,$$
the scale \(k\) can be chosen in exactly
$$\left\lfloor\frac{n}{s}\right\rfloor$$
ways.
For fixed \(s\ge 3\), how many primitive pairs \((\alpha,\beta)\) with \(\alpha+\beta=s\) belong to the first family?
The number of coprime decompositions \(s=\alpha+\beta\) with \(\alpha \gt \beta \ge 1\) is
$$\frac{\varphi(s)}{2},$$
because each reduced residue class modulo \(s\) corresponds to one ordered coprime split, and dividing by \(2\) forgets the order.
Now remove the bad cases where \(\alpha\beta\) is a square. Since \(\gcd(\alpha,\beta)=1\), this happens exactly when
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
So the excluded pairs are precisely the primitive representations
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
If \(R(s)\) denotes the number of those primitive two-square representations, then the kernel used by the implementations is
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
Therefore the total contribution of the two-root family is
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
The second family combines two primitive kernels. Take two primitive pairs \((\alpha,\beta)\) and \((\gamma,\delta)\), each counted by \(f\), and form
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
Expanding \(W^2\) gives a crucial cancellation:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
The mixed term involving \(\sqrt{\alpha\beta\gamma\delta}\) disappears because of the sign pattern. This leaves exactly two square-root directions, so \(W\) is another denesting of the required form.
If we write
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
then the integer part of \(W^2\) is
$$x=kst.$$
Hence each ordered pair of primitive kernels \((s,t)\) contributes
$$\left\lfloor\frac{n}{st}\right\rfloor$$
scaled values, and the ordered count is
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
The superscript “ord” matters: swapping the two kernels does not change the final value, so this sum counts the generic four-root construction twice.
Not every ordered four-root construction is genuinely new. Some of them collapse to only two independent squarefree radicals and are therefore already included in \(C_1(n)\).
Write the two primitive pairs as
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
where \(\sigma_1,\sigma_2,\tau_1,\tau_2\) are squarefree. The four radicals inside \(W\) then have squarefree parts
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
A collision with the two-root family occurs exactly when these four squarefree products merge into only two distinct squarefree directions. The implementation parameterizes those collisions by squarefree, pairwise-coprime factors \(\rho_1,\rho_2,\rho_3,\rho_4\) such that
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
Then
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
and likewise
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
So the supposed four-root expression is really a two-root value. Let \(C_3(n)\) be the number of ordered constructions of exactly this collapsing kind. These must be removed from the ordered four-root count before the final symmetry factor is applied.
After subtracting the collapsing ordered constructions and then forgetting the order of the two primitive kernels, the implementations compute
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
This is the exact decomposition used by the C++, Python, and Java implementations.
A simple two-root example is
$$V=\sqrt5+\sqrt2.$$
Then
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
Here the primitive kernel is \(s=5+2=7\), and because \(5\cdot2=10\) is not a square, this value belongs to the first family. Every scale \(k\) with \(7k\le n\) gives another valid value from the same kernel.
A genuine four-root example uses \((\alpha,\beta)=(2,1)\) and \((\gamma,\delta)=(3,1)\):
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
Its square is
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
So the integer part is \(12=3\cdot4\), which shows why the second family is indexed by products of primitive kernel sums.
The implementations first build a totient sieve up to \(n\). From that array they initialize
$$f(s)=\frac{\varphi(s)}{2}$$
for \(s\ge 3\), then subtract one for every primitive representation \(s=u^2+v^2\) with \(u \gt v\) and \(\gcd(u,v)=1\). That produces the kernel sequence \(f(s)\).
Next they form prefix sums of \(f\). The first family \(C_1(n)\) is then a direct divisor-style sum. The ordered second-family term \(C_2^{\mathrm{ord}}(n)\) is not evaluated by a quadratic double loop. Instead, the code groups equal quotients of \(\left\lfloor n/i\right\rfloor\) into harmonic intervals and combines them with prefix sums, which turns the convolution into a much smaller collection of block sums.
The overlap term \(C_3(n)\) is handled separately. The code precomputes squarefree flags, coprimality lookup tables, and squares up to \(\lfloor\sqrt n\rfloor\). It then enumerates only the parameter combinations that can force a four-root value to collapse into two squarefree directions, using many early inequality breaks to prune the search. The C++ implementation parallelizes this expensive overlap phase; the Python version mirrors the same mathematics more directly, and the Java version reuses the same optimized core computation.
Building the totient sieve and the kernel \(f\) takes \(O(n\log\log n)\) time and \(O(n)\) memory. The first family sum \(C_1(n)\) is \(O(n)\). The ordered convolution \(C_2^{\mathrm{ord}}(n)\) is accelerated by harmonic blocking and prefix sums, so the code avoids the naive \(O(n^2)\) double loop and works with a subquadratic number of quotient blocks instead.
The practical bottleneck is the overlap correction \(C_3(n)\). Its exact worst-case count is awkward to state cleanly because it depends on several nested squarefree and coprimality constraints, but the implementation reduces it sharply through precomputed tables, squarefree filtering, and early stopping inequalities. Overall memory usage remains \(O(n)\), dominated by the arithmetic arrays up to \(n\).
Für eine Schranke \(n\) sollen alle verschiedenen reellen Werte von
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
gezählt werden, wobei \(y\) und \(z\) keine Quadratzahlen sind und der äußere Ausdruck sich in eine endliche vorzeichenbehaftete Summe einfacher Quadratwurzeln denesten lässt. Verschiedene Tripel \((x,y,z)\) können denselben reellen Wert erzeugen; dieser wird trotzdem nur einmal gezählt. Die Implementierungen berechnen diesen Wert für \(n=5{,}000{,}000\).
Das Programm zerlegt die denestbaren Werte in zwei Strukturfamilien. Die erste Familie besteht aus Denestings mit zwei einfachen Wurzeln. Die zweite Familie besteht aus Denestings mit vier einfachen Wurzeln und genau einem Minuszeichen. Am Ende werden beide Familien zusammengeführt, wobei diejenigen Vierwurzel-Fälle entfernt werden, die in Wahrheit schon zur Zweiwurzel-Familie gehören.
Sei \(F(n)\) die Anzahl aller verschiedenen denestbaren Werte mit ganzzahligem Teil \(x\le n\). Die Implementierung baut \(F(n)\) aus einem arithmetischen Kern \(f(s)\) und drei Zähltermen \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\) und \(C_3(n)\) auf.
Wir beginnen mit einem Wert der Form
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
Dann gilt
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
Ist \(\alpha\beta\) keine Quadratzahl, dann besitzt \(V^2\) genau eine irrationale Wurzelrichtung und passt in das geforderte Muster, denn
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
wobei \(k^2\alpha\beta\) ebenfalls keine Quadratzahl ist. Jedes primitive Paar \((\alpha,\beta)\) liefert also eine unendliche Skalierungsfamilie zulässiger Werte, und der ganzzahlige Teil ist
$$x=k(\alpha+\beta).$$
Für die feste primitive Summe
$$s=\alpha+\beta$$
gibt es genau
$$\left\lfloor\frac{n}{s}\right\rfloor$$
zulässige Skalierungen \(k\).
Für festes \(s\ge 3\) fragen wir: Wie viele primitive Paare \((\alpha,\beta)\) mit \(\alpha+\beta=s\) gehören zur ersten Familie?
Die Anzahl teilerfremder Zerlegungen \(s=\alpha+\beta\) mit \(\alpha \gt \beta \ge 1\) ist
$$\frac{\varphi(s)}{2},$$
denn jede reduzierte Restklasse modulo \(s\) entspricht einer teilerfremden Zerlegung, und durch Division durch \(2\) wird die Reihenfolge vergessen.
Nun entfernen wir die schlechten Fälle, in denen \(\alpha\beta\) eine Quadratzahl ist. Wegen \(\gcd(\alpha,\beta)=1\) passiert das genau dann, wenn
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
Die auszuschließenden Paare sind also genau die primitiven Darstellungen
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
Bezeichnet \(R(s)\) ihre Anzahl, so ist der in den Implementierungen verwendete Kern
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
Damit lautet der Gesamtbeitrag der Zweiwurzel-Familie
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
Die zweite Familie kombiniert zwei primitive Kerne. Man nehme zwei primitive Paare \((\alpha,\beta)\) und \((\gamma,\delta)\), die beide von \(f\) gezählt werden, und setze
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
Beim Quadrieren tritt eine entscheidende Auslöschung auf:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
Der gemischte Term mit \(\sqrt{\alpha\beta\gamma\delta}\) verschwindet wegen des Vorzeichenmusters. Übrig bleiben genau zwei Wurzelrichtungen, also ist \(W\) wieder ein Denesting der geforderten Form.
Schreiben wir
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
dann ist der ganzzahlige Teil von \(W^2\)
$$x=kst.$$
Somit trägt jedes geordnete Paar primitiver Kerne \((s,t)\)
$$\left\lfloor\frac{n}{st}\right\rfloor$$
skalierte Werte bei, und die geordnete Zählung ist
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
Die Kennzeichnung “ord” ist wichtig: Vertauscht man die beiden Kerne, ändert sich der Endwert nicht, daher zählt diese Summe die generische Vierwurzel-Konstruktion doppelt.
Nicht jede geordnete Vierwurzel-Konstruktion ist wirklich neu. Manche Fälle kollabieren auf nur zwei unabhängige quadratfreie Wurzelrichtungen und sind damit bereits in \(C_1(n)\) enthalten.
Schreibe die beiden primitiven Paare als
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
wobei \(\sigma_1,\sigma_2,\tau_1,\tau_2\) quadratfrei sind. Die vier Wurzeln in \(W\) besitzen dann die quadratfreien Kerne
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
Eine Überschneidung mit der Zweiwurzel-Familie tritt genau dann auf, wenn diese vier Produkte zu nur zwei verschiedenen quadratfreien Richtungen zusammenfallen. Die Implementierung parametrisiert solche Kollisionen durch quadratfreie, paarweise teilerfremde Faktoren \(\rho_1,\rho_2,\rho_3,\rho_4\) mit
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
Dann gilt
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
sowie
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
Der vermeintliche Vierwurzel-Ausdruck ist also in Wahrheit ein Zweiwurzel-Wert. Sei \(C_3(n)\) die Anzahl geordneter Konstruktionen genau dieser kollabierenden Art. Diese müssen vor der abschließenden Symmetrierung aus der geordneten Vierwurzel-Zählung entfernt werden.
Nach dem Abzug der kollabierenden geordneten Konstruktionen und dem Vergessen der Reihenfolge der beiden primitiven Kerne berechnen die Implementierungen
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
Genau diese Zerlegung steckt hinter den C++-, Python- und Java-Implementierungen.
Ein einfaches Zweiwurzel-Beispiel ist
$$V=\sqrt5+\sqrt2.$$
Dann ist
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
Der primitive Kern ist hier \(s=5+2=7\), und weil \(5\cdot2=10\) keine Quadratzahl ist, gehört dieser Wert zur ersten Familie. Jedes \(k\) mit \(7k\le n\) erzeugt einen weiteren gültigen Wert aus demselben Kern.
Ein echtes Vierwurzel-Beispiel verwendet \((\alpha,\beta)=(2,1)\) und \((\gamma,\delta)=(3,1)\):
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
Es gilt
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
Der ganzzahlige Teil ist also \(12=3\cdot4\). Genau deshalb wird die zweite Familie durch Produkte primitiver Kernsummen indiziert.
Die Implementierungen bauen zuerst ein Totientensieb bis \(n\) auf. Daraus initialisieren sie
$$f(s)=\frac{\varphi(s)}{2}$$
für \(s\ge 3\) und ziehen dann für jede primitive Darstellung \(s=u^2+v^2\) mit \(u \gt v\) und \(\gcd(u,v)=1\) eins ab. So entsteht die Kernfolge \(f(s)\).
Anschließend werden Präfixsummen von \(f\) gebildet. Die erste Familie \(C_1(n)\) ist dann eine direkte Divisorsumme. Der geordnete Term der zweiten Familie \(C_2^{\mathrm{ord}}(n)\) wird nicht durch eine quadratische Doppelschleife berechnet. Stattdessen gruppiert der Code gleiche Quotienten \(\left\lfloor n/i\right\rfloor\) in harmonische Intervalle und kombiniert diese Intervalle mit den Präfixsummen, sodass nur noch eine viel kleinere Anzahl von Blockauswertungen nötig ist.
Der Überlappungsterm \(C_3(n)\) wird separat behandelt. Dafür werden quadratfreie Markierungen, Teilerfremdheitstabellen und Quadrate bis \(\lfloor\sqrt n\rfloor\) vorab berechnet. Danach enumeriert der Code nur die Parameterkombinationen, die eine Vierwurzel-Konstruktion auf zwei quadratfreie Richtungen kollabieren lassen, und schneidet den Suchraum mit vielen frühen Ungleichungsabbrüchen stark zu. Die C++-Implementierung parallelisiert diesen teuren Überlappungsblock; die Python-Version bildet dieselbe Mathematik direkter nach, und die Java-Version verwendet dieselbe optimierte Kernberechnung weiter.
Totientensieb und Aufbau des Kerns \(f\) benötigen \(O(n\log\log n)\) Zeit und \(O(n)\) Speicher. Die Summe der ersten Familie \(C_1(n)\) kostet \(O(n)\). Die geordnete Faltung \(C_2^{\mathrm{ord}}(n)\) wird durch harmonische Blockung und Präfixsummen stark beschleunigt; die Implementierung vermeidet damit die naive quadratische Doppelschleife und arbeitet stattdessen mit einer subquadratischen Anzahl von Quotientenblöcken.
Der praktische Engpass ist die Überlappungskorrektur \(C_3(n)\). Eine saubere geschlossene Worst-Case-Formel ist hier unhandlich, weil mehrere geschachtelte quadratfreie und teilerfremde Bedingungen zusammenwirken. Die Implementierung drückt die Kosten jedoch deutlich durch Vorberechnungstabellen, quadratfreie Filter und frühe Abbruchbedingungen. Insgesamt bleibt der Speicherverbrauch \(O(n)\), dominiert von den arithmetischen Feldern bis \(n\).
Verilen \(n\) sınırı için
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
biçimindeki farklı gerçek değerlerin sayısı istenir. Burada \(y\) ve \(z\) tam kare değildir ve dıştaki kök, işaretli sonlu bir basit karekök toplamına ayrıştırılabilmelidir. Farklı \((x,y,z)\) üçlüleri aynı gerçek sayıyı verebilir; böyle durumlarda o değer yalnızca bir kez sayılır. Uygulamalar bu sayıyı \(n=5{,}000{,}000\) için hesaplar.
Program denestable değerleri iki yapısal aileye ayırır. Birinci aile iki basit kökten gelen ayrıştırmalardır. İkinci aile dört basit kökten ve tek bir eksi işaretinden gelir. Son adımda iki aile birleştirilir ve aslında birinci aileye düşen dört köklü çakışmalar çıkarılır.
\(x\le n\) koşulunu sağlayan farklı denestable değerlerin sayısını \(F(n)\) ile gösterelim. Uygulama bunu aritmetik bir çekirdek dizi \(f(s)\) ve üç sayım terimi \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\), \(C_3(n)\) üzerinden kurar.
Şu biçimde bir değer alalım:
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
Karesi
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}$$
olur. Eğer \(\alpha\beta\) tam kare değilse, \(V^2\) tam olarak tek bir irrasyonel karekök yönüne sahiptir ve istenen biçime uyar; çünkü
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta}$$
yazılabilir ve \(k^2\alpha\beta\) yine tam kare değildir. Böylece her asal iskeletli \((\alpha,\beta)\) çifti sonsuz bir ölçekleme ailesi üretir. Tamsayı kısmı
$$x=k(\alpha+\beta)$$
olur. Sabit
$$s=\alpha+\beta$$
için uygun ölçek sayısı
$$\left\lfloor\frac{n}{s}\right\rfloor$$
kadardır.
Sabit \(s\ge 3\) için, \(\alpha+\beta=s\) koşulunu sağlayan kaç asal iskeletli çift birinci aileye aittir?
\(\alpha \gt \beta \ge 1\) ve \(\gcd(\alpha,\beta)=1\) olan ayrışımların sayısı
$$\frac{\varphi(s)}{2}$$
olur. Bunun nedeni, mod \(s\) altında indirgenmiş artık sınıflarının teker teker aralarında asal parçalanmalara karşılık gelmesi ve sıralamanın unutulması için \(2\)'ye bölünmesidir.
Şimdi \(\alpha\beta\)'nin tam kare olduğu kötü durumları çıkarmamız gerekir. \(\gcd(\alpha,\beta)=1\) olduğundan bu ancak
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1$$
iken mümkündür. Yani çıkarılacak çiftler tam olarak
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1$$
biçimindeki ilkel iki-kare toplamlarıdır. Bunların sayısını \(R(s)\) ile gösterirsek, uygulamanın kullandığı çekirdek
$$f(s)=\frac{\varphi(s)}{2}-R(s)$$
olur. Böylece birinci ailenin toplam katkısı
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor$$
şeklindedir.
İkinci aile iki ilkel çekirdeği birleştirir. \(f\) tarafından sayılan iki çift \((\alpha,\beta)\) ve \((\gamma,\delta)\) seçip
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}$$
ifadesini kuralım. Karesi açılınca kritik bir sadeleşme olur:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
\(\sqrt{\alpha\beta\gamma\delta}\) içeren karışık terim işaret yapısı yüzünden yok olur. Geriye tam olarak iki karekök yönü kaldığı için \(W\) yine istenen biçimde bir ayrıştırmadır.
Şöyle yazalım:
$$s=\alpha+\beta,\qquad t=\gamma+\delta.$$
O zaman \(W^2\)'nin tamsayı kısmı
$$x=kst$$
olur. Dolayısıyla her sıralı ilkel çekirdek çifti \((s,t)\)
$$\left\lfloor\frac{n}{st}\right\rfloor$$
ölçekli değer üretir ve sıralı sayım
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor$$
olur. Buradaki “ord” önemlidir; iki çekirdeğin yerini değiştirmek son sayıyı değiştirmez, yani bu toplam genel durumda aynı değeri iki kez sayar.
Her sıralı dört-kök yapısı gerçekten yeni değildir. Bazıları yalnızca iki bağımsız kare çarpansız kök yönüne indirgenir ve zaten \(C_1(n)\) içinde yer alır.
İki ilkel çifti
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2$$
şeklinde yazalım; burada \(\sigma_1,\sigma_2,\tau_1,\tau_2\) kare çarpansız çekirdeklerdir. \(W\) içindeki dört kökün kare çarpansız parçaları
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2$$
olur. Bu dört çarpım yalnızca iki ayrı kare çarpansız yöne düştüğünde, değer birinci aile ile çakışır. Uygulama bu çakışmaları kare çarpansız ve çifter çifter aralarında asal \(\rho_1,\rho_2,\rho_3,\rho_4\) üzerinden
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4$$
parametrizasyonuyla yakalar. Böylece
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3}$$
ve ayrıca
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}$$
elde edilir. Yani görünüşte dört köklü olan ifade gerçekte iki köklü bir değerdir. Tam bu tür sıralı yapıları sayan düzeltme terimine \(C_3(n)\) denir. Son simetri düzeltmesinden önce bunların çıkarılması gerekir.
İki köke çöken sıralı yapıları çıkardıktan ve iki ilkel çekirdeğin sırasını unuttuktan sonra uygulama
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
formülünü hesaplar. C++, Python ve Java çözümlerinin ortak matematiksel omurgası budur.
Basit bir iki-kök örneği
$$V=\sqrt5+\sqrt2$$
ifadesidir. Bunun karesi
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}$$
olur. Burada ilkel çekirdek \(s=5+2=7\)'dir ve \(5\cdot2=10\) tam kare olmadığı için bu değer birinci aileye aittir. \(7k\le n\) koşulunu sağlayan her \(k\), aynı çekirdekten yeni bir değer üretir.
Gerçek bir dört-kök örneği olarak \((\alpha,\beta)=(2,1)\) ve \((\gamma,\delta)=(3,1)\) alınabilir:
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
Bunun karesi
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2$$
şeklindedir. Tamsayı kısmının \(12=3\cdot4\) olması, neden ikinci ailenin ilkel çekirdek toplamlarının çarpımıyla indekslendiğini açıkça gösterir.
Uygulamalar önce \(n\)'e kadar Euler totient dizisini kurar. Bu diziden
$$f(s)=\frac{\varphi(s)}{2}$$
başlangıcı oluşturulur ve \(u \gt v\), \(\gcd(u,v)=1\) koşullarıyla her ilkel \(s=u^2+v^2\) temsili için bir azaltım yapılır. Böylece çekirdek dizi \(f(s)\) elde edilir.
Sonra \(f\)'nin önek toplamları hesaplanır. Birinci aile \(C_1(n)\) doğrudan bölen tipi bir toplamdır. İkinci ailenin sıralı terimi \(C_2^{\mathrm{ord}}(n)\) ise kaba kuvvetle ikili döngüyle hesaplanmaz. Bunun yerine \(\left\lfloor n/i\right\rfloor\) değeri sabit kalan aralıklar harmonik bloklar halinde gruplanır ve bu bloklar önek toplamlarla birleştirilir. Böylece konvolüsyon çok daha az sayıda blok hesabına iner.
Çakışma düzeltmesi \(C_3(n)\) ayrı ele alınır. Kod, \(\lfloor\sqrt n\rfloor\)'ye kadar kare çarpansızlık işaretlerini, aralarında asallık tablolarını ve kareleri önceden üretir. Ardından yalnızca dört-kök yapısını iki kare çarpansız yöne çöktürebilecek parametreleri dener ve çok sayıda eşitsizlik tabanlı erken kesme ile aramayı budar. C++ uygulaması bu pahalı bölümü paralelleştirir; Python sürümü aynı matematiği daha doğrudan izler; Java sürümü ise aynı optimize çekirdeği yeniden kullanır.
Totient eleği ve \(f\) çekirdeğinin kurulması \(O(n\log\log n)\) zaman ve \(O(n)\) bellek gerektirir. Birinci aile toplamı \(C_1(n)\) için maliyet \(O(n)\)'dir. Sıralı konvolüsyon \(C_2^{\mathrm{ord}}(n)\), harmonik bloklama ve önek toplamlar sayesinde hızlandırılır; böylece saf \(O(n^2)\) ikili döngüden kaçınılır ve yerine alt-kuadratik sayıda bölüm bloğu işlenir.
Pratik darboğaz \(C_3(n)\) düzeltmesidir. En kötü durum için tek satırlık temiz bir üst sınır vermek zordur; çünkü iç içe kare çarpansızlık ve aralarında asallık koşulları vardır. Buna rağmen önceden hazırlanmış tablolar, kare çarpansız filtreler ve erken durdurma eşitsizlikleri maliyeti ciddi biçimde azaltır. Toplam bellek kullanımı \(n\)'e kadar tutulan aritmetik diziler tarafından belirlendiği için \(O(n)\) düzeyinde kalır.
Para un límite \(n\), se cuentan los valores reales distintos de
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
donde \(y\) y \(z\) no son cuadrados perfectos y la raíz exterior puede desanidarse como una suma finita con signos de raíces cuadradas simples. Distintos tríos \((x,y,z)\) pueden producir el mismo número real; en ese caso ese valor se cuenta una sola vez. Las implementaciones evalúan esta cantidad en \(n=5{,}000{,}000\).
El programa organiza los valores desanidables en dos familias estructurales. La primera proviene de desanidaciones con dos raíces simples. La segunda proviene de desanidaciones con cuatro raíces simples y un único signo negativo. Al final se combinan ambas familias y se eliminan los casos de cuatro raíces que en realidad ya pertenecían a la familia de dos raíces.
Sea \(F(n)\) el número de valores desanidables distintos con parte entera \(x\le n\). La implementación construye \(F(n)\) a partir de un núcleo aritmético \(f(s)\) y de tres términos de conteo \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\) y \(C_3(n)\).
Partimos de un valor de la forma
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
Al cuadrarlo se obtiene
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
Si \(\alpha\beta\) no es un cuadrado, entonces \(V^2\) tiene exactamente una dirección irracional y encaja en la forma pedida, porque
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
y \(k^2\alpha\beta\) sigue siendo no cuadrado. Por tanto, cada pareja primitiva \((\alpha,\beta)\) produce una familia infinita de escalados admisibles, y la parte entera vale
$$x=k(\alpha+\beta).$$
Si fijamos
$$s=\alpha+\beta,$$
el factor de escala \(k\) puede elegirse de
$$\left\lfloor\frac{n}{s}\right\rfloor$$
formas.
Para un \(s\ge 3\) fijo, ¿cuántas parejas primitivas \((\alpha,\beta)\) con \(\alpha+\beta=s\) pertenecen a la primera familia?
El número de descomposiciones coprimas \(s=\alpha+\beta\) con \(\alpha \gt \beta \ge 1\) es
$$\frac{\varphi(s)}{2},$$
porque cada clase residual reducida módulo \(s\) corresponde a una partición coprima, y dividir por \(2\) elimina el orden.
Ahora hay que quitar los casos malos en los que \(\alpha\beta\) es cuadrado. Como \(\gcd(\alpha,\beta)=1\), eso ocurre exactamente cuando
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
Así, los pares excluidos son precisamente las representaciones primitivas
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
Si \(R(s)\) cuenta esas representaciones primitivas como suma de dos cuadrados, entonces el núcleo usado por las implementaciones es
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
La contribución total de la familia de dos raíces queda
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
La segunda familia combina dos núcleos primitivos. Tomemos dos parejas primitivas \((\alpha,\beta)\) y \((\gamma,\delta)\), ambas contadas por \(f\), y definamos
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
Al expandir \(W^2\) aparece una cancelación clave:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
El término mezclado con \(\sqrt{\alpha\beta\gamma\delta}\) desaparece por el patrón de signos. Quedan exactamente dos direcciones radicales, así que \(W\) vuelve a ser una desanidación de la forma requerida.
Si escribimos
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
entonces la parte entera de \(W^2\) es
$$x=kst.$$
Por tanto, cada par ordenado de núcleos primitivos \((s,t)\) aporta
$$\left\lfloor\frac{n}{st}\right\rfloor$$
valores escalados, y el conteo ordenado es
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
El superíndice “ord” importa porque intercambiar los dos núcleos no cambia el valor final; en general esa suma cuenta dos veces la misma construcción de cuatro raíces.
No toda construcción ordenada de cuatro raíces es realmente nueva. Algunas colapsan a solo dos radicales cuadrados libres independientes y, por tanto, ya estaban contadas en \(C_1(n)\).
Escribamos las parejas primitivas como
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
donde \(\sigma_1,\sigma_2,\tau_1,\tau_2\) son partes libres de cuadrados. Las cuatro raíces de \(W\) tienen entonces partes libres de cuadrados
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
Hay colisión con la familia de dos raíces exactamente cuando estos cuatro productos se reducen a solo dos direcciones libres de cuadrados distintas. La implementación parametriza esas colisiones mediante factores \(\rho_1,\rho_2,\rho_3,\rho_4\) libres de cuadrados y coprimos dos a dos, tales que
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
Entonces
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
y también
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
Así, una expresión aparentemente de cuatro raíces es en realidad un valor de dos raíces. Denotemos por \(C_3(n)\) el número de construcciones ordenadas de este tipo colapsado. Hay que restarlas del conteo ordenado antes de aplicar el factor final de simetría.
Después de quitar las construcciones ordenadas que colapsan y de olvidar el orden de los dos núcleos primitivos, las implementaciones calculan
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
Esa es exactamente la descomposición que siguen las implementaciones en C++, Python y Java.
Un ejemplo simple de dos raíces es
$$V=\sqrt5+\sqrt2.$$
Entonces
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
Aquí el núcleo primitivo es \(s=5+2=7\), y como \(5\cdot2=10\) no es cuadrado, ese valor pertenece a la primera familia. Todo \(k\) con \(7k\le n\) produce otro valor válido procedente del mismo núcleo.
Un ejemplo genuino de cuatro raíces toma \((\alpha,\beta)=(2,1)\) y \((\gamma,\delta)=(3,1)\):
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
Su cuadrado es
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
La parte entera vale \(12=3\cdot4\), y eso muestra por qué la segunda familia queda indexada por productos de sumas primitivas.
Las implementaciones primero construyen una criba de totientes hasta \(n\). A partir de esa tabla inicializan
$$f(s)=\frac{\varphi(s)}{2}$$
para \(s\ge 3\), y después restan uno por cada representación primitiva \(s=u^2+v^2\) con \(u \gt v\) y \(\gcd(u,v)=1\). Así se obtiene la secuencia núcleo \(f(s)\).
Luego se forman sumas prefijo de \(f\). La primera familia \(C_1(n)\) se evalúa con una suma directa de tipo divisor. El término ordenado de la segunda familia \(C_2^{\mathrm{ord}}(n)\) no se calcula con un doble bucle cuadrático. En su lugar, el código agrupa los valores iguales de \(\left\lfloor n/i\right\rfloor\) en bloques armónicos y los combina con las sumas prefijo, reduciendo la convolución a un número mucho menor de bloques.
El término de solapamiento \(C_3(n)\) se trata aparte. El código precomputa marcas de enteros libres de cuadrados, tablas de coprimalidad y cuadrados hasta \(\lfloor\sqrt n\rfloor\). Después enumera solo las combinaciones de parámetros capaces de hacer que una construcción de cuatro raíces colapse a dos direcciones libres de cuadrados, usando muchas desigualdades de corte temprano para podar la búsqueda. La implementación en C++ paraleliza esta fase costosa; la versión en Python sigue la misma matemática de manera más directa; y la versión en Java reutiliza el mismo núcleo optimizado.
Construir la criba de totientes y el núcleo \(f\) requiere \(O(n\log\log n)\) tiempo y \(O(n)\) memoria. La suma de la primera familia \(C_1(n)\) cuesta \(O(n)\). La convolución ordenada \(C_2^{\mathrm{ord}}(n)\) se acelera con bloques armónicos y sumas prefijo, de modo que el programa evita el doble bucle ingenuo \(O(n^2)\) y trabaja con un número subcuadrático de bloques de cociente.
El cuello de botella práctico es la corrección de solapes \(C_3(n)\). Dar un peor caso cerrado y limpio es incómodo, porque intervienen varias restricciones anidadas de coprimalidad y de enteros libres de cuadrados. Aun así, la implementación reduce mucho ese coste gracias a las tablas precomputadas, al filtrado squarefree y a las desigualdades de parada temprana. El uso total de memoria se mantiene en \(O(n)\), dominado por los arreglos aritméticos de longitud \(n\).
给定上界 \(n\)，我们要统计所有不同的实数值
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
其中 \(y\) 与 \(z\) 都不是完全平方数，并且外层根式能够去嵌套为有限个带符号的简单平方根之和。不同的 \((x,y,z)\) 三元组可能表示同一个实数，但这个实数只能计数一次。实现最终计算的是 \(n=5{,}000{,}000\) 时的结果。
程序把所有可去嵌套的值分成两类结构。第一类来自只有两个简单平方根的去嵌套形式。第二类来自四个简单平方根、且恰好带一个负号的去嵌套形式。最后把这两类合并，并删去那些表面上属于四根式、实际上已经落入两根式计数中的重合项。
记 \(F(n)\) 为满足整数部分 \(x\le n\) 的不同可去嵌套值的个数。实现将 \(F(n)\) 分解为一个算术核函数 \(f(s)\) 以及三个计数项 \(C_1(n)\)、\(C_2^{\mathrm{ord}}(n)\)、\(C_3(n)\)。
先看形如
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1$$
的值。平方后得到
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
如果 \(\alpha\beta\) 不是平方数，那么 \(V^2\) 只有一个无理平方根方向，而且可以写成题目要求的形式，因为
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
并且 \(k^2\alpha\beta\) 仍然不是平方数。因此，每个原始配对 \((\alpha,\beta)\) 都生成一个按比例放大的合法家族，其整数部分为
$$x=k(\alpha+\beta).$$
若固定
$$s=\alpha+\beta,$$
那么满足条件的比例因子 \(k\) 一共有
$$\left\lfloor\frac{n}{s}\right\rfloor$$
个。
对于固定的 \(s\ge 3\)，有多少个满足 \(\alpha+\beta=s\) 的原始配对 \((\alpha,\beta)\) 属于第一类？
满足 \(\alpha \gt \beta \ge 1\) 且 \(\gcd(\alpha,\beta)=1\) 的互素拆分个数是
$$\frac{\varphi(s)}{2},$$
因为模 \(s\) 的每个既约剩余类对应一个互素拆分，而除以 \(2\) 正好去掉顺序。
接着要减去坏情况，即 \(\alpha\beta\) 本身是平方数的情形。由于 \(\gcd(\alpha,\beta)=1\)，这等价于
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
因此被排除的配对正好对应原始表示
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
若记这类原始两平方和表示的个数为 \(R(s)\)，则实现中使用的核函数为
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
于是两根式家族的总贡献为
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
第二类把两个原始核组合起来。取两个都被 \(f\) 计数的原始配对 \((\alpha,\beta)\) 和 \((\gamma,\delta)\)，定义
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
展开 \(W^2\) 时会出现关键消去：
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
本来可能出现的 \(\sqrt{\alpha\beta\gamma\delta}\) 混合项，因为符号结构而完全抵消。这样就只剩下两个平方根方向，所以 \(W\) 也是题目要求的去嵌套形式。
若记
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
则 \(W^2\) 的整数部分就是
$$x=kst.$$
因此每个有序原始核对 \((s,t)\) 会贡献
$$\left\lfloor\frac{n}{st}\right\rfloor$$
个按比例放大的值，有序计数为
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
这里的上标 “ord” 很重要，因为交换两个核并不会改变最终数值，所以这个和式在一般情况下会把同一个四根式值数两次。
并不是每个有序四根式构造都会产生真正的新值。有些构造最终只剩下两个独立的平方因子自由方向，因此这些值其实已经在 \(C_1(n)\) 中被统计过了。
把两个原始配对写成
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
其中 \(\sigma_1,\sigma_2,\tau_1,\tau_2\) 都是平方因子自由部分。则 \(W\) 中四个根号对应的平方因子自由核分别是
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
当这四个乘积只合并成两个不同的平方因子自由方向时，就会与两根式家族重合。实现使用平方因子自由且两两互素的 \(\rho_1,\rho_2,\rho_3,\rho_4\) 来参数化这种重合，其中
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
于是有
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
以及
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
这样一来，原本看似有四个方向的表达式实际上只落在两个平方因子自由方向上，也就是一个两根式值。记 \(C_3(n)\) 为这种塌缩型有序构造的总数。在做最后的对称性除以 \(2\) 之前，必须先把这些情况从有序四根式计数中扣掉。
去掉会塌缩的有序四根式，并且忽略两个原始核的顺序之后，程序计算的是
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
这正是 C++、Python 和 Java 实现共同遵循的数学分解。
一个简单的两根式例子是
$$V=\sqrt5+\sqrt2.$$
那么
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
这里的原始核是 \(s=5+2=7\)，而 \(5\cdot2=10\) 不是平方数，所以这个值属于第一类。所有满足 \(7k\le n\) 的 \(k\) 都会从这个核产生新的合法值。
一个真正的四根式例子取 \((\alpha,\beta)=(2,1)\) 与 \((\gamma,\delta)=(3,1)\)：
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
它的平方为
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
整数部分恰好是 \(12=3\cdot4\)，这正说明第二类为什么要用两个原始核和的乘积来索引。
实现首先构造到 \(n\) 为止的欧拉函数筛。然后据此初始化
$$f(s)=\frac{\varphi(s)}{2}$$
对所有 \(s\ge 3\) 成立；接着对每个原始表示 \(s=u^2+v^2\) 且 \(u \gt v\)、\(\gcd(u,v)=1\) 的情况减去 \(1\)，从而得到核序列 \(f(s)\)。
之后程序构造 \(f\) 的前缀和。第一类 \(C_1(n)\) 是直接的除数型求和。第二类的有序项 \(C_2^{\mathrm{ord}}(n)\) 并不采用朴素的二重循环，而是把 \(\left\lfloor n/i\right\rfloor\) 相同的区间合并成调和分块，再配合前缀和完成块求和，从而把卷积运算压缩成远少于 \(n^2\) 次的区间处理。
重合修正 \(C_3(n)\) 单独处理。代码预先计算平方因子自由标记、互素查表以及到 \(\lfloor\sqrt n\rfloor\) 的平方数。随后只枚举那些可能把四根式压缩成两个平方因子自由方向的参数组合，并用大量不等式提前停止来剪枝。C++ 实现对这部分高开销枚举进行了并行化；Python 版本更直接地复现同样的数学；Java 版本则复用同一套优化后的核心计算。
构造欧拉函数筛和核函数 \(f\) 需要 \(O(n\log\log n)\) 时间与 \(O(n)\) 内存。第一类求和 \(C_1(n)\) 的代价是 \(O(n)\)。有序卷积 \(C_2^{\mathrm{ord}}(n)\) 借助调和分块与前缀和避免了朴素 \(O(n^2)\) 双循环，因此只需处理一个次二次规模的商值分块集合。
实际运行中的瓶颈是重合修正 \(C_3(n)\)。由于里面叠加了多层平方因子自由限制和互素限制，很难写出一个既简洁又紧的最坏情况公式。不过实现通过预计算表、平方因子自由过滤以及提前终止不等式，大幅压低了这部分代价。总体内存仍为 \(O(n)\)，主要由长度到 \(n\) 的算术数组占据。
Для заданной границы \(n\) нужно посчитать все различные действительные значения вида
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
где \(y\) и \(z\) не являются квадратами, а внешний корень допускает денестинг в конечную знаковую сумму простых квадратных корней. Разные тройки \((x,y,z)\) могут задавать одно и то же число, но такое число учитывается только один раз. Реализации вычисляют это количество при \(n=5{,}000{,}000\).
Программа разбивает денестируемые значения на две структурные семьи. Первая семья состоит из представлений с двумя простыми корнями. Вторая семья состоит из представлений с четырьмя простыми корнями и одним минусом. В конце обе семьи объединяются, а затем удаляются те четырёхкорневые случаи, которые на самом деле уже входят в двухкорневой счёт.
Обозначим через \(F(n)\) число различных денестируемых значений с целой частью \(x\le n\). Реализация строит \(F(n)\) из арифметического ядра \(f(s)\) и трёх счётных членов \(C_1(n)\), \(C_2^{\mathrm{ord}}(n)\) и \(C_3(n)\).
Рассмотрим значение вида
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
Тогда
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
Если \(\alpha\beta\) не является квадратом, то у \(V^2\) остаётся ровно одно иррациональное корневое направление, и выражение укладывается в требуемый шаблон, потому что
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
а \(k^2\alpha\beta\) тоже не квадрат. Значит, каждая примитивная пара \((\alpha,\beta)\) порождает бесконечное семейство допустимых масштабирований, а целая часть равна
$$x=k(\alpha+\beta).$$
Если положить
$$s=\alpha+\beta,$$
то множитель \(k\) можно выбрать ровно
$$\left\lfloor\frac{n}{s}\right\rfloor$$
способами.
Для фиксированного \(s\ge 3\) нужно понять, сколько примитивных пар \((\alpha,\beta)\) с \(\alpha+\beta=s\) попадает в первую семью.
Число взаимно простых разложений \(s=\alpha+\beta\) при \(\alpha \gt \beta \ge 1\) равно
$$\frac{\varphi(s)}{2},$$
потому что каждый приведённый класс по модулю \(s\) задаёт одно взаимно простое разбиение, а деление на \(2\) убирает учёт порядка.
Теперь нужно исключить плохие случаи, когда \(\alpha\beta\) является квадратом. Из условия \(\gcd(\alpha,\beta)=1\) следует, что это эквивалентно
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
Значит, исключаемые пары в точности соответствуют примитивным представлениям
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
Если \(R(s)\) обозначает число таких примитивных представлений как суммы двух квадратов, то используемое в реализации ядро равно
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
Тогда полный вклад двухкорневой семьи равен
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
Вторая семья комбинирует два примитивных ядра. Возьмём две примитивные пары \((\alpha,\beta)\) и \((\gamma,\delta)\), обе учитываемые функцией \(f\), и определим
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
При возведении в квадрат происходит ключевое сокращение:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
Смешанный член с \(\sqrt{\alpha\beta\gamma\delta}\) исчезает из-за выбранного знакового шаблона. Остаются ровно два корневых направления, поэтому \(W\) тоже задаёт допустимый денестинг.
Если обозначить
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
то целая часть \(W^2\) равна
$$x=kst.$$
Следовательно, каждая упорядоченная пара примитивных ядер \((s,t)\) даёт
$$\left\lfloor\frac{n}{st}\right\rfloor$$
масштабированных значений, а упорядоченный счёт имеет вид
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
Индекс “ord” важен: перестановка двух ядер не меняет итоговое значение, поэтому эта сумма в общем случае считает каждую четырёхкорневую конструкцию дважды.
Не всякая упорядоченная четырёхкорневая конструкция даёт новое значение. Некоторые случаи сводятся всего к двум независимым квадратно-свободным направлениям и уже входят в \(C_1(n)\).
Запишем примитивные пары в виде
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
где \(\sigma_1,\sigma_2,\tau_1,\tau_2\) квадратно-свободны. Тогда четыре корня внутри \(W\) имеют квадратно-свободные части
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
Перекрытие с двухкорневой семьёй возникает ровно тогда, когда эти четыре произведения сливаются только в два различных квадратно-свободных направления. Реализация параметризует такие столкновения квадратно-свободными попарно взаимно простыми множителями \(\rho_1,\rho_2,\rho_3,\rho_4\), для которых
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
Тогда
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
а также
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
Следовательно, выражение, которое выглядело четырёхкорневым, на самом деле лежит всего в двух квадратно-свободных направлениях, то есть уже является двухкорневым значением. Обозначим через \(C_3(n)\) число упорядоченных конструкций именно такого схлопывающегося типа. Их нужно вычесть до применения конечного деления на \(2\).
После удаления схлопывающихся упорядоченных конструкций и после забывания порядка двух примитивных ядер реализации вычисляют
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
Именно эта формула лежит в основе реализаций на C++, Python и Java.
Простой двухкорневой пример:
$$V=\sqrt5+\sqrt2.$$
Тогда
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
Здесь примитивное ядро равно \(s=5+2=7\), а произведение \(5\cdot2=10\) не является квадратом, поэтому значение относится к первой семье. Любое \(k\), удовлетворяющее \(7k\le n\), даёт ещё одно допустимое значение из того же ядра.
Настоящий четырёхкорневой пример получается при \((\alpha,\beta)=(2,1)\) и \((\gamma,\delta)=(3,1)\):
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
Его квадрат равен
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
Целая часть здесь равна \(12=3\cdot4\), и это прямо показывает, почему вторая семья индексируется произведениями примитивных сумм.
Сначала реализации строят решето значений функции Эйлера до \(n\). Затем по этой таблице инициализируется
$$f(s)=\frac{\varphi(s)}{2}$$
для \(s\ge 3\), после чего из него вычитается единица для каждого примитивного представления \(s=u^2+v^2\) с \(u \gt v\) и \(\gcd(u,v)=1\). Так получается ядро \(f(s)\).
Далее строятся префиксные суммы этой последовательности. Первая семья \(C_1(n)\) считается прямой суммой делительного типа. Упорядоченный член второй семьи \(C_2^{\mathrm{ord}}(n)\) не вычисляется наивным двойным циклом. Вместо этого код группирует одинаковые значения \(\left\lfloor n/i\right\rfloor\) в гармонические интервалы и объединяет эти интервалы с префиксными суммами, резко уменьшая число реально вычисляемых блоков.
Член перекрытия \(C_3(n)\) считается отдельно. Код заранее помечает квадратно-свободные числа, строит таблицы взаимной простоты и массив квадратов до \(\lfloor\sqrt n\rfloor\). После этого перебираются только те комбинации параметров, которые могут заставить четырёхкорневую конструкцию схлопнуться в два квадратно-свободных направления; поиск дополнительно режется множеством ранних остановок по неравенствам. Реализация на C++ распараллеливает этот дорогой этап; версия на Python повторяет ту же математику более прямолинейно; версия на Java использует то же оптимизированное ядро вычисления.
Построение решета функции Эйлера и ядра \(f\) требует \(O(n\log\log n)\) времени и \(O(n)\) памяти. Сумма первой семьи \(C_1(n)\) имеет стоимость \(O(n)\). Упорядоченная свёртка \(C_2^{\mathrm{ord}}(n)\) ускоряется гармоническими блоками и префиксными суммами, так что реализация избегает наивного \(O(n^2)\) двойного цикла и работает с субквадратичным числом блоков одинаковых частных.
Практическое узкое место - это поправка перекрытий \(C_3(n)\). Её аккуратную замкнутую оценку в худшем случае неудобно писать, потому что там вложены несколько ограничений на квадратно-свободность и взаимную простоту. Тем не менее код резко сокращает стоимость за счёт предвычисленных таблиц, фильтрации по квадратно-свободным частям и ранних остановок. Общая память остаётся \(O(n)\) и в основном определяется арифметическими массивами длины \(n\).
لحدٍّ معيّن \(n\)، نريد عدّ القيم الحقيقية المختلفة للتعبير
$$\sqrt{x+\sqrt y+\sqrt z},\qquad 0 \lt x \le n,$$
بحيث يكون \(y\) و\(z\) غير مربعين كاملين، ويمكن فكّ الجذر الخارجي إلى مجموع ذي إشارات من عدد من الجذور التربيعية البسيطة. قد تعطي ثلاثيات مختلفة \((x,y,z)\) القيمة الحقيقية نفسها، لكن تلك القيمة تُحسب مرة واحدة فقط. تقوم التطبيقات بحساب هذه الكمية عند \(n=5{,}000{,}000\).
يقسّم البرنامج القيم القابلة لفكّ التعشيش إلى عائلتين بنيويتين. العائلة الأولى تأتي من صيغ تحتوي على جذرين بسيطين فقط. والعائلة الثانية تأتي من صيغ تحتوي على أربعة جذور بسيطة مع إشارة سالبة واحدة. وفي النهاية تُجمع العائلتان ثم تُحذف الحالات الرباعية التي كانت في الحقيقة محسوبة سابقًا داخل العائلة الثنائية.
لنرمز بـ \(F(n)\) إلى عدد القيم المختلفة القابلة لفكّ التعشيش التي تحقق \(x\le n\). تبني الشيفرات \(F(n)\) انطلاقًا من نواة حسابية \(f(s)\) وثلاثة حدود عدّ هي \(C_1(n)\) و\(C_2^{\mathrm{ord}}(n)\) و\(C_3(n)\).
لنأخذ قيمة من الشكل
$$V=\sqrt{k\alpha}+\sqrt{k\beta},\qquad \alpha \gt \beta \ge 1,\qquad \gcd(\alpha,\beta)=1,\qquad k\ge 1.$$
بتربيعها نحصل على
$$V^2=k(\alpha+\beta)+2k\sqrt{\alpha\beta}.$$
إذا لم يكن \(\alpha\beta\) مربعًا، فإن \(V^2\) يحتوي على اتجاه جذري لاعقلاني واحد فقط، ويطابق الصيغة المطلوبة لأن
$$2k\sqrt{\alpha\beta}=\sqrt{k^2\alpha\beta}+\sqrt{k^2\alpha\beta},$$
ومقدار \(k^2\alpha\beta\) يبقى غير مربع. لذلك فإن كل زوج أولي \((\alpha,\beta)\) يولّد عائلة لانهائية من القيم بعد التمديد، ويكون الجزء الصحيح
$$x=k(\alpha+\beta).$$
وعند تثبيت
$$s=\alpha+\beta,$$
فإن عدد اختيارات \(k\) الممكنة هو
$$\left\lfloor\frac{n}{s}\right\rfloor.$$
عند تثبيت \(s\ge 3\)، كم عدد الأزواج الأولية \((\alpha,\beta)\) التي تحقق \(\alpha+\beta=s\) وتنتمي إلى العائلة الأولى؟
عدد التفكيكات المتباينة أوليًا \(s=\alpha+\beta\) مع \(\alpha \gt \beta \ge 1\) يساوي
$$\frac{\varphi(s)}{2},$$
لأن كل فئة باقية مختزلة بترديد \(s\) تعطي تفكيكًا متباينًا أوليًا، والقسمة على \(2\) تزيل أثر الترتيب.
الآن يجب حذف الحالات السيئة التي يكون فيها \(\alpha\beta\) مربعًا. وبما أن \(\gcd(\alpha,\beta)=1\)، فإن ذلك يحدث بالضبط عندما
$$\alpha=u^2,\qquad \beta=v^2,\qquad \gcd(u,v)=1.$$
إذًا الأزواج المستبعدة هي تمامًا التمثيلات الأولية
$$s=u^2+v^2,\qquad u \gt v \ge 1,\qquad \gcd(u,v)=1.$$
إذا كان \(R(s)\) يعدّ هذه التمثيلات الأولية كمجموع مربعين، فإن النواة المستخدمة في التنفيذ هي
$$f(s)=\frac{\varphi(s)}{2}-R(s).$$
ومن ثم يكون إسهام العائلة الثنائية كلها
$$C_1(n)=\sum_{s\le n} f(s)\left\lfloor\frac{n}{s}\right\rfloor.$$
العائلة الثانية تدمج نواتين أوليتين. نأخذ زوجين أوليين \((\alpha,\beta)\) و\((\gamma,\delta)\) كلاهما معدودان بواسطة \(f\)، ثم نكوّن
$$W=\sqrt{k\alpha\gamma}+\sqrt{k\alpha\delta}+\sqrt{k\beta\gamma}-\sqrt{k\beta\delta}.$$
عند توسيع \(W^2\) يحدث إلغاء جوهري:
$$W^2=k(\alpha+\beta)(\gamma+\delta)+2k(\alpha-\beta)\sqrt{\gamma\delta}+2k(\gamma-\delta)\sqrt{\alpha\beta}.$$
الحد المختلط الذي يحتوي على \(\sqrt{\alpha\beta\gamma\delta}\) يختفي بسبب نمط الإشارات. وهكذا يبقى اتجاهان جذريان فقط، فيكون \(W\) أيضًا من الشكل القابل لفكّ التعشيش المطلوب.
إذا كتبنا
$$s=\alpha+\beta,\qquad t=\gamma+\delta,$$
فإن الجزء الصحيح في \(W^2\) يساوي
$$x=kst.$$
لذلك يساهم كل زوج مرتب من النوى الأولية \((s,t)\) بعدد
$$\left\lfloor\frac{n}{st}\right\rfloor$$
من القيم الممددة، ويكون العد المرتب
$$C_2^{\mathrm{ord}}(n)=\sum_{s\le n}\sum_{t\le n} f(s)f(t)\left\lfloor\frac{n}{st}\right\rfloor.$$
والرمز “ord” مهم هنا، لأن تبديل النواتين لا يغيّر القيمة النهائية، ولذلك فإن هذا المجموع يعدّ البنية الرباعية العامة مرتين.
ليست كل بنية رباعية مرتبة قيمة جديدة فعلًا. بعض هذه القيم ينهار إلى اتجاهين خاليين من المربعات فقط، وبالتالي يكون محسوبًا أصلًا ضمن \(C_1(n)\).
لنكتب الزوجين الأوليين على الصورة
$$\alpha=\sigma_1 a^2,\qquad \beta=\sigma_2 b^2,\qquad \gamma=\tau_1 c^2,\qquad \delta=\tau_2 d^2,$$
حيث \(\sigma_1,\sigma_2,\tau_1,\tau_2\) أجزاء خالية من المربعات. عندها تكون الأجزاء الخالية من المربعات للجذور الأربعة داخل \(W\) هي
$$\sigma_1\tau_1,\qquad \sigma_1\tau_2,\qquad \sigma_2\tau_1,\qquad \sigma_2\tau_2.$$
ويحدث التداخل مع العائلة الثنائية تمامًا عندما تندمج هذه النواتج الأربعة في اتجاهين فقط. ويستعمل التنفيذ توصيفًا بواسطة عوامل \(\rho_1,\rho_2,\rho_3,\rho_4\) خالية من المربعات ومتباينة أوليًا اثنين اثنين بحيث
$$\sigma_1=\rho_1\rho_2,\qquad \sigma_2=\rho_3\rho_4,\qquad \tau_1=\rho_1\rho_3,\qquad \tau_2=\rho_2\rho_4.$$
وعندها
$$\sqrt{\sigma_1\tau_1}=\rho_1\sqrt{\rho_2\rho_3},\qquad \sqrt{\sigma_2\tau_2}=\rho_4\sqrt{\rho_2\rho_3},$$
وكذلك
$$\sqrt{\sigma_1\tau_2}=\rho_2\sqrt{\rho_1\rho_4},\qquad \sqrt{\sigma_2\tau_1}=\rho_3\sqrt{\rho_1\rho_4}.$$
إذًا فإن التعبير الذي يبدو رباعي الجذور هو في الحقيقة قيمة ثنائية الجذور. ولنسمِّ \(C_3(n)\) عدد البنى المرتبة من هذا النوع المنهار. يجب طرح هذه الحالات من العد الرباعي المرتب قبل تطبيق عامل التناظر النهائي.
بعد إزالة البنى المرتبة التي تنهار إلى حالتين جذريتين، وبعد إهمال ترتيب النواتين الأوليتين، تحسب التطبيقات
$$\boxed{F(n)=C_1(n)+\frac{C_2^{\mathrm{ord}}(n)-C_3(n)}{2}.}$$
وهذه هي الصيغة الدقيقة التي تعتمد عليها تطبيقات C++ وPython وJava.
مثال بسيط من العائلة الثنائية هو
$$V=\sqrt5+\sqrt2.$$
وعندئذ
$$V^2=7+2\sqrt{10}=7+\sqrt{10}+\sqrt{10}.$$
النواة الأولية هنا هي \(s=5+2=7\)، وبما أن \(5\cdot2=10\) ليس مربعًا، فإن هذه القيمة تنتمي إلى العائلة الأولى. وكل \(k\) يحقق \(7k\le n\) يعطي قيمة صحيحة جديدة من النواة نفسها.
أما مثال حقيقي من العائلة الرباعية فيأخذ \((\alpha,\beta)=(2,1)\) و\((\gamma,\delta)=(3,1)\):
$$W=\sqrt6+\sqrt2+\sqrt3-1.$$
ومربعه يساوي
$$W^2=(2+1)(3+1)+2(2-1)\sqrt3+2(3-1)\sqrt2=12+2\sqrt3+4\sqrt2.$$
وبالتالي فإن الجزء الصحيح هو \(12=3\cdot4\)، وهذا يوضح لماذا تُفهرس العائلة الثانية بجداءات مجاميع النوى الأولية.
تبدأ التطبيقات ببناء غربال لقيم دالة أويلر حتى \(n\). ومن هذه القيم تُهيَّأ العلاقة
$$f(s)=\frac{\varphi(s)}{2}$$
لكل \(s\ge 3\)، ثم يُطرح واحد لكل تمثيل أولي من الشكل \(s=u^2+v^2\) مع \(u \gt v\) و\(\gcd(u,v)=1\). وهكذا نحصل على متتالية النواة \(f(s)\).
بعد ذلك تُبنى المجاميع البادئة لهذه المتتالية. العائلة الأولى \(C_1(n)\) مجرد مجموع مباشر من نوع قواسم. أما الحد المرتب للعائلة الثانية \(C_2^{\mathrm{ord}}(n)\) فلا يُحسب بحلقة مزدوجة تربيعية؛ بل تجمع الشيفرة المجالات التي تكون فيها \(\left\lfloor n/i\right\rfloor\) ثابتة داخل كتل توافقية، ثم تربط هذه الكتل بالمجاميع البادئة لتقليل الالتفاف إلى عدد أصغر كثيرًا من التجميعات.
أما حدّ التداخل \(C_3(n)\) فيُعالج منفصلًا. تحسب الشيفرة مسبقًا علامات الخلو من المربعات، وجداول التباين الأولي، ومربعات الأعداد حتى \(\lfloor\sqrt n\rfloor\). ثم تُعدَّد فقط التركيبات التي يمكنها جعل بنية رباعية تنهار إلى اتجاهين خاليين من المربعات، مع استخدام عدد كبير من متراجحات الإيقاف المبكر لتقليم البحث. يقوم تنفيذ C++ بعمل موازاة لهذه المرحلة المكلفة؛ ونسخة Python تتبع الرياضيات نفسها بصورة أكثر مباشرة؛ أما نسخة Java فتستعمل النواة المحسَّنة نفسها.
بناء غربال أويلر والنواة \(f\) يحتاج إلى زمن \(O(n\log\log n)\) وذاكرة \(O(n)\). مجموع العائلة الأولى \(C_1(n)\) تكلفته \(O(n)\). أما الالتفاف المرتب \(C_2^{\mathrm{ord}}(n)\) فيتسارع بفضل التقسيم التوافقي والمجاميع البادئة، ولذلك تتجنب الشيفرة الحلقة المزدوجة الساذجة \(O(n^2)\) وتعمل بدلًا من ذلك بعدد دون-تربيعي من كتل القيم.
عنق الزجاجة العملي هو تصحيح التداخل \(C_3(n)\). من غير السهل كتابة حدٍّ مغلقٍ بسيط للحالة الأسوأ لأن هناك عدة قيود متداخلة تتعلق بالخلو من المربعات وبالتباين الأولي. لكن التنفيذ يخفّض الكلفة كثيرًا باستخدام الجداول المسبقة، ومرشحات الأجزاء الخالية من المربعات، ومتراجحات الإيقاف المبكر. ويظل استهلاك الذاكرة الكلي \(O(n)\)، تهيمن عليه المصفوفات الحسابية ذات الطول \(n\).