Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Let me rephrase: There is no mathematical way to predict what the next prime number is, given any other number. In other words, there is no f(x) that will return the prime number closest to x without looking at either x-1 or x+1 first. (Unless, of course, either of those is a prime number.)
Let me rephrase: this depends on what you mean with "mathematical". For any commonly known acceptation of the term your claim is plainly wrong, period. If you mean that there's not a "closed form formula" in terms of say polynomials and/or elementary functions, then yes: it's true. But then it's also true of a whole lot of other things.

What is important is that such a function can be defined perfectly well in mathematical terms and efficient algorithms (i.e. primality tests) are now known, to compute it. Which cannot be said of the related, but different problem of factorization.

Furthermore, every single prime number generator is a variation on brute force. Your own nearest_prime() is a perfect example of this - you look at every number above and below n until you find one that is prime. That is a brute force algorithm.
Can you explain me how this fails to be "mathematical"?!?

Also, I would like to draw your attention to the fact that the nearest_prime() algorithm is of comparable complexity with that of isprime(), and my isprime() is a (as) naive (as possible) example, whereas efficient sieving algorithms now do exist, as I'm repeating ad nauseam.

As for primality tests, I refer you to Google's cache of the Wikipedia article (as it seems that en.wikipedia.com currently isn't available). Specifically, there are two quotes by some rather famous mathematicians. I'll repeat the one by Euler:

Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate.

So what?!? How does this relate to your claim that "there is no mathematical way to predict what the next prime number is, given any other number"?

Yes: the distribution of primes is of a formidable complexity in a fascinating way. How all this can relate to the OP's question and your answer to it is still beyond my comprehension...

If there is no order in the sequence of the primes, then there is no way to predict the closest prime to a given number. It is possible to determine it, but not to predict it.
Huh?!? Explain me what is the mathematical difference between the two! Maybe you mean that no sufficient and necessary condition is known for the determination of primality state of a given number that can not be directly brought back to the definition. But this is not strictly true either. For example in terms of Wilson's theorem (pseudo-LaTeX)

\pi(n)=1+\sum_0^{n} ( (j-2)!-j\floor{(j-2)!/j} ),

hence the n-th prime p_n can be given in terms of

p_n=1+\fract{1}{2}sum_1^{2^n} \xi(n,\pi(j)),

where

\xi(m,n)=0 if m=n, and \xi(m,n)=1+\sgn(m-n) otherwise.

Of course the direct link with the definition is still too evident, but then substitute the factorials with (shifted) gamma functions, and gamma functions with their expressions as definite integrals: then it much less so!

Even more astonishingly Matijasevic et al. have shown that polynomials in several variables do exist such that the range of their positive values coincides exactly with the primes (and their negative values are all composite).

Of course none of these results can be of any practical use for actual computations, but that is another matter...


In reply to Re^6: a close prime number by blazar
in thread a close prime number by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others avoiding work at the Monastery: (15)
    As of 2014-08-22 19:53 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (163 votes), past polls