# Primes - pattern or not?

1. Jun 29, 2007

### symbolipoint

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

2. Jun 30, 2007

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

3. Jun 30, 2007

### chaoseverlasting

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

4. Jun 30, 2007

### d_leet

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

5. Jun 30, 2007

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

6. Jun 30, 2007

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

7. Jun 30, 2007

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

8. Dec 21, 2007

### CRGreathouse

What do you mean by these statements?

9. Dec 21, 2007

### Gib Z

10. Dec 22, 2007

### CRGreathouse

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.

Last edited: Dec 22, 2007
11. Dec 22, 2007

### Hurkyl

Staff Emeritus
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!

12. Dec 22, 2007

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

13. Dec 22, 2007

### Hurkyl

Staff Emeritus
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?

14. Dec 22, 2007

### Gib Z

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

15. Apr 5, 2010

### pacdude9

Primes are, by definition, in a pattern.

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.