Counting Primes: The Basic Approach

Okay. Let's turn to actual prime counting...

Counting Primes Recursively

Möbius inversion is enough to let us use the compact recursive formula for $\Pi(n)$, p=(n,k=1,j=2)=>n< j?0:1/k-p(n/j,k+1)+p(n,k,j+1), and use it to count actual primes, rather than weighted prime powers.

Really?

See for yourself. It works like so:

Click the button, and this code will be run in the browser and count primes as expected...

It doesn't seem to count very large values.

...well, fine, it counts as expected up to a quite small input, anyway.

We only run this code here with the first 3 powers of 10 as input because larger values lead immediately to a stack overflow in most browsers.

Ah.

This identity for counting prime powers is, at least to my eyes, delightfully concise. That's one reason I've started these discussions with it, in fact. I use this form to good effect elsewhere to show off lots of intriguing prime counting variations.

Sure.

With that said, though, it's not very friendly to most programming environments unless they support tail-call optimization. And at the time of writing, most browsers do not.

I guess that makes sense.

Ultimately this is just a programming implementation issue, of course, not a fundamental mathematical one.

Counting Primes Recursively, Revised

So is that an insurmountable problem?

Not really. The core idea here can actually be rewritten a number of different ways with more or less verbosity, depending on your taste. An immediate and easy change is to unroll the last term, the p(n,k,j+1) one, and replace the recursion there with a loop. Do that, and the new function for computing $\Pi(n)$ becomes

function p(n, k = 1){
    let t = 0;
    for (let j = 2; j <= n; j++)
        t += 1 / k - p(n / j, k + 1);
    return t;
}

Given that, we can count primes with the following, only slightly longer bit of code.

What happens if you click the button now?

Ah - now it does seem to be counting primes successfully for larger and larger inputs. But it's honestly not that fast, I don't think. On my machine, it takes more than 2 minutes to count the primes under 100,000, which seems quite slow.

Indeed - that is not at all fast.

Still, it does provide a good starting point, I think. So now let's see how the algorithm can be evolved.