Let's turn to our third prime counting variation then.
What's this one for?
Well, compared to the first two, this one actually has a specific use.
Okay.
As before, start with the recursive definition we've been working with:
$$f_k(n,j)=\rec{\frac{1}{k}-f_{k+1}(\frac{n}{j},2) + f_k (n, j+1)}$$and
Right.
Now, once again, we'll tweak that definition slightly like this.
First, define the following simple function:
$$h(j)= \begin{cases} 0 & \text{if } 2 | j \\ 1 & \text{otherwise} \end{cases}$$What does $ | $ mean?
$ | $ is "evenly divides". Conceptually, you can think of $h(j)$ as identifying odd numbers.
Got it.
With that, here's our adjusted prime counting function:
$$g_k(n,j)=\rec{\rr{h(j) \cdot }(\frac{1}{k}-g_{k+1}(\frac{n}{j},2)) + g_k (n, j+1)}$$What do you think this will do? Care to hazard a guess?
Honestly, I have no idea. It seems like it ought to have a big impact on the resulting function.
Okay, well, let's apply it and see what happens.
Huh. That's really surprising. At first it looks like incorporating that function makes a huge difference, but then as I zoom out along the number line, the difference becomes almost negligible.
Right. Look closely at the black function, and you'll see it counts prime powers just fine in all cases except those increasingly rare instances where $x=2^k$.
Yeah. In just those cases, the red graph increases by $\frac{1}{k}$ while the black graph stays flat.
So put in more formal math notation, this means that, here,
$$g_1(n,2) = f_1(n,2) \rr{- \sum_{1 \le k \le \log_2 n} \frac{1}{k}}$$Which is why the difference became so negligible as I went up the number line.
Exactly.
Here's another nice way to put this. Do you remember the definition of harmonic numbers?
Oh. That's.... $\displaystyle H_n = \sum_{k=1}^n \frac{1}{k}$.
Right. So using that, we can say a bit more compactly that
$$g_1(n,2) = f_1(n,2) \rr{- H_{\fl{\log_2 n}}}$$Okay. That makes sense.
Now, here's the big take home point. When thinking about the distribution of primes, this simple relation means we can just as easily work with $g_1(n,2)$ as with $f_1(n,2)$.
Okay.
And if you think about it, in excluding numbers divisible by 2, this means only 50% of numbers are used in counting here. And because we are with nested counts of divisors, that fraction compounds rapidly.
That makes sense.
I'll say more about this in a second, but I think an animation might be especially useful for intuition here.
Ah, okay. Yeah, before, a huge amount of numbers had $2$ as a factor, let alone even numbers, now that I think about it. And now they've all disappeared. There's a lot less to count. And yet it doesn't change the prime counting at all, really...
Exactly. But let me show more elaborate examples before I talk about that.
Suppose I redefine $h(n)$ to exclude more factors, say 2, 3, and 5. I would ask you to guess what that might look like, but this is actually a pretty straightforward experiment. So $h(n)$ would now look like this:
$$h(j)= \begin{cases} 0 & \text{if } 2 | j \textrm{ or } 3 | j \textrm{ or } 5 | j \\ 1 & \text{otherwise} \end{cases}$$As you say, that seems straightforward.
If you look closely at the graph, you can see that the function is a cycle 30 elements long.
Because $2 \cdot 3 \cdot 5 = 30$, right?
Right. And it's symmetrical, too. And only 8 elements of the cycle are non-zero. So that means only 26.7% of numbers are used in counting this way.
Okay.
Now that I've changed that definition, I can leave $g_k(n,j)$ essentially the same.
$$g_k(n,j)=\rec{\rr{h(j) \cdot }(\frac{1}{k}-g_{k+1}(\frac{n}{j},2)) + g_k (n, j+1)}$$So now let's compare this new function to the baseline.
So this is like the previous example, it seems, but more so. In the early graph, say between $x=0$ and $x=100$, the graph of the two functions differs by a fair bit. But by, say, around $x=1,000,000$, the two functions only differ by around 10.
Precisely. In fact, if you look closely at the black function, you'll see the only difference between the two graphs is when $x=2^k$ or $x=3^k$ or $x=5^k$. In those cases, the red graph increases by $\frac{1}{k}$ while the black graph doesn't.
As you said, pretty straightforward.
Right. So we can write this difference explicitly as
$$g_1(n,2) = f_1(n,2) \rr{- \sum_{1 \le k \le \log_2 n} \frac{1}{k} - \sum_{1 \le k \le \log_3 n} \frac{1}{k} - \sum_{1 \le k \le \log_5 n} \frac{1}{k}}$$or, which is the same,
$$g_1(n,2) = f_1(n,2) \rr{- H_{\fl{\log_2 n}} - H_{\fl{\log_3 n}} - H_{\fl{\log_5 n}}}$$So this is all following the pattern set by the previous example.
It is. Watching an animation of this style of counting should make that even clearer.
Huh. That looks really, really different. There's a lot fewer products of multiple numbers in this version.
That's true. Let me race through one last example, just to belabor the point, though.
So again, I'll redefine $h(n)$, this time as
$$h(j)= \begin{cases} 0 & \text{if } 2 | j \textrm{ or } 3 | j \textrm{ or } 5 | j \textrm{ or } 7 | j \textrm{ or } 11 | j \textrm{ or } 13 | j \textrm{ or } 17| j \textrm{ or } 19 | j \\ 1 & \text{otherwise} \end{cases} $$And if we graph that, we'll see
Fine. Does this have a cycle too?
It does. But the cycle is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 $ elements long, which amounts to a cycle 9,699,690 elements long. Of those, 1,658,880 are non-zero, meaning 17.1% of numbers are used for counting.
Hmm.
Other than that change, $g_k(n,j)$ will remain the same.
$$g_k(n,j)=\rec{\rr{h(j) \cdot }(\frac{1}{k}-g_{k+1}(\frac{n}{j},2)) + g_k (n, j+1)}$$Graph that, compared to the original $f_1(n,2)$, and the result is
And this likewise follows the pattern set by the previous examples, with
$$g_1(n,2) = f_1(n,2) \rr{- H_{\fl{\log_2 n}} - H_{\fl{\log_3 n}} - H_{\fl{\log_5 n}} - H_{\fl{\log_7 n}} - H_{\fl{\log_{11} n}} - H_{\fl{\log_{13} n}} - H_{\fl{\log_{17} n}} - H_{\fl{\log_{19} n}}}$$So this is all working as expected. And will you make an animation of this recursive function as well?
No; there really wouldn't be a point, would there? The smallest node with a product of two numbers would be $23 \cdot 23 = 529$.
Oh, right. I guess I can just imagine a long string of black nodes connected to each other in a chain and get the same effect.
Right. At any rate, hopefully that's enough examples to cement what's going on here.
It does, but it would be nice to know the point of this.
Sure. It's actually pretty straightforward.
So, in the context of computation and prime counting, this variation is really valuable. $g_k(n,j)$ with several primes factored out can often be computed drastically more quickly than $f_k(n,j)$.
Oh, I suppose that makes sense.
But when I say drastically, I mean it. Wheel factorization is commonly used in most other prime counting contexts, providing reliable and important speed increases. So this technique isn't coming out of left field or anything.
It seemed like we were quickly running into diminishing returns, though, right?
Well, normally that's true, and just going by the percentage of numbers excluded, you would think that. But here, the speed increases are honestly pretty extreme. I write about evolving fast prime counting techniques starting with these ideas elsewhere.
Okay. That sounds interesting.
Anyway, I suppose this variation can be connected to the Riemann zeta function as well, right?
Yes. With a bit of work, the above ideas can be connected like so.
Introduce a scaling factor $j^{-s}$ to the recursive definition, using one of the definitions for $h(n)$ from above.
$$g_k(n,j)=\rec{\rr{j^{-s} \cdot h( j ) \cdot (}\frac{1}{k}-g_{k+1}(\frac{n}{j},2)\rr{)} + g_k (n, j+1)}$$Then apply the recursive definition to itself over and over until entirely unrolled.
So I take it this will be following roughly in the footsteps of previous examples, then.
Yes. For a suitable value of $s$, take the limit as $n$ goes to infinity. The following identities are the result of that process, for the three examples from above.
For the first example, using only odd numbers, you end up with $$\log(1-2^{-s})+\log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\left(1-2^{-s}\right) \zeta (s)-1)^k$$
Okay.
For the second example, excluding numbers divisible by the first 3 primes, you get $$\log(1-2^{-s})+\log(1-3^{-s})+\log(1-5^{-s})+\log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\left(1-2^{-s}\right) \left(1-3^{-s}\right) \left(1-5^{-s}\right) \zeta (s)-1)^k$$
Right..
And, finally, for the third example, excluding numbers divisible by the first 8 primes (the equations for which gets a bit messy), $$\log(1-2^{-s})+\log(1-3^{-s})+\log(1-5^{-s})+\log(1-7^{-s})+\log(1-11^{-s})+\log(1-13^{-s})+\log(1-17^{-s})+\log(1-19^{-s})+\log \zeta(s) = \\ \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\left(1-2^{-s}\right) \left(1-3^{-s}\right) \left(1-5^{-s}\right) \left(1-7^{-s}\right) \left(1-11^{-s}\right) \left(1-13^{-s}\right) \left(1-17^{-s}\right) \left(1-19^{-s}\right) \zeta (s)-1)^k$$
Got it, although that really is starting to get unwieldy.
It is. Let's move on to another variation now.