Several years ago, I figured out the following (novel, I think) approach for counting prime numbers. Empirically, it runs in something in the rough ballpark of $O(n)$ time and $O(\log n)$ space, but I'd really like to know its actual run time complexity from a more rigorous perspective.

So the approach looks like this:

$D_{0,a}(n) = 1$
$D_{1,a}(n) = \lfloor n\rfloor-a-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Pi(n) = \displaystyle\sum_{k=1}^{\lfloor\log_2 n\rfloor}{(-1)^{k+1} \over k}D_{k,2}(n)$
$D_{k,a}(n) = \displaystyle\sum_{j=1}^{k} \binom{k}{j}\sum_{m=a}^{\lfloor n^{\frac{1}{k}}\rfloor}D_{k-j,m+1}(\frac{n}{m^{j}}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pi(n) = \displaystyle\sum_{j=1}^{\lfloor\log_2 n\rfloor}{1 \over j} \cdot \mu(j)\Pi(n^{\frac{1}{j}})$

(with $\pi(n)$: prime counting function, $\mu(n)$: Mobius mu function, $\binom{k}{j}$: binomial coefficient)

For reference, I have a working C++ implementation of the algorithm here, some other detailed notes about the algorithm here, and a screenshot of the algorithm executing for ascending integer powers of 10 here. As you can see in that screenshot, just eyeballing it, increasing $n$ by x$10$ seems to increase the execution time around x$9.5$ or so (although it looks like that factor is slightly increasing).

MY QUESTION: Can anyone tell me how to analyze this?

As far as I understand, this analysis really comes down to evaluating the run time asymptotics of $D_{2,2}(n)$, $D_{3,2}(n)$, $D_{4,2}(n)$, $D_{5,2}(n)$, and so on.

I wrote $D_{k,a}(n)$ above recursively because it's certainly the most compact way to both write it and program it. But for seeing what computation is taking place, it's probably more useful to flatten out the recursion and simplify a bit. If I do that, you can see that $D_{2,2}(n)$ is

$$D_{2,2}(n) = ((2-1)^2 - \lfloor n^{1 \over 2} \rfloor ^2) + 2 \sum_{b = 2}^{\lfloor n^{1 \over 2} \rfloor} \lfloor {n \over b} \rfloor $$

and $D_{3,2}(n)$ is

$$ D_{3,2}(n)= (\lfloor n^{1 \over 3} \rfloor ^3 -(2-1)^3) + 3 \sum_{b = 2}^{\lfloor n^{1 \over 3} \rfloor} {\lfloor {{n \over b^2}} \rfloor} - 3 \sum_{b = 2}^{\lfloor n^{1 \over 3} \rfloor} {\lfloor ({n \over b})^{1 \over 2} \rfloor^2} + 6 \sum_{b = 2}^{\lfloor n^{1 \over 3} \rfloor} \sum_{c=b+1}^{\lfloor ({n \over b})^{{1 \over 2}} \rfloor} {\lfloor {n \over {b c}} \rfloor} $$

and so on. This is essentially a generalization of the Dirichlet hyperbola method.

Obviously the final term for each grows faster than the other terms (so the single sum from $D_{2,2}(n)$, and the double sum for $D_{3,2}(n)$.), so that's going to determine the run time complexity.

This holds more generally, and so evaluating the run time complexity of each of those functions comes down to evaluating the run time complexity of

$$\sum_{b=2}^{\lfloor n^{1 \over 2} \rfloor } {\lfloor {n \over {b}} \rfloor}$$

for $D_{2,2}(n)$,

$$\sum_{b = 2}^{\lfloor n^{1 \over 3} \rfloor} \sum_{c = b+1}^{\lfloor ({n \over b})^{1 \over 2} \rfloor }{\lfloor {n \over {b \cdot c}} \rfloor}$$

for $D_{3,2}(n)$,

$$\sum_{b = 2}^{\lfloor n^{1 \over 4} \rfloor} \sum_{c = b+1}^{\lfloor ({n \over b})^{1 \over 3} \rfloor } \sum_{d = c+1}^{\lfloor ({n \over {b \cdot c}})^{1 \over 2} \rfloor } {\lfloor {n \over {b \cdot c \cdot d}} \rfloor}$$

for $D_{4,2}(n)$, and so on.

But assuming that I'm even correct that these nested sums ought to determine the run time complexity of the more general prime counting algorithm, it's not at all clear to me how to analyze the run time complexity of these nested sums in the more general case.

Any ideas?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.