Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^6: a close prime number

by blazar (Canon)
on Feb 13, 2005 at 12:47 UTC ( [id://430569]=note: print w/replies, xml ) Need Help??


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

Replies are listed 'Best First'.
Re^7: a close prime number
by dragonchild (Archbishop) on Feb 13, 2005 at 20:13 UTC
    The important word in my assertion isn't mathematical, it's predict. You cannot determine the closest prime p to any number n without a primality test. Now, brute force algorithms are mathematically describable; I'm not saying they're not.

    Let me give you another example. Can you tell me the closest power of 2 to a given number N? Now, can you do it without breaking down a number into its composite primes? I can, by generating the sequence of powers of 2 and looking at them. That's predictive.

    Here's pseudocode for both algorithms, so you can see the difference.

    Brute-force algorithm: sub is_power { # Some algorithm to determine if a number is a power of two. } sub closest_power_of_two_brute { my $m = my $n = shift; return $n if is_power( $n, 2 ); while (1) { return $n if is_power( $++n, 2 ); return $m if is_power( $--m, 2 ); } }
    Predictive algorithm: sub iterate_over { my $v = shift; return sub { $v *= $v; }; } sub closest_power_of_two_predictive { my $n = shift; my $it = iterate_over( 2 ); my $l = $it->(); while ( my $v = $it->() ) { last if $v > $n; $l = $v; } abs( $n - $l ) > abs( $n - $v ) ? $v : $l; }

    Limbic~Region's example is much better than mine.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

      dragonchild,
      I understand the point you were trying to make, but you picked a bad example.
      print nearest_power_of_2( 50 ); sub nearest_power_of_2 { my $x = shift; my $n = log( $x ) / log( 2 ); return $x if $n == int $n; my ($below, $above) = (int $n, int $n + 1); $_ = 2 ** $_ for ($above, $below); return $above - $x > $x - $below ? $below : $above; }

      Cheers - L~R

      Thanks to blokhead for reminding me how to convert logarithmic bases
      Note: I have restisted the temptation to reply to your node for some time for I got to the conclusion that wrt this topic we speak "two different languages", so to say. Eventually, I'm trying once more, and I only ask you to go through all this paying attention to every word, even if in the end it resulted to be rather long.
      The important word in my assertion isn't mathematical, it's predict. You cannot determine the closest prime p to any number n without a primality test. Now, brute force algorithms are mathematically describable; I'm not saying they're not.
      Don't misunderstand me, I understand the point you're trying to make.

      However I have two remarks to make:

      1. mathematically speaking, which is appropriate in this case, "predict" is meaningless, for it belongs to the realm of astrology and the like rather than that of maths.

        You may contend that the term does appear frequently in tons of respectful mathematics text both in connection with probabilistic or approximate arguments and exact ones, but what I mean is that from a more exact, formalized point of view (of which mathematicians are aware) there is fundamentally no "onthological" difference between, say, one algorithm e.g. a "brute force one" to compute a given quantity and another one e.g. a "predictive" (whatever this may mean!) one. Of course provided that they are guaranteed to return the same quantity, in which case there is a necessary and sufficient condition asserting this.

        The difference that there can be between two such algorithms can be at most in terms of some "circumstantial" charachteristic ascribable to them, even if such "circumstantial charachteristics" may eventually turn out to be of a crucial importance in a practical application, telling wether, for example, a given number can be computed in a reasonable time or if such a computation would require 10^100 times the age of the universe.

      2. Taking into account what has been pointed out at the previous point, the OP wrote:
        If I have a certain number (eg 10) and I want to find out which are the closest prime numbers to it: (5 7 11 13).

        Please give me some ideas on how that can be accomplished.

        To which you replied:
        What have you tried? What directions are you thinking of?

        If you don't provide those items, we quite reasonably are going to consider this an attempt to get us to do your homework for you.

        To which he replied:
        I am thinking of using Math::Prime::Simple. The way with that was:
        @ranges = ( [ $myNum-100, $myNum+100 ] ); $primes = prime( @ranges );
        But this gives me ranges from -100 to +100 of $myNum. And I would have to parse through and check to see the 2 primenumbers smaller and greater than $myNum. Is there any nicer way?
        To which in turn you replied:
        There is no way of predicting what the next prime number is, given any other number. If there was, then current cryptography methods wouldn't work. All prime number generators are, for the most part, variations on brute force. The method you're looking at is probably as good as any.
        Which is the post I commented.

      Now, the OP's answer in terms of Math::Prime::Simple (which BTW I do not happen to know) shows that it is already a brute force attack, but he's concerned about the fact it's far too much brute force than is really needed. I think he would have been content with a brute force attack that wouldn't have involved a brute force attack over a (fixed size) range, which has two drawbacks:

      • it may involve far too many calculations than are really necessary,
      • it may still miss the wanted number (unlikely, if the involved numbers are small, as is reasonable).
      More importantly (IMHO) your claim that "there is no way of predicting what the next prime number is, given any other number" is still devoid of any mathematical significance. It's a matter of English semantics, for "to calculate the next prime brute force wise" is (a way) to "predict it".

      I think you should have said something along the lines of "there is no way to find what the nearest prime to a given number that does not involve a brute force attack based on running a primality testing on its neighbours" instead.

      As a minor nitpick, I would add, that there is no known way, but we do not know that there can't be, even if it appears likely that there will never be.

      Also, you explicitly mentioned prime numbers generators, that is, implicitly, primality tests. But there are now relatively fast primality tests. And your claim that "if there was, then current cryptography methods wouldn't work" is plainly false, for those cryptography methods are based on the related but different problem of factorization. But really there's much we still don't know even about the latter: for example we do not know yet if it is NP complete. (But it's likely not to be, they say!)

        I do not dispute the vast majority of your very carefully worded and well-thought-out reply. My use of the word predict in a mathematical context was probably confusing, and I apologize for that. And, you're very close in your restatement of my assertion; indeed, you're close enough for government work.

        However, I do take issue with much of your last paragraph. I will respond in parts.

        Also, you explicitly mentioned prime numbers generators, that is, implicitly, primality tests. But there are now relatively fast primality tests.

        The fact that they are fast is irrelevant. Deeper Blue beat Kasparov, but no-one is going to say that Deeper Blue actually understands the game of chess or the patterns inherent within it. DB used some serious brute force algorithms, even within the heuristics it used to prune the minimax tree. Granted, the game of chess among humans has become somewhat brute-forcish, given that some lines of the Spanish Torture are known for 30 moves (some games of chess don't last 30 moves!). But, there is still an element of analysis within the playing of chess among humans. There is still the attempt to apply patterns to discard 90% of the move options, something computers have not been able to do. If you want a better example, look at the problems with a Go program.

        And your claim that "if there was, then current cryptography methods wouldn't work" is plainly false, for those cryptography methods are based on the related but different problem of factorization.

        Really? If there was a way to calculate in O(1) time the next prime number larger than a given N (which is, essentially, what the OP was asking for), then cryptography that is based on large number factorization is no longer secure. Think about it for a second - it's not that there is a function P(x) that gives you the next prime number, but the work that leads up to it and that will be based on it. We can go into greater detail offline, if you want. And, factoring large numbers isn't NP-complete or even NP-hard. It's just "NP-slow", in the same way that beating a human in chess (and soon, Go) is NP-slow. The algorithms probably aren't going to improve much, but the computing speed will such that the algorithmic inefficiency factor goes to zero.

        Which, in an related side-topic, is why quantum cryptography is such an important leap - it's a completely unrelated way of encrypting data, away from factorizations, primes, and the like. It's physical encryption, not mathematical encryption.

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://430569]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2024-03-19 07:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found