Notes

Success! I found a reference to Mertens’ theorem in a paper by Adam Kalai, which is exactly what I needed to analyze the complexity of the prime sieve from the previous post.

Alas, my previous complexity guess was wrong. The actual complexity is $O(n^{3/2}/{\log }^{3}n)$. Apparently my numerical estimates didn’t go out far enough (also I was biased towards finding $O(n{\log }^{m}n)$).

From before, the cost of the algorithm is $O(C(n))$ where $$C(n)=\sum _{c<n}\pi (\mathrm{lpf}(c))$$ where $c<n$ means all composite numbers up to $n$. Note that any number with $\mathrm{lpf}(c)=p$ can be written as $\mathrm{pm}$, where $m$ is not divisible by any prime smaller than $p$. By Mertens’ theorem, the density of numbers not divisible by primes less than $p$ is $$\begin{array}{rlr}\prod _{q<p}(1-\frac{1}{q})& \approx & \frac{e^{-\gamma }}{\log p}\end{array}$$ We can now estimate $C(n)$ as $$\begin{array}{rl}C(n)=& \sum _{c<n}\pi (\mathrm{lpf}(c))\\ =& \sum _{p<n}\pi (p)\sum _{k=p}^{n/p}1\text{if}\forall q<p,q\nmid k\\ \approx & \sum _{p<\sqrt{n}}\pi (p)(\frac{n}{p}-p)\prod _{q<p}(1-\frac{1}{q})\\ \approx & e^{-\gamma }\sum _{p<\sqrt{n}}\pi (p)(\frac{n}{p}-p)\frac{1}{\log p}\\ \approx & e^{-\gamma }{\int }_2^{\sqrt{n}}\pi (x)(\frac{n}{x}-x)\frac{1}{\log x}\frac{\mathrm{dx}}{\log x}\\ \approx & e^{-\gamma }{\int }_2^{\sqrt{n}}\frac{x}{{\log }^{3}x}(\frac{n}{x}-x)\\ \approx & e^{-\gamma }{\int }_2^{\sqrt{n}}\frac{n-x^2}{{\log }^{3}x}\end{array}$$ Since the integrand is $O(n/{\log }^{3}n)$ for $x>n^{1/3}$, we get $C(n)=O(n^{3/2}/{\log }^{3}n)$. On the other hand, the integrand is $\omega (n/{\log }^{3}n)$ for $x<\sqrt{n/4}$, so in fact $C(n)=\Theta (n^{3/2}/{\log }^{3}n)$.

This adds another entry to the set of listful Sieve of Eratostheness-like algorithms that turn out to cost as much as trial division (up to a polylog factor). It’d be cool if a faster list based algorithm existed, but I expect that the answer is probably no.

Tags: laziness, primes, sieve

This entry was posted on Saturday, January 10th, 2009 at 1:21 pm and is filed under math. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.