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



Welcome to my white whale.


This webpage contains a description of a prime number counting algorithm I have cobbled together that operates in O(n^2/3 ln n ) time and O(n^1/3 ln n ) space, based on Linnik's identity, as well as a bunch of other combinatorial number theory stuff.

Also see: C++ Source Code for 5 Implementations
of Prime Counting with Linnik's Identity




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,


(1.1)

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

(1.2)

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


  1. The Strict Number of Divisors Summatory Functions and Counting Primes

  2. Properties of the Strict Number of Divisors Summatory Functions

  3. The Core Strict Number of Divisors Summatory Function Identity

  4. Calculating Up to

  5. Conclusion for This Algorithm

  6. Intermezzo


Part 2: Combinatorial Number Theory Related to Linnik's Identity


  1. The Strict Number of Divisors Summatory Functions and li(x)

  2. More Properties of the Strict Number of Divisors Summatory Functions

  3. The Strict Möbius Function Summatory Functions

  4. The Strict Number of Prime Powers Summatory Functions

  5. The Strict Inverse of Prime Powers Summatory Functions

  6. Generalizing the Transformation, and Some Promising Coefficients

  7. Other Root Functions

  8. Discontinuities as Fractional Parts

  9. A Few Identities for Chebyshev's Second Function,

  10. Further Questions

  11. References

    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 4: Other Derivations

    Appendix 5: C Source Code for the Algorithm






Special thanks to Roxanne Prichard and Mark Coffey




Dedicated, as always, to Annette














Part 1:


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):



(2.1)


Summing Linnik's identity, (1.1), from 2 to n then gives the following identity


(2.2)


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


(2.3)


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.


(2.4)










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



(3.1)


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:


(3.2)


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


(3.3)


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


(4.1)


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

(4.2)


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

(4.3)

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






(4.4)


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.









5. Calculating Up to


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


(5.1)

and the strict number of divisors function can in turn be calculated from the number of divisors function by

(5.2)


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.









7. Intermezzo


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 Lagarias-Miller-Odlyzko combinatorial method. Given the shallowness of my own number theory knowledge (in terms of the broader existing field of research), too, the possibilities for follow-on work and improvement to this algorithm, or to similar Linnik's identity-based 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 well-known 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 self-reinforcing, 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 lock-step 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 9-12. 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 9-12. 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.

















Part 2:


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

(8.1)

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



(8.2)

At least empirically, this is exactly and precisely equal to


(8.3)

(which can be rewritten as


(8.4)

), 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


(8.5)


then we will find that


(8.6)

Now, we already know from Riemann that


(8.7)

where are the zeroes to the Riemann Zeta function, and so, comparing the two functions, we see it must be the case that


(8.8)


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 Zeta-Function 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



9-A: 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 non-strict 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.



_______________________________________________



9-B: 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.



_______________________________________________



9-C: 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,


(9.1)


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


(9.2)

and so, taking advantage of that identity, we're left with the following


(9.3)

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


(9.4)


Alternatively, if we work with , and we're sensitive to the fact that is the non-strict version of and so counting needs to start at 1 rather than 2, we will find that


and so





_______________________________________________



9-D: 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


(9.5)

If we repeat the process again, we find we have


and, more generally,


(9.6)



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.



_______________________________________________



9-E: 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


(9.7)

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



(9.8)

and, more generally,


(9.9)

It should be fairly straightforward, from inspection, that we can rewrite this as


(9.9a)

and

(9.9b)

The expression in (9.8) can be rewritten as the rather tidy


(9.10)

This identity can also be written as


(9.10a)

(keeping in mind that ) and

(9.10b)

both of which suggest that the sum


(9.10c)


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


(9.10d)

_______________________________________________



9-F: 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 re-arrangement, we can turn (9.8) into the following identity for


(9.11)



_______________________________________________



9-G: Another Expression for



Though the derivation for this won't be given here, can also be expressed as



(9.12)

where are the Bernoulli numbers with . This is a special case of the more general formula


(9.13)

which can be generalized even further as


(9.14)

where .


Similarly, using the Gregory coefficients from (9.7) above, we can also say


(9.15)


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


(9.16)


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



10-A: 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.



_______________________________________________



10-B: Core Identities


We have


(10.1)

(10.2)


We will then sum these identities to work with the following family of functions


(10.3)

This function obeys the property


which can be rewritten as

(10.3a)


with

This can essentially be restated as


and more generally

(10.4)


_______________________________________________



10-C: 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


(10.5)

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


(10.6)


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.



_______________________________________________



10-D: 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,


(10.7)

and


(10.8)


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.



_______________________________________________



10-E: 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 non-strict 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

(10.9)


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 non-strict version of , that


and



_______________________________________________



10-F: 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:


(10.10)

and, consequently,


(10.10a)


Disregarding, for a moment, my notation, this means we have now expressed the prime power function in terms of the Möbius function


(10.11)

and, if we use to mean the Mertens Function,


(10.12)

which is


(10.12a)

and if we work through the arithmetic, we have


(10.12b)


The formula in (10.10) is also adequate for us to put together another recursive definition of , namely

(10.13)


_______________________________________________



10-G: 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,

(10.14)



_______________________________________________



10-H: 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


(10.15)


_______________________________________________



10-I: 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

(10.16)

If

then

(10.17)

For some value a <= k


and

(10.18)










11. The Strict Number of Prime Powers Summatory Functions



11-A: 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.


_______________________________________________



11-B: 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


(11.1)

(11.2)


We will then sum these identities, so that we are working with the following family of functions


(11.3)

It should be obvious that, in this notation,


These functions obey the following combinatorial identity



or, which is the same thing,


(11.3b)

All of this can be rewritten as


(11.4)

and more generally

(11.5)


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.


(11.5a)

_______________________________________________



11-C: 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

(11.6)


then we have the following general formula for expressing in terms of


(11.7)

and, correspondingly,

(11.7b)


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


(11.8)

and, correspondingly,

(11.8b)



_______________________________________________



11-D: 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 10-D, 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


(11.9)

or, which is to say,


(11.9b)

and, consequently,


(11.10)


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



(11.11)


and (11.10) as


(11.12)



_______________________________________________



11-E: 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


(11.13)

then we have


(11.14)

and

(11.15)


Abandoning my notation again for just a second, this means that, just as one example,






_______________________________________________



11-F: 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),


(11.16)

and

(11.17)


and, in particular,



Once again, abandoning my notation for a second, this means that



(11.18)


where M(n) is Mertens function, and


(11.19)

except, of course, for the value of 1.



_______________________________________________



11-G: 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


(11.20)

and


(11.21)


where M(n) is Mertens function. Setting aside my notation again for a second, this means that


(11.22)

and


(11.23)


_______________________________________________



11-H: In Terms of



From Linnik's Identity, we know that



If we make use of the basic identity from (3.1), this means that


(11.24)


or, alternatively,


(11.25)


(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


(11.25)



which are not entirely unfamiliar coefficients. In fact, if are the Bernoulli numbers, with , then we have


(11.26)

and

(11.27)

which, with the arithmetic worked through ((11.25) would yield identical results), is

(11.27a)


The expression (11.27) leads to yet another interesting recursive definition of , namely


(11.27b)


which is essentially the inversion of (9.10). Again, abandoning my notation, this means that



(11.28)


and

(11.28b)


_______________________________________________




11-I: Another Relationship between and



If we mirror the processes that led to (9.10) and (11.28b), we can derive the following recursive identities

(11.29)

and

(11.30)


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


(11.30a)

which, when the arithmetic is worked through, results in


(11.30b)

Working through (11.29) will produce (10.12b).


This identity can also be written as


(11.30c)

(keeping in mind that ) and


(11.30d)


_______________________________________________



11-J: More Identities



A few more identities connected to the family of functions will be given here without derivation.



(11.31)


(11.32)


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


(11.33)

which, of course, (11.26) is a special case of.









12. The Strict Inverse of Prime Powers Summatory Functions



12-A: 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 .


_______________________________________________



12-B: 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.



_______________________________________________



12-C: Core Identities



For this paper, we'll name our inversion function q', so


(12.1)


And so on. The first few values for , starting at 2:



We also have our summatory function


(12.2)


is essentially the Möbius function of the prime power function, and its Mertens function. also satisfies


and more generally

(12.3)

Additionally,


(12.3a)

and, more generally,



(12.3b)


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

(12.4)

Additionally,


and


Because , if we evaluate this last expression for , we get


Which is to say,


(12.5)


Additionally,

(12.5a)

which, with the arithmetic worked through, leads to


(12.5b)


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


(12.5c)




Other relationships that apply include (10.5) through (10.8), with P' and Q' replacing D' and M'.


_______________________________________________



12-D: 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

(12.6)

then

(12.7)

(12.8)


_______________________________________________



12-E: Non-strict q' and non-strict P'



One other side result for . To connect back more to the regular (non-strict) 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 non-strict functions.

(12.9)


Second, we can use these two identities to create a prime power inversion formula, such that if



then this can be inverted with , and



(12.10)

This means, too, that if


then

(12.11)


The family of functions inverts normally, so




and in particular , which is equal to , is










13. Generalizing the Transformation, and Some Promising Coefficients



13-A: 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 9-12 as well as opening the door to many more. It will end by listing some other promising coefficients to explore.


_______________________________________________



13-B: 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


_______________________________________________



13-C: 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 10-12, 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.


_______________________________________________



13-D: 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


(13.1)

and, where are the Gregory coefficients from (9.10),


(13.2)


_______________________________________________



13-E: Generalizing the Transformation Process




Taking a higher level view, if we have some function , and we define the following relationships


(13.3)

and we have some sequence of coefficients , and we further define the following relationships


(13.4)

then we will find the following relationships hold:


or, which is the same thing

(13.5)

Additionally,


(13.5a)


If we define the following sequence of constants


(13.6)

then we will further find that


(13.7)

and

(13.8)


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

(13.9)

and, for ,

(13.10)

We then have

(13.11)

and

(13.12)

and


(13.13)

We will also find the following relationships hold:


or, which is the same thing

(13.14)


If we define the following sequence of constants


(13.15)


then we will find that


(13.16)

and

(13.17)

This is, essentially, the basic pattern present in sections 9-12. 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


(13.17a)


Additionally, we can generalize the identity from (3.3) to express the symmetries of these functions as


(13.17b)



_______________________________________________


13-F: 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 .



_______________________________________________



13-G: 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 13-E should make clear.


This, incidentally, means that all of these families of functions have a set of coefficients that satisfies the equation


(13.18)

and, further, that all of them also have coefficients that satisfy the equation


(13.19)

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


(13.20)


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 13-F. 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),


(13.21)

and, repeating this process,


(13.22)


Another possibly interesting function to explore is


(13.23)


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


(13.24)









14. Other Root Functions



14-A: Overview



An interesting aspect of almost all of these identities, as alluded to in section 12 and elaborated on in 13-E, 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.


_______________________________________________



14-B:



So, for example, if we now use , then we will find that we have


(14.1)

and so on. In this same scheme, we have


(14.2)

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


(14.3)


which is essentially Linnik's Identity for the function . Additionally, we should also be able to say, at this point, from (11.9), that


(14.4)


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öbius-style inverses for both of these functions, with all attendant properties, could be generated as well.


Perhaps equally interesting for this case are the non-summatory identities


(14.5)

and, using from before as our prime power function


(14.6)


This can all be rewritten recursively as


(14.7)

and

(14.8)


_______________________________________________



14-C:



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 9-13 besides.


This can all be rewritten recursively as


(14.13)

and

(14.14)



_______________________________________________



14-D: Generalized



And so, more generally, we have



(14.15)



(14.16)


where a can, at the least, be any positive or negative real number.


We then have


(14.17)


and


(14.18)


This can all be rewritten recursively as


(14.19)

and

(14.20)


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 13-E 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



15-A: 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.



_______________________________________________



15-B: 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.



_______________________________________________



15-C: 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.


_______________________________________________



15-D: 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.


_______________________________________________



15-E: 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)



_______________________________________________



15-F: 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).


_______________________________________________


15-G: 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.


_______________________________________________



15-H: 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



_______________________________________________



15-I: 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


(16.1)

where is the Mangoldt function, or, in the notation from this paper,


(16.2)


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


(16.3)

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


(16.4)

which, with a bit of arm waving, has the raw material to yield the following recursive formula


(16.5)

The following similar recursive identity also seems to hold


(16.5a)


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


(16.6)


This can be rewritten recursively, giving us


(16.7)












17. Further Questions


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 Heath-Brown found in identity of Linnik[1] and the Möbius version of Vaughn's identity. Are there similar identities for a non-strict version of the prime-power 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 non-strict 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 Zeta-Function-related expressions for and , particularly their so-called 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.









18. References


[1] J. B. Friedlander and H. Iwaniec, Opera de Cribro, 346-347

[2] Deleglise, Marc and Rivat, Joel, Computing the summation of the Mobius function. Experiment. Math. 5 (1996), no. 4, 291-295.

[3] Ivic, A. A. The Riemann Zeta-Function: The Theory of the Riemann Zeta-Function 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




(11.21)

If are the Gregory coefficients from (9.10), then


(11.30)

and, which is essentially the same identity, from (11.30b)


(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,











Appendix 4: Other Derivations


_______________________________________________



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 re-arranged 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.




  1. #include "stdio.h"
  2. #include "stdlib.h"
  3. #include "math.h"
  4. #include "conio.h"
  5. #include "time.h"
  6. typedef long long BigInt;
  7.  
  8. 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,
  9.     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,
  10.     -1, 0, -1, 1, 0, 0, 1, -1, -1, 0, 0 };
  11.  
  12. static BigInt* binomials;       /* This is used as a doubly subscripted array, 128x128.  Indexing is done manually.*/
  13. static BigInt nToTheThird;
  14. static BigInt logn;
  15.  
  16. static BigInt numPrimes;
  17. static BigInt* primes;
  18.  
  19. static BigInt* factorsMultiplied;
  20. static BigInt* totalFactors;
  21. static BigInt* factors;         /* This is used as a doubly subscripted array, n^1/3 x ln n.  Indexing is done manually.*/
  22. static BigInt* numPrimeBases;
  23.  
  24. static BigInt* DPrime;          /* This is used as a doubly subscripted array, n^1/3 x ln n.  Indexing is done manually.*/
  25.  
  26. static BigInt curBlockBase;
  27.  
  28. static double t;
  29.  
  30. static BigInt nToTheHalf;
  31. static BigInt numDPowers;
  32. static double* dPrime;
  33.  
  34. static BigInt S1Val;
  35. static BigInt S1Mode;
  36. static BigInt* S3Vals;
  37. static BigInt* S3Modes;
  38.  
  39. static bool ended;
  40. static BigInt maxSieveValue;
  41.  
  42. static BigInt ceilval;
  43.  
  44. static BigInt n;
  45.  
  46. BigInt binomial( double n, int k ){
  47.     double t = 1;
  48.     for( int i = 1; i <= k; i++ ){
  49.         t *= ( n - ( k - i ) ) / i;
  50.     }
  51.     return BigInt( t + .1 );
  52. }
  53.  
  54. static BigInt invpow(double n, double k) {
  55.     return (BigInt)(pow(n, 1.0 / k) + .00000001);
  56. }
  57.  
  58. /* See http://www.icecreambreakfast.com/primecount/primecounting.html#ch5 for a description of
  59. calculating d_k'(n) from a complete factorization of a number n.*/
  60. static BigInt d1(BigInt* a, BigInt o, BigInt k, BigInt l){
  61.     BigInt t = 1;
  62.     for (BigInt j = 0; j < l; j++) t *= binomials[(a[o*logn+ j] - 1 + k)*128 + a[o*logn+ j]];
  63.     return t;
  64. }
  65.  
  66. /* See http://www.icecreambreakfast.com/primecount/primecounting.html#ch5 for a description of
  67. calculating d_k'(n) from a complete factorization of a number n.*/
  68. static BigInt d2(BigInt* a, BigInt o, BigInt k, BigInt l, BigInt numfacts ){
  69.     if (numfacts < k) return 0;
  70.     BigInt t = 0;
  71.     for (BigInt j = 1; j <= k; j++) t += ( ( k - j ) % 2 == 1 ? -1:1 ) * binomials[k * 128 + j] * d1(a, o, j, l);
  72.     if( t < 0 ){
  73.         int asdf  = 9;
  74.     }
  75.     return (BigInt)t;
  76. }
  77.  
  78. static void allocPools( BigInt n ){
  79.     nToTheThird = (BigInt)pow(n, 1.0 / 3);
  80.  
  81.     logn = (BigInt)(log(pow(n, 2.00001 / 3)) / log(2.0)) + 1;
  82.     factorsMultiplied = new BigInt[nToTheThird];
  83.     totalFactors = new BigInt[nToTheThird];
  84.     factors = new BigInt[nToTheThird * logn];
  85.     numPrimeBases = new BigInt[nToTheThird];
  86.     DPrime = new BigInt[(nToTheThird + 1) * logn];
  87.     binomials = new BigInt[128*128+ 128];
  88.     for (BigInt j = 0; j < 128; j++) for (BigInt k = 0; k <= j; k++)binomials[j * 128 + k] = binomial(j, k);
  89.     for (BigInt j = 0; j < logn; j++) DPrime[j] = 0;
  90.     curBlockBase = 0;
  91.  
  92.     t = n - 1;
  93.  
  94.     nToTheHalf = (BigInt)pow(n, 1.0 / 2);
  95.     numDPowers = (BigInt)(log(pow(n, 2.00001 / 3)) / log(2.0)) + 1;
  96.     dPrime = new double[(nToTheThird + 1) * (numDPowers + 1)];
  97.  
  98.     S1Val = 1;
  99.     S1Mode = 0;
  100.     S3Vals = new BigInt[nToTheThird + 1];
  101.     S3Modes = new BigInt[nToTheThird + 1];
  102.  
  103.     ended = false;
  104.     maxSieveValue = (BigInt)(pow(n, 2.00001 / 3));
  105.  
  106.     for (BigInt j = 2; j < nToTheThird + 1; j++){
  107.         S3Modes[j] = 0;
  108.         S3Vals[j] = 1;
  109.     }
  110. }
  111.  
  112. static void deallocPools(){
  113.     delete factorsMultiplied;
  114.     delete totalFactors;
  115.     delete factors;
  116.     delete numPrimeBases;
  117.     delete DPrime;
  118.     delete binomials;
  119.     delete dPrime;
  120.     delete S3Vals;
  121.     delete S3Modes;
  122.     delete primes;
  123. }
  124.  
  125. /* 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*/
  126. static void fillPrimes(){
  127.     BigInt* primesieve = new BigInt[nToTheThird + 1];
  128.     primes = new BigInt[nToTheThird + 1];
  129.     numPrimes = 0;
  130.     for (BigInt j = 0; j <= nToTheThird; j++) primesieve[j] = 1;
  131.     for (BigInt k = 2; k <= nToTheThird; k++){
  132.         BigInt cur = k;
  133.         if (primesieve[k] == 1){
  134.             primes[numPrimes] = k;
  135.             numPrimes++;
  136.             while (cur <= nToTheThird){
  137.                 primesieve[cur] = 0;
  138.                 cur += k;
  139.             }
  140.         }
  141.     }
  142.     delete primesieve;
  143. }
  144.  
  145. /* This resets some state used for the sieving and factoring process.*/
  146. static void clearPools(){
  147.     for (BigInt j = 0; j < nToTheThird; j++){
  148.         numPrimeBases[j] = -1;
  149.         factorsMultiplied[j] = 1;
  150.         totalFactors[j] = 0;
  151.     }
  152. }
  153.  
  154. /* We can use sieving on our current n^1/3 sized block of numbers to
  155. get their complete prime factorization signatures, with which we can then
  156. quickly compute d_k' values.*/
  157. static void factorRange(){
  158.     for (BigInt j = 0; j < numPrimes; j++){
  159.         // mark everything divided by each prime, adding a new entry.
  160.         BigInt curPrime = primes[j];
  161.         if (curPrime * curPrime > curBlockBase + nToTheThird) break;
  162.         BigInt curEntry = ( curBlockBase % curPrime == 0 ) ? 0:curPrime - (curBlockBase % curPrime);
  163.         while (curEntry < nToTheThird){
  164.             if( curEntry+curBlockBase != 0 ){
  165.                 factorsMultiplied[curEntry] *= curPrime;
  166.                 totalFactors[curEntry]++;
  167.                 numPrimeBases[curEntry]++;
  168.                 factors[curEntry*logn+ numPrimeBases[curEntry]] = 1;
  169.             }
  170.             curEntry += curPrime;
  171.         }
  172.         // mark everything divided by each prime power
  173.         BigInt cap = (BigInt)( log((double)(nToTheThird+curBlockBase)) / log((double)curPrime) + 1 );
  174.         BigInt curbase = curPrime;
  175.         for (BigInt k = 2; k < cap; k++){
  176.             curPrime *= curbase;
  177.             curEntry = (curBlockBase % curPrime == 0) ? 0 : curPrime - (curBlockBase % curPrime);
  178.             while (curEntry < nToTheThird){
  179.                 factorsMultiplied[curEntry] *= curbase;
  180.                 totalFactors[curEntry]++;
  181.                 if (curEntry + curBlockBase != 0)factors[curEntry*logn+ numPrimeBases[curEntry]] = k;
  182.                 curEntry += curPrime;
  183.             }
  184.         }
  185.     }
  186.     // account for prime factors > n^1/3
  187.     for (BigInt j = 0; j < nToTheThird; j++){
  188.         if (factorsMultiplied[j] < j+curBlockBase){
  189.             numPrimeBases[j]++;
  190.             totalFactors[j]++;
  191.             factors[j*logn+ numPrimeBases[j]] = 1;
  192.         }
  193.     }
  194. }
  195.  
  196. /* By this point, we have already factored, through sieving, all the numbers in the current n^1/3 sized block we are looking at.
  197. With a complete factorization, we can calculate d_k'(n) for a number.
  198. Then, D_k'(n) = d_k'(n) + D_k'(n-1).*/
  199. static void buildDivisorSums(){
  200.     for (BigInt j = 1; j < nToTheThird+1; j++){
  201.         if (j + curBlockBase == 1 || j + curBlockBase == 2) continue;
  202.         for (BigInt k = 0; k < logn; k++){
  203.             DPrime[j * logn + k] = DPrime[(j - 1) * logn + k] + d2(factors, j - 1, k, numPrimeBases[j - 1] + 1, totalFactors[j - 1]);
  204.         }
  205.     }
  206.     for (BigInt j = 0; j < logn; j++) DPrime[j] = DPrime[nToTheThird*logn+ j];
  207. }
  208.  
  209. /* 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'.*/
  210. static void find_dVals(){
  211.     curBlockBase = 1;
  212.     clearPools();
  213.     factorRange();
  214.     buildDivisorSums();
  215.  
  216.     for (BigInt j = 2; j <= nToTheThird; j++){
  217.         for (BigInt m = 1; m < numDPowers; m++){
  218.             double s = 0;
  219.             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]);
  220.             dPrime[j*(numDPowers + 1)+ m] = s;
  221.         }
  222.     }
  223. }
  224.  
  225. static void resetDPrimeVals(){
  226.     curBlockBase = 0;
  227.     for (BigInt k = 0; k < nToTheThird + 1; k++)
  228.         for (BigInt j = 0; j < logn; j++)
  229.             DPrime[k * logn + j] = 0;
  230. }
  231.  
  232. /* This function is calculating the first two sums of http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
  233. It is written to rely on values of D_k' from smallest to greatest, to use the segmented sieve.*/
  234. static void calcS1(){
  235.     if (S1Mode == 0){
  236.         while (S1Val <= ceilval){
  237.             BigInt cnt = (n / S1Val - n / (S1Val + 1));
  238.             for (BigInt m = 1; m < numDPowers; m++) t += cnt * (m % 2 == 1 ? -1 : 1) * (1.0 / (m + 1)) * DPrime[(S1Val - curBlockBase + 1) * logn + m];
  239.             S1Val++;
  240.             if (S1Val >= n / nToTheHalf){
  241.                 S1Mode = 1;
  242.                 S1Val = nToTheHalf;
  243.                 break;
  244.             }
  245.         }
  246.     }
  247.     if (S1Mode == 1){
  248.         while (n / S1Val <= ceilval){
  249.             for (BigInt m = 1; m < numDPowers; m++) t += (m % 2 == 1 ? -1 : 1) * (1.0 / (m + 1)) * DPrime[(n / S1Val - curBlockBase + 1) * logn + m];
  250.             S1Val--;
  251.             if (S1Val < nToTheThird + 1){
  252.                 S1Mode = 2;
  253.                 break;
  254.             }
  255.         }
  256.     }
  257. }
  258.  
  259. /* 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*/
  260. static void calcS2(){
  261.     for (BigInt j = 2; j <= nToTheThird; j++)
  262.         for (BigInt k = 1; k < numDPowers; k++)
  263.             t += (n / j - 1) * pow(-1.0, (double)k) * (1.0 / (k + 1)) * (DPrime[j * logn + k] - DPrime[(j - 1) * logn + k]);
  264. }
  265.  
  266. /* This loop is calculating the two double sums in http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
  267. It is written to rely on values of D_k' from smallest to greatest, to use the segmented sieve.*/
  268. static void calcS3(){
  269.     for (BigInt j = 2; j <= nToTheThird; j++){
  270.         if (S3Modes[j] == 0){
  271.             BigInt endsq = (BigInt)(pow(n / j, .5));
  272.             BigInt endVal = (n / j) / endsq;
  273.             while (S3Vals[j] <= ceilval){
  274.                 BigInt cnt = (n / (j * S3Vals[j]) - n / (j * (S3Vals[j] + 1)));
  275.                 for (BigInt m = 1; m < numDPowers; m++) t += cnt * DPrime[(S3Vals[j] - curBlockBase + 1) * logn + m] * dPrime[j*(numDPowers + 1)+ m];
  276.                 S3Vals[j]++;
  277.                 if (S3Vals[j] >= endVal){
  278.                     S3Modes[j] = 1;
  279.                     S3Vals[j] = endsq;
  280.                     break;
  281.                 }
  282.             }
  283.         }
  284.         if (S3Modes[j] == 1){
  285.             while (n / (j * S3Vals[j]) <= ceilval){
  286.                 for (BigInt m = 1; m < numDPowers; m++) t += DPrime[(n / (j * S3Vals[j]) - curBlockBase + 1) * logn + m] * dPrime[j * (numDPowers + 1) + m];
  287.                 S3Vals[j]--;
  288.                 if (S3Vals[j] < nToTheThird / j + 1){
  289.                     S3Modes[j] = 2;
  290.                     break;
  291.                 }
  292.             }
  293.         }
  294.     }
  295. }
  296.  
  297. /*  This is the most important function here. How it works:
  298. *    first we allocate our n^1/3 ln n sized pools and other variables.
  299. *    Then we go ahead and sieve to get our primes up to n^1/3
  300. *    We also calculate, through one pass of sieving, values of d_k'(n) up to n^1/3
  301. *    Then we go ahead and calculate the loop S2 (check the description of the algorithm), which only requires
  302. *    values of d_k'(n) up to n^1/3, which we already have.
  303. *    Now we're ready for the main loop.
  304. *    We do the following roughly n^1/3 times.
  305. *    First we clear our sieving variables.
  306. *    Then we factor, entirely, all of the numbers in the current block sized n^1/3 that we're looking at.
  307. *    Using our factorization information, we calculate the values for d_k'(n) for the entire range we're looking,
  308. *    and then sum those together to have a rolling set of D_k'(n) values
  309. *    Now we have values for D_k'(n) for this block sized n^1/3
  310. *    First we see if any of the values of S1 that we need to compute are in this block. We can do this by
  311. *    (see the paper) walking through the two S1 loops backwards, which will use the D_k'(n)
  312. *    values in order from smallest to greatest
  313. *    We then do the same thing will all of the S3 values
  314. *    Once we have completed this loop, we will have calculated the prime power function for n.
  315. *  
  316. *   This loop is essentially calculating
  317. *   http://www.icecreambreakfast.com/primecount/primecounting.html#4_4
  318. */
  319.  
  320. static double calcPrimePowerCount(BigInt nVal){
  321.     n = nVal;
  322.     allocPools(n);
  323.     fillPrimes();
  324.     find_dVals();
  325.     calcS2();
  326.     resetDPrimeVals();
  327.  
  328.     for (curBlockBase = 0; curBlockBase <= maxSieveValue; curBlockBase += nToTheThird ){
  329.         clearPools();
  330.         factorRange();
  331.         buildDivisorSums();
  332.  
  333.         ceilval = curBlockBase + nToTheThird - 1;
  334.         if (ceilval > maxSieveValue) {
  335.             ceilval = maxSieveValue;
  336.             ended = true;
  337.         }
  338.  
  339.         calcS1();
  340.         calcS3();
  341.         if (ended) break;
  342.     }
  343.  
  344.     deallocPools();
  345.  
  346.     return t;
  347. }
  348.  
  349. static BigInt countprimes(BigInt num) {
  350.     double total = 0.0;
  351.     for (BigInt i = 1; i < log((double)num) / log(2.0); i++) {
  352.         double val = calcPrimePowerCount( invpow(num, i)) / (double)i * mu[i];
  353.         total += val;
  354.     }
  355.     return total+.1;
  356. }
  357.  
  358. int scaleNum = 10;
  359. int main(int argc, char* argv[]){
  360.     int oldClock = (int)clock();
  361.     int lastDif = 0;
  362.  
  363.     printf( "                                                                    Time\n");
  364.     printf( "                                                                    Increase\n");
  365.     printf( "                                                                    for x%d\n", scaleNum);
  366.     printf( "         __ Input Number __   __ Output Number __ _ MSec _ _ Sec _  Input\n");
  367.     printf( "                                                                    \n");
  368.     for( BigInt i = scaleNum; i <= 1000000000000000000; i *= scaleNum ){
  369.         printf( "%17I64d(10^%4.1f): ", i, log( (double)i )/log(10.0) );
  370.         BigInt total = (BigInt)(countprimes( i )+.00001);
  371.         int newClock = (int)clock();
  372.         printf( " %20I64d %8d : %4d: x%f\n",
  373.             total, newClock - oldClock, ( newClock - oldClock ) / CLK_TCK,
  374.             ( lastDif ) ? (double)( newClock - oldClock ) / (double)lastDif : 0.0 );
  375.         lastDif = newClock - oldClock;
  376.         oldClock = newClock;
  377.     }
  378.  
  379.     getch();
  380.  
  381.     return 0;
  382. }
  383.  


This document as a nicely formatted PDF file

But it lacks interactive graphs and the javascript interpreter, and may occassionally be a bit out of date


Share |





(c) 2011 icecreambreakfast.com | Contact