A Prime Counting Gallery

A Few Other Recursive Formulas for Context

Okay, let's say I'm intrigued. What is this basic formula for counting primes, then?

Well, do you have a bit of tolerance for a slight, useful digression? A little context might be helpful.

Why?

I want to highlight a few other recursive formulas that should be more familiar. They have nothing to do with the primes themselves.

That's fine, I guess, but why are you bringing them up?

Well, they are mechanically similar to the formula I'll introduce in a second. I'm just trying to set the stage, so to speak. I think the formula we'll use for prime counting is actual rather astonishing for how mundane it appears, and I hope that claim is easier to see when viewed in the context of some other, more familiar functions that feel simpler. It's also a nice opportunity for a fascinating animation.

I guess that makes sense.

Good. Let's start with an old favorite when introducing recursion, factorials. If you need to define the factorial function in terms of itself, how would you write it?

Oh, that's... $\displaystyle n! = n \cdot (n-1)!$ with the end condition $1! = 1$, right? I mean, for whole numbers, at least.

Right. Now, my intention is to emphasize visual symmetry with the prime counting formula. So I'll rewrite that slightly as

And with this definition, $f(n,1)$ computes $n!$, just as you say.

That seems straightforward enough.

Here's a second example to get in the right mindset.

Go ahead.

Another common example of a recursive formula is the one for Fibonacci numbers. Do you remember that?

For Fibonacci numbers, that's... $F_n = F_{n-1}+F_{n-2}$, with initial conditions $F_0=0$ and $F_1=1$.

Right, good. Well, it turns out you can write this in a slightly different form that will be more useful for the symmetry I want to emphasize.

Define instead $f_n$ as $f_{n} = 1+f_{n - 1} +f_{n-2}$, with initial conditions $f_0 = 0$ and $f_1 = 1$. If you do that, the nth Fibonacci number will equal $1+f(n-2,1)$.

Really? Huh. That does seem a little less clear, though.

Perhaps so, but withhold judgment for a second. At any rate, it could thus be written out as

And if you attempt to compute 1+$f(n-2,1)$, you will indeed find a result of $F_n$, the nth Fibonacci number.

Okay, that seems to work, I guess.

One nice feature of recursive forms like this is the way they lend themselves to striking animations demonstrating their approach to counting in a really deep way. I won't describe how this works in detail right now, but the following animation, derived precisely from that recursive formula, should provide a really natural sense of this approach working.

Wow, that's fascinating. It seems like there are several different aspects of Fibonacci numbers at play there. It's enumerating all possible ways off adding up $1$s and $2$s, and Fibonacci numbers seem to come out the other side, right?

Pretty interesting, isn't it? Well, hopefully not too interesting; we're really here for prime numbers, not the Fibonacci sequence. Anyway, use a mouse to highlight different nodes, and you'll see the parameters of $f(n,j)$ being called at that point; this animation is essentially an evolving call graph for larger $n$ parameters.

Hopefully these two examples give a sense of the flavor of formula I'll now introduce.

The Recursive Prime Counting Formula

Okay, I've followed thus far. But what does this all have to do with prime counting?

You're right. Enough delaying. Here is the formula in its most basic, unmodified form:

And now might be a good time to point out that, if you happen to be on a PC, you can tap F12 and go to your browser's interactive console, where all the JavaScript code in this discussion is live and executable. So you can run all the code we've just seen and should see the following output if you do:

Anyway, I hope you'll concede this definition we just saw bears a certain resemblance to the Fibonacci definition I just worked through.

Sure, I can see that visually. But wait, you're saying this formula counts primes somehow?

Well, try itself yourself. If you were to graph $f_1(n, 2)$, with some caching for the sake of reasonable performance, you'd see the following immediately:

With a mouse, you can drag this graph around and zoom in and out, as though it were something like Google Maps. There are also buttons on the right to highlight representative parts of the functions.

The interactivity is certainly compelling. But the graph can't be counting primes; the $y$ value is never even a whole number after $x=3$.

That's true. It's actually more accurate to say it's a weighted prime power counting function.

Which means?

If some number $n=p^k$, the graph goes up by $\frac{1}{k}$.

Oh, okay. So, the output of this function only changes at primes or prime powers. Let's see...

Good, good.

I trust the computation here, I guess, but it's hard to understand how any of this is working...

Well maybe, as with Fibonacci above, an animation might help. At least, it might give another perspective. So this is what we'll do. We will start with some number $n$, and then we'll keep advancing it from time to time to watch the function $f_1(n,2)$ working in real time. If we do that, it will look like this:

If you're on a PC, make sure to hover your mouse over the different nodes to see the recursive function they correspond to. You can also try tapping them on mobile devices for the same information. Like before with Fibonacci, this too is basically an animating call graph of $f_k(n,j)$.

Okay. So I think I get it. That recursive function, when called over and over, is just literally tracking down any possible product of whole numbers that, when multiplied together, is $\le n$, as long as each whole number is $> 1$.

Exactly. And then it weights each count by a coefficient, and the weighted count of prime powers comes out the other side.

Why in the world does that work?

Puzzling, isn't it? I will slide by that right now, but consider tapping the "Order by Δ" on that animation. It will animate exactly the same divisors, emerging at exactly the same times, but they'll be sorted by the numbers they are decompositions of. So the nodes will be the same, but the tree will be reordered. It might help make the functioning of the core combinatorial property we'll be using clearer.

Okay. Is there standard notation for the function we just saw, $\frac 1p$ when $n=p^k$ and 0 otherwise?

People working in number theory don't seem to have settled on any standard notation for it, as far as I can tell. It's often expressed using a different function with standard notation as $\frac{\Lambda(n)}{\log n}$. Here $\Lambda(n)$ is the von Mangoldt function.

That seems strange. Is that function more commonly used?

It is. There's reasons for it, especially in analytic number theory, but we really ought to move on. We will return to it briefly by the end of this discussion, though. And meanwhile, the normal count of primes is very commonly written as $\pi(n)$.

Really? That seems needlessly confusing.

Well, standards are standards. So it goes. At any rate, for these articles I will notate our weighted prime counting function $f_1(n,2)$ as $\Pi(n)$. So, using $\pi(n)$ or the von Mangoldt function from before, we could say of $f_1(n,2)$ that

$$\Pi(n) = f_1(n,2) = \sum_{j=2}^n \frac{\Lambda(j)}{\log j} = \sum_{k=1} \frac{1}{k} \pi(n^\frac{1}{k}) $$

You can read more about this function here.

As a practical matter, $f_1(n,2)$ is not, as I've written it, a fast way to count primes.

Oh?

No, not at all. Actually, behind the scenes I use a different method to cache the prime count for the interactive graph here. The user experience would be otherworldly terrible otherwise.

I guess that makes sense, but if it's so slow, why bring up this way of writing it in the first place?

Well, if you need speed, there are techniques evolved from this specific idea that can be remarkably fast and, dare I say, elegant. But that's not its charm here. Instead, I hope you find it obvious that it's a very tidy, compact way to count prime powers. Its simplicity strongly suggests there's something natural about this way of expressing that weighted count of prime powers.

I guess I can see that.

But better still, it's also a form that can be very productively nudged slightly to explore other interesting prime number related ideas. So think of it more as a baseline or starting point for more elaborate variations. The simplicity of this form will help bring some clarity for subsequent changes.

So our subsequent dialogues here are primarily an exploration, then, something like a conceptual tour?

Right. I want to demonstrate via interactive function graphs, animating recursive function call graphs, and working JavaScript code several such changes and results. So I won't be focused on rigorous definitions or proof.

And Some Number Theory Context

If you won't focus on rigor or proof, can you at least gesture at how this connects with a more rigorous foundation?

Well, look. I'm champing at the bit to show off these variations, because they're really interesting. I have a lot of striking animations and ideas to work through. But sure, a bit of background context is probably not a bad idea.

I actively want to try avoiding calculus and complex analysis in what I have to demonstrate, for the most part, unless it's really pulling its weight. I really value that the following identities and ideas can mostly be explored easily in common programming languages. I think that's a really appealing feature of them, that they can be explored given a smart, curious reader without any university level math background.

I can see that draw of that.

But you're not wrong that a cautious or curious reader may well wonder whether these ideas are even valid. So for the sake of a bit of context, I'll quickly gesture at how these ideas connect to more common approaches in analytic number theory.

Okay.

I'll cover this more in depth later, but the recursive function $f_k(n,j)$ above can be generalized by introducing a scaling factor. With that introduction, it becomes $$f_k(n,j) = \rr{j^{-s} \cdot (}\frac{1}{k}-f_{k+1}(\frac{n}{j},2)\rr{)} + f_k (n, j+1)$$ $s$ here is a complex value.

Okay, I think I follow that added complexity.

And then, with a bit of rearrangement and an aggressive unrolling of sums, you can rewrite this exact idea as the more explicit, bulkier $$f_1(n,2)=\sum_{ {j_1}=2}^n { {j_1}^{-s}}- \frac{1}{2} \sum_{ {j_1}=2}^n \sum_{ {j_2}=2}^{\lfloor \frac{n}{ {j_1}} \rfloor} ({j_1} \cdot {j_2})^{-s}+ \frac{1}{3} \sum_{ {j_1}=2}^n \sum_{ {j_2}=2}^{\lfloor \frac{n}{ {j_1}} \rfloor} \sum_{ {j_3}=2}^{\lfloor \frac{n}{ {j_1} \cdot {j_2}} \rfloor} ( {j_1} \cdot {j_2} \cdot {j_3})^{-s}- ...$$

Okay.

And now it's time to introduce some actual calculus. If the real part of $s$ is greater than 1, then a limit exists for $f_1(n,2)$ as $n$ goes to infinity. And the limit of the entire expression ends up being $$\log \zeta(s) = \sum_{k=1}^\infty \frac{(-1)^{k+1}}{k} (\zeta(s)-1)^k$$ You might recognize this as a Taylor series for the logarithm, sometimes called the Newton-Mercator series, only here $x$ is replaced by $\zeta(s)$. And here, $\zeta(s)$ is of course the Riemann zeta function. So what I'm saying is, this idea is well within normal well-trod analytic number theory territory. It's not relying on any gimmicks or any kind of sleight-of-hand.

Well, that certainly did escalate the demands of prior math knowledge considerably.

Well, if you don't follow it, don't worry. You won't need to understand any of that to keep up with future discussions. As I say, a major point of the approach here is the style of formula can cover lots of rich ideas about primes without introducing the need for a background in complex analysis or dealing with questions of convergence.

Are there any references for these approaches?

Well, as far as I'm aware, a related form of the identity at the heart of all these articles was first published by Soviet mathematician Yuri Linnik in the early 1960s as, essentially, $$\frac{\Lambda(n)}{\log n}=\sum_{ {\substack{ j_1 =n \\ j > 1}}} 1- \frac{1}{2} \sum_{ \substack{ {j_1} \cdot {j_2} = n \\ j > 1}} 1+ \frac{1}{3} \sum_{ \substack{ {j_1} \cdot {j_2} \cdot {j_3}=n \\ j > 1}} 1-\dots$$ You can see that idea expressed in the following excerpt of a 1963 translation of his 1961 book "The Dispersion Method in Binary Additive Problems".

You could also check Chapter 13 of Iwaniec and Kowalski's Analytic Number Theory or Chapter 17 of Friedlander and Iwaniec's Opera De Cribro as a reference and discussion for this particular identity. Chapter 2 of Bateman and Diamond's Analytic Number Theory - An Introductory Course also covers a more generalized form of this idea from a different, more algebraic perspective.

Okay, that seems clear enough. What's your particular interest here?

Well, I'll admit it's a bit personal. I independently discovered a form of the recursive prime counting identity $f_j(n,k)$ above myself back in the fall of 2004 totally out of the blue as a special case of a much more general approach to counting numbers by their prime signatures quickly while using nearly no memory. And I've since evolved a couple relatively efficient methods for counting primes based on it. Indeed, although as written it's slow, with a bit of ingenuity and elbow grease, the core idea really can be harnessed into some striking ways to count primes, with one such approach running in roughly $O(n)$ time and $O(\log n)$ space with amazing constant time performance, and another running in $O(n^{\frac{2}{3}+\epsilon})$ time and $O(n^{\frac{1}{3}+\epsilon})$ space. I'll return to that topic elsewhere, but that's not the focus here.

Got it.

Okay. Enough context. Let's start examining variations of this prime counting approach.