in reply to Re: Finding the next larger prime.
in thread Finding the next larger prime.

If I interpret this correctly [...] the theorum provides a way of calculating a set of bounds within which the next prime will be located which reduces the search area considerably

Your conclusion is dead wrong but I don't think it is due to a problem of interpretation. (:

You could use the theorem to restrict the search area for the next prime but it would be much more useful to use other techniques to restrict the search area:

  1. Assume the next prime after some prime (P) is larger than P. In fact, you should probably start looking at P+2 unless P is 2 (in which case you simply return 3 without performing any calculations).
  2. Assume the next prime after P doesn't have a prime between P and it. That is, start looking close to P and stop looking when you find a prime.

That is, if you used the theorem to find the lower bound of where to search, it would return a value quite a bit below P so using the (obvious) lower limit of P will be a much better choice. And finding an upper bound of where to search is of no use since it will be too high to make sense to start looking there and starting on the low end means we know we will find a prime (the one we are looking for) before we get to the upper bound (or else we'd have proved the theorem incorrect).

                - tye
  • Comment on Re^2: Finding the next larger prime. (conclusions)

Replies are listed 'Best First'.
Re: Re^2: Finding the next larger prime. (conclusions)
by BrowserUk (Patriarch) on Oct 30, 2003 at 19:37 UTC

    So, what your saying (if I interpret you correctly:), is that despite all of the revisions and improvements made to the Prime Number Theorum, the margin for error for the lower bound for a given prime P will always be greater than the distance between P and P-1?

    If so, its a shame none of the reference material I read actually states that minor caveat! Or maybe they did, but not in a way that I understood.

    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
    Hooray!
[reply]

      I assume the articles didn't bother to state that because it isn't particularly relavent to what they are discussing and they probably consider it obvious. (:

      Of course the bounds are not accurate to a "distance" of around 1 or 2! No such bound can ever be more accurate than the "after P try P+2" idea (or else it would be incorrect) or even equally as accurate (or else it would be exact and constitute a closed formula for computing primes).

      Ah! Perhaps you aren't aware that...

      No matter how large of numbers you deal with, you can find (P such that) P and P+2 that are both prime and you can find arbitrarily large D such that (there is a P where) P and P+D are adjacent primes (as I recall, the proofs of these aren't even very complicated, involving N! with +1 and/or -1 inserted here and there).

      That is, even extremely large adjacent primes can be as close together as 2 or very far apart. The theorems you've been reading put bounds on how big you have to make P before you can get D to be a desired size.

      (updated)

                      - tye
[reply]

        I have read that there are an infinite number of Ns where N-1 and N+1 are both prime, but I never made the connection between that and this -- till now. Why they couldn't just say that in the first place...

        As I said in the original post, this was a half remembered impression I picked up from reading something that I readily admit to not fully understanding. {sigh}

        From my perspective, this make the Prime Number Theorum about as useful as knowing that you can cause perl to dump core in 6 characters. It's statable and provably true (so I read), but beyond that it's nothing more than an object of curiosity.

        I realise my problem is my own ignorance, but I wish these darn things carried a Management Summary and a ROI value that one could assess before getting drawn in to actually trying to understand them:)

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail
        Hooray!
[reply]

In Section Seekers of Perl Wisdom