Let \(Q(N)\) denote the number of squarefree positive integers not exceeding \(N\). Problem 193 asks for \(Q(2^{50})\), where an integer is squarefree if no prime square divides it.
The implementations compute this count by turning the condition “has no square prime factor” into an exact divisor sum. This also matches the original wording “below \(2^{50}\)”, because \(2^{50}\) itself is divisible by \(4\) and therefore is not squarefree.
A direct approach would test each integer separately and look for a square divisor. The real solution reverses that viewpoint: instead of scanning numbers one by one, it counts how many integers are multiples of each square and combines those counts with Möbius signs.
Write \(\mu(d)\) for the Möbius function. For a fixed integer \(n\), consider
$$\sum_{d^2\mid n}\mu(d).$$
Only squarefree values of \(d\) can contribute, because \(\mu(d)=0\) whenever \(d\) contains a repeated prime factor. If \(S(n)\) is the set of primes whose squares divide \(n\), then every contributing \(d\) is the product of a subset of \(S(n)\). Therefore
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
If no prime square divides \(n\), then \(S(n)\) is empty and the sum is \(1\). Otherwise the sum is \(0\). So we obtain the exact indicator
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
This is inclusion-exclusion in a compact number-theoretic form: the squarefree condition is encoded by the square divisors \(d^2\).
Summing the indicator over \(1\le n\le N\) gives
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
Now interchange the order of summation. For a fixed \(d\), the condition \(d^2\mid n\) means that \(n\) is a multiple of \(d^2\), and there are exactly \(\left\lfloor N/d^2\right\rfloor\) such multiples. Hence
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
The upper limit is \(\lfloor\sqrt N\rfloor\) because the floor term becomes zero as soon as \(d^2>N\). For Problem 193 this means the whole computation only needs
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$$
Möbius values, not data up to \(2^{50}\).
For \(N=100\), only \(d\le 10\) matter. The nonzero Möbius values in that range are
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
while \(\mu(4)=\mu(8)=\mu(9)=0\). Substituting into the formula gives
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
Numerically,
$$Q(100)=100-25-11-4+2-2+1=61.$$
This matches the first checkpoint in the reference implementation and shows exactly how the alternating inclusion-exclusion terms combine.
Once the counting formula is known, the remaining task is to compute \(\mu(d)\) for every \(d\le \lfloor\sqrt N\rfloor\). The implementations do this with a linear sieve that maintains a prime list and a composite marker array.
The recurrence follows directly from the definition of \(\mu\):
$$\mu(1)=1.$$
If \(i\) is newly discovered to be prime, then \(\mu(i)=-1\). For each prime \(p\) and each current \(i\), form \(v=ip\). If \(p\mid i\), then \(p^2\mid v\), so \(\mu(v)=0\) and the inner loop stops for that \(i\). If \(p\nmid i\), then \(v\) gains one new distinct prime factor, so
$$\mu(v)=-\mu(i).$$
Because every composite number is generated once through its smallest prime factor, the Möbius table is filled in linear time up to \(\lfloor\sqrt N\rfloor\).
The C++, Python, and Java implementations all follow the same two-phase structure. First they set the target limit \(N\), compute \(M=\lfloor\sqrt N\rfloor\), and build the Möbius table \(\mu(1),\mu(2),\dots,\mu(M)\) with the linear-sieve recurrence above. The C++ version also supports a custom limit and can run built-in checkpoints at \(N=100\) and \(N=1024\).
After the sieve is complete, the implementations evaluate the exact formula
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
Terms with \(\mu(k)=0\) are skipped immediately, so only squarefree \(k\) contribute. The running total is accumulated in 64-bit integer arithmetic, which is sufficient here because \(k^2\le N=2^{50}\) and the final count is safely inside that range.
No implementation tests every integer up to \(N\) for square divisibility, and no implementation factors numbers near \(2^{50}\). All of the work is concentrated in the Möbius table up to \(2^{25}\) and the final divisor-sum pass.
Let \(M=\lfloor\sqrt N\rfloor\). The linear sieve runs in \(O(M)\) time, and the final summation over \(k=1,\dots,M\) is another \(O(M)\) pass. Therefore the total running time is
$$O(\sqrt N).$$
The memory usage is also \(O(M)\), coming from the Möbius array, the composite-marker array, and the prime list. For Problem 193 this means \(O(2^{25})\) storage rather than anything proportional to \(2^{50}\), which is exactly what makes the computation practical.
Sei \(Q(N)\) die Anzahl quadratfreier positiver Zahlen, die nicht größer als \(N\) sind. In Problem 193 wird \(Q(2^{50})\) gesucht; eine Zahl ist quadratfrei, wenn kein Primquadrat sie teilt.
Die Implementierungen berechnen diese Anzahl, indem sie die Bedingung „hat keinen quadratischen Primfaktor“ in eine exakte Teilersumme umformen. Das passt auch zur Formulierung „unterhalb von \(2^{50}\)“, denn \(2^{50}\) selbst ist durch \(4\) teilbar und damit nicht quadratfrei.
Ein naiver Zugang würde jede Zahl einzeln testen und nach einem quadratischen Teiler suchen. Die eigentliche Lösung dreht die Perspektive um: Statt Zahlen nacheinander zu prüfen, zählt sie für jedes Quadrat \(d^2\), wie viele Vielfache davon bis \(N\) vorkommen, und kombiniert diese Beiträge mit Möbius-Vorzeichen.
Bezeichne mit \(\mu(d)\) die Möbiusfunktion. Für ein festes \(n\) betrachten wir
$$\sum_{d^2\mid n}\mu(d).$$
Nur quadratfreie Werte von \(d\) können beitragen, denn \(\mu(d)=0\), sobald \(d\) einen wiederholten Primfaktor enthält. Sei \(S(n)\) die Menge aller Primzahlen, deren Quadrat \(n\) teilt. Dann ist jedes beitragende \(d\) das Produkt einer Teilmenge von \(S(n)\). Daher gilt
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
Ist \(S(n)\) leer, so ist die Summe \(1\); andernfalls ist sie \(0\). Damit erhalten wir den exakten Indikator
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
Das ist Inklusion-Exklusion in kompakter zahlentheoretischer Form: Die Quadratfreiheit wird vollständig über die Quadratdivisoren \(d^2\) kodiert.
Summiert man den Indikator über \(1\le n\le N\), so erhält man
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
Nun vertauschen wir die Summationsreihenfolge. Für festes \(d\) bedeutet \(d^2\mid n\), dass \(n\) ein Vielfaches von \(d^2\) ist, und davon gibt es genau \(\left\lfloor N/d^2\right\rfloor\). Also
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Die obere Grenze ist \(\lfloor\sqrt N\rfloor\), weil der Floor-Term verschwindet, sobald \(d^2>N\). Für Problem 193 braucht man also nur
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$$
Möbius-Werte und keine Daten bis \(2^{50}\).
Für \(N=100\) sind nur \(d\le 10\) relevant. Die von null verschiedenen Möbiuswerte in diesem Bereich sind
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
während \(\mu(4)=\mu(8)=\mu(9)=0\) gilt. Einsetzen liefert
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
Numerisch ergibt das
$$Q(100)=100-25-11-4+2-2+1=61.$$
Genau dieser Wert ist der erste Prüfpunkt der Referenzimplementierung und zeigt anschaulich, wie die alternierenden Inklusion-Exklusion-Terme zusammenspielen.
Ist die Zählformel einmal bekannt, muss man nur noch \(\mu(d)\) für alle \(d\le \lfloor\sqrt N\rfloor\) berechnen. Die Implementierungen erledigen das mit einem linearen Sieb, das eine wachsende Primliste und ein Komposit-Markierungsfeld verwaltet.
Die Rekursion folgt direkt aus der Definition von \(\mu\):
$$\mu(1)=1.$$
Wird \(i\) neu als Primzahl erkannt, dann ist \(\mu(i)=-1\). Für jede Primzahl \(p\) und jedes aktuelle \(i\) bildet man \(v=ip\). Gilt \(p\mid i\), dann teilt \(p^2\) die Zahl \(v\), also ist \(\mu(v)=0\), und die innere Schleife endet für dieses \(i\). Gilt \(p\nmid i\), dann erhält \(v\) genau einen neuen verschiedenen Primfaktor, also
$$\mu(v)=-\mu(i).$$
Da jede zusammengesetzte Zahl genau einmal über ihren kleinsten Primfaktor erzeugt wird, wird die Möbiustabelle bis \(\lfloor\sqrt N\rfloor\) in linearer Zeit gefüllt.
Die C++-, Python- und Java-Implementierungen folgen alle derselben Zweiphasenstruktur. Zuerst setzen sie das Ziel \(N\), berechnen \(M=\lfloor\sqrt N\rfloor\) und bauen mit der obigen linearen Sieb-Rekursion die Tabelle \(\mu(1),\mu(2),\dots,\mu(M)\) auf. Die C++-Version unterstützt zusätzlich ein frei wählbares Limit und eingebaute Prüfungen für \(N=100\) und \(N=1024\).
Nach Abschluss des Siebs werten die Implementierungen die exakte Formel
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor$$
aus. Terme mit \(\mu(k)=0\) werden sofort übersprungen, sodass nur quadratfreie \(k\) beitragen. Die laufende Summe wird mit 64-Bit-Ganzzahlarithmetik geführt; das reicht hier sicher aus, weil \(k^2\le N=2^{50}\) und auch das Endergebnis klar innerhalb dieses Bereichs liegt.
Keine Implementierung testet jede Zahl bis \(N\) einzeln auf Quadratteilbarkeit, und keine zerlegt Zahlen in der Nähe von \(2^{50}\). Die gesamte Arbeit steckt in der Möbiustabelle bis \(2^{25}\) und in einem einzigen Durchlauf über die Divisorsumme.
Sei \(M=\lfloor\sqrt N\rfloor\). Das lineare Sieb benötigt \(O(M)\) Zeit, und die abschließende Summe über \(k=1,\dots,M\) ist ein weiterer \(O(M)\)-Durchlauf. Insgesamt ergibt sich also
$$O(\sqrt N).$$
Der Speicherbedarf ist ebenfalls \(O(M)\), verursacht durch die Möbiustabelle, das Markierungsfeld für zusammengesetzte Zahlen und die Primliste. Für Problem 193 bedeutet das Speicher in der Größenordnung \(2^{25}\) statt irgendetwas proportional zu \(2^{50}\); genau dadurch wird die Rechnung praktikabel.
\(Q(N)\), \(N\)'i aşmayan squarefree pozitif tamsayıların sayısı olsun. Problem 193, \(Q(2^{50})\) değerini sorar; bir sayı, hiçbir asalın karesi onu bölmüyorsa squarefree'dir.
Uygulamalar bu sayımı, “kare asal çarpanı yok” koşulunu tam bir bölen toplamına çevirerek yapar. Bu yaklaşım, sorudaki “\(2^{50}\)'nin altında” ifadesiyle de uyumludur; çünkü \(2^{50}\) zaten \(4\)'e bölündüğü için squarefree değildir.
Naif yaklaşım her sayıyı tek tek inceleyip bir kare bölen arardı. Gerçek çözüm bakış açısını tersine çevirir: sayıları tek tek test etmek yerine, her \(d^2\) karesinin kaç sayıyı böldüğünü sayar ve bu katkıları Möbius işaretleriyle birleştirir.
\(\mu(d)\) Möbius fonksiyonu olsun. Sabit bir \(n\) için şu toplamı ele alalım:
$$\sum_{d^2\mid n}\mu(d).$$
Burada yalnızca squarefree \(d\) değerleri katkı verebilir; çünkü \(d\) tekrar eden bir asal çarpan içeriyorsa \(\mu(d)=0\) olur. \(S(n)\), karesi \(n\)'yi bölen asallar kümesi olsun. O zaman katkı veren her \(d\), \(S(n)\)'in bir alt kümesindeki asalların çarpımıdır. Dolayısıyla
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
Eğer \(n\)'yi bölen hiçbir asal karesi yoksa \(S(n)\) boştur ve toplam \(1\) olur; aksi halde toplam \(0\)'dır. Böylece tam gösterge fonksiyonunu elde ederiz:
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
Bu, dahil etme-dışlama ilkesinin sayılar kuramındaki sıkıştırılmış biçimidir: squarefree koşulu, \(d^2\) kare bölenleri üzerinden kodlanır.
Göstergeyi \(1\le n\le N\) aralığında toplarsak
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d)$$
elde edilir. Şimdi toplamların sırasını değiştiririz. Sabit bir \(d\) için \(d^2\mid n\) koşulu, \(n\)'nin \(d^2\)'nin katı olması demektir; bu sayılardan tam olarak \(\left\lfloor N/d^2\right\rfloor\) tane vardır. Bu yüzden
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Üst sınır \(\lfloor\sqrt N\rfloor\)'dür; çünkü \(d^2>N\) olduğunda taban fonksiyonu sıfır olur. Problem 193 için gereken en büyük değer
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$$
olduğu için programın \(2^{50}\)'ye kadar veri tutmasına gerek yoktur.
\(N=100\) için yalnızca \(d\le 10\) önemlidir. Bu aralıktaki sıfır olmayan Möbius değerleri
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
ve ayrıca \(\mu(4)=\mu(8)=\mu(9)=0\)'dır. Formüle yerleştirince
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor$$
çıkar. Sayısal olarak
$$Q(100)=100-25-11-4+2-2+1=61.$$
Bu, referans uygulamadaki ilk kontrol değeridir ve dahil etme-dışlama terimlerinin nasıl birleştiğini somut biçimde gösterir.
Sayım formülü bulunduğunda geriye yalnızca \(d\le \lfloor\sqrt N\rfloor\) için \(\mu(d)\) değerlerini hesaplamak kalır. Uygulamalar bunu, bir asal listesi ve bileşik işaretleme dizisi tutan lineer bir elek ile yapar.
Bağıntı doğrudan \(\mu\)'nün tanımından gelir:
$$\mu(1)=1.$$
Eğer \(i\) yeni keşfedilen bir asalsa \(\mu(i)=-1\) olur. Her asal \(p\) ve her güncel \(i\) için \(v=ip\) alınır. \(p\mid i\) ise \(p^2\mid v\) olur; dolayısıyla \(\mu(v)=0\) yazılır ve bu \(i\) için iç döngü durur. \(p\nmid i\) ise \(v\) tam bir yeni farklı asal çarpan kazanmıştır; o halde
$$\mu(v)=-\mu(i).$$
Her bileşik sayı en küçük asal çarpanı üzerinden tam bir kez üretildiği için, Möbius tablosu \(\lfloor\sqrt N\rfloor\)'ye kadar lineer zamanda doldurulur.
C++, Python ve Java uygulamalarının üçü de aynı iki aşamalı yapıyı izler. Önce hedef sınır \(N\) belirlenir, \(M=\lfloor\sqrt N\rfloor\) hesaplanır ve yukarıdaki lineer-elek bağıntısıyla \(\mu(1),\mu(2),\dots,\mu(M)\) tablosu kurulur. C++ sürümü ayrıca özel bir sınır alabilir ve \(N=100\) ile \(N=1024\) için yerleşik kontroller çalıştırabilir.
Eleğin ardından uygulamalar tam formülü hesaplar:
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
\(\mu(k)=0\) olan terimler anında atlanır; bu yüzden yalnızca squarefree \(k\) değerleri katkı yapar. Toplam 64 bit tamsayı aritmetiğiyle biriktirilir; bu yeterlidir çünkü \(k^2\le N=2^{50}\) ve nihai sonuç da rahatça bu aralıkta kalır.
Hiçbir uygulama \(N\)'ye kadar her sayıyı tek tek kare bölen açısından test etmez ve hiçbiri \(2^{50}\) civarındaki sayıları çarpanlarına ayırmaz. Bütün iş, \(2^{25}\)'e kadar olan Möbius tablosunda ve son bölen-toplamı geçişinde toplanır.
\(M=\lfloor\sqrt N\rfloor\) olsun. Lineer elek \(O(M)\) zamanda çalışır; \(k=1,\dots,M\) üzerindeki son toplam da ikinci bir \(O(M)\) geçişidir. Dolayısıyla toplam çalışma süresi
$$O(\sqrt N)$$
olur. Bellek kullanımı da Möbius dizisi, bileşik işaretleme dizisi ve asal listesi nedeniyle \(O(M)\)'dir. Problem 193 için bu, \(2^{50}\) ölçeğinde değil \(2^{25}\) ölçeğinde depolama demektir; hesabı uygulanabilir kılan tam olarak budur.
Sea \(Q(N)\) el número de enteros positivos libres de cuadrados que no exceden \(N\). El Problema 193 pide \(Q(2^{50})\); un número es libre de cuadrados si ningún cuadrado de un primo lo divide.
Las implementaciones calculan esa cantidad convirtiendo la condición “no tiene factor primo al cuadrado” en una suma exacta sobre divisores. Eso también coincide con la formulación “por debajo de \(2^{50}\)”, porque \(2^{50}\) es divisible por \(4\) y por lo tanto no es libre de cuadrados.
Un enfoque ingenuo probaría cada entero por separado y buscaría algún divisor cuadrado. La solución real invierte la perspectiva: en lugar de inspeccionar los números uno por uno, cuenta cuántos enteros son múltiplos de cada cuadrado \(d^2\) y combina esas cuentas con los signos de Möbius.
Sea \(\mu(d)\) la función de Möbius. Para un entero fijo \(n\), consideremos
$$\sum_{d^2\mid n}\mu(d).$$
Solo pueden contribuir los valores squarefree de \(d\), porque \(\mu(d)=0\) cuando \(d\) contiene un factor primo repetido. Si \(S(n)\) es el conjunto de primos cuyos cuadrados dividen a \(n\), entonces cada \(d\) que aporta es el producto de un subconjunto de \(S(n)\). Por tanto,
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
Si ningún cuadrado primo divide a \(n\), entonces \(S(n)\) es vacío y la suma vale \(1\). En caso contrario vale \(0\). Así obtenemos el indicador exacto
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
Esta es la inclusión-exclusión escrita en forma aritmética: la condición de ser libre de cuadrados queda codificada por los divisores cuadrados \(d^2\).
Si sumamos el indicador para \(1\le n\le N\), obtenemos
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
Ahora intercambiamos el orden de las sumas. Para un \(d\) fijo, la condición \(d^2\mid n\) significa que \(n\) es múltiplo de \(d^2\), y hay exactamente \(\left\lfloor N/d^2\right\rfloor\) múltiplos de ese tipo. Por eso
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
El límite superior es \(\lfloor\sqrt N\rfloor\), porque el término con piso se vuelve cero cuando \(d^2>N\). Para el Problema 193, eso significa que solo hacen falta
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$$
valores de Möbius, no datos hasta \(2^{50}\).
Para \(N=100\), solo importan los \(d\le 10\). Los valores no nulos de Möbius en ese rango son
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
mientras que \(\mu(4)=\mu(8)=\mu(9)=0\). Sustituyendo en la fórmula se obtiene
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
Numéricamente,
$$Q(100)=100-25-11-4+2-2+1=61.$$
Ese es exactamente el primer punto de verificación de la implementación de referencia y muestra con claridad cómo se combinan los términos alternantes de inclusión-exclusión.
Una vez obtenida la fórmula de conteo, solo queda calcular \(\mu(d)\) para todos los \(d\le \lfloor\sqrt N\rfloor\). Las implementaciones lo hacen con una criba lineal que mantiene una lista de primos y un arreglo de marcadores de compuestos.
La recurrencia sale directamente de la definición de \(\mu\):
$$\mu(1)=1.$$
Si \(i\) se descubre como primo, entonces \(\mu(i)=-1\). Para cada primo \(p\) y cada valor actual \(i\), se forma \(v=ip\). Si \(p\mid i\), entonces \(p^2\mid v\), así que \(\mu(v)=0\) y el bucle interno termina para ese \(i\). Si \(p\nmid i\), entonces \(v\) gana exactamente un nuevo factor primo distinto, de modo que
$$\mu(v)=-\mu(i).$$
Como cada número compuesto se genera una sola vez a través de su menor factor primo, la tabla de Möbius se llena en tiempo lineal hasta \(\lfloor\sqrt N\rfloor\).
Las implementaciones en C++, Python y Java siguen la misma estructura en dos fases. Primero fijan el límite \(N\), calculan \(M=\lfloor\sqrt N\rfloor\) y construyen la tabla \(\mu(1),\mu(2),\dots,\mu(M)\) con la recurrencia de criba lineal descrita arriba. La versión en C++ además permite usar un límite distinto y ejecutar comprobaciones internas en \(N=100\) y \(N=1024\).
Una vez terminada la criba, las implementaciones evalúan la fórmula exacta
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
Los términos con \(\mu(k)=0\) se descartan inmediatamente, así que solo contribuyen los \(k\) squarefree. La suma acumulada se mantiene con aritmética entera de 64 bits; eso basta aquí porque \(k^2\le N=2^{50}\) y el resultado final queda holgadamente dentro de ese rango.
Ninguna implementación prueba cada entero hasta \(N\) para ver si tiene un divisor cuadrado, y ninguna factoriza números cercanos a \(2^{50}\). Todo el trabajo real se concentra en la tabla de Möbius hasta \(2^{25}\) y en un solo barrido final de la suma sobre divisores.
Sea \(M=\lfloor\sqrt N\rfloor\). La criba lineal cuesta \(O(M)\) tiempo y la suma final sobre \(k=1,\dots,M\) es otro recorrido \(O(M)\). Por consiguiente, el tiempo total es
$$O(\sqrt N).$$
La memoria también es \(O(M)\), debido al arreglo de Möbius, al marcador de compuestos y a la lista de primos. Para el Problema 193 esto significa almacenar información del orden de \(2^{25}\), no del orden de \(2^{50}\), y esa es justamente la razón por la que el cálculo es viable.
设 \(Q(N)\) 表示不超过 \(N\) 的正整数中，无平方因子整数的个数。Problem 193 要求的是 \(Q(2^{50})\)；这里“无平方因子”指的是没有任何素数的平方能够整除该数。
这些实现并不是去逐个检测每个整数，而是把“没有平方素因子”这个条件改写成一个精确的除数求和公式。它也和题目里“低于 \(2^{50}\)”的说法一致，因为 \(2^{50}\) 本身能被 \(4\) 整除，所以根本不是无平方因子整数。
最朴素的思路，是对每个 \(n\) 单独判断是否存在某个 \(p^2\mid n\)。真正的解法完全换了角度：不是逐个检查整数，而是对每个平方 \(d^2\) 统计“有多少个数被它整除”，再用 Möbius 符号把这些计数做一次精确的包含-排除合并。
记 \(\mu(d)\) 为 Möbius 函数。对固定的整数 \(n\)，考虑
$$\sum_{d^2\mid n}\mu(d).$$
这里真正会产生贡献的只有 squarefree 的 \(d\)，因为一旦 \(d\) 含有重复素因子，就有 \(\mu(d)=0\)。设 \(S(n)\) 是所有满足 \(p^2\mid n\) 的素数集合，那么每个有贡献的 \(d\) 恰好对应于 \(S(n)\) 的一个子集乘积。因此
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
如果 \(n\) 没有任何平方素因子，那么 \(S(n)\) 为空，和就是 \(1\)；只要 \(S(n)\) 非空，和就变成 \(0\)。于是得到完全精确的指示函数
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
这就是包含-排除在数论中的紧凑写法：squarefree 条件被编码进了所有平方除数 \(d^2\)。
把这个指示函数对 \(1\le n\le N\) 求和，就得到
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
接下来交换求和顺序。对固定的 \(d\)，条件 \(d^2\mid n\) 等价于“\(n\) 是 \(d^2\) 的倍数”，而这样的 \(n\) 恰好有 \(\left\lfloor N/d^2\right\rfloor\) 个，所以
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
这里的上界是 \(\lfloor\sqrt N\rfloor\)，因为一旦 \(d^2>N\)，对应的地板函数就为零。对 Problem 193 来说，这意味着真正需要的最大范围只有
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432,$$
也就是说，程序只需要算到 \(2^{25}\) 的 Möbius 值，而不需要接近 \(2^{50}\) 的任何逐项处理。
为了让这个公式更直观，可以把 \(N=100\) 完整算一遍。此时只有 \(d\le 10\) 会有贡献。该范围内非零的 Möbius 值是
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
而 \(\mu(4)=\mu(8)=\mu(9)=0\)。代入公式后有
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
把数字写出来就是
$$Q(100)=100-25-11-4+2-2+1=61.$$
这正好对应参考实现里的第一个检查值，也很好地说明了这些交替符号的项如何精确抵消重叠计数。
有了计数公式之后，剩下的任务就是计算所有 \(d\le \lfloor\sqrt N\rfloor\) 的 \(\mu(d)\)。三份实现都采用线性筛，同时维护一个素数表和一个合数标记数组。
它使用的递推直接来自 \(\mu\) 的定义：
$$\mu(1)=1.$$
如果某个 \(i\) 在筛过程中第一次出现时就没有被标记为合数，那么它是素数，于是 \(\mu(i)=-1\)。对每个素数 \(p\) 和当前的 \(i\)，令 \(v=ip\)。如果 \(p\mid i\)，那么 \(p^2\mid v\)，所以 \(\mu(v)=0\)，并且这个 \(i\) 的内部循环立刻停止。如果 \(p\nmid i\)，那么 \(v\) 只是多了一个新的不同素因子，因此
$$\mu(v)=-\mu(i).$$
由于每个合数都会通过它的最小素因子被生成恰好一次，所以整张 Möbius 表可以在线性时间内填到 \(\lfloor\sqrt N\rfloor\)。
C++、Python 和 Java 三个实现都遵循同样的两阶段结构。第一阶段先确定目标上界 \(N\)，再计算 \(M=\lfloor\sqrt N\rfloor\)，然后用上面的线性筛递推构造 \(\mu(1),\mu(2),\dots,\mu(M)\)。其中 C++ 版本还支持自定义上界，并且内置了 \(N=100\) 和 \(N=1024\) 两个校验点。
筛完之后，程序直接计算精确公式
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
凡是 \(\mu(k)=0\) 的项都会被立即跳过，所以真正有贡献的只是不含平方因子的 \(k\)。累加过程使用 64 位整数；这在这里完全足够，因为 \(k^2\le N=2^{50}\)，而最终答案也远远没有接近 64 位整数的极限。
实现从来不会把 \(1\) 到 \(N\) 的所有整数逐个拿出来检测，也不会去分解接近 \(2^{50}\) 的大数。全部实质工作都压缩在“先算到 \(2^{25}\) 的 Möbius 表，再跑一次除数求和”这两个步骤里。
令 \(M=\lfloor\sqrt N\rfloor\)。线性筛的时间复杂度是 \(O(M)\)，最后对 \(k=1,\dots,M\) 的求和又是一次 \(O(M)\) 遍历，因此总时间复杂度为
$$O(\sqrt N).$$
空间复杂度同样是 \(O(M)\)，主要来自 Möbius 数组、合数标记数组和素数表。对 Problem 193 而言，这意味着需要的是 \(2^{25}\) 量级的存储，而不是任何与 \(2^{50}\) 同量级的结构，这正是算法可行的根本原因。
Пусть \(Q(N)\) обозначает число квадратсвободных положительных целых, не превосходящих \(N\). В задаче 193 требуется найти \(Q(2^{50})\); число называется квадратсвободным, если никакой квадрат простого числа его не делит.
Реализации вычисляют это количество, переписывая условие «нет квадратного простого делителя» в виде точной суммы по делителям. Это также согласуется с формулировкой «ниже \(2^{50}\)», потому что \(2^{50}\) само делится на \(4\) и потому не является квадратсвободным.
Наивное решение проверяло бы каждое число по отдельности и искало у него квадратный делитель. Настоящее решение переворачивает задачу: оно не перебирает числа по одному, а считает, сколько чисел делится на каждый квадрат \(d^2\), после чего объединяет эти количества с помощью знаков функции Мёбиуса.
Обозначим через \(\mu(d)\) функцию Мёбиуса. Для фиксированного \(n\) рассмотрим сумму
$$\sum_{d^2\mid n}\mu(d).$$
Ненулевой вклад дают только квадратсвободные \(d\), поскольку \(\mu(d)=0\), как только в \(d\) появляется повторяющийся простой множитель. Пусть \(S(n)\) - множество всех простых \(p\), для которых \(p^2\mid n\). Тогда каждый вносящий вклад делитель \(d\) есть произведение элементов некоторого подмножества \(S(n)\). Следовательно,
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
Если квадрат простого числа не делит \(n\), то \(S(n)\) пусто и сумма равна \(1\). Во всех остальных случаях сумма равна \(0\). Значит, мы получаем точный индикатор
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
Это и есть принцип включения-исключения в компактной арифметической записи: условие квадратсвободности кодируется квадратными делителями \(d^2\).
Просуммируем этот индикатор по всем \(1\le n\le N\):
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
Теперь меняем порядок суммирования. Для фиксированного \(d\) условие \(d^2\mid n\) означает, что \(n\) кратно \(d^2\), а таких чисел ровно \(\left\lfloor N/d^2\right\rfloor\). Поэтому
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
Верхняя граница равна \(\lfloor\sqrt N\rfloor\), потому что при \(d^2>N\) выражение под полом становится нулем. Для задачи 193 это означает, что нужно знать значения Мёбиуса лишь до
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432,$$
а не работать напрямую на масштабе \(2^{50}\).
При \(N=100\) имеют значение только \(d\le 10\). Ненулевые значения функции Мёбиуса на этом диапазоне равны
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
а \(\mu(4)=\mu(8)=\mu(9)=0\). Подстановка в формулу дает
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
Численно это равно
$$Q(100)=100-25-11-4+2-2+1=61.$$
Именно это значение используется как первая контрольная точка в эталонной реализации и наглядно показывает, как работают чередующиеся члены включения-исключения.
После вывода формулы подсчета остается вычислить \(\mu(d)\) для всех \(d\le \lfloor\sqrt N\rfloor\). Реализации делают это линейным решетом, поддерживая список простых чисел и массив отметок составных.
Используемая рекурсия напрямую следует из определения \(\mu\):
$$\mu(1)=1.$$
Если число \(i\) впервые встречается как непромеченное, то оно простое, и \(\mu(i)=-1\). Для каждого простого \(p\) и текущего \(i\) образуется \(v=ip\). Если \(p\mid i\), то \(p^2\mid v\), значит \(\mu(v)=0\), и внутренний цикл для этого \(i\) завершается. Если \(p\nmid i\), то \(v\) получает ровно один новый простой множитель, поэтому
$$\mu(v)=-\mu(i).$$
Поскольку каждое составное число порождается ровно один раз через свой наименьший простой делитель, таблица Мёбиуса заполняется за линейное время до \(\lfloor\sqrt N\rfloor\).
Реализации на C++, Python и Java используют одну и ту же двухфазную схему. Сначала задается предел \(N\), вычисляется \(M=\lfloor\sqrt N\rfloor\), а затем по описанной выше линейной рекурсии строится таблица \(\mu(1),\mu(2),\dots,\mu(M)\). Версия на C++ дополнительно позволяет задать другой предел и выполнить встроенные проверки на \(N=100\) и \(N=1024\).
После завершения решета программы вычисляют точную формулу
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
Члены с \(\mu(k)=0\) сразу пропускаются, так что вклад дают только квадратсвободные \(k\). Накопление суммы ведется в 64-битной целочисленной арифметике; этого здесь достаточно, потому что \(k^2\le N=2^{50}\), а итоговое значение тоже далеко от переполнения.
Ни одна реализация не проверяет по отдельности все числа до \(N\) на делимость квадратом и не факторизует числа порядка \(2^{50}\). Вся работа сведена к таблице Мёбиуса до \(2^{25}\) и к одному проходу по итоговой сумме.
Пусть \(M=\lfloor\sqrt N\rfloor\). Линейное решето работает за \(O(M)\), а заключительное суммирование по \(k=1,\dots,M\) - это еще один проход за \(O(M)\). Следовательно, полное время работы равно
$$O(\sqrt N).$$
Память также имеет порядок \(O(M)\): ее требуют массив значений Мёбиуса, массив пометок составных чисел и список простых. Для задачи 193 это означает хранение данных масштаба \(2^{25}\), а не чего-то соизмеримого с \(2^{50}\), и именно это делает вычисление осуществимым.
ليكن \(Q(N)\) هو عدد الأعداد الصحيحة الموجبة الخالية من المربعات التي لا تتجاوز \(N\). تطلب المسألة 193 إيجاد \(Q(2^{50})\)، حيث يكون العدد خاليًا من المربعات إذا لم يقسمه مربع أي عدد أولي.
تقوم التطبيقات بحساب هذا العدد عبر تحويل الشرط «لا يملك عاملًا أوليًا مربعًا» إلى مجموع دقيق على القواسم. وهذا منسجم أيضًا مع صياغة «أقل من \(2^{50}\)»، لأن \(2^{50}\) نفسه يقبل القسمة على \(4\)، ولذلك فهو ليس عددًا خاليًا من المربعات.
الطريقة الساذجة كانت ستفحص كل عدد على حدة لتتحقق من وجود قاسم مربّع. أمّا الحل الحقيقي فيعكس زاوية النظر: بدل فحص الأعداد واحدًا واحدًا، يعدّ كم عددًا يقبل القسمة على كل مربع \(d^2\)، ثم يجمع هذه الأعداد بإشارات دالة موبيوس.
لنكتب \(\mu(d)\) لدالة موبيوس. لعدد ثابت \(n\)، تأمل المجموع
$$\sum_{d^2\mid n}\mu(d).$$
لا تسهم إلا قيم \(d\) الخالية من المربعات، لأن \(\mu(d)=0\) متى احتوى \(d\) على عامل أولي مكرر. إذا رمزنا بـ \(S(n)\) إلى مجموعة الأعداد الأولية التي تقسم مربعاتها العدد \(n\)، فإن كل \(d\) مسهم هو حاصل ضرب مجموعة جزئية من عناصر \(S(n)\). ومن ثم
$$\sum_{d^2\mid n}\mu(d)=\sum_{T\subseteq S(n)}(-1)^{|T|}=(1-1)^{|S(n)|}.$$
إذا كانت \(S(n)\) فارغة، أي لا يوجد مربع أولي يقسم \(n\)، فالمجموع يساوي \(1\). وإذا لم تكن فارغة، فالمجموع يساوي \(0\). وهكذا نحصل على دالة المؤشر الدقيقة
$$\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{d^2\mid n}\mu(d).$$
وهذه ليست إلا مبدأ الشمول والاستبعاد في صورة عددية مضغوطة: شرط الخلو من المربعات مُشفَّر بالكامل عبر القواسم المربعة \(d^2\).
إذا جمعنا دالة المؤشر على جميع \(1\le n\le N\)، نحصل على
$$Q(N)=\sum_{n\le N}\mathbf{1}_{\mathrm{sqfree}}(n)=\sum_{n\le N}\sum_{d^2\mid n}\mu(d).$$
ثم نبدل ترتيب الجمع. فبالنسبة إلى \(d\) ثابت، الشرط \(d^2\mid n\) يعني أن \(n\) مضاعف لـ \(d^2\)، وعدد هذه المضاعفات هو بالضبط \(\left\lfloor N/d^2\right\rfloor\). لذلك
$$Q(N)=\sum_{d\le \sqrt N}\mu(d)\left\lfloor\frac{N}{d^2}\right\rfloor.$$
والحد الأعلى هو \(\lfloor\sqrt N\rfloor\)، لأن قيمة الجزء الصحيح تصبح صفرًا متى صار \(d^2>N\). وفي هذه المسألة لا نحتاج إلا إلى
$$\lfloor\sqrt{2^{50}}\rfloor=2^{25}=33{,}554{,}432$$
قيمة من دالة موبيوس، لا إلى أي معالجة قريبة من الحجم \(2^{50}\).
عندما يكون \(N=100\)، لا يهم إلا \(d\le 10\). القيم غير الصفرية لدالة موبيوس في هذا المجال هي
$$\mu(1)=1,\ \mu(2)=-1,\ \mu(3)=-1,\ \mu(5)=-1,\ \mu(6)=1,\ \mu(7)=-1,\ \mu(10)=1,$$
بينما \(\mu(4)=\mu(8)=\mu(9)=0\). بالتعويض في الصيغة نحصل على
$$Q(100)=\left\lfloor\frac{100}{1^2}\right\rfloor-\left\lfloor\frac{100}{2^2}\right\rfloor-\left\lfloor\frac{100}{3^2}\right\rfloor-\left\lfloor\frac{100}{5^2}\right\rfloor+\left\lfloor\frac{100}{6^2}\right\rfloor-\left\lfloor\frac{100}{7^2}\right\rfloor+\left\lfloor\frac{100}{10^2}\right\rfloor.$$
وبالأعداد الصريحة:
$$Q(100)=100-25-11-4+2-2+1=61.$$
وهذا يطابق أول نقطة تحقق في التطبيق المرجعي، ويبين بوضوح كيف تتكامل حدود الشمول والاستبعاد ذات الإشارات المتناوبة.
بعد الوصول إلى صيغة العد، يبقى فقط حساب \(\mu(d)\) لكل \(d\le \lfloor\sqrt N\rfloor\). تنفذ التطبيقات ذلك عبر غربال خطي يحافظ على قائمة بالأعداد الأولية ومصفوفة لوضع علامات على الأعداد المركبة.
العلاقة المستعملة تأتي مباشرة من تعريف \(\mu\):
$$\mu(1)=1.$$
إذا ظهر \(i\) لأول مرة من دون أن يكون مركبًا، فهو عدد أولي ومن ثم \(\mu(i)=-1\). ولكل عدد أولي \(p\) ولكل \(i\) حالي نكوّن \(v=ip\). إذا كان \(p\mid i\)، فإن \(p^2\mid v\)، وعندها \(\mu(v)=0\) وتتوقف الحلقة الداخلية لذلك \(i\). وإذا كان \(p\nmid i\)، فإن \(v\) يكتسب عاملًا أوليًا متميزًا جديدًا واحدًا، ولذلك
$$\mu(v)=-\mu(i).$$
ولأن كل عدد مركب يُولَّد مرة واحدة فقط عبر أصغر عامل أولي له، فإن جدول موبيوس يُملأ بزمن خطي حتى \(\lfloor\sqrt N\rfloor\).
تتبع تطبيقات C++ وPython وJava جميعها البنية نفسها ذات المرحلتين. أولًا تحدد الحد \(N\)، ثم تحسب \(M=\lfloor\sqrt N\rfloor\)، وبعد ذلك تبني جدول \(\mu(1),\mu(2),\dots,\mu(M)\) باستخدام غربال موبيوس الخطي السابق. إصدار C++ يسمح كذلك بحد مخصص، ويمكنه تشغيل نقطتي تحقق داخليتين عند \(N=100\) و\(N=1024\).
بعد اكتمال الغربال، تُقيِّم التطبيقات الصيغة الدقيقة
$$Q(N)=\sum_{k=1}^{M}\mu(k)\left\lfloor\frac{N}{k^2}\right\rfloor.$$
وتُتخطى فورًا الحدود التي تحقق \(\mu(k)=0\)، فلا يبقى إلا \(k\) الخالي من المربعات. ويُجمع الناتج باستعمال حساب صحيح من 64 بت، وهذا كافٍ هنا لأن \(k^2\le N=2^{50}\) ولأن العدد النهائي يبقى بعيدًا عن حدود هذا النوع العددي.
لا يوجد أي تنفيذ يفحص جميع الأعداد حتى \(N\) واحدًا واحدًا من أجل القابلية للقسمة على مربع، ولا يوجد أي تنفيذ يقوم بتحليل أعداد قريبة من \(2^{50}\) إلى عواملها. كل العمل الفعلي ينحصر في جدول موبيوس حتى \(2^{25}\) ثم مرور نهائي واحد على مجموع القواسم.
ليكن \(M=\lfloor\sqrt N\rfloor\). يعمل الغربال الخطي بزمن \(O(M)\)، كما أن الجمع النهائي على \(k=1,\dots,M\) هو مرور آخر بتكلفة \(O(M)\). إذن الزمن الكلي هو
$$O(\sqrt N).$$
أما الذاكرة فهي أيضًا \(O(M)\)، بسبب مصفوفة موبيوس، ومصفوفة تعليم الأعداد المركبة، وقائمة الأعداد الأولية. وفي المسألة 193 يعني ذلك تخزينًا بحجم \(2^{25}\) تقريبًا بدل أي شيء متناسب مع \(2^{50}\)، وهذا هو سبب كون الحساب عمليًا.