The quantity to evaluate is
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
where \(\Omega(n)\) is the total number of prime factors of \(n\), counted with multiplicity. For the actual input \(N=10^{14}\), direct enumeration is hopeless, so the solution rewrites the summand as a convolution between the ordinary divisor function and a sparse multiplicative correction supported only on powerful numbers.
The whole method starts from the fact that both \(2^{\Omega(n)}\) and the divisor-counting function \(\tau(n)\) are multiplicative. That makes it natural to search for a second multiplicative function whose convolution with \(\tau\) reproduces the target summand.
Define a multiplicative function \(c(n)\) by
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
Now consider the Dirichlet convolution \((\tau * c)(n)\). Since both factors are multiplicative, it is enough to verify the identity on prime powers.
Let \(n=p^e\). Then
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
The remaining finite arithmetic-geometric sum simplifies to
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
Therefore
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
By multiplicativity, this yields the identity
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
Introduce the divisor summatory function
$$D(x)=\sum_{m \le x}\tau(m).$$
Using the convolution identity, we get
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
Because \(c(p)=0\), the function \(c(q)\) vanishes whenever some prime appears to the first power only. Thus the surviving \(q\) are exactly the integers for which every prime exponent is either \(0\) or at least \(2\). These are the powerful numbers.
The divisor summatory function can be written as
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
Counting lattice points under the hyperbola \(uv=x\) gives the classical identity
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
This is already much faster than summing \(\tau(m)\) one value at a time. The implementation then improves it further by grouping together consecutive indices that share the same quotient \(\left\lfloor x/u\right\rfloor\), so each call runs in roughly square-root time.
Every powerful number has a unique factorization
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
The recursion chooses primes in increasing order, and for each chosen prime it tries the exponents \(2,3,4,\dots\) until the product would exceed \(N\). This guarantees uniqueness: the same powerful number cannot be generated in two different branches.
The local weight also matches the definition of \(c\). If a prime already appears with exponent \(e\ge 2\), increasing that exponent by \(1\) multiplies the contribution by
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
That is why the recursive coefficient simply doubles whenever the search extends one more power of the same prime.
Directly,
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
Now apply the decomposition. First,
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
The powerful numbers not exceeding \(10\) are
$$1,\ 4,\ 8,\ 9,$$
with weights
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
Hence
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
This small example shows exactly what the full algorithm does at large scale: the dense part is handled by \(D(x)\), and the sparse correction comes from powerful-number factors.
The C++, Python, and Java implementations begin by generating all primes up to \(\lfloor\sqrt{N}\rfloor\). No larger prime can appear in a powerful factor \(q\le N\) with exponent at least \(2\), so this prime list is sufficient for the entire recursive search.
Next, the implementation memoizes evaluations of \(D(x)\). Each fresh query uses the hyperbola formula above, together with quotient blocks where many consecutive divisors give the same floor value. Because the recursion repeatedly asks for \(D(\lfloor N/q\rfloor)\) at overlapping arguments, this cache removes a large amount of duplicate work.
Finally, the recursive search walks through powerful numbers \(q\). Every state contributes \(D(\lfloor N/q\rfloor)\), then branches by appending a new prime with exponent \(2\) or by increasing that exponent further while the product stays within range. The accumulated sum is stored in wide integer arithmetic so that the final value is preserved exactly.
Let \(R=\lfloor\sqrt{N}\rfloor\). Building the prime sieve costs \(O(R\log\log R)\) time and \(O(R)\) memory. A fresh computation of \(D(x)\) needs about \(O(\sqrt{x})\) quotient blocks, and memoization reuses repeated arguments across the recursion. The recursive states correspond to powerful numbers \(q\le N\), which form a sparse subset of the integers, so the search tree is far smaller than a full scan up to \(N\). In practice the overall method is sublinear in \(N\) and easily fast enough for \(N=10^{14}\).
Gesucht ist der Wert
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
wobei \(\Omega(n)\) die Gesamtzahl der Primfaktoren von \(n\) mit Vielfachheiten bezeichnet. Für den eigentlichen Parameter \(N=10^{14}\) ist direkte Enumeration unmöglich, daher schreibt die Lösung den Summanden als Faltung aus der gewöhnlichen Teilerfunktion und einer sehr dünn besetzten multiplikativen Korrekturfunktion um, die nur auf powerful numbers von Null verschieden ist.
Der gesamte Ansatz nutzt aus, dass sowohl \(2^{\Omega(n)}\) als auch die Teilerfunktion \(\tau(n)\) multiplikativ sind. Deshalb lohnt es sich, nach einer zweiten multiplikativen Funktion zu suchen, deren Dirichlet-Faltung mit \(\tau\) genau den Zielterm ergibt.
Definiere eine multiplikative Funktion \(c(n)\) durch
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
Betrachte nun die Dirichlet-Faltung \((\tau * c)(n)\). Da beide Faktoren multiplikativ sind, genügt die Überprüfung auf Primzahlpotenzen.
Für \(n=p^e\) gilt
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
Die verbleibende arithmetisch-geometrische Summe vereinfacht sich zu
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
Damit folgt
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
Wegen der Multiplikativität erhält man insgesamt
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
Definiere die summatorische Teilerfunktion
$$D(x)=\sum_{m \le x}\tau(m).$$
Mit der Faltungsidentität ergibt sich
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
Da \(c(p)=0\) gilt, verschwindet \(c(q)\) immer dann, wenn in \(q\) ein Primfaktor genau mit Exponent \(1\) vorkommt. Übrig bleiben also genau die Zahlen, bei denen jeder Primexponent entweder \(0\) oder mindestens \(2\) ist. Das sind die powerful numbers.
Die summatorische Teilerfunktion lässt sich schreiben als
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
Das Zählen von Gitterpunkten unter der Hyperbel \(uv=x\) liefert die klassische Formel
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
Das ist bereits deutlich schneller als die direkte Summation aller \(\tau(m)\). Die Implementierung beschleunigt jeden Aufruf zusätzlich, indem sie zusammenhängende Bereiche von \(u\) bündelt, für die derselbe Quotient \(\left\lfloor x/u\right\rfloor\) auftritt.
Jede powerful number besitzt eine eindeutige Darstellung
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
Die Rekursion wählt Primzahlen in streng wachsender Reihenfolge und probiert zu jeder gewählten Primzahl die Exponenten \(2,3,4,\dots\), solange das Produkt \(\le N\) bleibt. Dadurch ist Eindeutigkeit garantiert: dieselbe powerful number kann in keiner anderen Verzweigung erneut entstehen.
Auch das lokale Gewicht passt exakt zur Definition von \(c\). Wird der Exponent einer bereits verwendeten Primzahl von \(e\ge 2\) auf \(e+1\) erhöht, so vervielfacht sich der Beitrag um
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
Darum verdoppelt sich der rekursive Faktor bei jeder zusätzlichen Potenz derselben Primzahl.
Direkt berechnet ist
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
Nun die Zerlegung. Zunächst gilt
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
Die powerful numbers bis \(10\) sind
$$1,\ 4,\ 8,\ 9,$$
mit den Gewichten
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
Daher folgt
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
Dieses kleine Beispiel zeigt genau die Struktur der großen Rechnung: der dichte Anteil steckt in \(D(x)\), die dünne Korrektur in den powerful-number-Faktoren.
Die C++-, Python- und Java-Implementierungen erzeugen zuerst alle Primzahlen bis \(\lfloor\sqrt{N}\rfloor\). Größere Primzahlen können in einem powerful-Faktor \(q\le N\) nicht mit Exponent mindestens \(2\) auftreten, daher reicht diese Liste vollständig aus.
Anschließend werden Werte der summatorischen Teilerfunktion \(D(x)\) zwischengespeichert. Jeder neue Aufruf verwendet die Hyperbelformel und Quotientenblöcke, bei denen viele aufeinanderfolgende Divisoren denselben Ganzzahlquotienten liefern. Weil die Rekursion dieselben Argumente \(\lfloor N/q\rfloor\) häufig wiederholt anfragt, spart diese Memoisierung viel Arbeit.
Zum Schluss durchläuft eine Rekursion alle powerful numbers \(q\). Jeder Zustand trägt \(D(\lfloor N/q\rfloor)\) bei und verzweigt dann, indem eine neue Primzahl mit Exponent \(2\) angehängt oder derselbe Exponent weiter erhöht wird, solange das Produkt im zulässigen Bereich bleibt. Die Summe wird dabei in hinreichend breiten Ganzzahltypen exakt akkumuliert.
Mit \(R=\lfloor\sqrt{N}\rfloor\) kostet das Primzahlsieb \(O(R\log\log R)\) Zeit und \(O(R)\) Speicher. Eine frische Berechnung von \(D(x)\) benötigt ungefähr \(O(\sqrt{x})\) Quotientenblöcke; durch Memoisierung werden identische Argumente jedoch mehrfach genutzt. Die rekursiven Zustände entsprechen powerful numbers \(q\le N\), also einer sehr dünnen Teilmenge aller Zahlen. Insgesamt ist das Verfahren daher klar sublinear in \(N\) und für \(N=10^{14}\) praktisch schnell genug.
Hesaplanmak istenen büyüklük
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
burada \(\Omega(n)\), \(n\)'in üsleriyle birlikte sayılan toplam asal çarpan sayısıdır. Gerçek giriş \(N=10^{14}\) olduğunda doğrudan tarama yapılamaz; bu yüzden çözüm, hedef terimi sıradan bölen fonksiyonu ile yalnızca powerful number'larda sıfır olmayan seyrek bir çarpımsal düzeltmenin konvolüsyonu olarak yeniden yazar.
Yöntemin çıkış noktası şudur: hem \(2^{\Omega(n)}\) hem de bölen sayısı fonksiyonu \(\tau(n)\) çarpımsaldır. Bu nedenle \(\tau\) ile Dirichlet konvolüsyonu hedef terimi veren başka bir çarpımsal fonksiyon aramak doğaldır.
\(c(n)\) fonksiyonunu şöyle tanımlayalım:
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
Şimdi \((\tau * c)(n)\) Dirichlet konvolüsyonuna bakalım. İki fonksiyon da çarpımsal olduğu için eşitliği asal kuvvetlerde doğrulamak yeterlidir.
\(n=p^e\) için
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
Kalan sonlu aritmetik-geometrik toplam sadeleşip
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e $$
verir. Dolayısıyla
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
Çarpımsallık sayesinde genel sonuç
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
olur.
Bölen toplam fonksiyonunu
$$D(x)=\sum_{m \le x}\tau(m)$$
şeklinde tanımlayalım. Konvolüsyon özdeşliğiyle
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right) \end{aligned}$$
elde edilir. \(c(p)=0\) olduğu için bir asalın üssü tam \(1\) ise o sayı katkı vermez. Böylece yalnızca her asal üssü ya \(0\) ya da en az \(2\) olan sayılar kalır. Bunlar powerful number'lardır.
Bölen toplam fonksiyonu aynı zamanda
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1$$
şeklinde yazılabilir. \(uv=x\) hiperbolünün altındaki kafes noktalarını sayınca klasik formül çıkar:
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
Bu ifade, \(\tau(m)\)'leri tek tek toplamaktan çok daha hızlıdır. Uygulama bunu bir adım daha ileri götürüp aynı bölüm değerini veren ardışık \(u\) aralıklarını blok halinde işler; böylece tek bir çağrı yaklaşık karekök zamanda tamamlanır.
Her powerful number'ın tekil ayrışımı
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2)$$
şeklindedir. Rekürsiyon asalları artan sırayla seçer ve seçilen her asal için \(2,3,4,\dots\) üslerini, çarpım \(N\)'i aşana kadar dener. Bu sayede aynı sayı farklı bir dalda yeniden üretilemez.
Yerel katsayı da tam olarak \(c\) tanımına uyar. Bir asalın üssü \(e\ge 2\) iken onu \(e+1\)'e çıkarmak katkıyı
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2$$
kat artırır. Bu yüzden aynı asalın bir kuvvet daha eklenmesi rekürsiyondaki katsayının ikiye katlanmasına karşılık gelir.
Doğrudan hesaplayalım:
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
Şimdi ayrışımı kullanalım. Önce
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
\(10\)'u aşmayan powerful number'lar
$$1,\ 4,\ 8,\ 9$$
ve bunların ağırlıkları
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1$$
olur. O halde
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
Bu küçük örnek, büyük ölçekte yapılan işi açıkça gösterir: yoğun kısım \(D(x)\) ile, seyrek düzeltme ise powerful-number çarpanlarıyla gelir.
C++, Python ve Java uygulamaları önce \(\lfloor\sqrt{N}\rfloor\)'e kadar olan asalları üretir. \(q\le N\) olan bir powerful çarpanın içinde daha büyük bir asal en az ikinci kuvvetle yer alamayacağı için bu liste tüm rekürsiyon için yeterlidir.
Daha sonra \(D(x)\) hesapları önbelleğe alınır. Her yeni çağrı hiperbol formülünü ve aynı bölüm değerini paylaşan blokları kullanır. Rekürsiyon sırasında \(\lfloor N/q\rfloor\) biçimindeki aynı argümanlar sık sık tekrarlandığından bu önbellek ciddi bir kazanç sağlar.
Son aşamada rekürsiyon powerful number'ları gezer. Her durum \(D(\lfloor N/q\rfloor)\) katkısını ekler; ardından yeni bir asal ikinci kuvvetten başlayarak eklenir veya aynı asalın üssü artırılır. Çarpım sınırı aştığında dal kapanır. Toplam, sonucun tam korunması için geniş tamsayı aritmetiğiyle biriktirilir.
\(R=\lfloor\sqrt{N}\rfloor\) olsun. Asal süzgeci \(O(R\log\log R)\) zaman ve \(O(R)\) bellek gerektirir. \(D(x)\)'in yeni bir hesaplaması yaklaşık \(O(\sqrt{x})\) bölüm bloğu kullanır; fakat önbellek aynı argümanları tekrar hesaplamayı engeller. Rekürsiyon durumları \(q\le N\) olan powerful number'lara karşılık geldiği için arama ağacı tüm sayılar kümesinden çok daha küçüktür. Bu nedenle toplam yöntem \(N\)'e göre belirgin biçimde alt doğrusal kalır ve \(N=10^{14}\) için pratiktir.
La cantidad que se debe calcular es
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
donde \(\Omega(n)\) cuenta el número total de factores primos de \(n\) con multiplicidad. Para el valor real \(N=10^{14}\), una enumeración directa es imposible, así que la solución reescribe el sumando como una convolución entre la función divisor ordinaria y una corrección multiplicativa muy dispersa, distinta de cero solo en los powerful numbers.
El punto de partida es que tanto \(2^{\Omega(n)}\) como la función divisor \(\tau(n)\) son multiplicativas. Por eso conviene buscar una segunda función multiplicativa cuya convolución de Dirichlet con \(\tau\) produzca exactamente el término objetivo.
Definimos una función multiplicativa \(c(n)\) por
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
Consideremos ahora la convolución de Dirichlet \((\tau * c)(n)\). Como ambas funciones son multiplicativas, basta verificar la identidad en potencias primas.
Para \(n=p^e\), tenemos
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
La suma aritmético-geométrica restante se simplifica a
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
Por lo tanto,
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
Por multiplicatividad, obtenemos la identidad global
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
Introducimos la función sumatoria de divisores
$$D(x)=\sum_{m \le x}\tau(m).$$
Usando la identidad de convolución, se obtiene
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
Como \(c(p)=0\), la función \(c(q)\) se anula cuando alguna prima aparece con exponente exactamente \(1\). Sobreviven solo los enteros cuyos exponentes primos son todos \(0\) o al menos \(2\). Esos son precisamente los powerful numbers.
La función sumatoria puede escribirse como
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
Contar puntos de la retícula bajo la hipérbola \(uv=x\) da la fórmula clásica
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
Esto ya es mucho más rápido que sumar \(\tau(m)\) término a término. La implementación lo acelera aún más agrupando bloques consecutivos de índices que comparten el mismo cociente \(\left\lfloor x/u\right\rfloor\), de modo que cada evaluación se hace en tiempo aproximadamente de raíz cuadrada.
Todo powerful number tiene una factorización única
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
La recursión elige los primos en orden creciente y, para cada primo elegido, prueba los exponentes \(2,3,4,\dots\) mientras el producto siga siendo \(\le N\). Eso garantiza unicidad: el mismo powerful number no puede aparecer en dos ramas distintas.
El peso local también coincide exactamente con la definición de \(c\). Si una prima ya aparece con exponente \(e\ge 2\), aumentar ese exponente a \(e+1\) multiplica la contribución por
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
Por eso el coeficiente recursivo simplemente se duplica cuando se añade una potencia más de la misma prima.
De forma directa,
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
Ahora usemos la descomposición. Primero,
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
Los powerful numbers que no exceden \(10\) son
$$1,\ 4,\ 8,\ 9,$$
con pesos
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
Entonces
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
Este ejemplo pequeño muestra exactamente la idea del algoritmo completo: la parte densa se absorbe en \(D(x)\) y la corrección dispersa llega a través de factores powerful.
Las implementaciones en C++, Python y Java generan primero todos los primos hasta \(\lfloor\sqrt{N}\rfloor\). Ningún primo mayor puede aparecer con exponente al menos \(2\) dentro de un factor powerful \(q\le N\), así que esa lista basta para toda la búsqueda recursiva.
Después, la implementación memoriza las evaluaciones de \(D(x)\). Cada consulta nueva utiliza la fórmula de la hipérbola y bloques de cocientes constantes. Como la recursión solicita muchas veces los mismos valores \(\lfloor N/q\rfloor\), este almacenamiento evita repetir trabajo costoso.
Por último, la búsqueda recursiva recorre los powerful numbers \(q\). Cada estado añade \(D(\lfloor N/q\rfloor)\) y luego se ramifica agregando una nueva prima con exponente \(2\) o elevando más ese exponente mientras el producto siga dentro del límite. La suma final se acumula con aritmética entera suficientemente amplia para conservar el resultado exacto.
Si \(R=\lfloor\sqrt{N}\rfloor\), la criba de primos cuesta \(O(R\log\log R)\) tiempo y \(O(R)\) memoria. Una evaluación nueva de \(D(x)\) requiere aproximadamente \(O(\sqrt{x})\) bloques de cocientes, aunque la memoización reutiliza los argumentos repetidos. Los estados recursivos corresponden a powerful numbers \(q\le N\), que forman un subconjunto muy escaso de los enteros. En conjunto, el método es claramente sublineal respecto de \(N\) y resulta práctico para \(N=10^{14}\).
需要计算的量是
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
其中 \(\Omega(n)\) 表示 \(n\) 的素因子总数，并且要按重数计算。对题目的实际参数 \(N=10^{14}\) 来说，逐个枚举所有整数完全不可行，因此解法必须把目标项改写成“普通约数函数”和“只在 powerful number 上非零的稀疏乘法函数”之间的卷积。
整个方法的出发点是：\(2^{\Omega(n)}\) 和约数个数函数 \(\tau(n)\) 都是乘法函数。既然如此，就可以尝试构造另一个乘法函数，使它与 \(\tau\) 的 Dirichlet 卷积正好等于目标项。
定义乘法函数 \(c(n)\) 为
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
现在考虑 Dirichlet 卷积 \((\tau * c)(n)\)。由于两边都是乘法性的，只需要在素数幂上验证恒等式即可。
设 \(n=p^e\)，则有
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
后面的有限等差等比和可以化简为
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
因此
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
再利用乘法性，就得到对所有 \(n\ge 1\) 都成立的恒等式
$$ 2^{\Omega(n)} = (\tau * c)(n). $$
记约数求和函数为
$$D(x)=\sum_{m \le x}\tau(m).$$
由卷积恒等式可得
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
由于 \(c(p)=0\)，一旦某个素因子在 \(q\) 中的指数恰好等于 \(1\)，这个 \(q\) 的贡献就会消失。于是最终保留下来的正是所有素因子指数要么为 \(0\)、要么至少为 \(2\) 的整数，也就是 powerful number。
约数求和函数还可以写成
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
这表示的是双曲线 \(uv=x\) 下方的格点个数，因此有经典公式
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
这已经比逐项计算 \(\tau(m)\) 快得多。实现中还会把那些给出相同商值 \(\left\lfloor x/u\right\rfloor\) 的连续区间合并成块一起处理，所以一次新的 \(D(x)\) 计算大约只需要平方根级别的工作量。
每个 powerful number 都有唯一分解
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
递归按照素数递增的顺序选择质因子，并且对每个选中的素数尝试指数 \(2,3,4,\dots\)，直到乘积超过 \(N\) 为止。这样就不会重复：同一个 powerful number 不可能从两条不同分支生成。
局部权重也完全符合 \(c\) 的定义。如果某个素数当前指数为 \(e\ge 2\)，再把它升到 \(e+1\)，权重会乘上
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
这正是实现中“同一个素数每增加一层幂次，系数就翻倍”的数学原因。
先直接计算：
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
现在看卷积分解。先有
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
不超过 \(10\) 的 powerful number 是
$$1,\ 4,\ 8,\ 9,$$
对应权重分别为
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
因此
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
这个小例子准确体现了大规模算法的结构：密集部分由 \(D(x)\) 统一处理，稀疏修正则来自 powerful number 的因子。
C++、Python 和 Java 实现都会先筛出所有不超过 \(\lfloor\sqrt{N}\rfloor\) 的素数。原因很简单：如果某个素数大于 \(\sqrt{N}\)，那么它的平方已经超过 \(N\)，不可能出现在任何满足 \(q\le N\) 的 powerful 因子中。
接着，实现会对 \(D(x)\) 的结果做缓存。每次遇到新的 \(x\)，就用双曲线公式和“相同商值分块”的技巧来计算；而当递归再次请求同一个 \(\lfloor N/q\rfloor\) 时，就可以直接复用缓存结果。
最后，递归过程按素数递增顺序遍历所有可能的 powerful number \(q\)。每个状态先贡献一个 \(D(\lfloor N/q\rfloor)\)，再尝试把新素数以平方开始乘进去，或者把当前素数的指数继续往上加。只要乘积仍然不超过 \(N\)，这一分支就继续展开。总和使用足够宽的整数类型保存，因此不会丢失精度。
记 \(R=\lfloor\sqrt{N}\rfloor\)。构造素数筛需要 \(O(R\log\log R)\) 时间和 \(O(R)\) 空间。一次全新的 \(D(x)\) 计算大约要处理 \(O(\sqrt{x})\) 个商值块，但缓存会消除大量重复计算。递归状态对应于所有 \(q\le N\) 的 powerful number，它们相对于全部整数来说非常稀疏，所以搜索树远小于从 \(1\) 到 \(N\) 的线性扫描。整体方法因此明显是 \(N\) 的次线性算法，并且足以处理 \(10^{14}\) 规模的数据。
Нужно вычислить величину
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
где \(\Omega(n)\) обозначает общее число простых множителей числа \(n\) с учетом кратности. Для реального параметра \(N=10^{14}\) прямой перебор невозможен, поэтому решение переписывает слагаемое как свертку обычной функции числа делителей с разреженной мультипликативной поправкой, отличной от нуля только на powerful numbers.
Основная идея опирается на то, что и \(2^{\Omega(n)}\), и функция числа делителей \(\tau(n)\) являются мультипликативными. Значит, разумно построить еще одну мультипликативную функцию, чья свертка Дирихле с \(\tau\) дает именно целевой член.
Определим мультипликативную функцию \(c(n)\) так:
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
Рассмотрим теперь свертку Дирихле \((\tau * c)(n)\). Поскольку оба сомножителя мультипликативны, достаточно проверить формулу на степенях простого.
Пусть \(n=p^e\). Тогда
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
Оставшаяся конечно-разностная геометрическая сумма упрощается до
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
Следовательно,
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
По мультипликативности получаем общую формулу
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
Введем сумматор делителей
$$D(x)=\sum_{m \le x}\tau(m).$$
Тогда из тождества свертки следует
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
Поскольку \(c(p)=0\), функция \(c(q)\) обращается в нуль всякий раз, когда какой-то простой множитель входит в \(q\) ровно в первой степени. Поэтому остаются только числа, у которых каждый простой показатель либо равен \(0\), либо не меньше \(2\). Это и есть powerful numbers.
Сумматор делителей можно записать так:
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
Подсчет узлов решетки под гиперболой \(uv=x\) дает классическую формулу
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
Это уже намного быстрее, чем суммировать \(\tau(m)\) по одному значению. Реализация ускоряет вычисление еще сильнее, объединяя подряд идущие значения \(u\), для которых частное \(\left\lfloor x/u\right\rfloor\) одинаково, в один блок.
Каждое powerful number имеет единственное разложение
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
Рекурсия выбирает простые числа в возрастающем порядке и для каждого выбранного простого пробует показатели \(2,3,4,\dots\), пока произведение не превысит \(N\). Поэтому один и тот же объект не может возникнуть в двух разных ветвях.
Локальный вес тоже идеально совпадает с определением \(c\). Если некоторый простой уже имеет показатель \(e\ge 2\), то переход к \(e+1\) умножает вклад на
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
Именно поэтому при наращивании одной и той же степени простого рекурсивный коэффициент просто удваивается.
При прямом подсчете получаем
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
Теперь применим разложение. Сначала
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
Powerful numbers, не превосходящие \(10\), это
$$1,\ 4,\ 8,\ 9,$$
с весами
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
Следовательно,
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
Этот маленький пример в точности демонстрирует структуру большого алгоритма: плотная часть сосредоточена в \(D(x)\), а редкие поправки приходят от powerful number.
Реализации на C++, Python и Java сначала строят список всех простых чисел до \(\lfloor\sqrt{N}\rfloor\). Больше и не нужно: простой \(p>\sqrt{N}\) уже имеет квадрат больше \(N\) и потому не может входить в powerful-множитель \(q\le N\).
Затем реализация кэширует значения \(D(x)\). Каждый новый запрос вычисляется по формуле гиперболы с разбиением на блоки одинаковых частных. Поскольку рекурсия много раз запрашивает одни и те же значения \(\lfloor N/q\rfloor\), этот кэш экономит значительную часть времени.
После этого рекурсивный обход перечисляет все допустимые powerful numbers \(q\). Каждый узел добавляет вклад \(D(\lfloor N/q\rfloor)\), а затем ветвится: можно присоединить новый простой во второй степени или увеличить уже выбранную степень, пока произведение не выходит за предел \(N\). Сумма хранится в достаточно широком целочисленном формате, так что итоговый ответ сохраняется точно.
Пусть \(R=\lfloor\sqrt{N}\rfloor\). Построение решета простых требует \(O(R\log\log R)\) времени и \(O(R)\) памяти. Новое вычисление \(D(x)\) занимает примерно \(O(\sqrt{x})\) блоков частных, но одинаковые аргументы переиспользуются из кэша. Рекурсивные состояния соответствуют powerful numbers \(q\le N\), а это очень редкое подмножество целых чисел. Поэтому вся схема работает существенно быстрее линейного прохода по всем \(1,\dots,N\) и практически удобна для \(N=10^{14}\).
الكمية المطلوب حسابها هي
$$S(N)=\sum_{n \le N} 2^{\Omega(n)},$$
حيث تمثل \(\Omega(n)\) العدد الكلي للعوامل الأولية للعدد \(n\) مع احتساب التكرار. عندما يكون \(N=10^{14}\) لا يمكن إجراء تعداد مباشر لكل الأعداد، لذلك تعيد الفكرة كتابة الحد المطلوب على صورة التفاف بين دالة عدد القواسم العادية وتصحيح ضربي متناثر لا يكون غير صفري إلا على powerful numbers.
ينطلق الحل من ملاحظة أن كلًا من \(2^{\Omega(n)}\) ودالة عدد القواسم \(\tau(n)\) دالتان ضربيتان. لذلك من الطبيعي بناء دالة ضربية أخرى يكون التفاف ديريشليه الخاص بها مع \(\tau\) مساويًا تمامًا للحد الهدف.
لنعرّف دالة ضربية \(c(n)\) كما يلي:
$$c(1)=1,\qquad c(p)=0,\qquad c(p^e)=2^{e-2}\quad (e\ge 2).$$
ننظر الآن إلى التفاف ديريشليه \((\tau * c)(n)\). وبما أن الدالتين ضربيتان، فيكفي التحقق من الهوية على قوى الأعداد الأولية فقط.
إذا كان \(n=p^e\)، فإن
$$\begin{aligned} (\tau * c)(p^e) &= \sum_{k=0}^{e} \tau(p^{e-k})\,c(p^k) \\ &= (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2}. \end{aligned}$$
ويتبسط هذا المجموع المنتهي من النوع الحسابي-الهندسي إلى
$$ (e+1) + \sum_{k=2}^{e} (e-k+1)\,2^{k-2} = 2^e. $$
ومن ثم
$$ (\tau * c)(p^e)=2^e=2^{\Omega(p^e)}. $$
وبالضربية نحصل على الصيغة العامة
$$ 2^{\Omega(n)} = (\tau * c)(n)\quad (n\ge 1). $$
لنعرّف دالة المجموع التراكمي للقواسم
$$D(x)=\sum_{m \le x}\tau(m).$$
وباستخدام هوية الالتفاف نحصل على
$$\begin{aligned} S(N) &= \sum_{n \le N} (\tau * c)(n) \\ &= \sum_{q \le N} c(q)\sum_{m \le N/q}\tau(m) \\ &= \sum_{q \le N} c(q)\,D\!\left(\left\lfloor \frac{N}{q}\right\rfloor\right). \end{aligned}$$
وبما أن \(c(p)=0\)، فإن \(c(q)\) يساوي الصفر كلما ظهر عدد أولي في \(q\) بأس يساوي \(1\) بالضبط. لذلك لا يبقى إلا الأعداد التي تكون فيها جميع الأسس الأولية إما \(0\) أو على الأقل \(2\)، وهذه هي powerful numbers.
يمكن أيضًا كتابة دالة المجموع على الصورة
$$D(x)=\sum_{m \le x}\tau(m)=\sum_{uv \le x}1.$$
وهذا يعني عدّ نقاط الشبكة الواقعة تحت القطع الزائد \(uv=x\)، ومنه نحصل على العلاقة الكلاسيكية
$$D(x)=2\sum_{u=1}^{\lfloor\sqrt{x}\rfloor}\left\lfloor\frac{x}{u}\right\rfloor-\lfloor\sqrt{x}\rfloor^2.$$
هذه الصيغة أسرع كثيرًا من جمع \(\tau(m)\) قيمة بقيمة. ثم تزيدها التطبيقات سرعةً بتجميع الفهارس المتتالية التي تعطي نفس خارج القسمة \(\left\lfloor x/u\right\rfloor\) في كتل واحدة، وبذلك تصبح كلفة الاستدعاء الجديد تقريبًا من رتبة الجذر التربيعي.
لكل powerful number تحليل وحيد من الشكل
$$q=\prod_{i=1}^{r} p_i^{e_i}\qquad (e_i\ge 2).$$
تختار التراجعية الأعداد الأولية بترتيب تصاعدي، ولكل عدد أولي مختار تجرب الأسس \(2,3,4,\dots\) ما دام حاصل الضرب لا يتجاوز \(N\). ولهذا لا يمكن أن يظهر العدد نفسه في فرعين مختلفين.
كما أن الوزن المحلي يطابق تعريف \(c\) بدقة. فإذا كان للأس الأولي قيمة \(e\ge 2\)، فإن رفعه إلى \(e+1\) يضاعف المساهمة بعامل
$$\frac{c(p^{e+1})}{c(p^e)}=\frac{2^{e-1}}{2^{e-2}}=2.$$
ولهذا يتضاعف المعامل في التراجعية كلما أضيفت قوة جديدة من العدد الأولي نفسه.
بالحساب المباشر نجد أن
$$\begin{aligned} S(10) &= 2^{\Omega(1)}+2^{\Omega(2)}+2^{\Omega(3)}+2^{\Omega(4)}+2^{\Omega(5)} \\ &\quad +2^{\Omega(6)}+2^{\Omega(7)}+2^{\Omega(8)}+2^{\Omega(9)}+2^{\Omega(10)} \\ &= 1+2+2+4+2+4+2+8+4+4=33. \end{aligned}$$
والآن نطبق التفكيك. أولًا لدينا
$$D(10)=\sum_{m \le 10}\tau(m)=27,\qquad D(2)=3,\qquad D(1)=1.$$
والـ powerful numbers التي لا تتجاوز \(10\) هي
$$1,\ 4,\ 8,\ 9,$$
وبالأوزان
$$c(1)=1,\qquad c(4)=1,\qquad c(8)=2,\qquad c(9)=1.$$
إذن
$$\begin{aligned} S(10) &= c(1)D(10)+c(4)D(2)+c(8)D(1)+c(9)D(1) \\ &= 1\cdot 27 + 1\cdot 3 + 2\cdot 1 + 1\cdot 1 \\ &= 33. \end{aligned}$$
يوضح هذا المثال الصغير بدقة ما يفعله الحل الكامل: الجزء الكثيف تجمعه \(D(x)\)، أما التصحيحات المتناثرة فتأتي من عوامل powerful number.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الأعداد الأولية حتى \(\lfloor\sqrt{N}\rfloor\). فلا يمكن لعدد أولي أكبر من ذلك أن يظهر بأس لا يقل عن \(2\) داخل عامل powerful يحقق \(q\le N\).
بعد ذلك تحفظ التطبيقات قيم \(D(x)\) في ذاكرة مؤقتة. كل قيمة جديدة تُحسب بصيغة القطع الزائد مع تجميع مقاطع القواسم التي تشترك في نفس خارج القسمة. ولأن التراجعية تطلب كثيرًا القيم نفسها من الشكل \(\lfloor N/q\rfloor\)، فإن هذا التخزين المؤقت يزيل قدرًا كبيرًا من العمل المكرر.
أخيرًا تجتاز التراجعية جميع powerful numbers الممكنة \(q\). كل حالة تضيف \(D(\lfloor N/q\rfloor)\)، ثم تتفرع إما بإضافة عدد أولي جديد بدءًا من مربعه، أو بزيادة أس عدد أولي اختير بالفعل، ما دام حاصل الضرب ما زال ضمن الحد. ويُجمع الناتج باستخدام حساب صحيح واسع بما يكفي للحفاظ على القيمة النهائية كاملة.
إذا وضعنا \(R=\lfloor\sqrt{N}\rfloor\)، فإن بناء غربال الأعداد الأولية يحتاج إلى \(O(R\log\log R)\) زمنًا و\(O(R)\) ذاكرة. أما الحساب الجديد لـ \(D(x)\) فيحتاج تقريبًا إلى \(O(\sqrt{x})\) من كتل القسمة، لكن إعادة استخدام القيم المخزنة تختصر التكرار كثيرًا. وتمثل الحالات التراجعية powerful numbers \(q\le N\)، وهي مجموعة متناثرة جدًا مقارنة بجميع الأعداد الصحيحة. لذلك تبقى الخوارزمية دون خطية بوضوح بالنسبة إلى \(N\)، وهي عملية تمامًا عند \(N=10^{14}\).