Counting the Primes


Counting the primes: once one realises that Eratosthenes sieve removes composite numbers in repeatable patterns it is a relatively straightforward job of estimating how many integers are left as prime; however since these patterns only start being effective after p squared the proportions at any one location vary:

Thus the number of primes in each sequence of integers (for each prime factor) is 1 in 2, 2 in 6, 8 in 30, 48 in 210, 480 in 2310, 5760 in 30030 or in general terms

{Π(pn – 1) } / pn #

or (p-1)#/p#

These build upon each other at the steps of p squared (4,9,25,49 etc) so as p tends to infinity the number of primes should equal n- sum of all such factors – 1 (as 1 has not been accounted for). To be continued.

Advertisements
This entry was posted in Prime Number Distribution and tagged . Bookmark the permalink.

11 Responses to Counting the Primes

  1. Hugh says:

    Yes, except you need an error term since the primes are within those patterns.

    Like

    • No you don’t need an error term – there is no error – the count is precise; however you have to understand what is being counted – not the numbers of primes in the integers, but the numbers of “primes” generated by a limited number of prime factors. Some of these “primes” prove to be composites once higher levels of prime factors are added. This tehcnique is only really of use in determining a trend, and once I have time, should be of use in looking at the pairs.

      Like

  2. Hugh says:

    Yes, that’s fair enough. The fractal pattern is in the multiples, not in the gaps eventually left behind.

    But there are two problems in turning this into a prime counting technique. Firstly, the first prime in each series of multiples (eg 1×5, 5×5, 7×5, 11×5…) is a prime. So at the end of any prime counting method that starts from these fractions, you need to subtract the number of patterns that started in the range, and thus include one prime number. But the result you are looking for is the number of primes, which is the same thing. So you need to know the answer in order to work the answer out.

    The other problem is also complex – you’re right that from the square of one prime (p1) to its square all the non-primes in the pattern are sieved out by the primes up to p1. But the range from p1 squared to p2 squared is only a tiny fraction of the length of the relevant primorial once you are past the first few primes, so it is illegitimate to use any kind of averaging step to work out how many primes you should find in this space.

    I had a bash at using a similar method to work out what’s going on with twin primes, but while it was interesting, my attempt at a proof turned out to be balderdash. So I’m not criticising, I’m completely facscinated by the same patterns you are looking at. I just think it is way too simplistic to say prime counting is in any way straightforward because of these patterns.

    Like

    • Let’s see if I can write this in English: the composites coming from Erathostenes sieve come in repeatable patterns. Initially, they are just multiples of two primes, but higher up are multiples of more than one. However, all primes are included and the primes (and their multiples) align on multiples of p# for any particular p.

      So if we look at each repeat we see there are a set proportion of composites and “primes” or pseudoprimes (they are not prime because of the entry of higher level prime factors) but a series can be established for which a limit may be established. The proportion of primes to total integers or primes to composites can be calculated. Clearly p# becomes rapidly larger and these proportions do not show in the list of primes, as the “patterns” are lost

      Thus for example for a sieve of 7, the integers removed are 49, 77, 91…..or 7×11, 7×13, 7×17 etc:
      (11 13 17 19 23 29 31 37)

      77 91 119 133 161 203 217 259
      adding 210 to each of these gives the next set ad infinitum of composites removed from the sieve
      287 301 329 343 371 413 427 469

      The proportion of these that are multipels of just two primes (i.e. 7 x ?) decreases through the series of integers, but the proportion that are pseudo primes stays the same (8 in 210). Working thru the whole sieve gives a series of proportions of “primes” or psedoprimes and composites. This series then needs to be extended to infinity to see where it ends up
      1 in 2
      1 in 6
      2 in 30
      8 in 210
      48 in 2310
      79 in 4810 (this looks wrong.!.)

      Like

  3. Hugh says:

    Note also that your equation is closely related to the equation Euler inverted and equated with the harmonic series, which is also related to the zeta function.

    1/2 * 2/3 *4/5 * 6/7 * 8/9…. (p-1)/p

    See How Euler Did It 29 by Ed Sandifer for a good explanation.

    The fact that this equation when inverted diverges was used as a proof of the infinity of primes by Euler. In the version above, it gives one rather inaccurate estimate of the density of primes, but it does indeed need an error term, just as the Riemann zeta function does when used to estimate primes.

    Like

  4. Hugh says:

    Oh, I meant 10/11, not 8/9

    Like

  5. Hugh says:

    OK, I’ll try working through these points:

    “Let’s see if I can write this in English: the composites coming from Erathostenes sieve come in repeatable patterns. Initially, they are just multiples of two primes, but higher up are multiples of more than one. However, all primes are included and the primes (and their multiples) align on multiples of p# for any particular p.”

    I don’t think this is quite correct. The pattern of composites for any particular set of primes repeats, yes. And yes as you go up you get self-similar patterns of multiples with 2,3 ….n factors being generated. But there are always more primes to add to the pattern and this prevents the actual pattern of composites from repeating as a whole. Pretty much every time (eg) the pattern created by multiples of 5/7/11/13 repeats, there are more primes entering the picture.

    “So if we look at each repeat we see there are a set proportion of composites and “primes” or pseudoprimes (they are not prime because of the entry of higher level prime factors) but a series can be established for which a limit may be established. The proportion of primes to total integers or primes to composites can be calculated. ”

    So this isn’t correct. The proportion of primes reduces with each new prime that enters the pattern.

    “Clearly p# becomes rapidly larger and these proportions do not show in the list of primes, as the “patterns” are lost”

    Correct. Or the patterns are still there, but there is a gradual accretion of more layers that change the overall pattern and the length of the symmetry.

    “Thus for example for a sieve of 7, the integers removed are 49, 77, 91…..or 7×11, 7×13, 7×17 etc:
    (11 13 17 19 23 29 31 37)

    77 91 119 133 161 203 217 259
    adding 210 to each of these gives the next set ad infinitum of composites removed from the sieve
    287 301 329 343 371 413 427 469”

    Agreed.

    “The proportion of these that are multipels of just two primes (i.e. 7 x ?) decreases through the series of integers, but the proportion that are pseudo primes stays the same (8 in 210). Working thru the whole sieve gives a series of proportions of “primes” or psedoprimes and composites. This series then needs to be extended to infinity to see where it ends up
    1 in 2
    1 in 6
    2 in 30
    8 in 210
    48 in 2310
    79 in 4810 (this looks wrong.!.)”

    Yes I think that last one is wrong. But yes, this all makes sense in principle.

    However it is of no use in counting primes because it presupposes we have a complete list of primes as part of the calculation. And the whole point of prime counting is that we are trying to extend this pattern to very high numbers where this kind of calculation doesn’t help.

    Plus my original objection still applies. Knowing the proportion of 2310 numbers that are multiples of 5/7/11 doesn’t help us to know 1) how many of those numbers are higher primes than 11 or 2) how many of those numbers are primes that are within the pattern (eg 5, 7, 11).

    In this case it is bleeding obvious that there are 3 primes within the pattern, 5, 7 and 11. So the error term is 3. But as you extend the pattern on and on, the only way to know what error term you need for a very high number is to know how many primes there are below that number. Which is the problem you are trying to solve.

    Like

    • Yes there are elements of the blindingly obvious in this, but you are criticising the obvious, not what what is described. The series describes does NOT count the number of “pure” primes that one observes; it measures the underlying “pure” primes and the pseduo primes that get “knocked out” as higher level prime factors come into operation at p^2. The patterns I am observing are only “visible” between p n ^2 and p n+1 ^ 2 (sorry no formatting; between the square of one prime and the square of the next). These patterns are of length p#, so get “hidden” in a stepwise manner.

      The “new” primes are the result of the larger prime factors coming into play and yes, this does muck up the issue, but not my analysis. And no we don’t need to know the next prime to do this: we are looking at the distribution of the primes around p^2 with knowledge of the prime factors around p : so this issue is not an issue.

      “Knowing the proportion of 2310 numbers that are multiples of 5/7/11 doesn’t help us to know 1) how many of those numbers are higher primes than 11 or 2) how many of those numbers are primes that are within the pattern (eg 5, 7, 11).” Knowing how many composite numbers there are below a point gives us the number of primes – that’s the simple description. I am counting primes by counting composites, by subtraction. This doesn’t allow us to answer every question posed about the primes but it does seem to help.

      I am afraid I still cannot understand what you mean by an error term, but feel free to attempt to educate me. Keep it simple.

      regards and thanks for the commentary

      Like

    • And I guess that 4810 should in fact be 30030

      Like

  6. Hugh says:

    OK, just to try and clear up what I mean about the error term. Your original statement was this.

    “Counting the primes: once one realises that Eratosthenes sieve removes composite numbers in repeatable patterns it is a relatively straightforward job of estimating how many integers are left as prime”

    There are two separate problems with this statement:

    1) As you recognise, there are “pure primes” both inside and outside the pattern. Between p n ^2 and p n+1 ^, we know that all composites are multiples of primes up to n. But if we sieve out all the primes up to n we only have a rough way of guessing how many of the remaining numbers outside the pattern are prime. Because the complete primorial pattern is much, much longer than the region p n ^2 and p n+1 ^, the actual density of primes and composites in this region may be rather different to the average density of “primes” left in the full primorial length pattern. We can’t just assume that the percentage of primes in the entire symmetrical pattern gives us a good estimate for a short section of the pattern.You could allow for this if you had a good way to estimate how much variation there could be in the density of primes and composites, but this would just mean that the counting method had a significant margin of error.

    2) In addition to the gaps in the pattern, which must be prime in the region between p n ^2 and p n+1 ^, we need to know how many primes there are that have also been sieved out, the primes that are within the pattern. So we need to know the value of n (in other words, whether p n is the 1000th prime, the 2000th prime, the 10000000th prime etc). To count pure primes, we’d need to add n to the cumulative count of gaps in the pattern in all the regions up to this point. This is what I mean by the error term. It creates a circular problem and it becomes a significant issue when we get to large numbers. This creates a significant problem when it comes to using this method to count actual primes (even if we could safely assume the average density in each region was fairly uniform).

    So for counting actual primes, this method won’t improve on existing methods.

    However you then clarified to:

    “The series describes does NOT count the number of “pure” primes that one observes; it measures the underlying “pure” primes and the pseduo primes that get “knocked out” as higher level prime factors come into operation at p^2. The patterns I am observing are only “visible” between p n ^2 and p n+1 ^ 2 (sorry no formatting; between the square of one prime and the square of the next). These patterns are of length p#, so get “hidden” in a stepwise manner.”

    Well, yes, but that brings us back to the problem I am talking about above. Even if you ignore the need for the error term, then it is not legitimate to assume that the average percentage of primes and composites applies to a subsection of the symmetrical pattern.

    What you’re describing is something that could be used to count “numbers that are not multiples of a particular range of primes” if we knew the number of primes up to a particular range. But there are significant obstacles to going from there to counting primes in a given region, or (for instance) estimating how many primes there are below a trillion.

    Like

  7. Hugh says:

    And sorry I am so long winded, but it is hard to make these points too succinctly. Just one more point on this.

    “And no we don’t need to know the next prime to do this: we are looking at the distribution of the primes around p^2 with knowledge of the prime factors around p : so this issue is not an issue.”

    Well, yes, but firstly this only gives us a very rough estimate as this is a small section of a very long pattern (as I said above).

    And secondly, the calculation that would give us the proportion of primes in this region would be something like:

    1/2 x 2/3 x 4/5 x 6/7 x 10/11 x …. ((p n) – 1)/(p n) + the error term (= the number of primes up to p n).

    And that calculation can only be performed if we have a complete list of the primes up to p n. So in order to count primes in the region of p n ^ 2, p n+1 ^ 2, we need to already know how many primes there are up to p n and their values. Which brings me back to the problem of circularity.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s