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

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.

Huh?!? You're joking, aren't you? The same fact that you say "all prime number generators are, for the most part, variations on brute force" is in contradiction with the claim that "there is no way of predicting what the next prime number is, given any other number".

More precisely if I have any isprime() sub, e.g. 

sub isprime {
    my $n=shift;
    return undef if abs $n == 1;
    return isprime -$n if $n<0;
    return 0 if $n == 0;
    $n%$_ or return 0 for (2..sqrt $n);
    1;
}

[download]
(I'm not posting a better one for others already have, and even better ones are available elsewhere.) or the witty 
sub isprime {
    (1 x shift) !~ /^1?$|^(11+?)\1+$/;
}

[download]
(this is Abigail's - who else?) then a sub like this: 
sub nearest_prime {
    my $n=my $m=shift;
    return $n if isprime $n;
    while (1) {
        return $n if isprime ++$n;
        return $m if isprime --$m;
    }
}

[download]
would answer the OP's question.

Important: not only primality testing algorithms do exist, but fast ones exist too. What in some sense there is "no way" to do is to factorize a composite number which is a different problem. But really even for the latter problem there are perfectly deterministic algorithms. "Only" it is believed to be computationally "hard" (in a mathematically precise sense), whereas the former is not. It is on this last conjecture (not proved yet!) that many cryptography methods rely.

Since the OP did not specify the size of a problem, but gave an example with small numbers, an effective answer in terms of some efficient sieving algorithm can be given.

Replies are listed 'Best First'.
Re^5: a close prime number
by dragonchild (Archbishop) on Feb 12, 2005 at 20:27 UTC
    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.)

    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.

    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.

    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.

    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.

[reply]
      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...

[reply]
[d/l]
[select]
        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 );
    }
}

        [download]
        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;
}

        [download]

        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.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom