To roll out the second useful technique for speeding up prime counting, I want to rewrite what we're counting and introduce some function names to reference and think about.
Why?
Well, just watch. Earlier, I noted we could write our core idea as $$p_k( n )=\sum_{j=2}^{\lfloor n \rfloor} \frac{1}{k}-p_{k+1}(\frac{n}{j}) $$ and $$\Pi(n) = p_1(n)$$
Sure.
Well, obviously that recursion can be applied to itself. And if we do that repeatedly, eventually we'll arrive at an expression that looks like this:
$$\Pi( n )=\sum_{t=2}^n 1- \frac{1}{2} \sum_{t=2}^n \sum_{u=2}^{\lfloor \frac{n}{t} \rfloor} 1+ \frac{1}{3} \sum_{t=2}^n \sum_{u=2}^{\lfloor \frac{n}{t} \rfloor} \sum_{v=2}^{\lfloor \frac{n}{t \cdot u} \rfloor} 1- ...$$Yeah, that seems reasonable.
Well, now I'll name each nested sum as $$D'_{ 1}( n ) = \sum_{t=2}^n 1$$ and $$D'_{ 2 }( n ) = \sum_{t=2}^n \sum_{u=y}^{\lfloor \frac{n}{t} \rfloor} 1$$ and $$D'_{ 3 }( n ) = \sum_{t=2}^n \sum_{u=y}^{\lfloor \frac{n}{t} \rfloor} \sum_{v=2}^{\lfloor \frac{n}{t \cdot u} \rfloor} 1$$ and so on.
More generally, I'll call $D'_k(n)$ the strict divisor summatory function. And pulling back from the meat-and-potato arithmetic for a moment, I'll think of $D'_k(n)$ conceptually as the count of solutions to $j_1 \cdot j_2 \cdot \dots \cdot j_k \le n$ where $j>1$ and order matters. That's more of a set theory way of thinking about what $D'_k(n)$ represents.
Sure. I get that, conceptually.
And finally, I'll rewrite the weighted prime counting function as $$\Pi( n )= \sum_{k = 1}^{ \lfloor \frac{\log n}{\log 2} \rfloor } \frac{( -1 )^{ k+1 }}{k}\cdot D'_{ k }( n )$$ The upper bound on the sum is a consequence of the fact that $D'_k(n)=0$ if $2^k > n$. I could technically use $\infty$ as the upper bound of the sum, and the result would be the same. But this is useful for actual computation.
Wait... earlier, animations we looked at expressed our weighted prime power counting function as $$\Pi(n) = \color{#303030}\#\bullet\color{black} - \frac{1}{2} \cdot \color{#d02020}\#\bullet\color{black}+ \frac{1}{3} \cdot \color{#d09030}\#\bullet\color{black}- \frac{1}{4} \cdot \color{#808080}\#\bullet\color{black}+ \frac{1}{5} \cdot \color{#b0b0b0}\#\bullet\color{black} ...$$ Is that essentially this formula?
It is indeed. That's just another way of expressing this exact idea, just using colors instead of the symbols $D_k'(n)$.
I guess I follow, but none of this alters the computation we were already doing, right?
Correct. Or, well, not yet anyway.
Here's a JavaScript implementation of this rewritten approach.
If you execute this, you should find it's miserably slow and about as slow as our first recursive version.
I do indeed find that.
Well, that's fine.
It's somewhere to start.
From here, our main activity is finding ways to improve the computation of DivisorCount(n, k).
So are you suggesting I won't need to read any code below the section helpfully labeled "EVERYTHING BELOW THIS LINE IS UNCHANGED BETWEEN EXAMPLES"?
... Yes. I am indeed suggesting that.
Can do.
Good. Okay, now I'll reintroduce wheel factorization, with a proper implementation this time.