Computing the Prime Counting Function with Linnik's Identity
in Time and Space,
and Related Combinatorial Number Theory Work
Nathan McKenzie
March 24, 2011
email: nathan _AT_ icecreambreakfast.com
1. Overview
This paper will describe an algorithm for counting primes in roughlytime andspace, starting from Linnik's identity. It will then describe a number of other number theoretic results springing from the same combinatorial area as Linnik's identity, including connections to li(n), a connection between the Möbius function and the prime power function, an inversion of Linnik's identity to get strict number of divisors in terms of a family of prime power functions, an inversion function for the prime power function analogous to the role played by the Möbius function to the divisor function, a generalization of the underlying patterns beneath all of these connections, and many other results besides.
The identity of Linnik[1] which we will be interested in states, for our purposes,
where p is a prime number andis the strict number of divisor function such that
The strict number of divisor function is connected to the standard number of divisor function by
where is the standard number of divisor function such that
and
The approach for prime counting here is very closely related to the method for calculating Mertens function described by Deléglise and Rivat in [2].
Table of Contents
Part 1: Computing the Prime Counting Function
The Strict Number of Divisors Summatory Functions and Counting Primes
Properties of the Strict Number of Divisors Summatory Functions
The Core Strict Number of Divisors Summatory Function Identity
Part 2: Combinatorial Number Theory Related to Linnik's Identity
More Properties of the Strict Number of Divisors Summatory Functions
Generalizing the Transformation, and Some Promising Coefficients
Appendix 1: Collection of Expressions for Mertens Function and
Appendix 2: Expressions as the Strict Number of Divisors Summatory Functions
Appendix 3: Core Identity Derivations
Appendix 5: C Source Code for the Algorithm
Special thanks to Roxanne Prichard and Mark Coffey
Dedicated, as always, to Annette
Computing the
Prime Counting Function
2. The Strict Number of Divisors Summatory Functions and Counting Primes
We begin by defining the following strict number of divisors summatory function for the function from (1.2):
Summing Linnik's identity, (1.1), from 2 to n then gives the following identity
where the right hand side is the prime power counting function.
If we rely on standard techniques, we can invert the prime power counting function like so
whereis the prime counting function and is the Möbius function, and we finally arrive at our goal, which is the number of primes in terms of the strict number of divisors summatory functions.
3. Properties of the Strict Number of Divisors Summatory Functions
So, our goal, from this perspective, is finding the fastest methods possible for calculating the strict number of divisors summatory functions from (2.1).
Some core properties used to that end will include the following
These identities and Linnik's identity above are, incidentally, enough to derive, with a bit of work, the following tidy recursive formula for the prime power counting function, which won't be used for this prime counting algorithm:
The derivation for this can be found in Appendix 4. Going down another path, by adding a second parameter, we can build another useful identity for the the sum of strict divisor functions
where the sum of strict divisor functions we're interested in is
which, with (2.4), is enough for us to count primes like so:
Although this paper will not rely on these identities, they also serve as an interesting basis for counting primes – especially with a suitably large wheel, they can perform surprisingly well for a prime counting method that uses nearly constant amounts of memory. Finding other ways of speeding up their computation is an interesting challenge.
4. The Core Strict Number of Divisors Summatory Function Identity
The core combinatorial identity we will use to count the strict divisor sums (the derivation for this can be found in Appendix 3) is the following
where a is some number for which . The useful aspect of this identity is that it only relies on values ofup to a, and values of D' up to. Thus, if we make use of our prime counting function identity from (2.2)
and keep in mind that
then, as a first pass, our identity for counting the prime power function is
There are two subsequent steps required for turning this equation into its final form for our purposes.
First, for any sum of the form
it should be clear that there are onlyterms we are concerned with, and so any such identity can be split into
The second step is choosing a suitable value for a. For this paper, we will chooseas our value for a, which means that we will need to calculate up toand up to , a task that will be covered in the next section. And so our final identity for the prime power counting function is
Obviously calculatingup to can be done relatively quickly. Thus, if you can calculateup toin roughlytime, the above equation can be computed in something like steps because of the two double sums.
It's worth remembering for all of these calculations that if , then and , so the actual number of D' terms that need to be evaluated inside the double sums is on the order of ln n.
To compute up to in roughly time and space, we will turn to sieving. First, we will need to compute all of the primes up to, which are the largest primes needed to sieve a block of numbers no greater than . We will then sieve in blocks of size, thus establishing our memory boundary, and this process will be repeated times. We will be sieving in such a way that we have the full prime factorization of all entries in each block, so each entry should be in this form:
We will specifically need the full power signature of each entry.
Because the normal number of divisors function can be calculated from the above power signature by
and the strict number of divisors function can in turn be calculated from the number of divisors function by
we can use our sieve information to calculate the strict number of divisor function for each entry in the sieve. We can then use the straightforward fact that
to give us all the values for in each block. We will have to store off the final values of the functions at the end of each block to use as the starting values for the next blocks.
As mentioned, this process runs in something like time.
6. Conclusion for
this Algorithm
The trick to implementing this algorithm, then, is to interleave the sieving described in section 5 with a gradual computation of the sums from (4.4). Essentially, the sums from (4.4) need to be evaluated in order from smallest terms of to greatest, more or less as a queue. What this means in practice is that for the first sum,
the second sum will be evaluated first (again, interleaved with the sieving of blocks of in size), and, once that is finished, the first sum will be evaluated with j starting with the value of and then decreasing until it is , all interleaved with the sieving. In the C code, you can see this process manually worked through in the function calcS1().
A similar process is necessary for the double sums. You can see this process worked through in the function calcS3().
This algorithm can be sped up considerably by using a wheel, which decreases the amount of operations involved in sieving, the double sums calculated in (4.4), and potentially a constant factor in the memory usage as well. C source code for the algorithm is present in Appendix 5, but it doesn't implement a wheel and so will not run anywhere near as fast as it could.
If anything is too unclear in this description, hopefully browsing the source code in Appendix 5 will make it more clear. Alternatively, the paper in [2] covers many of the same ideas and might be a useful reference for another description of an extremely similar process.
The appealing thing about quantitative performance numbers is that it's very easy to tell whether an algorithm or process is probably interesting to the broader social world. The algorithm described here runs in roughly time and space, which puts it in spitting distance of the LagariasMillerOdlyzko combinatorial method. Given the shallowness of my own number theory knowledge (in terms of the broader existing field of research), too, the possibilities for followon work and improvement to this algorithm, or to similar Linnik's identitybased approaches, is not so bad.
So there is much reassuring about tasks with quantitative performance measurement. In what follows for the rest of this paper, I do not have that safety net. In the course of turning thefamily of functions around in my head, trying my hardest to find ways to speed up their computation or decompose them in interesting ways, I have, not surprisingly, unearthed all sorts of other, related, combinatorial identities that seemed intriguing but that I wasn't able to find a use for in this algorithm. The rest of this paper will document those identities and ideas.
I apologize in advance if I'm cataloging wellknown research. I've tried to do my due diligence, becoming passingly familiar with several books on analytic number theory, but I'll freely concede my knowledge on that front is still fairly thin. Alternatively, it's also quite possible that much of this is either obvious or trivial.
It is probably more useful to view the rest of this paper more as a travelogue and repository of ideas than a rigorous work of mathematics. The contents tend to be selfreinforcing, internally consistent, occasionally elegant, and backed by substantial empirical tests. General processes of derivation are frequently gestured at. Nevertheless, this is not, and does not attempt to be, a work of lockstep rigor.
The rest of the results in this paper can be broadly broken up into four categories.
First, based on Linnik's identity and a related identity for the connection between strict divisors and the Möbius Function, I generate a number of combinatorial identities for expressing the prime power function in terms of the Möbius Function, the Mertens Function in terms of the prime power counting function , the strict number of divisors summatory functions in terms of strict number of prime powers summatory functions, explore an inverse function for the prime power function, and many, many other similar and related identities besides. This work will be done in sections 912. Some of those results will be collated in Appendix 1, which will collect combinatorial identities for and the Mertens Function.
Second, I will show that a surprisingly broad collection of different, relatively interesting number theoretic expressions can be given as sums of the family by simply changing the coefficients of the functions. This in turn means that, if the family of functions has been calculated, quite a large number of other values can be calculated exactly, generally in time. Additionally, because the family of functions tend to be much more straightforward to approximate than the other functions we will be looking at, this opens up a route for approximating those functions. Discussions about approximation will show up in section 8; derivations for the various identities in terms of will be sprinkled throughout sections 912. They will be collected, finally, in Appendix 2.
Third, the process of collecting and describing these identities are purely combinatorial aspects of their relationships to each other; which is to say, they generally (with noted exceptions) do not rely on the fact that happens to equal 1. They are combinatorial properties based on the relationship between the functions. Consequently, most of the identities I derive above will also apply if we change the function at the root to equal some other value, like, say, . This will let us apply these various identities to a wider range of functions, and provides a way to think about several other sequences of prime powers in terms of divisor problems. The patterns at the core of all of this will be generalized in section 13, and several interesting applications will be covered in section 14.
Fourth, in section 15, this paper will introduce a method for splitting into two separate functions, one of which will contain the discontinuous aspects of the function as a property of the fractional function {n}. Similar techniques will be shown for Mertens function.
Combinatorial Number Theory
Related to Linnik's Identity
8. The Strict
Number of Divisors Summatory Functions and li(x)
One of the more useful aspects of expressing number theoretic functions as linear combinations of D' functions (of which we will do many more shortly) is that the family of D' functions lends itself relatively nicely to approximation, particularly when compared to many other number theoretic functions.
To approximate D', we're going to try to identify continuous volumes that contain all of the lattice square/cube/etc solutions to D' functions in their entirety, and no other lattice square solutions. So, for example, for , we want to work with a volume that satisfies the following properties:
The term suggests that our volume is going to be a two dimensional hyperbola, of course. But we will still have to account for the other two constraints. To account for the first one (), we will calculate the integral from 1 to n. To account for the second constraint (), we will have to subtract 1 from inside the integral.
And so, to approximate , we can calculate the volume of the two variable hyperbola that bounds it like so:
Similarly, will be bounded by a volume that satisfies
We can actually just integrate our approximation for from 1 to to generate an approximation of that contains all lattice cubes in , and only lattice cubes from . If we do this, we will find that
If we repeat this same idea for , we will find that
In the general case, we can say
Based on Linnik's Identity from (2.2), this series of approximations for the D' family of functions gives us a way to approximate the prime power counting function
At least empirically, this is exactly and precisely equal to
(which can be rewritten as
), where is the Log Integral. Given the Prime Number Theory, this shouldn't be entirely unexpected.
One consequence of this, based on the equations above, is that it provides an exact expression for the error in the PNT in terms of the error term of various sums of number of divisor problems. Thinking geometrically, the difference between the Log Integral and the actual number of prime powers is exactly equal to the volumes of these various hyperbolas that aren't contained within a lattice point, with the series of volumes combined with signs alternating and harmonically.
All of which is to say, if we express the error term in our approximation of like so
and the error term for like so
and we generalize the error term like so
then we will find that
Now, we already know from Riemann that
where are the zeroes to the Riemann Zeta function, and so, comparing the two functions, we see it must be the case that
I'm not sure if this is interesting or not. Finding different ways of arranging, counting, and analyzing the different volumes in the set of functions seems like it could be an interesting direction to explore.
Switching gears, there is one method of approximating the family of functions that I have not explored but that I find particularly intriguing.
In Ivic [3], on page 352, there is a discussion about the Dirichlet divisor problem, and about the various divisor sums being expressed as polynomials composed of ln n raised to various powers combined with coefficients constructed from Stieltjes Constants, which is the base approximation for the number of divisor sums from which to estimate the error term. This, in turn, points back at a paper by A. F. Lavrik, “On the Principal Term in the Divisor Problem and the Power Series of the Riemann ZetaFunction in a Neighborhood of Its Pole”.
And so here is where I hit my dead end on this particular approach. We know from Ivic and Lavrik that the sums of divisors principle term can be expressed as a certain polynomial, as mentioned in the referenced works.
We also know from basic combinatorics that
And, finally, we know from Linnik's Identity that
Thus, it stands to reason that we ought to be able to approximate the prime power counting function with these polynomials composed of ln n to various powers and Stieltjes Constants coefficients. Does this simply collapse back into li(n)? Does it have a better or different error term?
Unfortunately, constructing these polynomials outstrips my own paltry analytic number theory ability. Nevertheless, it seems like an interesting place to look as an approximation of the prime power counting function (and, indeed, for all of the other number theoretic functions cataloged in this paper that can be expressed exactly in terms of the functions).
9. More
Properties of the Strict Number of Divisors Summatory Functions
9A: Overview
This section will cover a few topics related to the family of functions. First, it will explore a few more combinatorial properties of them, stressing how they differ from their nonstrict equivalents. Next, it will show that not only can be expressed exactly as a linear combination of values, but various sums of can be as well. Finally, we will invert these expressions so that we can express exactly as various sums of , and we will end with another expression for in terms of itself.
_______________________________________________
9B: Mertens Function in terms of D'
We know, from a process similar to the derivation of Linnik's identity [1], that the following useful equation is true
And so, obviously,
where is Mertens function. As a result, we could use the same process described above to calculate Mertens function in roughly time and space, although the algorithm's constant time performance would be considerably worse because of the inability to use a wheel.
_______________________________________________
9C: Möbius Inversion
From here on out, we're going to be using a strict version of the Möbius function, which will be identical to the regular Möbius function except that it will return a value of 0 for 1, and we will name this function . So, pretty obviously,
One striking difference between the strict number of divisor functions and the standard one is the effect that Möbius inversion has. We might begin by trying, in a close analogue to normal inversion,
but that equation does not produce as expected. But we're not done; because of (9.1), we can rewrite this as
Now, one of the basic identities of these functions is
and so, taking advantage of that identity, we're left with the following
which, perhaps amusingly, is almost a perverse opposite to the standard Möbius inversion.
If we try adding together two subsequent values for k on the left side of (9.3), we find that the expression on the right hand side almost entirely cancels out, and (with a final flip of minus signs), we are left with
Alternatively, if we work with , and we're sensitive to the fact that is the nonstrict version of and so counting needs to start at 1 rather than 2, we will find that
and so
_______________________________________________
9D: Sums of in terms of D'
There are some other interesting expressions we can build with . We remember from (2.2) that
If we sum that expression up for values ranging from to , we obviously have
We can again use (9.2) to collect terms on the left hand side of the equation, and we're left with
If we repeat the process again, we find we have
and, more generally,
As before, this means that if we have calculated the family of functions, we can compute the values of any of these expressions on the right hand side of the equations in time. It also provides a means, by using (8.1), for us to approximate any of these expressions.
_______________________________________________
9E: D' in Terms of Sums of
We can use the formula from (9.6) to establish, combinatorially, some more interesting identities connected to and . If we look at the first three instances of this function,
we can observe the useful feature that each successive identity uses fewer and fewer values. We can use this fact to eliminate terms from these functions, and in the process invert them. So, for example, by adding one half the second equation to the first equation, we have
thus removing from the right hand side of the equation. If we continue this process, we can isolate the functions.
Repeating this process, we will find that a sequence of coefficients emerges on the left hand side of the equation that can be generated with the following expression
with its first few values being . These numbers are the Gregory coefficients (numerators and denominators from OEIS, see also here and here  search for Gregory coefficients on this last link ), which are in many ways similar to the Bernoulli numbers. And so, with these coefficients, we have
and, more generally,
It should be fairly straightforward, from inspection, that we can rewrite this as
and
The expression in (9.8) can be rewritten as the rather tidy
This identity can also be written as
(keeping in mind that ) and
both of which suggest that the sum
might be worthy of study, particularly in terms of how well it can be approximated. At least from observation, it lacks the sorts of sharp discontinuities that and have.
Working through all the arithmetic from (9.9b), this also means that we can say that
_______________________________________________
9F: Another Expression for
As a final observation from this line of reasoning, let's take another look at (9.8). As always, . Consequently, if we're willing to do a little bit of term rearrangement, we can turn (9.8) into the following identity for
_______________________________________________
9G: Another Expression for
Though the derivation for this won't be given here, can also be expressed as
where are the Bernoulli numbers with . This is a special case of the more general formula
which can be generalized even further as
where .
Similarly, using the Gregory coefficients from (9.7) above, we can also say
This can be generalized further; if we have any two sets of coefficients, and , and those coefficients are multiplicative inverses (like and ), then we have
There's actually far more we can do with the family of functions, but we're going to define some other new functions first.
10. The Strict
Möbius Function Summatory Functions
10A: Overview
We're going to work in this section with a strict version of the Möbius function, which is to say, a Möbius function that yields 0 for the input of 1. We're also going to mirror the strict number of divisors functions in terms of structure, building Möbius equivalents of functions like and . Having established this family of functions, we're going to show how to express all of them exactly in terms of the strict number of divisors summatory functions. Having done that, we will then have what we need to invert the process, expressing the strict number of divisor functions precisely in terms of these new strict Möbius summatory functions. This, in turn, will allow us to build a version of Linnik's identity for the strict Möbius function, and so we can express the prime power function in terms of the Möbius function and in terms of the Mertens function. Finally, we will use our new strict Möbius functions to build new kinds of sums of and show how they can be expressed exactly as linear sums of our functions.
_______________________________________________
10B: Core Identities
We have
We will then sum these identities to work with the following family of functions
This function obeys the property
which can be rewritten as
with
This can essentially be restated as
and more generally
_______________________________________________
10C: M' in terms of D'
We know from (9.1) that we can express the strict Möbius function as
and thus
Relying on (9.1), we can sum up versions of the left side and right side of this equation like so
We can rely on (10.4) above for the left side of this equation, and (9.2) for the right side, and we're eventually left with
This process can be repeated as desired, giving us the more general formula
Given that the Möbius function and number of strict divisors can be expressed as
and
this also means that we can express the relationship between them as
And so, once again, based on (10.5) we find yet more reasonably interesting number theoretic quantities that we can calculate in time if we have already calculated the family of functions. This also provides a means of approximating these functions with (8.1), of course.
_______________________________________________
10D: D' in terms of M'
If we take a closer look at the m' functions in terms of d', we can notice something useful:
Each doesn't rely on any values of where . So, for example, if we subtract from , we have
And so we've eliminated the term from the expression. If we then add to the left hand side of the expression, we can eliminate from the right hand side of the expression. If we continue in this fashion, we can express any value of in terms of . (This process is extremely similar to series reversion.) This process reveals that, in fact,
and
Which in turn means that anything we can express as combinations of we can express as combinations of , and fairly trivially. In general, this is less useful, because these functions are harder to work with. Nevertheless, it does allow us to do some interesting things.
_______________________________________________
10E: Inversion
Because the strict count of divisors and the Möbius function are inverses, we might be inclined to sum up an expression like the following to get an inverse, which would work if we were working with the nonstrict equivalents:
Much as with Möbius inversion for the strict number of divisors, this does not in fact invert. We know, however, from (10.7) that we can rewrite as
If we thus replace with this expression in our inversion attempt, and then rely on (10.4) to collect terms, we find that we have
If we add the expression on the left together for two subsequent values of k, nearly all the terms on the right cancel out, and we're left, with a quick flip of the minus sign and an insertion of , which of course is just 1, with
Much as with inversion and , we will also find, if we use the nonstrict version of , that
and
_______________________________________________
10F: In terms of M'
We know from Linnik's identity that
We have shown, through the process that led to (10.8), how to express functions in terms of , which means we can change the functions in the summed version of Linnik's Identity with the family of functions. If the resulting coefficients are worked through, which is not exactly a pleasant task, we're left with the following identity:
and, consequently,
Disregarding, for a moment, my notation, this means we have now expressed the prime power function in terms of the Möbius function
and, if we use to mean the Mertens Function,
which is
and if we work through the arithmetic, we have
The formula in (10.10) is also adequate for us to put together another recursive definition of , namely
_______________________________________________
10G: m' Sums of In terms of M'
We can take the identity from (10.10) and build the following sum out of it
We can then apply (10.4) to the left hand expression, leaving us with
If we repeat this approach again, we have
and, more generally,
_______________________________________________
10H: m' sums of In terms of D'
The identity (10.14) lets us express various sums of in terms of thefamily of functions. As usual, however, the functions tend to be easiest to evaluate and approximate. Fortunately, equation (10.5) lets us convert equations expressed in terms of into equations expressed in terms of. As usual, walking through the arithmetic isn't precisely engaging, but if we work through this process, we arrive at expressions like
and, if we define the following combinatorial set of constants
we ultimately find that
_______________________________________________
10I: Other Connections Between M' and D'
A handful of other properties of and in relation to each other will be provided here without derivation or comment.
If
then
If
then
For some value a <= k
and
11. The Strict
Number of Prime Powers Summatory Functions
11A: Overview
This section is going cover a family of functions built from the prime power function that is suggested by Linnik's Identity. It will provide some core identities of that family of functions, it will show how to express various entries in terms of , and it will allow us to invert Linnik's identity, and show how to express both and in terms of it. We'll end with another expression for in terms of our new strict number of prime powers functions that rely on Bernoulli numbers.
_______________________________________________
11B: Core Identities
We're going to work in this section with the prime power function, repeating many of the same processes we did with the M' functions. And so we have
We will then sum these identities, so that we are working with the following family of functions
It should be obvious that, in this notation,
These functions obey the following combinatorial identity
or, which is the same thing,
All of this can be rewritten as
and more generally
Similar to (3.3), the functions can be expressed in ways that take advantage of their natural symmetries, similar to the Dirichlet hyperbola method, with a taking an initial value of 2.
_______________________________________________
11C: P' in terms of D'
From Linnik's identity, we know that
and
By (11.4), we know that
We can use Linnik's identity to convert both functions on the right hand side of the equation to get them in terms of D' and d', so that we have
If we multiply all these terms out, we can make use of the basic properties of D', from (9.2), to collect terms, at which point we will find that
We can repeat this process to evaluate , starting with
and then swapping out with Linnik's identity and with the sum in terms of that we just calculated. If we then use (9.2) to combine terms, we find that we have
This process can, of course, be repeated. In the general case, if we have the following formula for generating coefficients
then we have the following general formula for expressing in terms of
and, correspondingly,
Equation (11.7) is a somewhat interesting statement. Essentially, it provides a mechanism for approximating, by (8.1), not just the number of prime powers less than some number n, but also the number of pairs of prime powers multiplied together, or triplets, and so on. It also means that, if you have already calculated the entire family of family of functions, which, by the results of this paper, you can calculate in at worst roughly time and space, you can compute any of these values in time.
It should be obvious that, because of the results from (10.10) and (10.11), we can also express in terms of . I won't work through the derivation here, but it's almost identical to the process for , above. The results are extremely similar, even using the same coefficients. They are as follows
and, correspondingly,
_______________________________________________
11D: in terms of P'
Now that we have the family of functions in terms of , we will notice that any given equation for doesn't rely on values of where . This gives us enough room to isolate values of and express them in terms of . As with section 10D, this process is extremely similar to series reversion.
We begin with the sum of Linnik's identity
If we take our expression from
multiply it by one half, and then add it to our expression for , we have
We can then continue this process by multiplying our expression for in terms of by and subtracting it from this expression. If we continue this process, we can eventually isolate . Once we do, we find we are left with
or, which is to say,
and, consequently,
This is essentially Linnik's identity inverted.
Equation (11.9b) also bears a striking resemblance to the power series expression for the exponential function
Once again, stepping away from my notation for a second, we can rewrite (11.9) as
and (11.10) as
_______________________________________________
11E: in terms of P'
Now that we have equations (11.8) and (11.10), we can build formulas for more values of . If we begin with
we can sum both sides of the equation by values ranging from to , like so.
The right side of this equation is obviously . On the left side, meanwhile, we can replace by
(11.10) to stay in terms of , and so we have (with a little bit of unrolling)
If we multiply out this expression, collect terms, and then make use of (11.5), we find that we have
If we do this exact process again, we have
And, of course, we can ultimately express this more generally. If we have the following coefficients
then we have
and
Abandoning my notation again for just a second, this means that, just as one example,
_______________________________________________
11F: in terms of
As before, the process that generated (11.14) can also be used to generate a number of identities that put in terms of . Although it won't be worked through here, the process is essentially identical to what has already been shown. If we work through it, we find that, with the coefficients from (11.13),
and
and, in particular,
Once again, abandoning my notation for a second, this means that
where M(n) is Mertens function, and
except, of course, for the value of 1.
_______________________________________________
11G: Recursive Expressions for and in terms of
As with so many other expressions throughout this paper, we can reformulate (11.9) and its M(n) equivalent a recursive expressions, and, as such, we have the following
and
where M(n) is Mertens function. Setting aside my notation again for a second, this means that
and
_______________________________________________
11H: In Terms of
From Linnik's Identity, we know that
If we make use of the basic identity from (3.1), this means that
or, alternatively,
(11.14) and (11.15) provide us with the means for expressing and in terms of and . Thus, we can change the right hand sides of (11.24) and (11.25) to be in terms of . This paper won't work through the math of collecting these coefficients, but if we go through this process for (11.24), we will find that
which are not entirely unfamiliar coefficients. In fact, if are the Bernoulli numbers, with , then we have
and
which, with the arithmetic worked through ((11.25) would yield identical results), is
The expression (11.27) leads to yet another interesting recursive definition of , namely
which is essentially the inversion of (9.10). Again, abandoning my notation, this means that
and
_______________________________________________
11I: Another Relationship between and
If we mirror the processes that led to (9.10) and (11.28b), we can derive the following recursive identities
and
where are the Bernoulli numbers, are the Gregory coefficients found in (9.7), and M(n) is the Mertens function.
If (11.30) is unrolled, it can also be written as
which, when the arithmetic is worked through, results in
Working through (11.29) will produce (10.12b).
This identity can also be written as
(keeping in mind that ) and
_______________________________________________
11J: More Identities
A few more identities connected to the family of functions will be given here without derivation.
Additionally, there is an equivalent here for the equation from (9.13),
where are the Bernoulli numbers with , but these functions reduce to a simpler form here because, by (11.10), the left hand sum reduces to 1, and so we have
which, of course, (11.26) is a special case of.
12. The Strict
Inverse of Prime Powers Summatory Functions
12A: Overview
This section will introduce an inversion function for the prime power function of section 11. It will provide several more interesting properties of that rely on this function, and it will also provide methods to express this inversion function in terms of .
_______________________________________________
12B: General Inversion
One of the more interesting aspects of the relationships cataloged in sections 9 and 10 between and is that they're generally purely combinatorial relationships; they don't rely on any specific properties of at all, which is, in the entire system, the only function that isn't based on any other identities in the system. Consequently, we can draw the conclusion that, if we have some function , and we define the following expression
then the inverse function for , in this context, will be given by
If you then build extended values of
and you build some summatory functions
You'll then find that , , , and possess all the relationships that and have, regardless of the function (note that, in sections 9 and 10, this only applies to equations that are solely expressed in terms of and and and , with none being explicitly evaluated.)
So let's do this now with our prime power function, , from section 11.
_______________________________________________
12C: Core Identities
For this paper, we'll name our inversion function q', so
And so on. The first few values for , starting at 2:
We also have our summatory function
is essentially the Möbius function of the prime power function, and its Mertens function. also satisfies
and more generally
Additionally,
and, more generally,
Our interest in and comes mainly from what other relationships about they let us express. Because these identities are derived in exactly the same fashion as those for and , their paper trail will be left out here.
Of note is
Additionally,
and
Because , if we evaluate this last expression for , we get
Which is to say,
Additionally,
which, with the arithmetic worked through, leads to
which has the picturesque quality that the sum only consists of Q' of n over prime powers. The inverse, from
can also be written as
Other relationships that apply include (10.5) through (10.8), with P' and Q' replacing D' and M'.
_______________________________________________
12D: Q' in terms of D'
As always, both for approximation and computation, it's attractive to be able to express functions in terms of the families of functions. The family of functions can, in fact, be expressed thusly, although the fractional churn that is applying to the coefficients is starting to become slightly more severe. At any rate, those identities will be given here. The process for arriving at these values is the same sort of inversions that have been happening throughout the course of this paper, so they won't be detailed here.
and, more generally, if we have the two family of constants
(which were the constants for converting into )
and
then
_______________________________________________
12E: Nonstrict q' and nonstrict P'
One other side result for . To connect back more to the regular (nonstrict) divisor and Möbius functions, we can define a new function, , which is identical to , except that . We can also do the same thing with , and so in this context with be a prime power function where .
This opens up the door to a few other interesting identities.
First, we have the following identity to translate from our strict functions to these new nonstrict functions.
Second, we can use these two identities to create a prime power inversion formula, such that if
then this can be inverted with , and
This means, too, that if
then
The family of functions inverts normally, so
and in particular , which is equal to , is
13. Generalizing
the Transformation, and Some Promising Coefficients
13A: Overview
This section will begin by introducing repeated transformations, showing how to express both and as some other families of functions. It will then massively generalize the underlying process, introducing a general transformation technique that essentially captures most of the relationships presented in sections 912 as well as opening the door to many more. It will end by listing some other promising coefficients to explore.
_______________________________________________
13B: Repeated Transformations
From [1] we know, using my notation, that
and from (10.7) we know that its inverse,
is also true. So these are, essentially, reversible actions. It's interesting, incidentally, to draw the connection here between both of these expressions and
At any rate, as such, this transformation cannot be repeated for any sort of interesting results.
This is not the case for the connection between and . We know from Linnik's identity, again in my notation, that
Conversely, we also know from (11.10) that
all of which bears an important resemblance to
and
_______________________________________________
13C: The Exponential of
Unlike with the Möbius inversion above, both of these are transformations that can be repeated. And so, for example, if we define a new function with the following properties
and then go through all of the typical work performed on new such functions in sections 1012, we will find that, for example,
and that all of the to relationships will be repeated, with in the role of , and with in the role of .
This family of functions Z' has the interesting property, incidentally, of being combinatorial related by
At any rate, regardless of how many times this process is repeated in either direction, we should still end up with families of functions that can be expressed exactly as linear combinations of the family of functions, and approximated or evaluated thusly. Actually, what's more, any of these families of functions (and their inversions) can be expressed exactly as linear combinations of any other family of functions or its inversions.
_______________________________________________
13D: The Log of
Purely for the sake of novelty and collecting more formulas for , we will end this short stub of a section with the observation that, if we define the following function in terms of the family of functions from section 11,
and then proceed through all of the other function defining we've tended to do, we will find that all of the to relationships will be repeated, with in the role of , and with in the role of , and thus we will see that
and, where are the Gregory coefficients from (9.10),
_______________________________________________
13E: Generalizing the Transformation Process
Taking a higher level view, if we have some function , and we define the following relationships
and we have some sequence of coefficients , and we further define the following relationships
then we will find the following relationships hold:
or, which is the same thing
Additionally,
If we define the following sequence of constants
then we will further find that
and
If , has a corresponding series of coefficients that can be used to invert these relationships. As before, this process is extremely similar to series reversion. If we have from (13.6), then
and, for ,
We then have
and
and
We will also find the following relationships hold:
or, which is the same thing
If we define the following sequence of constants
then we will find that
and
This is, essentially, the basic pattern present in sections 912. Linnik's identity is one such transformation, and (11.10) is its inversion. [1] gives another such identity for, roughly, , and (10.7) is its inversion..
As an aside, we can generalize the property from (9.16): if we have any two sets of coefficients, and , and those coefficients are multiplicative inverses (like and ), then we have
Additionally, we can generalize the identity from (3.3) to express the symmetries of these functions as
_______________________________________________
13F: Some Transformation Inversion Coefficient Pairs
The following pairs of coefficients, calculated with (13.10), can be used to convert series between each other:


So, as an example, if the coefficients for expressing in terms of is , then the coefficients for expressing in terms of is .
_______________________________________________
13G: Some Other Possible Coefficients
, , , , and related families of functions, can all be expressed exactly as linear combinations of . They can also all be expressed exactly as linear combinations of , and of , and of , and so on – as can, in fact, . Any set of functions can serve as the basis for all the others, which the details of 13E should make clear.
This, incidentally, means that all of these families of functions have a set of coefficients that satisfies the equation
and, further, that all of them also have coefficients that satisfy the equation
Important to note is that each of these families of functions are governed by the same distribution patterns that govern the . In particular, if we have the family of functions given by
then we will find that when , . It will also generally be the case that when , , unless the coefficients cause the terms to cancel out. Additionally, and when
This paper has primarily explored families of functions of the form where has represented some sort of normal mathematical relationship. So, by coefficients, if mirrors the identity n, then mirrors , mirrors , mirrors , mirrors , and mirrors . This is largely captured in the table in 13F. The connection of these coefficients to normal functions is useful here, but it is not necessary. In particular, we can look for coefficients that are selected because the resulting family of functions is more amenable to analysis and approximation – much as the family of functions are easier to reason about and calculate than, for example, the family of functions.
A few families of functions that might be interesting to explore in this regard are, if are the Gregory coefficients found in (9.7),
and, repeating this process,
Another possibly interesting function to explore is
At least visually, all of these families of functions seem to have smaller discontinuities, especially (13.22) and (13.23). Hence, it might be interesting to see if these functions can be approximated well, and then to express our other families of functions, like and , in terms of them.
So, as just one example, for (13.23), , the Gregory coefficients. If is plugged into (13.6) and then (13.9) and (13.10), this gives us a set of coefficients such that
14A: Overview
An interesting aspect of almost all of these identities, as alluded to in section 12 and elaborated on in 13E, is that they generally are combinatorial aspects of the relationships between these functions; the fact that is generally not relevant to these identities...
This in turn means that many of the identities found in sections 9 through 13 will still hold even if we swap out with some other function. (Note that the following is mostly based on heuristic reasoning and a fair bit of empiricism) As far as I can tell, these relationships hold with taking on all sorts of values, but there's a much, much smaller range of functions for which the resulting identities say anything interesting about prime power sequences – from what I have found, essentially only for cases when , of which is obviously one such case.
_______________________________________________
14B:
So, for example, if we now use , then we will find that we have
and so on. In this same scheme, we have
and so on as well. At this point, all of our identities, particularly from section 11, should still hold, and so we can say, for example, that
which is essentially Linnik's Identity for the function . Additionally, we should also be able to say, at this point, from (11.9), that
As before, for most functions, it's likely easier to evaluate or to approximate the family of functions than anything connected to prime powers; all of the relationships found in Appendix 2 below should hold for the family of functions just described. Obviously Möbiusstyle inverses for both of these functions, with all attendant properties, could be generated as well.
Perhaps equally interesting for this case are the nonsummatory identities
and, using from before as our prime power function
This can all be rewritten recursively as
and
_______________________________________________
14C:
As another example, if we have , then we obviously have
(14.9)
and so on, and we also have
(14.10)
and so on – essentially, we're looking at both the harmonic series and its prime power equivalent here.
Given these two families of functions, we in turn have
(14.11)
which, again, is essentially the Linnik's identity for this family of functions, and we have
(14.12)
where in the nth harmonic number. And, of course, we have all the other identities from sections 913 besides.
This can all be rewritten recursively as
(14.13)
and
(14.14)
_______________________________________________
14D: Generalized
And so, more generally, we have
where a can, at the least, be any positive or negative real number.
We then have
and
This can all be rewritten recursively as
and
It should be pretty obvious from inspection that, as n approaches infinity in these identities, the limit of from (14.15) is , the Riemann Zeta Function. It's not too difficult to see how the combinatorial arguments here continue to apply (and the more general transformation process from 13E too).
This paper has no particular results from this process, only a general observation that this seems like it could be a productive or at least interesting tool.
15.
Discontinuities as Fractional Parts
15A: Overview
In this section, we're going to split into two separate functions, one of which will be fairly smooth and continuous, and the other of which will contain all the discontinuous oscillations. We will do this with , too. This will be done in the hopes of providing another angle for examining the oscillating parts of both of these functions.
_______________________________________________
15B: Replacing Floor Functions with Fractional Parts
It should be clear that, if we denote the fractional part of a number by {n}, that we can take, say, ,
and we can replace the floor with our fractional part like so
which can be rewritten as
(15.1)
A moment's thought should make it clear that we could do this for any value of , and in turn for both and , as well as all the other functions expressed as linear combinations of in this paper.
It turns out that the first double sum in (15.1) happens to be relatively smooth and continuous, at least in comparison to almost all the other functions studied in this paper, and so this process lets us isolate the sharp and discontinuous oscillations of the functions into sums of the second sort. We will discuss the left sums first.
_______________________________________________
15C: The Function D*
So let's go ahead and name this new family of functions D*. They have the following properties.
(15.2)
They're almost identical to except, of course, for the lack of a floor function.
If our regular function is closely related to the regular number of divisors functions , these new functions also are connected to the Harmonic number series; in fact, if is the nth Harmonic number, such that
then
(15.3)
For these functions, it will be useful to define a series of strict number of divisor harmonic numbers, such that
(15.4)
With our new series , we can express the following aspects of D*
(15.5)
(15.6)
(15.7)
As mentioned, these functions are much smoother than which (15.6), combined with (15.4) would highly suggest.
_______________________________________________
15D: The Function P*
Because our overarching goal is to extract the discontinuous aspects of , we're going to build a function similar to D* but for prime powers.
Our function P* can be defined by Linnik's Identity equivalent,
(15.8)
or, equivalently,
(15.9)
A
graph of P* from 0 to 360
P* has several identities similar to D*. If we define the following, where,
or, equivalently,
(15.10)
we will find that
(15.11)
and
(15.12)
and
(15.13)
Looking at (15.12) and (15.10) should be enough to make it clear that P* is a relatively smooth function.
I'm not currently sure how easily or tightly P* can be approximated.
_______________________________________________
15E: Separating out P*
The prime power counting function can be expressed as
Mirroring the process that led to (15.1), we can split this up into two parts,
(15.14)
(15.14a)
(15.15)
We have at least suggestive evidence from (15.12) and (15.10) that P* is a pretty smooth function, and so it can't account, at all, for the discontinuities that show up in . This in turn suggests the jumps in must be equivalently encoded in (15.14a) somehow.
A graph of from 0 to 360
At least visually, this certainly seems to be the case.
If we name the function in (15.14a) , then we can rewrite (15.14a) as
(15.16)
or
(15.17)
which is
(15.17a)
which is also
(15.18)
It can also be expressed as
(15.18a)
where are the Gregory coefficients.
Quite similarly to (11.27a), if we work through the arithmetic, we have
(15.18b)
_______________________________________________
15F: Recursive Sums of P* and
A few more recursive relationships of these functions follow, with the Gregory coefficients from (9.7)
(15.19)
(15.19a)
The connection between (15.20) and (9.10) is perhaps interesting. Additionally,
(15.20)
and
(15.20a)
both of which are closely connected to (11.20).
_______________________________________________
15G: The Function M*
We can also repeat this process for , which is Mertens function minus 1. So, we have
or, equivalently,
A graph of M*(n) from 0 to 360
M* has several identities similar to D*. So
(15.21)
and we will find that
(15.22)
and
(15.23)
and
(15.24)
Looking at (15.23) and (15.21), it should, again, be pretty clear that M* is a relatively smooth function.
_______________________________________________
15H: Separating out M*
can be expressed as
Mirroring the process that led to (15.1), we can split this up into two parts,
(15.25)
(15.25a)
where M(n) is Mertens function. Once again, M* is a pretty smooth function, and so it seems very likely that the discontinuities of M(n) must be encoded in the function described by (15.25a). And, at least visually, that does seem to be the case.
If we name the function in (15.25a) , we can rewrite it as
(15.26)
A
graph of
from 0 to 360
_______________________________________________
15I: Recursive Sums of M* and
These functions also have the following properties
(15.27)
and
(15.28)
16. A Few
Identities for Chebyshev's Second Function,
This section will provide just a few identities for , Chebyshev's second function, which is defined as
where is the Mangoldt function, or, in the notation from this paper,
We will start with an identity apparently from Mertens, the derivation of which is not clear to me... so this section will be a bit fuzzy.
We start with
where is the Mertens function.
The beginning of Section 9 showed how we can express Mertens function in terms of the family of functions, and so we can rewrite (16.3) as
which, with a bit of arm waving, has the raw material to yield the following recursive formula
The following similar recursive identity also seems to hold
And lastly, if we take (16.3) and make use of our identity from (11.16) which expresses the Mertens function in terms of the strict prime power function, we have
This can be rewritten recursively, giving us
As much work as this paper has covered, there are still plenty of open avenues for further exploration. A few of those will be detailed here.
Section 8 discusses a method for approximating the family of functions in some interesting ways that have not been attempted in this paper. This seems intriguing.
At least visually, the functions in (13.23) look especially interesting, particularly for approximation (particularly because they can be inverted to give an exact expression for and because they are relatively smooth, especially for higher values of k for ). This could warrant further exploration.
Section 13 outlines a general method of transforming both and into other series. Are there other series that are useful to explore? What are the limits of such transformations?
The Möbius function is, of course, rife with all sorts of interesting combinatorial identities, like the identity of HeathBrown found in identity of Linnik[1] and the Möbius version of Vaughn's identity. Are there similar identities for a nonstrict version of the primepower counting function , where ? Could any such identities be useful for fast prime counting or other results connected to primes?
More generally, this paper has been entirely and solely concerned with strict versions of these functions (so functions that begin counting at 2). Are there any interesting properties when considering nonstrict prime power counting functions?
Equation 11.8, seen here,
seems awfully interesting, and yet this paper has little to say about it. Can anything fruitful be done with this line of equations and general area of research?
In particular, can we use this identity to count primes quickly? The general approach would look like this: first, let's work with an altered, partially sieved version of that yields 0 for powers of selected primes. So, if we have some lowest prime L we are interested in, we will have
If we then denote Legendre's identity as , the count of numbers left over after a partial sieve, then we will find that
Our goal, of course, is to find , so with a little term rearrangement, we have
So we need to calculate the terms on the right hand side of the equals sign. We might remember, at this point, our equation from (11.5a). If we adjust it slightly to account for our partial sieving, we have
and so our goal, from this method, is to calculate
for some well chosen value of L. How promising is this approach?
Because this paper arose almost entirely from my work on making my prime counting algorithm, some of these results are relatively under explored. Section 14 in particular gestures in large directions that are mostly untouched, at least by me. Are there useful things to be done with these observations?
This paper contains almost no calculus or analysis, and makes no use of ZetaFunctionrelated expressions for and , particularly their socalled explicit formulas. Can anything interesting be said by applying such techniques or ideas to any of the combinatorial identities found in this paper?
Can anything new or interesting be said about based on analogues to techniques in this paper?
Equations (11.8), (11.10), and (11.19) all give ways of expressing some very common terms that show up in a wide range of equations in terms of combinations of prime powers. Are there equations for which applying these three identities provide interesting insights?
And, pretty obviously, finding faster ways to calculate the functions, or more interesting ways to approximate them generally, or to say things about their error terms, have spill over effects to all the other functions expressed exactly by functions as detailed in this paper.
[1] J. B. Friedlander and H. Iwaniec, Opera de Cribro, 346347
[2] Deleglise, Marc and Rivat, Joel, Computing the summation of the Mobius function. Experiment. Math. 5 (1996), no. 4, 291295.
[3] Ivic, A. A. The Riemann ZetaFunction: The Theory of the Riemann ZetaFunction With Applications. New York: Wiley, 1985, 352
Appendices
Appendix 1: A
Collection of Combinatorial Expressions for Mertens Function and
The Mertens Function and the Prime Power counting function are two particularly interesting functions. Here will be collected many of the combinatorial identities for these functions, where is the strict number of divisors summatory function from (3.1).
_______________________________________________
or, which is essentially the same,
which is
If we have the following series of constants, the Gregory coefficients,
then
If we have as the strict Möbius summatory function, from (10.4), then
Or, which is essentially the same,
and, again, which is the same, if is the Mertens Function,
which is
If we have as the strict prime power summatory function, from (11.5), then
or, which is the same, of course,
If we have , which are the Bernoulli numbers, and , then we have
and
both of which can be rewritten as
and
If M(n) is the Mertens function,
If we have as the strict inverse of prime powers summatory function, from (12.1), then
and
and, from (12.5b),
And from (13.1)
And, which is the same thing, from (13.1)
And we also have, with the Gregory coefficients from above,
If we have from (15.10), and {n} is the fractional part of n, then
As per (13.12), if is some function in terms of such that, with coefficients ,
and with inversion coefficients derived from through the formula described in (13.10), then
and
Additionally,
_______________________________________________
Mertens Function
which can be reformulated as
which in turn is the relatively well known
The following four statements are essentially restatements of another idea
If are the Gregory coefficients from (9.10), then
and, which is essentially the same identity, from (11.30b)
If we have from (15.21), and {n} is the fractional part of n, then
As per (13.12), if is some function in terms of such that, with coefficients ,
and with inversion coefficients derived from through the formula described in (13.10), then
and
Additionally,
Appendix 2:
Expressions in Terms of the Strict Number of Divisors Summatory
Functions
Because they are scattered through out this paper, I'm going to collect here all of the different identities referenced throughout this paper that can be expressed as linear combinations of (3.1), both for computation and approximation. Once again, if you can calculate the family of values then you can calculate any and all of these values in time.
Here is the strict Möbius summatory function, from (10.4), is the strict prime power summatory function, from (11.5), and is the strict inverse prime power summatory function from (12.2).
Although for most of this paper , the prime power counting function, and , the Möbius function, see section 14 for a considerable increase in the generality of these expressions and ideas.
If we have the constant
then
And if we have the constants
then
And if we have the constants
and
then
Appendix
3: Core D' Identity Derivation
We want to show here the core combinatorial identity used for evaluating in this paper.
Rather than derive this process generally, we're just going to show how to derive it for a single value here, and let that point to how the process of deriving such identities works.
For the sake of explanation, we will define
(a3.1)
and thus
We will work through this for . We begin with the most basic property of ,
Our entire goal in using the process is to only calculate values of We will operate, during this derivation, as though such values can be looked up instantly, which the sieving takes care of for the main algorithm. So, obviously if we split this formula into two pieces,
(a3.2)
The second sum is our , and so we have now
(a3.3)
Looking at our remaining sum, we know that we can rewrite it as
(a3.4)
Our entire goal in this process is to avoid calculating any values of Thus, we can take each of these sums and split them in a fashion similar to (a3.2) And so we have
(a3.5)
Each pair is split up between values of where on the left and the rest on the right (which, by this scheme, can be calculated automatically). So let's separate out these two sets of numbers. With a bit of reflection, it should be clear that, if the right hand side terms are collected, they are equal, in a more general version of this calculation, to
(a3.6)
which, if we go back to above, is the value for the inner loop when m = 1.
So, we have taken care of the right hand terms of (a3.5). Let's collect the our remaining terms.
If we manually write these sums out, we have
If we then manually add up these remain terms, we will find that we have
(a3.7)
And so we can use (a3.6) and (a3.7) to rewrite (a3.5) as
(a3.8)
which in turn lets us rewrite (a3.3) as
(a3.9)
It's worth taking a moment to point out that the process that let us derive (a3.8) can be generalized (and in fact we will continue to use it in this section). The generalized identity is
(a3.9a)
So now, continuing our goal of only evaluating values of where , we're left to evaluate (a3.7) Similar to (a3.4) above, we can rewrite (a3.7) as
(a3.10)
Also similar to (a3.5) above, we can split these terms into two groups, those that rely on for , and the other terms. And so we have
(a3.11)
Once again, these right hand expressions are all of the form for , and so we can assume instant computation for them, and we can collect them as
(a3.12)
which, if we go back to above, is the value for the inner loop when m = 2. And so, if we collect our remaining terms in (a3.11), we have
(a3.13)
If we once again manually write these sums out, we have
(a3.14)
If we then manually add up these remain terms, we will find that we have
(a3.15)
Which means, if we make use of (a3.12) and (a3.14), we can rewrite (a3.11) as
(a3.16)
and thus (a3.9) as
(a3.17)
We're nearly done with this laborious process. Looking at (a3.17) and remembering our goal of never calculating a value of where , we're left to calculate the remaining sum, (a3.15). As before, we can rewrite (a3.15) as
(a3.18)
Following the pattern established in (a3.5), we can split these sums into
(a3.19)
Once again, these right hand expressions are all of the form for , and so we can assume instant computation for them, and we can collect them as
(a3.20)
which, if we go back to above, is the value for the inner loop when m = 3. If we collect our remaining terms in (a3.19), we have
(a3.21)
Write these sums out, and we have, of course,
(a3.22)
and, as before, if we collect terms, we rewrite this sum as
(a3.23)
Unlike in previous iterations, however, we're going to break our fundamental rule. Because = j – 1 and can be calculated in constant time, we can end at any computations relying on it, even when . (a3.23) is from (a3.1), above. Thus, relying on (a3.23) and (a3.20), we can rewrite (a3.19) as
(a3.24)
This in turns lets us rewrite( a3.17) as
(a3.25)
It should be clear from inspection of (a3.1), (a3.6), a(3.12), and (a3.20), that
and so we finally arrive at our desired expression for ,
(a3.26)
This process obviously can be generalized, and thus we end at our desired expression,
_______________________________________________
Deriving the First Recursive Formula for
We want to show that we can express as
We begin by noting that our various strict number of divisors summatory functions can be written as follows
and so on. Consequently, by Linnik's identity, we have
Looking at these sums, it should be clear that they can be rearranged like so
and it's just a small jump from here to extract the recursive relationship out from the middle of this equation.
This process is the core of all the other recursive relationships that show up in this paper.
Appendix
5: C Source Code for the Prime Counting Algorithm
This is a C implementation of the algorithm described in this paper. Owing to precision issues , it actually stops returning valid values at relatively low values, say around 10^11, an eminently fixable problem. This code can be sped up quite a bit, at least in constant terms, by implementing a wheel. There are almost certainly other bits and pieces of this code (particularly in the functions d1 and d2) that can be sped up quite a bit as well, in constant terms.
 #include "stdio.h"
 #include "stdlib.h"
 #include "math.h"
 #include "conio.h"
 #include "time.h"
 typedef long long BigInt;

 static BigInt mu[] = { 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1,
 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1,
 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0 };

 static BigInt* binomials; /* This is used as a doubly subscripted array, 128x128. Indexing is done manually.*/
 static BigInt nToTheThird;
 static BigInt logn;

 static BigInt numPrimes;
 static BigInt* primes;

 static BigInt* factorsMultiplied;
 static BigInt* totalFactors;
 static BigInt* factors; /* This is used as a doubly subscripted array, n^1/3 x ln n. Indexing is done manually.*/
 static BigInt* numPrimeBases;

 static BigInt* DPrime; /* This is used as a doubly subscripted array, n^1/3 x ln n. Indexing is done manually.*/

 static BigInt curBlockBase;

 static double t;

 static BigInt nToTheHalf;
 static BigInt numDPowers;
 static double* dPrime;

 static BigInt S1Val;
 static BigInt S1Mode;
 static BigInt* S3Vals;
 static BigInt* S3Modes;

 static bool ended;
 static BigInt maxSieveValue;

 static BigInt ceilval;

 static BigInt n;

 BigInt binomial( double n, int k ){
 double t = 1;
 for( int i = 1; i <= k; i++ ){
 t *= ( n  ( k  i ) ) / i;
 }
 return BigInt( t + .1 );
 }

 static BigInt invpow(double n, double k) {
 return (BigInt)(pow(n, 1.0 / k) + .00000001);
 }

 /* See http://www.icecreambreakfast.com/primecount/primecounting.html#ch5 for a description of
 calculating d_k'(n) from a complete factorization of a number n.*/
 static BigInt d1(BigInt* a, BigInt o, BigInt k, BigInt l){
 BigInt t = 1;
 for (BigInt j = 0; j < l; j++) t *= binomials[(a[o*logn+ j]  1 + k)*128 + a[o*logn+ j]];
 return t;
 }

 /* See http://www.icecreambreakfast.com/primecount/primecounting.html#ch5 for a description of
 calculating d_k'(n) from a complete factorization of a number n.*/
 static BigInt d2(BigInt* a, BigInt o, BigInt k, BigInt l, BigInt numfacts ){
 if (numfacts < k) return 0;
 BigInt t = 0;
 for (BigInt j = 1; j <= k; j++) t += ( ( k  j ) % 2 == 1 ? 1:1 ) * binomials[k * 128 + j] * d1(a, o, j, l);
 if( t < 0 ){
 int asdf = 9;
 }
 return (BigInt)t;
 }

 static void allocPools( BigInt n ){
 nToTheThird = (BigInt)pow(n, 1.0 / 3);

 logn = (BigInt)(log(pow(n, 2.00001 / 3)) / log(2.0)) + 1;
 factorsMultiplied = new BigInt[nToTheThird];
 totalFactors = new BigInt[nToTheThird];
 factors = new BigInt[nToTheThird * logn];
 numPrimeBases = new BigInt[nToTheThird];
 DPrime = new BigInt[(nToTheThird + 1) * logn];
 binomials = new BigInt[128*128+ 128];
 for (BigInt j = 0; j < 128; j++) for (BigInt k = 0; k <= j; k++)binomials[j * 128 + k] = binomial(j, k);
 for (BigInt j = 0; j < logn; j++) DPrime[j] = 0;
 curBlockBase = 0;

 t = n  1;

 nToTheHalf = (BigInt)pow(n, 1.0 / 2);
 numDPowers = (BigInt)(log(pow(n, 2.00001 / 3)) / log(2.0)) + 1;
 dPrime = new double[(nToTheThird + 1) * (numDPowers + 1)];

 S1Val = 1;
 S1Mode = 0;
 S3Vals = new BigInt[nToTheThird + 1];
 S3Modes = new BigInt[nToTheThird + 1];

 ended = false;
 maxSieveValue = (BigInt)(pow(n, 2.00001 / 3));

 for (BigInt j = 2; j < nToTheThird + 1; j++){
 S3Modes[j] = 0;
 S3Vals[j] = 1;
 }
 }

 static void deallocPools(){
 delete factorsMultiplied;
 delete totalFactors;
 delete factors;
 delete numPrimeBases;
 delete DPrime;
 delete binomials;
 delete dPrime;
 delete S3Vals;
 delete S3Modes;
 delete primes;
 }

 /* This finds all the primes less than n^1/3, which will be used for sieving and generating complete factorizations of numbers up to n^2/3*/
 static void fillPrimes(){
 BigInt* primesieve = new BigInt[nToTheThird + 1];
 primes = new BigInt[nToTheThird + 1];
 numPrimes = 0;
 for (BigInt j = 0; j <= nToTheThird; j++) primesieve[j] = 1;
 for (BigInt k = 2; k <= nToTheThird; k++){
 BigInt cur = k;
 if (primesieve[k] == 1){
 primes[numPrimes] = k;
 numPrimes++;
 while (cur <= nToTheThird){
 primesieve[cur] = 0;
 cur += k;
 }
 }
 }
 delete primesieve;
 }

 /* This resets some state used for the sieving and factoring process.*/
 static void clearPools(){
 for (BigInt j = 0; j < nToTheThird; j++){
 numPrimeBases[j] = 1;
 factorsMultiplied[j] = 1;
 totalFactors[j] = 0;
 }
 }

 /* We can use sieving on our current n^1/3 sized block of numbers to
 get their complete prime factorization signatures, with which we can then
 quickly compute d_k' values.*/
 static void factorRange(){
 for (BigInt j = 0; j < numPrimes; j++){
 // mark everything divided by each prime, adding a new entry.
 BigInt curPrime = primes[j];
 if (curPrime * curPrime > curBlockBase + nToTheThird) break;
 BigInt curEntry = ( curBlockBase % curPrime == 0 ) ? 0:curPrime  (curBlockBase % curPrime);
 while (curEntry < nToTheThird){
 if( curEntry+curBlockBase != 0 ){
 factorsMultiplied[curEntry] *= curPrime;
 totalFactors[curEntry]++;
 numPrimeBases[curEntry]++;
 factors[curEntry*logn+ numPrimeBases[curEntry]] = 1;
 }
 curEntry += curPrime;
 }
 // mark everything divided by each prime power
 BigInt cap = (BigInt)( log((double)(nToTheThird+curBlockBase)) / log((double)curPrime) + 1 );
 BigInt curbase = curPrime;
 for (BigInt k = 2; k < cap; k++){
 curPrime *= curbase;
 curEntry = (curBlockBase % curPrime == 0) ? 0 : curPrime  (curBlockBase % curPrime);
 while (curEntry < nToTheThird){
 factorsMultiplied[curEntry] *= curbase;
 totalFactors[curEntry]++;
 if (curEntry + curBlockBase != 0)factors[curEntry*logn+ numPrimeBases[curEntry]] = k;
 curEntry += curPrime;
 }
 }
 }
 // account for prime factors > n^1/3
 for (BigInt j = 0; j < nToTheThird; j++){
 if (factorsMultiplied[j] < j+curBlockBase){
 numPrimeBases[j]++;
 totalFactors[j]++;
 factors[j*logn+ numPrimeBases[j]] = 1;
 }
 }
 }

 /* By this point, we have already factored, through sieving, all the numbers in the current n^1/3 sized block we are looking at.
 With a complete factorization, we can calculate d_k'(n) for a number.
 Then, D_k'(n) = d_k'(n) + D_k'(n1).*/
 static void buildDivisorSums(){
 for (BigInt j = 1; j < nToTheThird+1; j++){
 if (j + curBlockBase == 1  j + curBlockBase == 2) continue;
 for (BigInt k = 0; k < logn; k++){
 DPrime[j * logn + k] = DPrime[(j  1) * logn + k] + d2(factors, j  1, k, numPrimeBases[j  1] + 1, totalFactors[j  1]);
 }
 }
 for (BigInt j = 0; j < logn; j++) DPrime[j] = DPrime[nToTheThird*logn+ j];
 }

 /* This general algorithm relies on values of D_k' <= n^2/3 and d_k' <= n^1/3. This function calculates those values of d_k'.*/
 static void find_dVals(){
 curBlockBase = 1;
 clearPools();
 factorRange();
 buildDivisorSums();

 for (BigInt j = 2; j <= nToTheThird; j++){
 for (BigInt m = 1; m < numDPowers; m++){
 double s = 0;
 for (BigInt r = 1; r < numDPowers; r++) s += pow(1.0, (double)( r + m )) * (1.0 / (r + m + 1)) * (DPrime[j * logn + r]  DPrime[(j  1) * logn + r]);
 dPrime[j*(numDPowers + 1)+ m] = s;
 }
 }
 }

 static void resetDPrimeVals(){
 curBlockBase = 0;
 for (BigInt k = 0; k < nToTheThird + 1; k++)
 for (BigInt j = 0; j < logn; j++)
 DPrime[k * logn + j] = 0;
 }

 /* This function is calculating the first two sums of http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
 It is written to rely on values of D_k' from smallest to greatest, to use the segmented sieve.*/
 static void calcS1(){
 if (S1Mode == 0){
 while (S1Val <= ceilval){
 BigInt cnt = (n / S1Val  n / (S1Val + 1));
 for (BigInt m = 1; m < numDPowers; m++) t += cnt * (m % 2 == 1 ? 1 : 1) * (1.0 / (m + 1)) * DPrime[(S1Val  curBlockBase + 1) * logn + m];
 S1Val++;
 if (S1Val >= n / nToTheHalf){
 S1Mode = 1;
 S1Val = nToTheHalf;
 break;
 }
 }
 }
 if (S1Mode == 1){
 while (n / S1Val <= ceilval){
 for (BigInt m = 1; m < numDPowers; m++) t += (m % 2 == 1 ? 1 : 1) * (1.0 / (m + 1)) * DPrime[(n / S1Val  curBlockBase + 1) * logn + m];
 S1Val;
 if (S1Val < nToTheThird + 1){
 S1Mode = 2;
 break;
 }
 }
 }
 }

 /* This loop is calculating the 3rd term that runs from 2 to n^1/3 in http://www.icecreambreakfast.com/primecount/primecounting.html#4_4*/
 static void calcS2(){
 for (BigInt j = 2; j <= nToTheThird; j++)
 for (BigInt k = 1; k < numDPowers; k++)
 t += (n / j  1) * pow(1.0, (double)k) * (1.0 / (k + 1)) * (DPrime[j * logn + k]  DPrime[(j  1) * logn + k]);
 }

 /* This loop is calculating the two double sums in http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
 It is written to rely on values of D_k' from smallest to greatest, to use the segmented sieve.*/
 static void calcS3(){
 for (BigInt j = 2; j <= nToTheThird; j++){
 if (S3Modes[j] == 0){
 BigInt endsq = (BigInt)(pow(n / j, .5));
 BigInt endVal = (n / j) / endsq;
 while (S3Vals[j] <= ceilval){
 BigInt cnt = (n / (j * S3Vals[j])  n / (j * (S3Vals[j] + 1)));
 for (BigInt m = 1; m < numDPowers; m++) t += cnt * DPrime[(S3Vals[j]  curBlockBase + 1) * logn + m] * dPrime[j*(numDPowers + 1)+ m];
 S3Vals[j]++;
 if (S3Vals[j] >= endVal){
 S3Modes[j] = 1;
 S3Vals[j] = endsq;
 break;
 }
 }
 }
 if (S3Modes[j] == 1){
 while (n / (j * S3Vals[j]) <= ceilval){
 for (BigInt m = 1; m < numDPowers; m++) t += DPrime[(n / (j * S3Vals[j])  curBlockBase + 1) * logn + m] * dPrime[j * (numDPowers + 1) + m];
 S3Vals[j];
 if (S3Vals[j] < nToTheThird / j + 1){
 S3Modes[j] = 2;
 break;
 }
 }
 }
 }
 }

 /* This is the most important function here. How it works:
 * first we allocate our n^1/3 ln n sized pools and other variables.
 * Then we go ahead and sieve to get our primes up to n^1/3
 * We also calculate, through one pass of sieving, values of d_k'(n) up to n^1/3
 * Then we go ahead and calculate the loop S2 (check the description of the algorithm), which only requires
 * values of d_k'(n) up to n^1/3, which we already have.
 * Now we're ready for the main loop.
 * We do the following roughly n^1/3 times.
 * First we clear our sieving variables.
 * Then we factor, entirely, all of the numbers in the current block sized n^1/3 that we're looking at.
 * Using our factorization information, we calculate the values for d_k'(n) for the entire range we're looking,
 * and then sum those together to have a rolling set of D_k'(n) values
 * Now we have values for D_k'(n) for this block sized n^1/3
 * First we see if any of the values of S1 that we need to compute are in this block. We can do this by
 * (see the paper) walking through the two S1 loops backwards, which will use the D_k'(n)
 * values in order from smallest to greatest
 * We then do the same thing will all of the S3 values
 * Once we have completed this loop, we will have calculated the prime power function for n.
 *
 * This loop is essentially calculating
 * http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
 */

 static double calcPrimePowerCount(BigInt nVal){
 n = nVal;
 allocPools(n);
 fillPrimes();
 find_dVals();
 calcS2();
 resetDPrimeVals();

 for (curBlockBase = 0; curBlockBase <= maxSieveValue; curBlockBase += nToTheThird ){
 clearPools();
 factorRange();
 buildDivisorSums();

 ceilval = curBlockBase + nToTheThird  1;
 if (ceilval > maxSieveValue) {
 ceilval = maxSieveValue;
 ended = true;
 }

 calcS1();
 calcS3();
 if (ended) break;
 }

 deallocPools();

 return t;
 }

 static BigInt countprimes(BigInt num) {
 double total = 0.0;
 for (BigInt i = 1; i < log((double)num) / log(2.0); i++) {
 double val = calcPrimePowerCount( invpow(num, i)) / (double)i * mu[i];
 total += val;
 }
 return total+.1;
 }

 int scaleNum = 10;
 int main(int argc, char* argv[]){
 int oldClock = (int)clock();
 int lastDif = 0;

 printf( " Time\n");
 printf( " Increase\n");
 printf( " for x%d\n", scaleNum);
 printf( " __ Input Number __ __ Output Number __ _ MSec _ _ Sec _ Input\n");
 printf( " \n");
 for( BigInt i = scaleNum; i <= 1000000000000000000; i *= scaleNum ){
 printf( "%17I64d(10^%4.1f): ", i, log( (double)i )/log(10.0) );
 BigInt total = (BigInt)(countprimes( i )+.00001);
 int newClock = (int)clock();
 printf( " %20I64d %8d : %4d: x%f\n",
 total, newClock  oldClock, ( newClock  oldClock ) / CLK_TCK,
 ( lastDif ) ? (double)( newClock  oldClock ) / (double)lastDif : 0.0 );
 lastDif = newClock  oldClock;
 oldClock = newClock;
 }

 getch();

 return 0;
 }
