A Hilbert number is a positive integer of the form \(4k+1\). The problem asks for the number of Hilbert numbers below a large exclusive limit \(X\) that are squarefree inside the Hilbert semigroup: equivalently, numbers \(n\equiv1\pmod4\) such that no Hilbert number \(h>1\) satisfies \(h^2\mid n\).
The implementations work with the inclusive bound \(N=X-1\), so the target quantity is
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
A direct scan with explicit Hilbert-square testing is far too slow near \(10^{16}\), so the solution rewrites the condition as a Möbius-weighted sum over odd square divisors.
The main job is to understand which ordinary prime exponents are allowed in a squarefree Hilbert number, and then encode that description with inclusion-exclusion.
Write an odd number \(n\equiv1\pmod4\) as
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
If some prime \(p\equiv1\pmod4\) has \(a_p\ge2\), then \(p\) itself is a Hilbert number and \(p^2\mid n\), so \(n\) is not squarefree in the Hilbert sense.
For primes \(q\equiv3\pmod4\), one copy of \(q^2\) is still allowed because \(q\not\equiv1\pmod4\). But two square units are too many. If
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
then we can build a nontrivial Hilbert number from those \(3\bmod4\) primes: for example \(q^2\) from one prime with \(b_q\ge4\), or \(qr\) from two different primes with \(b_q,b_r\ge2\). Its square then divides \(n\).
Therefore \(n\) is squarefree Hilbert exactly when
$$a_p\le1\quad\text{for every }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
The previous criterion has a concrete consequence. A squarefree Hilbert number is of one of two types:
$$\text{either }n\text{ is ordinary squarefree,}$$
$$\text{or }n=q^2m\text{ for exactly one prime }q\equiv3\pmod4\text{ and an ordinary squarefree }m.$$
The second case is unique. If two different \(3\bmod4\) primes contributed square factors, or if one such prime contributed exponent at least \(4\), then the sum of the floor terms above would be at least \(2\), which is forbidden.
This explains examples such as \(45=3^2\cdot5\), which is allowed, and \(81=3^4\), which is not.
Let \(\mathbf{1}_{\mathrm{sqf}}(m)\) be the indicator of ordinary squarefree integers. The standard identity is
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
Using the decomposition from Step 2, the indicator of squarefree Hilbert numbers becomes
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
The first term counts numbers with no square factor at all. The second term restores the legal case where the only square part is one factor \(q^2\) with \(q\equiv3\pmod4\).
Substitute the Möbius identity into both squarefree indicators:
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
In the second double sum, reindex with \(v=qu\). Then all terms become contributions from odd squares \(v^2\mid n\):
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
where
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
This is the exact coefficient formula used by the implementations. The correction term cancels illegal square divisors such as \(5^2\), keeps legal ones such as \(3^2\), and subtracts higher powers such as \(3^4\) again.
Let
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
For any odd \(v\), the condition \(v^2\mid n\) with \(n\equiv1\pmod4\) is equivalent to writing \(n=v^2m\) with \(m\equiv1\pmod4\), because \(v^2\equiv1\pmod4\). Hence
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
Only values \(v\le\sqrt{N}\) contribute, so the sum is finite:
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
There are exactly \(25\) integers \(n\le99\) with \(n\equiv1\pmod4\). For this bound, only odd \(v\le9\) matter.
The relevant coefficients are
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
Indeed, \(c(5)=-1\) removes multiples of \(25\), while \(c(9)=-1\) removes multiples of \(81=(3^2)^2\). The terms for \(3\) and \(7\) vanish because a single square \(3^2\) or \(7^2\) is still allowed in the Hilbert setting.
Therefore
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
which matches the checkpoint count below \(100\).
The C++, Python, and Java implementations all use the same arithmetic plan. They first convert the exclusive input bound \(X\) into the inclusive bound \(N=X-1\), compute \(U=\lfloor\sqrt{N}\rfloor\), and store only odd candidates up to \(U\). That halves the sieve size immediately, because every relevant square root \(v\) is odd.
Next, the implementation builds an odd-only prime sieve, derives the Möbius function \(\mu(v)\) on those odd values, and records the primes congruent to \(3\pmod4\). It then starts from the base coefficients \(\mu(v)\) and adds the correction term \(\mu(v/q)\) along odd multiples of each prime \(q\equiv3\pmod4\), producing the final weights \(c(v)\).
Finally, it evaluates
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
for every odd \(v\le U\) and accumulates the result. The C++ version keeps the same formula but can split the final summation into several ranges when multithreading is enabled; the Python and Java versions run the same arithmetic in a single thread.
Let \(U=\lfloor\sqrt{N}\rfloor\). Building the odd-only sieve and the odd Möbius table costs \(O(U\log\log U)\) time and \(O(U)\) memory. Adding the correction terms over multiples of primes \(q\equiv3\pmod4\) has the same harmonic-sum behavior, so it also stays within \(O(U\log\log U)\) time.
The final accumulation is a single pass over the odd indices, so it is \(O(U)\). Overall, the method is near-linear in \(\sqrt{N}\) and uses \(O(U)\) memory.
Eine Hilbert-Zahl ist eine positive ganze Zahl der Form \(4k+1\). Gesucht ist die Anzahl der Hilbert-Zahlen unter einer großen exklusiven Schranke \(X\), die im Hilbert-Halbgruppen-Sinn quadratfrei sind: also Zahlen \(n\equiv1\pmod4\), für die keine Hilbert-Zahl \(h>1\) die Bedingung \(h^2\mid n\) erfüllt.
Die Implementierungen arbeiten mit der inklusiven Grenze \(N=X-1\). Gezählt wird also
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
Ein direkter Test aller Kandidaten wäre in der Größenordnung von \(10^{16}\) viel zu langsam. Deshalb wird die Bedingung in eine Möbius-gewichtete Summe über ungerade Quadratwurzeln umgeformt.
Der entscheidende Schritt besteht darin, genau zu beschreiben, welche gewöhnlichen Primzahl-Exponenten in einer quadratfreien Hilbert-Zahl erlaubt sind, und diese Beschreibung dann mit Inklusion-Exklusion zu kodieren.
Schreibe eine ungerade Zahl \(n\equiv1\pmod4\) in der Form
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
Falls für eine Primzahl \(p\equiv1\pmod4\) der Exponent \(a_p\ge2\) gilt, dann ist \(p\) selbst eine Hilbert-Zahl und \(p^2\mid n\). Also ist \(n\) im Hilbert-Sinn nicht quadratfrei.
Für Primzahlen \(q\equiv3\pmod4\) ist genau eine Kopie von \(q^2\) noch erlaubt, weil \(q\not\equiv1\pmod4\) ist. Zwei solche Quadrat-Einheiten sind jedoch zu viel. Wenn
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
dann lässt sich aus diesen \(3\bmod4\)-Primzahlen eine nichttriviale Hilbert-Zahl bilden, etwa \(q^2\) aus einer Primzahl mit \(b_q\ge4\) oder \(qr\) aus zwei verschiedenen Primzahlen mit \(b_q,b_r\ge2\). Deren Quadrat teilt dann \(n\).
Damit ist \(n\) genau dann Hilbert-quadratfrei, wenn
$$a_p\le1\quad\text{für alle }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
Aus diesem Kriterium folgt eine sehr konkrete Beschreibung. Eine quadratfreie Hilbert-Zahl ist von genau einem der beiden Typen:
$$\text{entweder ist }n\text{ im gewöhnlichen Sinn quadratfrei,}$$
$$\text{oder }n=q^2m\text{ für genau eine Primzahl }q\equiv3\pmod4\text{ und ein gewöhnlich quadratfreies }m.$$
Der zweite Fall ist eindeutig. Würden zwei verschiedene \(3\bmod4\)-Primzahlen Quadratfaktoren beitragen oder würde eine solche Primzahl Exponent mindestens \(4\) besitzen, dann wäre die Summe der Bodenfunktionen oben mindestens \(2\) und der Fall damit verboten.
So erklärt sich zum Beispiel, warum \(45=3^2\cdot5\) erlaubt ist, aber \(81=3^4\) nicht.
Sei \(\mathbf{1}_{\mathrm{sqf}}(m)\) die Indikatorfunktion gewöhnlich quadratfreier Zahlen. Dann gilt die Standardidentität
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
Mit der Zerlegung aus Schritt 2 wird der Indikator für quadratfreie Hilbert-Zahlen zu
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
Der erste Term zählt Zahlen ganz ohne Quadratfaktor. Der zweite Term stellt den zulässigen Sonderfall wieder her, dass der einzige Quadratteil genau ein Faktor \(q^2\) mit \(q\equiv3\pmod4\) ist.
Setzt man die Möbius-Identität in beide Quadratfrei-Indikatoren ein, erhält man
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
In der zweiten Doppelsumme wird nun mit \(v=qu\) umindiziert. Dann erscheinen alle Beiträge als Beiträge von ungeraden Quadraten \(v^2\mid n\):
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
wobei
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
Genau diese Koeffizientenformel verwenden die Implementierungen. Der Korrekturterm entfernt unzulässige Quadratfaktoren wie \(5^2\), lässt zulässige Fälle wie \(3^2\) stehen und zieht höhere Potenzen wie \(3^4\) wieder ab.
Definiere
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
Für ungerades \(v\) ist die Bedingung \(v^2\mid n\) zusammen mit \(n\equiv1\pmod4\) äquivalent zu \(n=v^2m\) mit \(m\equiv1\pmod4\), denn \(v^2\equiv1\pmod4\). Daher
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
Nur Werte \(v\le\sqrt{N}\) tragen bei, also ist die Summe endlich:
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
Es gibt genau \(25\) Zahlen \(n\le99\) mit \(n\equiv1\pmod4\). Für diese Schranke sind nur ungerade \(v\le9\) relevant.
Die benötigten Koeffizienten sind
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
Dabei entfernt \(c(5)=-1\) die Vielfachen von \(25\), und \(c(9)=-1\) entfernt die Vielfachen von \(81=(3^2)^2\). Die Terme für \(3\) und \(7\) verschwinden, weil ein einzelnes Quadrat \(3^2\) oder \(7^2\) im Hilbert-Sinn noch erlaubt ist.
Also gilt
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
genau wie beim Kontrollwert für Zahlen unter \(100\).
Die C++-, Python- und Java-Implementierungen folgen demselben arithmetischen Plan. Zuerst wird die exklusive Eingabeschranke \(X\) in die inklusive Schranke \(N=X-1\) umgewandelt, dann \(U=\lfloor\sqrt{N}\rfloor\) berechnet und nur ungerade Kandidaten bis \(U\) gespeichert. Dadurch halbiert sich die Siebgröße sofort, weil jede relevante Quadratwurzel \(v\) ungerade ist.
Anschließend baut die Implementierung ein Sieb nur für ungerade Zahlen auf, berechnet daraus die Möbius-Funktion \(\mu(v)\) auf diesen ungeraden Werten und sammelt alle Primzahlen \(3\pmod4\). Danach startet sie mit den Basis-Koeffizienten \(\mu(v)\) und addiert entlang der ungeraden Vielfachen jeder Primzahl \(q\equiv3\pmod4\) den Korrekturterm \(\mu(v/q)\), wodurch die endgültigen Gewichte \(c(v)\) entstehen.
Zum Schluss wird
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
für jedes ungerade \(v\le U\) ausgewertet und aufsummiert. Die C++-Version verwendet dieselbe Formel, kann die Endsumme aber bei Bedarf auf mehrere Bereiche aufteilen; die Python- und Java-Versionen führen dieselbe Arithmetik in einem Thread aus.
Sei \(U=\lfloor\sqrt{N}\rfloor\). Das Sieb nur auf ungeraden Zahlen und die Berechnung der Möbius-Tabelle kosten \(O(U\log\log U)\) Zeit und \(O(U)\) Speicher. Das Hinzufügen der Korrekturterme über die Vielfachen der Primzahlen \(q\equiv3\pmod4\) hat dasselbe harmonische Summenverhalten und bleibt daher ebenfalls in \(O(U\log\log U)\) Zeit.
Die abschließende Aufsummierung ist ein einzelner Durchlauf über die ungeraden Indizes und kostet \(O(U)\). Insgesamt ist das Verfahren also nahezu linear in \(\sqrt{N}\) und verwendet \(O(U)\) Speicher.
Bir Hilbert sayısı, \(4k+1\) biçimindeki pozitif tamsayıdır. Bu problem, büyük bir dışlayıcı üst sınır \(X\) altındaki Hilbert sayılarından Hilbert yarıgrubu anlamında karesiz olanların sayısını ister; yani \(n\equiv1\pmod4\) olup hiçbir \(h>1\) Hilbert sayısı için \(h^2\mid n\) sağlamayan sayıları.
Uygulamalar kapsayıcı sınır olarak \(N=X-1\) kullanır. Dolayısıyla hedef büyüklük
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
\(10^{16}\) civarında her adayı tek tek test etmek çok pahalıdır. Bu yüzden çözüm, koşulu tek sayılı kare bölenler üzerinde Möbius ağırlıklı bir toplama dönüştürür.
Asıl fikir, bir Hilbert karesiz sayıda sıradan asal üslerinin nasıl görünebileceğini tam olarak anlamak ve sonra bunu dahil et-çıkar ile kodlamaktır.
Tek ve \(n\equiv1\pmod4\) olan bir sayıyı
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}$$
şeklinde yazalım. Eğer \(p\equiv1\pmod4\) olan bir asal için \(a_p\ge2\) ise, \(p\) zaten bir Hilbert sayısıdır ve \(p^2\mid n\) olur. O halde \(n\), Hilbert anlamında karesiz değildir.
\(q\equiv3\pmod4\) olan asallarda ise bir tane \(q^2\) bulunmasına izin vardır; çünkü \(q\) tek başına Hilbert sayısı değildir. Fakat iki kare birimi fazladır. Eğer
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2$$
olursa, bu \(3\bmod4\) asallarından önemsiz olmayan bir Hilbert sayısı kurulabilir: örneğin \(b_q\ge4\) ise \(q^2\), iki farklı asal için \(b_q,b_r\ge2\) ise \(qr\). Bunun karesi de \(n\)'yi böler.
Demek ki \(n\) ancak ve ancak şu koşullarda Hilbert-karesizdir:
$$a_p\le1\quad\text{her }p\equiv1\pmod4\text{ için},$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
Bu ölçüt çok somut bir sonuç verir. Hilbert-karesiz bir sayı tam olarak iki tipten biridir:
$$\text{ya }n\text{ sıradan anlamda karesizdir,}$$
$$\text{ya da }n=q^2m\text{ biçimindedir; burada }q\equiv3\pmod4\text{ asal ve }m\text{ sıradan karesizdir.}$$
İkinci durum tektir. İki farklı \(3\bmod4\) asalı kare katkısı yapsaydı ya da bunlardan biri üs olarak en az \(4\) taşısaydı, yukarıdaki taban toplamı en az \(2\) olur ve durum yasaklanırdı.
Bu yüzden \(45=3^2\cdot5\) kabul edilirken \(81=3^4\) kabul edilmez.
\(\mathbf{1}_{\mathrm{sqf}}(m)\) sıradan karesiz sayı göstergesi olsun. Standart özdeşlik
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u)$$
şeklindedir. Adım 2'deki ayrışıma göre Hilbert-karesiz gösterge
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right)$$
olur. İlk terim hiç kare çarpanı olmayan sayıları, ikinci terim ise tek yasal kare parçası olarak bir \(q^2\) taşıyan sayıları geri ekler.
Möbius özdeşliğini her iki karesizlik göstergesine de yerleştirirsek
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right)$$
elde edilir. İkinci çift toplamda \(v=qu\) yeniden indekslemesini yapınca tüm terimler tek kareler \(v^2\mid n\) üzerinden birleşir:
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
burada
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
Uygulamaların kullandığı tam katsayı formülü budur. Düzeltme terimi \(5^2\) gibi yasak kareleri siler, \(3^2\) gibi yasal durumları korur ve \(3^4\) gibi daha yüksek kuvvetleri yeniden çıkarır.
Şunu tanımlayalım:
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
Tek bir \(v\) için, \(v^2\mid n\) ve \(n\equiv1\pmod4\) koşulu, \(v^2\equiv1\pmod4\) olduğu için \(n=v^2m\) ve \(m\equiv1\pmod4\) yazımıyla aynıdır. Böylece
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right)$$
olur. Sadece \(v\le\sqrt{N}\) katkı verdiğinden toplam sonludur:
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
\(n\le99\) ve \(n\equiv1\pmod4\) olan tam olarak \(25\) sayı vardır. Bu sınırda yalnızca \(v\le9\) olan tek değerler önemlidir.
Gerekli katsayılar
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1$$
şeklindedir. Burada \(c(5)=-1\), \(25\)'in katlarını çıkarır; \(c(9)=-1\) ise \(81=(3^2)^2\)'in katlarını çıkarır. \(3\) ve \(7\) terimlerinin sıfır olması, tek bir \(3^2\) ya da \(7^2\) faktörünün Hilbert anlamında hâlâ izinli olmasındandır.
Dolayısıyla
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
ve bu sonuç \(100\)'den küçük değerler için verilen kontrol sayısıyla aynıdır.
C++, Python ve Java uygulamalarının aritmetik çekirdeği aynıdır. Önce dışlayıcı giriş sınırı \(X\), kapsayıcı sınır \(N=X-1\)'e çevrilir; sonra \(U=\lfloor\sqrt{N}\rfloor\) hesaplanır ve yalnızca \(U\)'ya kadar tek adaylar tutulur. Çünkü ilgili her karekök \(v\) tektir ve bu seçim eleman sayısını hemen yarıya indirir.
Daha sonra uygulama yalnız tek sayılar üzerinde çalışan bir asal süzgeci kurar, bu sayılarda Möbius fonksiyonu \(\mu(v)\)'yu üretir ve \(3\pmod4\) asallarını ayırır. Ardından taban katsayıları \(\mu(v)\) ile başlar ve her \(q\equiv3\pmod4\) asalı için tek katlar boyunca \(\mu(v/q)\) düzeltmesini ekleyerek son ağırlıklar \(c(v)\)'yi oluşturur.
Son adımda
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
her tek \(v\le U\) için hesaplanıp toplanır. C++ sürümü aynı formülü kullanır; yalnız istenirse son toplamı birden çok aralığa bölüp paralel çalıştırabilir. Python ve Java sürümleri aynı hesabı tek iş parçacığında yapar.
\(U=\lfloor\sqrt{N}\rfloor\) olsun. Yalnız tek sayılar için kurulan süzgeç ve tek sayılardaki Möbius tablosu \(O(U\log\log U)\) zamanda ve \(O(U)\) bellekte hesaplanır. \(q\equiv3\pmod4\) asallarının katları üzerinde yapılan düzeltme toplaması da aynı harmonik toplam davranışına sahip olduğundan yine \(O(U\log\log U)\) zaman içinde kalır.
Son biriktirme aşaması tek sayılı dizinler üzerinde tek geçişli olduğundan \(O(U)\)'dur. Toplamda yöntem \(\sqrt{N}\)'e göre yaklaşık lineer davranır ve \(O(U)\) bellek kullanır.
Un número de Hilbert es un entero positivo de la forma \(4k+1\). El problema pide cuántos números de Hilbert por debajo de un límite exclusivo grande \(X\) son squarefree dentro del semigrupo de Hilbert; es decir, cuántos \(n\equiv1\pmod4\) no son divisibles por \(h^2\) para ninguna cantidad de Hilbert \(h>1\).
Las implementaciones trabajan con el límite inclusivo \(N=X-1\), así que la cantidad buscada es
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
Comprobar cada candidato de forma directa es inviable cerca de \(10^{16}\), por lo que la solución convierte la condición en una suma con pesos de Möbius sobre divisores cuadrados impares.
La clave es describir exactamente qué exponentes primos ordinarios puede tener un número de Hilbert squarefree y después codificar esa descripción mediante inclusión-exclusión.
Escribimos un número impar \(n\equiv1\pmod4\) como
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
Si existe un primo \(p\equiv1\pmod4\) con \(a_p\ge2\), entonces \(p\) ya es un número de Hilbert y \(p^2\mid n\). Por tanto, \(n\) no es squarefree en el sentido de Hilbert.
Para los primos \(q\equiv3\pmod4\), una sola copia de \(q^2\) todavía está permitida, porque \(q\not\equiv1\pmod4\). Pero dos unidades cuadradas ya son demasiadas. Si
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
entonces podemos construir un número de Hilbert no trivial con esos primos \(3\bmod4\): por ejemplo \(q^2\) si un primo tiene \(b_q\ge4\), o \(qr\) si dos primos distintos satisfacen \(b_q,b_r\ge2\). El cuadrado de ese número divide a \(n\).
Así, \(n\) es Hilbert-squarefree exactamente cuando
$$a_p\le1\quad\text{para todo }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
El criterio anterior tiene una consecuencia muy concreta. Un número de Hilbert squarefree es de uno de estos dos tipos:
$$\text{o bien }n\text{ es squarefree en el sentido ordinario,}$$
$$\text{o bien }n=q^2m\text{ para un único primo }q\equiv3\pmod4\text{ y un }m\text{ squarefree ordinario.}$$
El segundo caso es único. Si dos primos distintos \(3\bmod4\) aportaran factores cuadrados, o si uno solo de ellos tuviera exponente al menos \(4\), entonces la suma de las partes enteras anterior sería al menos \(2\), y el caso quedaría prohibido.
Eso explica por qué \(45=3^2\cdot5\) está permitido mientras que \(81=3^4\) no lo está.
Sea \(\mathbf{1}_{\mathrm{sqf}}(m)\) el indicador de enteros squarefree ordinarios. La identidad estándar es
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
Usando la descomposición del Paso 2, el indicador de números de Hilbert squarefree toma la forma
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
El primer término cuenta los números sin ningún factor cuadrado. El segundo recupera el caso legal en el que la única parte cuadrada es un factor \(q^2\) con \(q\equiv3\pmod4\).
Sustituyendo la identidad de Möbius en ambos indicadores de squarefreeness se obtiene
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
En la segunda suma doble reindexamos con \(v=qu\). Así, todos los términos pasan a ser contribuciones de cuadrados impares \(v^2\mid n\):
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
donde
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
Esta es exactamente la fórmula de coeficientes usada por las implementaciones. El término corrector elimina cuadrados ilegales como \(5^2\), conserva casos legales como \(3^2\) y vuelve a restar potencias mayores como \(3^4\).
Definimos
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
Para cualquier \(v\) impar, la condición \(v^2\mid n\) junto con \(n\equiv1\pmod4\) equivale a escribir \(n=v^2m\) con \(m\equiv1\pmod4\), porque \(v^2\equiv1\pmod4\). Entonces
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
Solo contribuyen los valores \(v\le\sqrt{N}\), así que la suma es finita:
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
Hay exactamente \(25\) enteros \(n\le99\) con \(n\equiv1\pmod4\). Para este límite solo importan los valores impares \(v\le9\).
Los coeficientes relevantes son
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
En efecto, \(c(5)=-1\) quita los múltiplos de \(25\), mientras que \(c(9)=-1\) quita los múltiplos de \(81=(3^2)^2\). Los términos para \(3\) y \(7\) se anulan porque un solo cuadrado \(3^2\) o \(7^2\) sigue siendo legal en el contexto de Hilbert.
Por tanto,
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
que coincide con el valor de comprobación para los números menores que \(100\).
Las implementaciones en C++, Python y Java siguen el mismo plan aritmético. Primero convierten el límite exclusivo \(X\) en el límite inclusivo \(N=X-1\), calculan \(U=\lfloor\sqrt{N}\rfloor\) y almacenan solo candidatos impares hasta \(U\). Eso reduce de inmediato el tamaño de la criba, porque toda raíz cuadrada relevante \(v\) es impar.
Después, la implementación construye una criba de primos solo para impares, obtiene la función de Möbius \(\mu(v)\) sobre esos valores impares y registra los primos congruentes con \(3\pmod4\). A continuación parte de los coeficientes base \(\mu(v)\) y añade el término corrector \(\mu(v/q)\) a lo largo de los múltiplos impares de cada primo \(q\equiv3\pmod4\), produciendo así los pesos finales \(c(v)\).
Finalmente evalúa
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
para cada \(v\) impar con \(v\le U\) y acumula el resultado. La versión en C++ usa la misma fórmula, pero puede dividir la suma final en varios rangos cuando se activa el paralelismo; las versiones en Python y Java ejecutan la misma aritmética en un solo hilo.
Sea \(U=\lfloor\sqrt{N}\rfloor\). Construir la criba para impares y la tabla impar de Möbius cuesta \(O(U\log\log U)\) tiempo y \(O(U)\) memoria. Añadir los términos correctores sobre los múltiplos de primos \(q\equiv3\pmod4\) tiene el mismo comportamiento de suma armónica, así que también queda dentro de \(O(U\log\log U)\).
La acumulación final es un único recorrido sobre los índices impares, por lo que cuesta \(O(U)\). En conjunto, el método es casi lineal en \(\sqrt{N}\) y usa \(O(U)\) memoria.
Hilbert 数是形如 \(4k+1\) 的正整数。本题要求统计小于某个很大外界上限 \(X\) 的 Hilbert 数中，有多少个在 Hilbert 半群意义下是 squarefree 的；也就是说，统计满足 \(n\equiv1\pmod4\) 且不存在任何 \(h>1\)、\(h\equiv1\pmod4\) 使得 \(h^2\mid n\) 的那些数。
实现里把外界上限转成包含式上限 \(N=X-1\)，因此真正要计算的是
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
如果直接逐个检查每个候选数是否含有 Hilbert 平方因子，那么在 \(10^{16}\) 量级上完全不可行，所以解法必须把这个条件改写成一个可以筛法求出的 Möbius 加权求和。
核心任务是先弄清楚：一个 Hilbert-squarefree 数的普通素因子指数到底允许长成什么样；然后再把这个结构用容斥和 Möbius 函数压缩成一个单一求和公式。
把一个奇数 \(n\equiv1\pmod4\) 写成
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
如果某个素数 \(p\equiv1\pmod4\) 满足 \(a_p\ge2\)，那么 \(p\) 本身就是 Hilbert 数，于是 \(p^2\mid n\)。这立刻说明 \(n\) 不是 Hilbert 意义下的 squarefree。
对于 \(q\equiv3\pmod4\) 的素数，情况不同。一个 \(q^2\) 还允许出现，因为 \(q\) 自己并不是 Hilbert 数。但是“平方单位”一旦积累到两个，就会出问题。如果
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
那么就能从这些 \(3\bmod4\) 素数里拼出一个非平凡的 Hilbert 数。例如：
$$\text{若某个 }b_q\ge4,\text{ 可取 }q^2,$$
$$\text{若两个不同素数 }q,r\text{ 满足 }b_q,b_r\ge2,\text{ 可取 }qr.$$
无论哪种情况，得到的那个 Hilbert 数的平方都会整除 \(n\)。
因此，\(n\) 恰好在下面两个条件同时成立时才是 Hilbert-squarefree：
$$a_p\le1\quad\text{对所有 }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
上面的判别条件可以直接转化成结构描述。一个 Hilbert-squarefree 数只可能属于以下两类之一：
$$\text{要么 }n\text{ 本身就是普通意义下的 squarefree 数，}$$
$$\text{要么 }n=q^2m,\text{ 其中 }q\equiv3\pmod4\text{ 是唯一的一个素数，且 }m\text{ 是普通 squarefree 数。}$$
这里的“唯一”非常重要。如果有两个不同的 \(3\bmod4\) 素数都贡献了平方部分，或者同一个这样的素数指数至少达到 \(4\)，那么上一步里的地板和就至少是 \(2\)，这种数就必须被排除。
所以 \(45=3^2\cdot5\) 是允许的，因为它只是一个合法的 \(3^2\) 乘上普通 squarefree 数 \(5\)；但 \(81=3^4\) 不允许，因为它已经含有 \((3^2)^2=9^2\)，而 \(9\equiv1\pmod4\) 本身就是 Hilbert 数。
设 \(\mathbf{1}_{\mathrm{sqf}}(m)\) 表示“\(m\) 在普通意义下是 squarefree”的指示函数。经典恒等式是
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
把步骤 2 的结构分解代进去，就得到 Hilbert-squarefree 的指示函数
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
第一项负责统计完全没有平方因子的数。第二项把“唯一平方部分正好是某个 \(q^2\)”这种在 Hilbert 意义下仍然合法的情况重新加回来。
把 Möbius 恒等式代入上式中的两个 squarefree 指示函数，可得
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
在第二个双重求和中作变量替换 \(v=qu\)，所有项就都变成了“某个奇数平方 \(v^2\) 整除 \(n\)”的贡献。于是
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
其中统一系数定义为
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
这正是实现里真正使用的系数公式。它的作用可以直观理解为：把 \(5^2\) 这种非法平方部分扣掉，把 \(3^2\) 这种合法平方部分保留下来，同时再把 \(3^4\) 这种已经“过头”的高次平方重新减掉。
定义
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
对任意奇数 \(v\)，因为 \(v^2\equiv1\pmod4\)，所以条件“\(v^2\mid n\) 且 \(n\equiv1\pmod4\)”等价于把 \(n\) 写成
$$n=v^2m,\qquad m\equiv1\pmod4.$$
因此总计数可以写成
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
由于只有 \(v\le\sqrt{N}\) 才会产生非零贡献，最终得到有限和
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
不超过 \(99\) 且满足 \(n\equiv1\pmod4\) 的整数一共有 \(25\) 个。这个范围内只需要考虑奇数 \(v\le9\)。
对应的系数是
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
其中 \(c(5)=-1\) 会删掉所有 \(25\) 的倍数，而 \(c(9)=-1\) 会删掉所有 \(81=(3^2)^2\) 的倍数。至于 \(c(3)\) 和 \(c(7)\) 为零，是因为单独出现一个 \(3^2\) 或 \(7^2\) 在 Hilbert 意义下仍然是允许的。
于是
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
这正好和“小于 \(100\) 的答案”为 \(23\) 的检查点一致。
C++、Python 和 Java 实现共享同一个算术核心。它们先把外界输入上限 \(X\) 变成包含式上限 \(N=X-1\)，再计算 \(U=\lfloor\sqrt{N}\rfloor\)，并且只存储到 \(U\) 为止的奇数候选值。因为每个相关的平方根 \(v\) 都是奇数，这一步立刻把筛表规模减半。
接着，实现会构造一个只处理奇数的素数筛，在这些奇数位置上计算 Möbius 函数 \(\mu(v)\)，同时记录所有满足 \(q\equiv3\pmod4\) 的素数。然后从基础权重 \(\mu(v)\) 出发，沿着每个这样的素数的奇数倍位置加入修正项 \(\mu(v/q)\)，从而得到最终的系数 \(c(v)\)。
最后，对每个奇数 \(v\le U\) 计算
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
并累加。C++ 版本使用同一公式，但在启用多线程时会把最终求和拆成多个区间并行处理；Python 和 Java 版本则在单线程中完成同样的运算。
记 \(U=\lfloor\sqrt{N}\rfloor\)。奇数筛和奇数 Möbius 表的构造需要 \(O(U\log\log U)\) 时间与 \(O(U)\) 空间。对所有 \(q\equiv3\pmod4\) 的素数沿倍数加入修正项，本质上具有同样的调和级数行为，因此时间复杂度仍然是 \(O(U\log\log U)\)。
最终累加只是对奇数索引做一次线性扫描，所以是 \(O(U)\)。整体来看，该方法对 \(\sqrt{N}\) 近似线性，空间复杂度为 \(O(U)\)。
Числом Гильберта здесь называется положительное целое вида \(4k+1\). Требуется посчитать, сколько таких чисел меньше большого внешнего предела \(X\) являются squarefree в смысле полугруппы Гильберта, то есть сколько чисел \(n\equiv1\pmod4\) не делятся на \(h^2\) ни для какого числа Гильберта \(h>1\).
Реализации работают с включительной границей \(N=X-1\), поэтому фактически вычисляется
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
Прямой перебор с явной проверкой всех квадратов Гильберта слишком дорог уже около \(10^{16}\), поэтому решение переводит условие в сумму по нечетным квадратным делителям с весами, построенными через функцию Мёбиуса.
Главная идея состоит в том, чтобы сначала понять допустимую структуру обычных простых показателей, а затем свернуть это описание в одну формулу с включением-исключением.
Запишем нечетное число \(n\equiv1\pmod4\) в виде
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
Если для некоторого простого \(p\equiv1\pmod4\) выполняется \(a_p\ge2\), то \(p\) само является числом Гильберта, и потому \(p^2\mid n\). Следовательно, \(n\) уже не squarefree в нужном смысле.
Для простых \(q\equiv3\pmod4\) одна копия \(q^2\) еще допустима, потому что само \(q\) не является числом Гильберта. Но двух квадратных единиц уже достаточно, чтобы возник запрет. Если
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
то из этих простых \(3\bmod4\) можно составить нетривиальное число Гильберта: например, \(q^2\), если у одного простого \(b_q\ge4\), или \(qr\), если у двух разных простых \(b_q,b_r\ge2\). Квадрат такого числа делит \(n\).
Значит, число \(n\) является Hilbert-squarefree тогда и только тогда, когда
$$a_p\le1\quad\text{для всех }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
Из этого критерия сразу следует простая классификация. Hilbert-squarefree число имеет один из двух видов:
$$\text{либо }n\text{ squarefree в обычном смысле,}$$
$$\text{либо }n=q^2m\text{ для ровно одного простого }q\equiv3\pmod4\text{ и обычного squarefree }m.$$
Второй случай единственный. Если бы квадратные множители давали два разных простых \(3\bmod4\) или один такой простой входил бы с показателем хотя бы \(4\), то сумма целых частей сверху была бы не меньше \(2\), а это запрещено.
Именно поэтому \(45=3^2\cdot5\) допустимо, а \(81=3^4\) уже нет.
Пусть \(\mathbf{1}_{\mathrm{sqf}}(m)\) обозначает индикатор обычных squarefree чисел. Тогда выполняется стандартная формула
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
С учетом разложения из шага 2 индикатор Hilbert-squarefree чисел равен
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
Первое слагаемое считает числа вообще без квадратных делителей. Второе возвращает разрешенный случай, когда единственная квадратная часть имеет вид \(q^2\) для простого \(q\equiv3\pmod4\).
Подставляя формулу Мёбиуса в оба индикатора squarefree, получаем
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
Во второй двойной сумме сделаем замену \(v=qu\). Тогда все слагаемые становятся вкладом от нечетных квадратов \(v^2\mid n\):
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
где
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
Это в точности та формула коэффициентов, которую используют реализации. Поправочный член убирает запрещенные квадраты вроде \(5^2\), сохраняет разрешенные случаи вроде \(3^2\) и затем снова вычитает слишком большие степени вроде \(3^4\).
Введем функцию
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
Для любого нечетного \(v\) условие \(v^2\mid n\) вместе с \(n\equiv1\pmod4\) эквивалентно представлению \(n=v^2m\) с \(m\equiv1\pmod4\), потому что \(v^2\equiv1\pmod4\). Поэтому
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
Ненулевой вклад дают только \(v\le\sqrt{N}\), значит окончательно
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
Чисел \(n\le99\) с условием \(n\equiv1\pmod4\) ровно \(25\). Для такой границы важны только нечетные \(v\le9\).
Нужные коэффициенты равны
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
Коэффициент \(c(5)=-1\) вычитает кратные \(25\), а \(c(9)=-1\) вычитает кратные \(81=(3^2)^2\). Слагаемые для \(3\) и \(7\) обращаются в ноль, потому что один квадрат \(3^2\) или \(7^2\) в задаче Гильберта еще разрешен.
Итак,
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
что совпадает с контрольным значением для чисел меньше \(100\).
Реализации на C++, Python и Java используют один и тот же арифметический план. Сначала внешний эксклюзивный предел \(X\) переводится во включительный предел \(N=X-1\), затем вычисляется \(U=\lfloor\sqrt{N}\rfloor\), и до этого значения хранятся только нечетные кандидаты. Это сразу вдвое уменьшает размер решета, потому что каждая существенная квадратная корень \(v\) нечетна.
Далее реализация строит решето простых только по нечетным числам, вычисляет на них функцию Мёбиуса \(\mu(v)\) и отдельно сохраняет простые числа, сравнимые с \(3\pmod4\). После этого она берет базовые коэффициенты \(\mu(v)\) и добавляет поправку \(\mu(v/q)\) вдоль нечетных кратных каждого простого \(q\equiv3\pmod4\), получая итоговые веса \(c(v)\).
В конце для каждого нечетного \(v\le U\) вычисляется
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
и все значения суммируются. Версия на C++ использует ту же формулу, но при необходимости разбивает заключительную сумму на несколько диапазонов; версии на Python и Java выполняют ту же арифметику в одном потоке.
Пусть \(U=\lfloor\sqrt{N}\rfloor\). Построение решета по нечетным числам и таблицы Мёбиуса требует \(O(U\log\log U)\) времени и \(O(U)\) памяти. Добавление поправочных членов по кратным простых \(q\equiv3\pmod4\) имеет такое же гармоническое суммарное поведение и потому тоже укладывается в \(O(U\log\log U)\).
Заключительное накопление представляет собой один линейный проход по нечетным индексам, то есть стоит \(O(U)\). В результате весь метод почти линейный по \(\sqrt{N}\) и использует \(O(U)\) памяти.
عدد هيلبرت هنا هو كل عدد صحيح موجب من الصورة \(4k+1\). والمطلوب هو حساب عدد أعداد هيلبرت الأصغر من حد خارجي كبير \(X\) والتي تكون squarefree داخل شبه زمرة هيلبرت؛ أي الأعداد \(n\equiv1\pmod4\) التي لا يوجد لها عدد هيلبرت \(h>1\) بحيث \(h^2\mid n\).
التنفيذات تعمل بحد شامل هو \(N=X-1\)، ولذلك فإن الكمية المطلوبة هي
$$S(N)=\#\{n\le N:n\equiv1\pmod4,\ \nexists h\equiv1\pmod4,\ h>1,\ h^2\mid n\}.$$
الفحص المباشر لكل عدد مرشح غير عملي إطلاقًا قرب \(10^{16}\)، لذا يحول الحل هذا الشرط إلى مجموع موزون بدالة موبيوس على القواسم المربعة الفردية.
الفكرة الأساسية هي أن نفهم أولًا كيف يمكن أن تبدو أسس العوامل الأولية العادية في عدد Hilbert-squarefree، ثم نحول هذا الوصف إلى صيغة واحدة باستخدام مبدأ الاشتمال والاستبعاد.
لنكتب عددًا فرديًا \(n\equiv1\pmod4\) بالشكل
$$n=\prod_{p\equiv1\pmod4} p^{a_p}\prod_{q\equiv3\pmod4} q^{b_q}.$$
إذا وُجد عدد أولي \(p\equiv1\pmod4\) له أس \(a_p\ge2\)، فإن \(p\) نفسه عدد هيلبرت، وبالتالي \(p^2\mid n\). عندها لا يكون \(n\) squarefree بالمعنى المطلوب.
أما بالنسبة إلى الأعداد الأولية \(q\equiv3\pmod4\)، فوجود نسخة واحدة من \(q^2\) لا يزال مسموحًا لأن \(q\) نفسه ليس عدد هيلبرت. لكن وجود وحدتين مربعتين يصبح ممنوعًا. فإذا كان
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\ge2,$$
فيمكن تكوين عدد هيلبرت غير تافه من هذه الأعداد الأولية الموافقة لـ \(3\bmod4\): مثل \(q^2\) عندما يكون \(b_q\ge4\)، أو \(qr\) إذا كان هناك عددان أوليان مختلفان يحققان \(b_q,b_r\ge2\). وعندئذٍ يقسم مربع ذلك العدد \(n\).
إذن يكون \(n\) Hilbert-squarefree إذا وفقط إذا تحققت الشروط التالية معًا:
$$a_p\le1\quad\text{for all }p\equiv1\pmod4,$$
$$\sum_{q\equiv3\pmod4}\left\lfloor\frac{b_q}{2}\right\rfloor\le1.$$
الشرط السابق يعطي وصفًا ملموسًا جدًا. فالعدد Hilbert-squarefree لا بد أن يكون من أحد النوعين التاليين:
$$n\text{ is ordinarily squarefree.}$$
$$n=q^2m,\quad q\equiv3\pmod4,\quad q\text{ prime},\quad m\text{ ordinarily squarefree.}$$
وهذه الحالة الثانية وحيدة. فلو ساهم عددان أوليان مختلفان من نوع \(3\bmod4\) بجزء مربع، أو لو ظهر أحدهما بأس لا يقل عن \(4\)، لأصبحت مجموعات الجزء الصحيح السابقة على الأقل \(2\)، وذلك ممنوع.
لهذا يكون \(45=3^2\cdot5\) مسموحًا، بينما \(81=3^4\) غير مسموح.
لنرمز إلى دالة المؤشر للأعداد squarefree بالمعنى المعتاد بالرمز \(\mathbf{1}_{\mathrm{sqf}}(m)\). عندئذٍ لدينا الهوية القياسية
$$\mathbf{1}_{\mathrm{sqf}}(m)=\sum_{u^2\mid m}\mu(u).$$
وباستخدام التفكيك من الخطوة 2، يصبح مؤشر الأعداد Hilbert-squarefree هو
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\mathbf{1}_{\mathrm{sqf}}(n)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}}}\mathbf{1}_{q^2\mid n}\,\mathbf{1}_{\mathrm{sqf}}\!\left(\frac{n}{q^2}\right)\right).$$
الحد الأول يعد الأعداد التي لا تحتوي على أي عامل مربع أصلًا. أما الحد الثاني فيعيد إدخال الحالة المسموح بها التي يكون فيها الجزء المربع الوحيد هو عامل من الصورة \(q^2\) حيث \(q\equiv3\pmod4\).
إذا عوضنا بهوية موبيوس في مؤشري squarefree السابقين نحصل على
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\left(\sum_{u^2\mid n}\mu(u)+\sum_{\substack{q\equiv3\pmod4\\ q\text{ prime}\\ q^2\mid n}}\ \sum_{u^2\mid n/q^2}\mu(u)\right).$$
وفي المجموع المزدوج الثاني نعيد الفهرسة بوضع \(v=qu\). عندها تصبح جميع الحدود مساهمات من مربعات فردية \(v^2\mid n\):
$$I(n)=\mathbf{1}_{n\equiv1\pmod4}\sum_{\substack{v^2\mid n\\ v\text{ odd}}} c(v),$$
حيث
$$c(v)=\mu(v)+\sum_{\substack{q\mid v\\ q\equiv3\pmod4\\ q\text{ prime}}}\mu\!\left(\frac{v}{q}\right).$$
وهذه هي بالضبط صيغة المعاملات التي تستخدمها التنفيذات. فحد التصحيح يزيل المربعات غير المسموح بها مثل \(5^2\)، ويحافظ على الحالات المسموح بها مثل \(3^2\)، ثم يعيد طرح القوى الأعلى مثل \(3^4\).
لنعرّف
$$A(t)=\#\{m\le t:m\equiv1\pmod4\}=\left\lfloor\frac{t+3}{4}\right\rfloor.$$
لكل \(v\) فردي، فإن الشرط \(v^2\mid n\) مع \(n\equiv1\pmod4\) يكافئ كتابة
$$n=v^2m,\qquad m\equiv1\pmod4,$$
وذلك لأن \(v^2\equiv1\pmod4\). ومن ثم
$$S(N)=\sum_{\substack{v\ge1\\ v\text{ odd}}} c(v)\,A\!\left(\left\lfloor\frac{N}{v^2}\right\rfloor\right).$$
ولا يساهم إلا \(v\le\sqrt{N}\)، ولذلك نحصل في النهاية على
$$\boxed{S(N)=\sum_{\substack{1\le v\le\lfloor\sqrt{N}\rfloor\\ v\text{ odd}}} c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor.}$$
يوجد بالضبط \(25\) عددًا صحيحًا \(n\le99\) يحقق \(n\equiv1\pmod4\). وفي هذا المدى لا نحتاج إلا إلى القيم الفردية \(v\le9\).
المعاملات ذات الصلة هي
$$c(1)=1,\qquad c(3)=0,\qquad c(5)=-1,\qquad c(7)=0,\qquad c(9)=-1.$$
فالمعامل \(c(5)=-1\) يزيل مضاعفات \(25\)، بينما \(c(9)=-1\) يزيل مضاعفات \(81=(3^2)^2\). أما الحدّان الخاصان بـ \(3\) و\(7\) فينعدمان لأن وجود مربع واحد فقط من \(3^2\) أو \(7^2\) ما زال مسموحًا في سياق هيلبرت.
لذلك
$$S(99)=A(99)-A\!\left(\left\lfloor\frac{99}{25}\right\rfloor\right)-A\!\left(\left\lfloor\frac{99}{81}\right\rfloor\right)=25-1-1=23,$$
وهو تمامًا مقدار نقطة التحقق للأعداد الأصغر من \(100\).
تتبع تنفيذات C++ وPython وJava الخطة الحسابية نفسها. فهي أولًا تحوّل الحد الخارجي الاستبعادي \(X\) إلى حد شامل \(N=X-1\)، ثم تحسب \(U=\lfloor\sqrt{N}\rfloor\)، وبعد ذلك تخزن فقط القيم الفردية حتى \(U\). وهذا يقلل حجم الغربال إلى النصف مباشرة لأن كل جذر مربع ذي صلة \(v\) يكون فرديًا.
بعد ذلك يبني التنفيذ غربالًا للأعداد الأولية على القيم الفردية فقط، ويستخرج دالة موبيوس \(\mu(v)\) على هذه القيم، ويجمع الأعداد الأولية الموافقة لـ \(3\pmod4\). ثم يبدأ من معاملات الأساس \(\mu(v)\) ويضيف حد التصحيح \(\mu(v/q)\) على امتداد المضاعفات الفردية لكل عدد أولي \(q\equiv3\pmod4\)، وبهذا تتكوّن الأوزان النهائية \(c(v)\).
وفي النهاية يحسب
$$c(v)\left\lfloor\frac{\left\lfloor N/v^2\right\rfloor+3}{4}\right\rfloor$$
لكل \(v\) فردي لا يتجاوز \(U\)، ثم يجمع النتائج. وتستخدم نسخة C++ الصيغة نفسها لكنها تستطيع تقسيم المجموع الأخير إلى عدة مقاطع عند تفعيل التوازي، بينما تنفذ نسختا Python وJava الحساب نفسه على خيط واحد.
إذا وضعنا \(U=\lfloor\sqrt{N}\rfloor\)، فإن بناء غربال الأعداد الفردية وجدول موبيوس الفردي يحتاج إلى \(O(U\log\log U)\) زمنًا و\(O(U)\) ذاكرة. كما أن إضافة حدود التصحيح عبر مضاعفات الأعداد الأولية \(q\equiv3\pmod4\) لها السلوك التوافقي نفسه، ولذلك تبقى أيضًا ضمن \(O(U\log\log U)\).
أما التجميع النهائي فهو مرور خطي واحد على الفهارس الفردية، أي \(O(U)\). وبصورة إجمالية تكون الطريقة شبه خطية في \(\sqrt{N}\) وتستخدم \(O(U)\) من الذاكرة.