Is the Set of Prime Numbers a Pattern or Something Else?

[symbolipoint]

Is the set (or should I say, "sequence"?) of prime numbers a legitimate PATTERN or something else?

 

[Gib Z]

It has not been proven weather or not there is any efficient algorithm that generates the primes, although if the Riemann Hypothesis is true then there is not. The RH is probably true by the way.

 

[chaoseverlasting]

Why is the Riemenn Hypothesis true? I read somewhere that the occurance of prime numbers varies as a logarithmic function.

 

[d_leet]

Why is the Riemenn Hypothesis true? I read somewhere that the occurance of prime numbers varies as a logarithmic function.

He didn't say that the Riemann Hypothesis is true, he just said it probably is.

 

[Gib Z]

Yes that does seem to baffle me >.< The Prime Number theorem does state that p_n~ n \log_e n so it would seem that there in fact is a pattern ...But I'm quite sure what I said before is also correct, so perhaps the PNT does not count as an efficient algorithm.

 

[matt grime]

Would you mind defining what you mean by pattern? If you don't have a definition, then it is not meaningful to ask if anything satisfies that definition.

 

[ktoz]

This isn't especially insightful but do primes have any special significance outside the context of multiplication or division?

Partitioning a prime is no different than partitioning a non-prime so, in that context, there is nothing special about them. Multiplication and division are essentially just the special case of partitions into uniform parts and, in that light, primes are just evidence that this convention has the intrinsic limitations.

In that sense, primes are similar to reals, irrationals or imaginaries in that they are named limits to the special case of partitions of equal parts.

Of course, all of this is pretty obvious and is no help in finding a "pattern" to primes, but it's a different way of thinking about what primes really are.

 

[CRGreathouse]

It has not been proven weather or not there is any efficient algorithm that generates the primes, although if the Riemann Hypothesis is true then there is not.

What do you mean by these statements?

 

[Gib Z]

Well, there are expressions that generate the prime numbers, you can take a look here (they all involve the floor function): http://en.wikipedia.org/wiki/Prime_number_formula#Formulas_using_the_floor_function

But all these all inefficient compared to other primality tests, and I've read that if the hypothesis is indeed correct, the current algorithms won't be able to be improved much more.

 

[CRGreathouse]

But all these all inefficient compared to other primality tests, and I've read that if the hypothesis is indeed correct, the current algorithms won't be able to be improved much more.

The naive method for calculating primality (count the divisors directly) takes exponential time, putting it in EXPTIME. It's also obviously in co-NP: a short proof of compositeness is given by listing one factor.

Pratt's primality test showed that PRIMES is in NP: a short (polynomial-size) proof of primality exists for every prime.

The (strong) Fermat test is a fast random test for compositeness, making PRIMES in co-RP: easy (polynomial-time) to prove composite.

After many years, the cyclotomic test of AKS showed that PRIMES is in P: easy (polynomial-time) to prove prime.Usually "efficient algorithm" is interpreted as "polynomial-time algorithm", as I've written above. So generally I would say that there are efficient algorithms for checking primality (all of the AKS-class algorithms, and possibly ECPP, are in P). But I don't know what the Riemann Hypothesis has to do with this. Why would that mean that there are no efficient algorithms?

I mean, PRIMES isn't known to be P-hard, though I think that's widely believed. So perhaps "there is no efficient algorithm for PRIMES" means, e.g., that PRIMES is not in NC (generally glossed as the class of efficiently parallellizable algorithms). But why would RH show this? I've not heard anything along these lines. I mean the GRH would imply that only a logarithmic number of (strong?) Fermat tests would suffice to prove a number prime, which would be another algorithm in P -- though in my experience even going well below the Miller limit takes a fair bit longer than conventional tests.

 

[Hurkyl]

And, of course, generating large intervals of primes is much easier than testing each number in the interval for primality -- to generate the list of primes less than N, the Sieve of Eratosthenes does O(1) operations per number on average. The Sieve of Atkin does less than 1 operation per number on average!

 

[Gib Z]

I'm not too sure about anything I'm saying here really, but for arbitrarily large integers Polynomial time would take an infinite amount of time to compute primality, while "efficient" in the context I used it would take a finite amount of time/operation for any integer, and and the number of operations would be bounded from above. I may be completely wrong about this.

 

[Hurkyl]

I'm not too sure about anything I'm saying here really, but for arbitrarily large integers Polynomial time would take an infinite amount of time to compute primality,

Why would you even begin to think that? Each integer is finite; why would you think it takes an infinite amount of time to test some of them for primality?

while "efficient" in the context I used it would take a finite amount of time/operation for any integer, and and the number of operations would be bounded from above. I may be completely wrong about this.

By your definition of "efficient", you cannot even read integers "efficiently".

 

[Gib Z]

I'm very terrible at this then :( My bad

 

[pacdude9]

Primes are, by definition, in a pattern.

A pattern, from the French patron, is a type of theme of recurring events or objects, sometimes referred to as elements of a set. These elements repeat in a predictable manner.

The pattern that the primes follow is that they are not divisible by any positive integer other than itself and 1. The simplest pattern that comes to mind is a pattern based off of the Sieve of Eratosthenes, so the pattern that a finite set of primes would follow could be generated by the sieve.