http://www.perlmonks.org?node_id=430569


in reply to Re^5: a close prime number
in thread a close prime number

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