We must count positive integers \(n \le N\) whose number of divisors satisfies
$$\tau(n)\equiv 1 \pmod{6}.$$
The C++, Python, and Java implementations evaluate this count for \(N=10^{36}\). A direct scan up to \(10^{36}\) is impossible, so the solution rewrites the divisor condition into a rigid factorization pattern and then counts those patterns efficiently.
Write the prime factorization of \(n\) as
$$n=\prod_i p_i^{e_i}.$$
Then the divisor-count function is
$$\tau(n)=\prod_i (e_i+1).$$
The problem is therefore to characterize exactly when this product is congruent to \(1\) modulo \(6\).
If a product is congruent to \(1\) modulo \(6\), then it is odd and also not divisible by \(3\). Hence every factor \(e_i+1\) must itself be odd and must avoid divisibility by \(3\). The only possible residue classes are
$$e_i+1\equiv 1 \text{ or } 5 \pmod{6}.$$
Equivalently, every exponent must satisfy
$$e_i\equiv 0 \text{ or } 4 \pmod{6}.$$
So an integer contributes exactly when each prime exponent is of the form \(6k\) or \(6k+4\). No other residue class can appear.
For each prime exponent write
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
Now define
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
Then
$$n=a^6 b^4.$$
The integer \(b\) is squarefree because each prime enters it at most once. There is no need to impose \(\gcd(a,b)=1\): a prime may appear in both factors, and the exponent formula still stays unique because \(\beta_i\) records whether the residue class is \(0\) or \(4\) modulo \(6\).
Conversely, any number of the form \(a^6 b^4\) with squarefree \(b\) has prime exponents \(6k\) or \(6k+4\), so this description is exact.
If a prime contributes only through \(a^6\), then its divisor factor is
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
If that prime also appears in \(b\), then the exponent becomes \(6\alpha_i+4\), so
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
Therefore
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
where \(\omega(b)\) denotes the number of distinct prime factors of \(b\). Hence
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ is even}.$$
The original problem is now equivalent to counting pairs \((a,b)\) such that
$$a^6 b^4\le N,$$
\(b\) is squarefree, and \(b\) has an even number of distinct prime factors.
Fix \(a\). Then \(b\) must satisfy
$$b\le \left(\frac{N}{a^6}\right)^{1/4}.$$
Define
$$E(x)=\#\{b\le x:\ b\text{ squarefree and }\omega(b)\text{ even}\}.$$
Then the desired count becomes
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
This is exactly the outer summation implemented by the program.
Let
$$Q(x)=\#\{n\le x:\ n\text{ is squarefree}\}.$$
The classical Möbius inversion identity for the squarefree indicator is
$$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d),$$
so summing over \(n\le x\) gives
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
Now split the squarefree numbers into two classes: \(E(x)\) for even \(\omega\), and \(O(x)\) for odd \(\omega\). Then
$$Q(x)=E(x)+O(x).$$
On squarefree integers we have
$$\mu(n)=(-1)^{\omega(n)},$$
hence the Mertens function
$$M(x)=\sum_{n\le x}\mu(n)$$
satisfies
$$M(x)=E(x)-O(x).$$
Solving the two linear equations gives the key formula
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
So the problem reduces to repeated evaluations of a squarefree summatory function and a Mertens summatory function.
Here
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
so only \(a=1\) and \(a=2\) are possible.
For \(a=1\), we have
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
The squarefree integers up to \(3\) are \(1,2,3\). Their values of \(\omega\) are \(0,1,1\), so only \(1\) has even parity. This contributes \(1\).
For \(a=2\), we have
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
so again the contribution is \(1\).
Therefore
$$F(100)=1+1=2.$$
The two valid integers are \(1\) and \(64=2^6\). By contrast, \(16=2^4\) is excluded because then \(\omega(b)=1\), so \(\tau(16)=5\not\equiv 1 \pmod{6}\).
The implementation first precomputes Möbius values up to a fixed cutoff using a sieve, and from that it builds prefix sums for both \(\mu(n)\) and the squarefree indicator. Those prefix tables immediately answer small queries for \(Q(x)\) and \(M(x)\).
For larger arguments, the Mertens function is evaluated with the standard quotient-grouped recursion: values of \(\left\lfloor n/k\right\rfloor\) repeat over long intervals, so the recursion processes equal-quotient blocks together and stores the results in a memo table. The squarefree count \(Q(x)\) is obtained directly from the Möbius summation formula above.
Finally, the C++, Python, and Java implementations iterate over all \(a\le \lfloor N^{1/6}\rfloor\), compute the exact fourth-root bound for \(b\), evaluate \(E(x)=(Q(x)+M(x))/2\), and add that contribution to the answer. The integer-root calculations are corrected after the floating-point estimate, and the large-integer variants use wider arithmetic so that boundary cases near perfect powers are handled exactly.
Let
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
The outer summation has \(A\) iterations. The sieve-style preprocessing up to the fixed cutoff costs linear or near-linear time in that cutoff and the same order of memory. Each squarefree query uses the sum
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
so its direct part is \(O(\sqrt{x})\), with \(x\le X\). The Mertens queries benefit from memoization over quotient blocks, so repeated large values are reused instead of recomputed. For the target problem, \(X=10^9\), hence \(\sqrt{X}\approx 31623\), which makes this strategy entirely practical. It is vastly faster than enumerating or factoring every \(n\le N\).
Gesucht ist die Anzahl positiver ganzer Zahlen \(n \le N\), deren Teileranzahl die Kongruenz
$$\tau(n)\equiv 1 \pmod{6}$$
erfüllt. Die C++-, Python- und Java-Implementierungen berechnen diese Anzahl für \(N=10^{36}\). Ein direkter Durchlauf bis zu dieser Größe ist unmöglich, daher wird die Bedingung auf \(\tau(n)\) in eine starre Faktorisierungsform übersetzt und dann effizient gezählt.
Schreibe die Primfaktorzerlegung von \(n\) als
$$n=\prod_i p_i^{e_i}.$$
Dann gilt für die Teilerfunktion
$$\tau(n)=\prod_i (e_i+1).$$
Also müssen wir genau verstehen, wann dieses Produkt modulo \(6\) gleich \(1\) ist.
Ist ein Produkt modulo \(6\) gleich \(1\), dann ist es ungerade und nicht durch \(3\) teilbar. Also muss jeder Faktor \(e_i+1\) selbst ungerade sein und darf nicht durch \(3\) teilbar sein. Damit bleiben nur die Restklassen
$$e_i+1\equiv 1 \text{ oder } 5 \pmod{6}.$$
Äquivalent dazu gilt für jeden Exponenten
$$e_i\equiv 0 \text{ oder } 4 \pmod{6}.$$
Genau diese beiden Restklassen sind erlaubt. Jede gültige Zahl besitzt also nur Primexponenten der Form \(6k\) oder \(6k+4\).
Für jeden Primexponenten schreiben wir
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
Definiere nun
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
Dann folgt sofort
$$n=a^6 b^4.$$
Die Zahl \(b\) ist quadratfrei, weil jede Primzahl höchstens einmal in \(b\) vorkommt. Eine Bedingung \(\gcd(a,b)=1\) ist nicht nötig: eine Primzahl darf in beiden Faktoren auftreten, und die Darstellung bleibt trotzdem eindeutig, weil \(\beta_i\) exakt speichert, ob der Exponent \(0\) oder \(4\) modulo \(6\) ist.
Umgekehrt liefert jede Darstellung \(a^6 b^4\) mit quadratfreiem \(b\) genau Exponenten der Form \(6k\) oder \(6k+4\). Die Beschreibung ist also vollständig.
Wenn eine Primzahl nur über \(a^6\) beiträgt, dann ist ihr Faktor in \(\tau(n)\)
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
Wenn dieselbe Primzahl zusätzlich in \(b\) vorkommt, dann ist der Exponent \(6\alpha_i+4\), also
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
Daher gilt insgesamt
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
wobei \(\omega(b)\) die Anzahl verschiedener Primteiler von \(b\) bezeichnet. Also
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ gerade ist}.$$
Das ursprüngliche Problem ist damit äquivalent zum Zählen aller Paare \((a,b)\) mit
$$a^6 b^4\le N,$$
wobei \(b\) quadratfrei ist und eine gerade Anzahl verschiedener Primfaktoren besitzt.
Fixiere \(a\). Dann muss
$$b\le \left(\frac{N}{a^6}\right)^{1/4}$$
gelten. Definiere
$$E(x)=\#\{b\le x:\ b\text{ quadratfrei und }\omega(b)\text{ gerade}\}.$$
Damit erhält man die Summenformel
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
Genau diese äußere Summe wird im Programm ausgewertet.
Setze
$$Q(x)=\#\{n\le x:\ n\text{ ist quadratfrei}\}.$$
Für den Indikator quadratfreier Zahlen gilt klassisch
$$1_{\text{quadratfrei}}(n)=\sum_{d^2\mid n}\mu(d),$$
und nach Summation über \(n\le x\) folgt
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
Zerlege nun die quadratfreien Zahlen in zwei Klassen: \(E(x)\) mit gerader \(\omega\) und \(O(x)\) mit ungerader \(\omega\). Dann gilt
$$Q(x)=E(x)+O(x).$$
Auf quadratfreien Zahlen ist
$$\mu(n)=(-1)^{\omega(n)},$$
daher erfüllt die Mertens-Funktion
$$M(x)=\sum_{n\le x}\mu(n)$$
die Beziehung
$$M(x)=E(x)-O(x).$$
Aus diesen beiden linearen Gleichungen folgt sofort
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
Damit reduziert sich das Problem auf wiederholte Auswertung einer quadratfreien Summenfunktion und der Mertens-Funktion.
Hier ist
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
also kommen nur \(a=1\) und \(a=2\) vor.
Für \(a=1\) erhält man
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
Die quadratfreien Zahlen bis \(3\) sind \(1,2,3\). Ihre Werte von \(\omega\) sind \(0,1,1\), also zählt nur die \(1\). Beitrag: \(1\).
Für \(a=2\) gilt
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
also erneut Beitrag \(1\).
Damit folgt
$$F(100)=1+1=2.$$
Die beiden gültigen Zahlen sind \(1\) und \(64=2^6\). Dagegen ist \(16=2^4\) ausgeschlossen, weil dann \(\omega(b)=1\) ungerade ist und somit \(\tau(16)=5\not\equiv 1 \pmod{6}\).
Die Implementierung berechnet zunächst die Möbius-Werte bis zu einer festen Grenze mit einem Sieb und bildet daraus Präfixsummen sowohl für \(\mu(n)\) als auch für den Indikator quadratfreier Zahlen. Kleine Anfragen an \(Q(x)\) und \(M(x)\) können dadurch sofort beantwortet werden.
Für größere Argumente wird die Mertens-Funktion mit der üblichen nach Quotienten gruppierten Rekursion berechnet: Werte von \(\left\lfloor n/k\right\rfloor\) wiederholen sich über längere Intervalle, daher werden ganze Blöcke mit gleichem Quotienten zusammengefasst und das Ergebnis wird zwischengespeichert. Der Wert \(Q(x)\) wird direkt mit der Möbius-Summenformel ausgewertet.
Anschließend laufen die C++-, Python- und Java-Implementierungen über alle \(a\le \lfloor N^{1/6}\rfloor\), bestimmen die exakte Schranke für \(b\), berechnen \(E(x)=(Q(x)+M(x))/2\) und addieren den Beitrag. Die Ganzzahlwurzeln werden nach der Gleitkommaschätzung korrigiert, und die Varianten für große Zahlen verwenden breitere Arithmetik, damit Randfälle nahe perfekter Potenzen exakt behandelt werden.
Setze
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
Die äußere Summe besitzt \(A\) Iterationen. Die Vorverarbeitung mit dem Sieb kostet lineare oder nahezu lineare Zeit in der gewählten Grenze und denselben Größenordnungs-Speicher. Jede Anfrage an die quadratfreie Summenfunktion verwendet
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
also \(O(\sqrt{x})\) Arbeit mit \(x\le X\). Die Mertens-Werte profitieren von Memoisierung über Quotientenblöcke, sodass große Argumente nicht immer neu berechnet werden. Für das Zielproblem gilt \(X=10^9\), also \(\sqrt{X}\approx 31623\); damit ist diese Strategie praktisch gut beherrschbar und viel schneller als das direkte Aufzählen oder Faktorisieren aller \(n\le N\).
Aranan şey, bölen sayısı
$$\tau(n)\equiv 1 \pmod{6}$$
koşulunu sağlayan \(n \le N\) pozitif tamsayılarının sayısıdır. C++, Python ve Java uygulamaları bu değeri \(N=10^{36}\) için hesaplar. \(10^{36}\)'ya kadar doğrudan tarama yapmak imkansız olduğundan çözüm, bölen fonksiyonu koşulunu özel bir üs yapısına dönüştürüp bu yapıları sayar.
\(n\)'in asal çarpanlara ayrılışı
$$n=\prod_i p_i^{e_i}$$
olsun. O zaman bölen sayısı
$$\tau(n)=\prod_i (e_i+1)$$
olur. Dolayısıyla problem, bu çarpımın ne zaman \(6\) modunda \(1\) verdiğini anlamaya indirgenir.
Bir çarpım \(6\) modunda \(1\) ise hem tektir hem de \(3\)'e bölünmez. Bu yüzden her bir çarpan \(e_i+1\) de tek olmalı ve \(3\)'e bölünmemelidir. Geriye yalnızca şu iki sınıf kalır:
$$e_i+1\equiv 1 \text{ veya } 5 \pmod{6}.$$
Buna eşdeğer olarak her üs için
$$e_i\equiv 0 \text{ veya } 4 \pmod{6}$$
yazabiliriz. Demek ki geçerli sayılar tam olarak bütün asal üsleri \(6k\) veya \(6k+4\) biçiminde olan sayılardır.
Her asal üs için
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}$$
yazalım. Sonra
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i$$
tanımlarını yapalım. Böylece
$$n=a^6 b^4$$
elde edilir. \(b\) squarefree'dir; çünkü her asal en fazla bir kez \(b\)'ye girer. Ayrıca \(\gcd(a,b)=1\) şartı gerekmez: aynı asal hem \(a\)'da hem \(b\)'de bulunabilir ve temsil yine de tektir; çünkü \(\beta_i\) ilgili üssün \(6\)'ya göre kalanın \(0\) mı \(4\) mü olduğunu belirler.
Ters yönde de, squarefree \(b\) ile yazılan her \(a^6 b^4\) ifadesi asal üsleri \(6k\) veya \(6k+4\) yapar. Yani bu karakterizasyon eksiksizdir.
Bir asal yalnızca \(a^6\) üzerinden geliyorsa ilgili bölen çarpanı
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}$$
olur. Aynı asal \(b\)'de de varsa üs \(6\alpha_i+4\) olur ve
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}$$
elde edilir. Dolayısıyla
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6}$$
olur; burada \(\omega(b)\), \(b\)'nin farklı asal bölen sayısıdır. Bu yüzden
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ çift}$$
sonucuna ulaşırız. Problem artık şu çiftleri saymaktır:
$$a^6 b^4\le N,$$
\(b\) squarefree olacak ve farklı asal çarpan sayısı çift olacaktır.
\(a\) sabitlenince
$$b\le \left(\frac{N}{a^6}\right)^{1/4}$$
olmalıdır. Şimdi
$$E(x)=\#\{b\le x:\ b\text{ squarefree ve }\omega(b)\text{ çift}\}$$
tanımını yapalım. O zaman aranan sayı
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right)$$
şeklini alır. Programın dış döngüsü tam olarak bu toplamı hesaplar.
Önce
$$Q(x)=\#\{n\le x:\ n\text{ squarefree}\}$$
olsun. Squarefree gösterge fonksiyonu için klasik özdeşlik
$$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d)$$
geçerlidir. \(n\le x\) üzerinde toplarsak
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor$$
elde edilir.
Şimdi squarefree sayıları iki sınıfa ayıralım: \(\omega\)'sı çift olanlar \(E(x)\), tek olanlar \(O(x)\). Açıkça
$$Q(x)=E(x)+O(x).$$
Squarefree sayılarda
$$\mu(n)=(-1)^{\omega(n)}$$
olduğundan, Mertens fonksiyonu
$$M(x)=\sum_{n\le x}\mu(n)$$
için
$$M(x)=E(x)-O(x)$$
yazılır. İki denklemi çözersek ana formül çıkar:
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
Böylece problem, squarefree toplama fonksiyonunu ve Mertens fonksiyonunu tekrar tekrar hesaplamaya indirgenir.
Bu durumda
$$\left\lfloor 100^{1/6}\right\rfloor=2$$
olduğu için yalnızca \(a=1\) ve \(a=2\) mümkündür.
\(a=1\) için
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3$$
elde edilir. \(3\)'e kadar squarefree sayılar \(1,2,3\) olduğundan ve bunların \(\omega\) değerleri sırasıyla \(0,1,1\) olduğundan yalnızca \(1\) katkı verir. Katkı: \(1\).
\(a=2\) için
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1$$
olur; katkı yine \(1\).
Dolayısıyla
$$F(100)=1+1=2.$$
Geçerli iki sayı \(1\) ve \(64=2^6\)'dır. Buna karşılık \(16=2^4\) sayılmaz; çünkü bu durumda \(\omega(b)=1\) tek olur ve \(\tau(16)=5\not\equiv 1 \pmod{6}\).
Uygulama önce sabit bir üst sınıra kadar Möbius değerlerini bir elekle önceden hesaplar ve buradan hem \(\mu(n)\) için hem de squarefree göstergesi için prefix toplamlar üretir. Böylece küçük \(Q(x)\) ve \(M(x)\) sorguları doğrudan cevaplanır.
Daha büyük argümanlarda Mertens fonksiyonu, aynı bölüm sonucunu veren aralıkları blok halinde işleyen klasik bölüm-gruplamalı özyineleme ile hesaplanır ve sonuçlar önbelleğe alınır. \(Q(x)\) ise yukarıdaki Möbius toplam formülü ile doğrudan bulunur.
Son olarak C++, Python ve Java uygulamaları tüm \(a\le \lfloor N^{1/6}\rfloor\) değerleri üzerinde dolaşır, \(b\) için tam dördüncü kök sınırını hesaplar, \(E(x)=(Q(x)+M(x))/2\) değerini alır ve cevaba ekler. Tamsayı kökleri kayan nokta tahmininden sonra düzeltilir; büyük sayı kullanan sürümlerde taşmayı önlemek ve tam kuvvet sınırlarını doğru yakalamak için daha geniş aritmetik kullanılır.
Şöyle tanımlayalım:
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
Dış toplam \(A\) adım sürer. Elek ön işleme maliyeti seçilen üst sınırda lineer ya da lineere çok yakın zamandır ve aynı mertebede bellek kullanır. Her squarefree sorgusu
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor$$
toplamını kullandığı için doğrudan kısmı \(O(\sqrt{x})\) iş yapar; burada \(x\le X\). Mertens sorguları ise bölüm blokları üzerinden memoization kullandığından büyük değerler tekrar hesaplanmaz. Hedef problemde \(X=10^9\) olduğundan \(\sqrt{X}\approx 31623\) elde edilir; bu da yöntemi pratik kılar ve tüm \(n\le N\) sayıları tek tek üretip çarpanlara ayırmaya göre çok daha hızlıdır.
Debemos contar los enteros positivos \(n \le N\) cuyo número de divisores cumple
$$\tau(n)\equiv 1 \pmod{6}.$$
Las implementaciones en C++, Python y Java evalúan esta cantidad para \(N=10^{36}\). Un barrido directo hasta \(10^{36}\) es imposible, así que la solución transforma la condición sobre \(\tau(n)\) en un patrón estructural de factorización y luego cuenta ese patrón de forma eficiente.
Escribamos la factorización prima de \(n\) como
$$n=\prod_i p_i^{e_i}.$$
Entonces la función número de divisores es
$$\tau(n)=\prod_i (e_i+1).$$
Por tanto, el problema consiste en describir exactamente cuándo este producto es congruente con \(1\) módulo \(6\).
Si un producto es congruente con \(1\) módulo \(6\), entonces es impar y no es múltiplo de \(3\). Por ello, cada factor \(e_i+1\) debe ser impar y además no divisible por \(3\). Las únicas clases residuales posibles son
$$e_i+1\equiv 1 \text{ o } 5 \pmod{6}.$$
De forma equivalente, cada exponente debe satisfacer
$$e_i\equiv 0 \text{ o } 4 \pmod{6}.$$
Así, los enteros válidos son exactamente aquellos cuyas potencias primas tienen la forma \(6k\) o \(6k+4\).
Para cada exponente primo escribimos
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
Definimos ahora
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
Entonces
$$n=a^6 b^4.$$
El número \(b\) es libre de cuadrados porque cada primo aparece en él a lo sumo una vez. No hace falta imponer \(\gcd(a,b)=1\): un primo puede aparecer en ambos factores y la representación sigue siendo única, porque \(\beta_i\) indica si el exponente es congruente con \(0\) o con \(4\) módulo \(6\).
Recíprocamente, cualquier expresión \(a^6 b^4\) con \(b\) libre de cuadrados produce exponentes de la forma \(6k\) o \(6k+4\). La caracterización es exacta.
Si un primo contribuye solo a través de \(a^6\), entonces su factor en \(\tau(n)\) es
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
Si además aparece en \(b\), entonces el exponente es \(6\alpha_i+4\) y
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
Por lo tanto,
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
donde \(\omega(b)\) es el número de factores primos distintos de \(b\). Así,
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ es par}.$$
El problema original se convierte en contar pares \((a,b)\) tales que
$$a^6 b^4\le N,$$
con \(b\) libre de cuadrados y con un número par de primos distintos.
Fijado \(a\), debemos tener
$$b\le \left(\frac{N}{a^6}\right)^{1/4}.$$
Definimos
$$E(x)=\#\{b\le x:\ b\text{ libre de cuadrados y }\omega(b)\text{ par}\}.$$
Entonces el conteo buscado es
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
Esta es exactamente la suma exterior que evalúa la implementación.
Sea
$$Q(x)=\#\{n\le x:\ n\text{ es libre de cuadrados}\}.$$
La identidad clásica para el indicador de números libres de cuadrados es
$$1_{\text{libre de cuadrados}}(n)=\sum_{d^2\mid n}\mu(d),$$
y al sumar sobre \(n\le x\) obtenemos
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
Ahora separamos los libres de cuadrados en dos clases: \(E(x)\) para paridad par de \(\omega\), y \(O(x)\) para paridad impar. Entonces
$$Q(x)=E(x)+O(x).$$
En números libres de cuadrados se cumple
$$\mu(n)=(-1)^{\omega(n)},$$
de modo que la función de Mertens
$$M(x)=\sum_{n\le x}\mu(n)$$
satisface
$$M(x)=E(x)-O(x).$$
Resolviendo estas dos ecuaciones lineales se obtiene la fórmula clave:
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
Así, el problema se reduce a evaluar repetidamente una suma de libres de cuadrados y una suma de Mertens.
Aquí
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
por lo que solo son posibles \(a=1\) y \(a=2\).
Para \(a=1\),
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
Los enteros libres de cuadrados hasta \(3\) son \(1,2,3\). Sus valores de \(\omega\) son \(0,1,1\), de modo que solo \(1\) tiene paridad par. Contribución: \(1\).
Para \(a=2\),
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
así que la contribución vuelve a ser \(1\).
Por tanto,
$$F(100)=1+1=2.$$
Los dos enteros válidos son \(1\) y \(64=2^6\). En cambio, \(16=2^4\) no se cuenta porque entonces \(\omega(b)=1\) es impar y \(\tau(16)=5\not\equiv 1 \pmod{6}\).
La implementación precomputa primero los valores de Möbius hasta un límite fijo mediante un cribado, y a partir de ellos construye sumas prefijas tanto de \(\mu(n)\) como del indicador de números libres de cuadrados. Eso permite contestar de inmediato las consultas pequeñas de \(Q(x)\) y \(M(x)\).
Para argumentos grandes, la función de Mertens se evalúa con la recursión estándar agrupada por cocientes: los valores de \(\left\lfloor n/k\right\rfloor\) se repiten en intervalos largos, así que el algoritmo procesa juntos los bloques con el mismo cociente y memoriza los resultados. El valor \(Q(x)\) se obtiene directamente con la fórmula sumatoria de Möbius.
Después, las implementaciones en C++, Python y Java recorren todos los \(a\le \lfloor N^{1/6}\rfloor\), calculan la cota exacta de cuarta raíz para \(b\), evalúan \(E(x)=(Q(x)+M(x))/2\) y acumulan la contribución. Los cálculos de raíces enteras corrigen la estimación de coma flotante, y las variantes para enteros grandes usan aritmética más ancha para tratar exactamente los casos límite cerca de potencias perfectas.
Sea
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
La suma exterior tiene \(A\) iteraciones. El preprocesamiento mediante cribado cuesta tiempo lineal o casi lineal en el límite elegido, y el mismo orden de memoria. Cada consulta de números libres de cuadrados usa
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
así que su parte directa es \(O(\sqrt{x})\), con \(x\le X\). Las consultas de Mertens se benefician de la memoización por bloques de cociente, de modo que los valores grandes no se recalculan desde cero. Para el problema objetivo, \(X=10^9\), por lo que \(\sqrt{X}\approx 31623\); esta estrategia resulta completamente práctica y es muchísimo más rápida que enumerar o factorizar todos los \(n\le N\).
我们要求出所有满足
$$\tau(n)\equiv 1 \pmod{6}$$
的正整数 \(n \le N\) 的个数，其中 \(\tau(n)\) 表示 \(n\) 的正因子个数。C++、Python 和 Java 实现都在计算 \(N=10^{36}\) 时的这个值。由于不可能直接枚举到 \(10^{36}\)，解法必须先把条件改写成一个非常刚性的质因数指数结构，再对这种结构做计数。
设
$$n=\prod_i p_i^{e_i}$$
是 \(n\) 的标准素因子分解，则约数函数满足
$$\tau(n)=\prod_i (e_i+1).$$
所以问题的核心在于：什么时候这个乘积在模 \(6\) 意义下恰好等于 \(1\)？
如果一个乘积模 \(6\) 同余于 \(1\)，那么它一定是奇数，并且不能被 \(3\) 整除。因此每一个因子 \(e_i+1\) 本身也必须是奇数，且不能被 \(3\) 整除。这样可行的余数类只剩下
$$e_i+1\equiv 1 \text{ 或 } 5 \pmod{6}.$$
等价地说，每个素数指数都必须满足
$$e_i\equiv 0 \text{ 或 } 4 \pmod{6}.$$
这一步已经把问题的结构完全固定了下来：只有所有质因数指数都形如 \(6k\) 或 \(6k+4\) 的整数才可能被计入答案。
对每个指数写成
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
然后定义
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
于是立刻得到
$$n=a^6 b^4.$$
这里的 \(b\) 必然是平方自由数，因为每个质数在 \(b\) 中最多出现一次。注意并不需要要求 \(\gcd(a,b)=1\)：某个质数完全可以同时出现在 \(a\) 和 \(b\) 中，对应的总指数仍然是 \(6\alpha_i+4\)，而这种分解依旧是唯一的，因为 \(\beta_i\) 精确记录了指数模 \(6\) 时究竟落在 \(0\) 还是 \(4\)。
反过来，任何形如 \(a^6 b^4\) 且 \(b\) 为平方自由的数，它的每个质数指数都一定是 \(6k\) 或 \(6k+4\)。因此这一步不是近似，而是严格等价。
如果某个质数只来自 \(a^6\)，那么对应的约数因子是
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
如果这个质数还出现在 \(b\) 中，那么指数就变成 \(6\alpha_i+4\)，于是
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
因此整个约数个数满足
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
其中 \(\omega(b)\) 表示 \(b\) 的不同素因子个数。所以
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ 为偶数}.$$
原问题于是被完全改写为：统计所有满足
$$a^6 b^4\le N,$$
且 \(b\) 为平方自由、并且 \(\omega(b)\) 为偶数的数对 \((a,b)\)。
固定 \(a\) 之后，\(b\) 必须满足
$$b\le \left(\frac{N}{a^6}\right)^{1/4}.$$
定义
$$E(x)=\#\{b\le x:\ b\text{ 是平方自由数且 }\omega(b)\text{ 为偶数}\}.$$
那么所求总数就是
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
这正是实现中最外层循环的数学含义。
先记
$$Q(x)=\#\{n\le x:\ n\text{ 是平方自由数}\}.$$
平方自由指示函数有经典恒等式
$$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d),$$
对所有 \(n\le x\) 求和后得到
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
现在把平方自由数按 \(\omega\) 的奇偶性拆成两类：偶数类记为 \(E(x)\)，奇数类记为 \(O(x)\)。显然有
$$Q(x)=E(x)+O(x).$$
另一方面，在平方自由数上
$$\mu(n)=(-1)^{\omega(n)},$$
因此 Mertens 函数
$$M(x)=\sum_{n\le x}\mu(n)$$
满足
$$M(x)=E(x)-O(x).$$
联立这两个式子即可得到关键公式
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
也就是说，问题最终化为反复计算一个平方自由前缀计数和一个 Möbius 前缀和。
此时
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
所以只需要考虑 \(a=1\) 和 \(a=2\)。
当 \(a=1\) 时，
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
不超过 \(3\) 的平方自由数是 \(1,2,3\)，它们的 \(\omega\) 分别是 \(0,1,1\)，因此只有 \(1\) 属于偶数类，贡献为 \(1\)。
当 \(a=2\) 时，
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
于是贡献仍然是 \(1\)。
所以
$$F(100)=1+1=2.$$
这两个合法整数正是 \(1\) 与 \(64=2^6\)。相比之下，\(16=2^4\) 对应的 \(b=2\)，其 \(\omega(b)=1\) 为奇数，因此 \(\tau(16)=5\not\equiv 1 \pmod{6}\)，不会被计入。
实现首先用筛法预处理一个固定范围内的 Möbius 函数值，并据此构造两类前缀和：一类是 \(\mu(n)\) 的前缀和，另一类是平方自由指示函数的前缀和。这样，小范围的 \(Q(x)\) 与 \(M(x)\) 查询就都能直接返回。
对于更大的输入，Mertens 函数采用标准的按商分块递归。因为 \(\left\lfloor n/k\right\rfloor\) 会在连续区间上保持不变，所以实现把这些区间作为整体处理，并把结果缓存起来以供后续重复使用。至于 \(Q(x)\)，则直接按上面的 Möbius 求和公式计算。
最后，C++、Python 和 Java 实现都会遍历全部 \(a\le \lfloor N^{1/6}\rfloor\)，为每个 \(a\) 计算出 \(b\) 的精确四次根上界，再用 \(E(x)=(Q(x)+M(x))/2\) 取得这一层的贡献并累加。整数开方都在浮点初值之后做了校正，而大整数版本使用更宽的数值类型，因此靠近完美幂边界时也不会发生误差。
记
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
外层求和共有 \(A\) 次迭代。筛法预处理在所选上界内需要线性或接近线性的时间，以及同阶内存。每次平方自由计数查询都使用
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
因此其直接求和值部分是 \(O(\sqrt{x})\)，其中 \(x\le X\)。Mertens 查询则通过按商分块的记忆化递归避免了重复计算大参数。对于目标问题，\(X=10^9\)，于是 \(\sqrt{X}\approx 31623\)；这使得整套方法在实践中完全可行，并且远快于枚举或分解所有 \(n\le N\) 的朴素方法。
Нужно посчитать количество положительных целых чисел \(n \le N\), для которых число делителей удовлетворяет условию
$$\tau(n)\equiv 1 \pmod{6}.$$
Реализации на C++, Python и Java вычисляют это значение для \(N=10^{36}\). Прямой перебор до \(10^{36}\) невозможен, поэтому решение сначала переводит условие на \(\tau(n)\) в жесткое описание простых показателей, а затем считает уже эту структуру.
Пусть разложение числа \(n\) на простые множители имеет вид
$$n=\prod_i p_i^{e_i}.$$
Тогда функция числа делителей равна
$$\tau(n)=\prod_i (e_i+1).$$
Значит, задача сводится к точному описанию тех случаев, когда это произведение сравнимо с \(1\) по модулю \(6\).
Если произведение сравнимо с \(1\) по модулю \(6\), то оно нечетно и не делится на \(3\). Следовательно, каждый множитель \(e_i+1\) тоже должен быть нечетным и не должен делиться на \(3\). Остаются только два возможных остатка:
$$e_i+1\equiv 1 \text{ или } 5 \pmod{6}.$$
Эквивалентно этому каждый показатель обязан удовлетворять
$$e_i\equiv 0 \text{ или } 4 \pmod{6}.$$
Итак, подходят ровно те числа, у которых все показатели в простом разложении имеют вид \(6k\) или \(6k+4\).
Для каждого простого показателя запишем
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
После этого определим
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
Тогда автоматически
$$n=a^6 b^4.$$
Число \(b\) является квадратсвободным, поскольку каждый простой входит в него не более одного раза. Условие \(\gcd(a,b)=1\) не требуется: один и тот же простой может присутствовать и в \(a\), и в \(b\), а представление все равно остается единственным, потому что \(\beta_i\) фиксирует, равен ли показатель \(0\) или \(4\) по модулю \(6\).
Обратно, любое число вида \(a^6 b^4\) с квадратсвободным \(b\) имеет простые показатели вида \(6k\) или \(6k+4\). Значит, это точная характеристика, а не просто удобная подстановка.
Если простой входит только через \(a^6\), то соответствующий множитель в \(\tau(n)\) равен
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
Если тот же простой присутствует и в \(b\), то показатель становится \(6\alpha_i+4\), а значит
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
Следовательно,
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
где \(\omega(b)\) обозначает число различных простых делителей \(b\). Поэтому
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\text{ четно}.$$
Исходная задача полностью эквивалентна подсчету пар \((a,b)\), для которых
$$a^6 b^4\le N,$$
число \(b\) квадратсвободно и имеет четное число различных простых множителей.
При фиксированном \(a\) число \(b\) должно удовлетворять неравенству
$$b\le \left(\frac{N}{a^6}\right)^{1/4}.$$
Определим функцию
$$E(x)=\#\{b\le x:\ b\text{ квадратсвободно и }\omega(b)\text{ четно}\}.$$
Тогда искомое количество равно
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
Именно эту внешнюю сумму и вычисляет программа.
Обозначим
$$Q(x)=\#\{n\le x:\ n\text{ квадратсвободно}\}.$$
Для индикатора квадратсвободности используется классическая формула
$$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d),$$
и после суммирования по \(n\le x\) получаем
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
Теперь разобьем квадратсвободные числа на два класса: \(E(x)\) для четной \(\omega\) и \(O(x)\) для нечетной. Тогда
$$Q(x)=E(x)+O(x).$$
На квадратсвободных числах выполняется
$$\mu(n)=(-1)^{\omega(n)},$$
поэтому функция Мертенса
$$M(x)=\sum_{n\le x}\mu(n)$$
удовлетворяет равенству
$$M(x)=E(x)-O(x).$$
Решая эту систему из двух линейных уравнений, получаем ключевую формулу
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
Тем самым задача сводится к многократному вычислению суммы по квадратсвободным числам и функции Мертенса.
Здесь
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
так что возможны только \(a=1\) и \(a=2\).
Для \(a=1\) имеем
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
Квадратсвободные числа до \(3\) равны \(1,2,3\). Их значения \(\omega\) равны \(0,1,1\), поэтому только число \(1\) дает четную парность. Вклад равен \(1\).
Для \(a=2\)
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
и вклад снова равен \(1\).
Следовательно,
$$F(100)=1+1=2.$$
Два подходящих числа — это \(1\) и \(64=2^6\). А вот \(16=2^4\) не учитывается: здесь \(\omega(b)=1\) нечетно, значит \(\tau(16)=5\not\equiv 1 \pmod{6}\).
Сначала реализация вычисляет значения функции Мёбиуса до фиксированной границы с помощью решета и строит по ним префиксные суммы как для \(\mu(n)\), так и для индикатора квадратсвободности. Это позволяет мгновенно отвечать на малые запросы для \(Q(x)\) и \(M(x)\).
Для больших аргументов функция Мертенса считается стандартной рекурсией по блокам одинакового частного: значения \(\left\lfloor n/k\right\rfloor\) повторяются на длинных интервалах, поэтому программа обрабатывает такие интервалы целиком и сохраняет результаты в таблице мемоизации. Значение \(Q(x)\) берется напрямую из суммирующей формулы с \(\mu(d)\).
Затем реализации на C++, Python и Java перебирают все \(a\le \lfloor N^{1/6}\rfloor\), вычисляют точную верхнюю границу четвертого корня для \(b\), находят \(E(x)=(Q(x)+M(x))/2\) и прибавляют вклад к ответу. Целочисленные корни исправляются после вещественной оценки, а версии для больших чисел используют более широкий тип арифметики, поэтому пограничные случаи около совершенных степеней обрабатываются точно.
Обозначим
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
Во внешней сумме \(A\) итераций. Предварительное решето требует линейного или почти линейного времени по выбранной границе и такого же порядка памяти. Каждый запрос к квадратсвободной сумме использует
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
то есть его прямой вклад равен \(O(\sqrt{x})\), где \(x\le X\). Запросы к функции Мертенса выигрывают от мемоизации по блокам одинакового частного, так что большие значения не пересчитываются заново. Для целевой задачи \(X=10^9\), а значит \(\sqrt{X}\approx 31623\); поэтому метод остается практичным и на порядки быстрее полного перебора или факторизации всех \(n\le N\).
نريد عدّ الأعداد الصحيحة الموجبة \(n \le N\) التي يحقق فيها عدد القواسم الشرط
$$\tau(n)\equiv 1 \pmod{6}.$$
تقوم تطبيقات C++ وPython وJava بحساب هذا العدد عند \(N=10^{36}\). وبما أن الفحص المباشر حتى \(10^{36}\) غير ممكن عمليًا، فإن الحل يعيد صياغة الشرط على \(\tau(n)\) في صورة بنية صارمة لأسس العوامل الأولية، ثم يعدّ هذه البنية بكفاءة.
لنكتب التحليل الأولي للعدد \(n\) على الصورة
$$n=\prod_i p_i^{e_i}.$$
عندها تكون دالة عدد القواسم
$$\tau(n)=\prod_i (e_i+1).$$
إذًا فجوهر المسألة هو تحديد متى يكون هذا حاصل الضرب مكافئًا لـ \(1\) بترديد \(6\).
إذا كان حاصل ضرب ما مكافئًا لـ \(1\) بترديد \(6\)، فلا بد أن يكون فرديًا وغير قابل للقسمة على \(3\). لذلك يجب أن يكون كل عامل من العوامل \(e_i+1\) فرديًا وغير قابل للقسمة على \(3\). وهذا لا يترك إلا الصنفين
$$e_i+1\equiv 1 \pmod{6}\quad\text{or}\quad e_i+1\equiv 5 \pmod{6}.$$
وبشكل مكافئ، يجب أن يحقق كل أس
$$e_i\equiv 0 \pmod{6}\quad\text{or}\quad e_i\equiv 4 \pmod{6}.$$
وعليه فإن الأعداد المقبولة هي بالضبط الأعداد التي تكون فيها جميع أسس العوامل الأولية من الشكل \(6k\) أو \(6k+4\).
لكل أس أولي نكتب
$$e_i=6\alpha_i+4\beta_i,\qquad \beta_i\in\{0,1\}.$$
ثم نعرّف
$$a=\prod_i p_i^{\alpha_i},\qquad b=\prod_{\beta_i=1} p_i.$$
فنحصل مباشرة على
$$n=a^6 b^4.$$
يكون العدد \(b\) خاليًا من المربعات لأن كل عدد أولي يظهر فيه مرة واحدة على الأكثر. ولا حاجة لفرض الشرط \(\gcd(a,b)=1\)، إذ قد يظهر العدد الأولي نفسه في \(a\) و\(b\) معًا، ومع ذلك تبقى الصيغة وحيدة لأن \(\beta_i\) يحدد هل بقايا الأس بترديد \(6\) هي \(0\) أم \(4\).
وبالعكس، فإن أي عدد من الشكل \(a^6 b^4\) مع \(b\) خالٍ من المربعات يملك أسسًا أولية من الشكل \(6k\) أو \(6k+4\). لذا فهذا الوصف دقيق تمامًا.
إذا ساهم عدد أولي ما عبر \(a^6\) فقط، فإن عامله داخل \(\tau(n)\) يساوي
$$e_i+1=6\alpha_i+1\equiv 1 \pmod{6}.$$
أما إذا ظهر هذا العدد الأولي أيضًا داخل \(b\)، فإن الأس يصبح \(6\alpha_i+4\)، ومن ثم
$$e_i+1=6\alpha_i+5\equiv 5\equiv -1 \pmod{6}.$$
إذًا
$$\tau(n)\equiv (-1)^{\omega(b)} \pmod{6},$$
حيث ترمز \(\omega(b)\) إلى عدد العوامل الأولية المختلفة للعدد \(b\). ولذلك
$$\tau(n)\equiv 1 \pmod{6}\iff \omega(b)\equiv 0 \pmod{2}.$$
وهكذا تصبح المسألة الأصلية مكافئة لعدّ الأزواج \((a,b)\) التي تحقق
$$a^6 b^4\le N,$$
بحيث يكون \(b\) خاليًا من المربعات ويملك عددًا زوجيًا من العوامل الأولية المختلفة.
بعد تثبيت \(a\)، لا بد أن يحقق \(b\)
$$b\le \left(\frac{N}{a^6}\right)^{1/4}.$$
لنعرّف
$$E(x)=\#\{b\le x:\ \mu(b)\ne 0,\ \omega(b)\equiv 0 \pmod{2}\}.$$
عندئذ يصبح العدد المطلوب
$$F(N)=\sum_{a=1}^{\lfloor N^{1/6}\rfloor} E\!\left(\left\lfloor\left(\frac{N}{a^6}\right)^{1/4}\right\rfloor\right).$$
وهذه بالضبط هي الصيغة الخارجية التي تنفذها الشيفرة.
لنكتب أولًا
$$Q(x)=\#\{n\le x:\ \mu(n)\ne 0\}.$$
لدالة مؤشر الأعداد الخالية من المربعات الهوية الكلاسيكية
$$1_{\text{squarefree}}(n)=\sum_{d^2\mid n}\mu(d),$$
وبجمعها على جميع \(n\le x\) نحصل على
$$Q(x)=\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor.$$
الآن نقسم الأعداد الخالية من المربعات إلى فئتين: \(E(x)\) عندما تكون \(\omega\) زوجية، و\(O(x)\) عندما تكون فردية. ومن الواضح أن
$$Q(x)=E(x)+O(x).$$
وعلى الأعداد الخالية من المربعات تحديدًا لدينا
$$\mu(n)=(-1)^{\omega(n)},$$
لذلك تحقق دالة ميرتنز
$$M(x)=\sum_{n\le x}\mu(n)$$
العلاقة
$$M(x)=E(x)-O(x).$$
وبحل هاتين المعادلتين الخطيّتين نحصل على الصيغة المفتاحية
$$E(x)=\frac{Q(x)+M(x)}{2}.$$
أي إن المسألة تختزل في النهاية إلى تكرار حساب مجموع للأعداد الخالية من المربعات ومجموع ميرتنز.
لدينا هنا
$$\left\lfloor 100^{1/6}\right\rfloor=2,$$
ولذلك لا يظهر إلا \(a=1\) و\(a=2\).
عندما \(a=1\) نحصل على
$$\left\lfloor\left(\frac{100}{1^6}\right)^{1/4}\right\rfloor=3.$$
الأعداد الخالية من المربعات حتى \(3\) هي \(1,2,3\)، وقيم \(\omega\) لها هي \(0,1,1\)، لذلك لا يساهم إلا العدد \(1\). المساهمة هنا تساوي \(1\).
وعندما \(a=2\) يكون
$$\left\lfloor\left(\frac{100}{2^6}\right)^{1/4}\right\rfloor=1,$$
فتكون المساهمة مرة أخرى \(1\).
إذن
$$F(100)=1+1=2.$$
والعددان الصحيحان هما \(1\) و\(64=2^6\). أما \(16=2^4\) فلا يدخل في العد لأن \(\omega(b)=1\) فردي، وبالتالي \(\tau(16)=5\not\equiv 1 \pmod{6}\).
تبدأ الشيفرة بحساب قيم دالة Möbius حتى حد ثابت باستخدام غربال، ثم تبني من هذه القيم مجاميع سابقة لكل من \(\mu(n)\) ولمؤشر كون العدد خاليًا من المربعات. وبهذا يمكن الإجابة فورًا عن الاستعلامات الصغيرة الخاصة بـ \(Q(x)\) و\(M(x)\).
أما عندما تكون المدخلات أكبر، فتُحسب دالة ميرتنز باستخدام العودية القياسية المجمعة حسب نواتج القسمة: فقيم \(\left\lfloor n/k\right\rfloor\) تتكرر على فترات طويلة، لذا تُعالَج هذه الفترات على شكل كتل ويُخزَّن الناتج لإعادة استعماله لاحقًا. وبالنسبة إلى \(Q(x)\)، فيُحسب مباشرة من صيغة مجموع Möbius المذكورة أعلاه.
بعد ذلك تمر تطبيقات C++ وPython وJava على جميع قيم \(a\le \lfloor N^{1/6}\rfloor\)، وتحسب الحد الأعلى الصحيح للجذر الرابع الخاص بـ \(b\)، ثم تستخرج \(E(x)=(Q(x)+M(x))/2\) وتضيف المساهمة إلى الجواب. كما تُصحَّح الجذور الصحيحة بعد التقدير العشري الأولي، وتستعمل النسخ الخاصة بالأعداد الكبيرة حسابًا أوسع لتفادي أخطاء الحواف القريبة من القوى التامة.
لنضع
$$A=\left\lfloor N^{1/6}\right\rfloor,\qquad X=\left\lfloor N^{1/4}\right\rfloor.$$
يحتوي المجموع الخارجي على \(A\) دورة. وتكلفة التمهيد بالغربال خطية أو شبه خطية في الحد المختار، وبالمرتبة نفسها من الذاكرة. وكل استعلام لعدّ الأعداد الخالية من المربعات يعتمد على
$$\sum_{d\le \sqrt{x}} \mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor,$$
ولذلك يكون جزؤه المباشر من الرتبة \(O(\sqrt{x})\) حيث \(x\le X\). أما استعلامات ميرتنز فتستفيد من التخزين المؤقت عبر كتل القسمة، فلا يعاد حساب القيم الكبيرة من الصفر في كل مرة. وبالنسبة إلى المسألة المستهدفة فإن \(X=10^9\)، وبالتالي \(\sqrt{X}\approx 31623\)، وهذا يجعل الطريقة عملية جدًا وأسرع بكثير من تعداد جميع \(n\le N\) أو تحليلها أوليًا واحدًا واحدًا.