# Patterns in Prime numbers, and the null hypothesis

I've read about many attempts to find patterns in prime numbers. First, is there a mathematical way to prove there is not a pattern to prime numbers? Since there are ways to check if a number is prime or not, can these methods be combined into some large function that produces prime numbers? And in case it isn't obvious, no, I never got passed pre-Cal.

• Various formalizations of the first question you ask, e.g. various forms of the Riemann hypothesis, are well-known open questions, so I'm not sure how to answer this question. You should read some Wikipedia articles and/or books; the list of references and links at the Wikipedia article on the Riemann hypothesis is pretty good. – Qiaochu Yuan Nov 20 '10 at 16:06
• It's not that there isn't any pattern; more of that we don't know the actual pattern (though there are results on how frequently they occur as we look at larger and larger numbers). – J. M. is a poor mathematician Nov 20 '10 at 16:07
• Certainly there are simple algorithms that will allow you to produce prime after prime by simply proceeding through the natural numbers one by one, but the problem with these algorithms is that at each successive prime takes longer and longer to find, so in the end it is an unfeasible method for characterizing the primes. As well, the definition of a prime really is a characterization of them, or "pattern" if you will, but it is not a very satisfying one because it is a "negative" characterization, not a "positive" one, which characterizes them as the holes in a number sieve. – Ralth Nov 20 '10 at 17:07
• @Everett: by definition, the usual primes are even natural numbers, aka non-negative integers. So they’re certainly rational, and real. On the other hand, algebraists do also consider generalisations of the prime numbers, in other rings; and these can include imaginary numbers and all sorts of other things. But when we just talk about the primes, by default we mean the primes in the natural numbers. – Peter LeFanu Lumsdaine Nov 21 '10 at 9:10
• @J. M.: It's not that we don't know the pattern, it's that there are lots of patterns: some we know, some we guess, and some we haven't even found yet. I'm always confused by this "no patterns in primes" thing; there are so many! – Charles Dec 29 '10 at 5:02

## 3 Answers

I like Dirichlet's Theorem, which states that for relatively prime $a,d \in \mathbb{Z}^+$, there are infinitely many primes in the progression $\{a + nd \mid n \in \mathbb{Z^+}\}$. Further, the proportion of primes in any relatively prime residue class of $d$ is about $1/\phi(d)$, where $\phi$ is the Euler phi function.

In essence, the primes can be seen as somewhat evenly distributed. You can see more below.

http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions

It really depends on what you mean by patterns. Legendre showed that there is no rational algebraic function that outputs only primes. You can read more about prime generating functions here

http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html

The famous Green-Tao theorem states that there are arbitrarily large arithmetic progressions in primes

http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem

I especially like this characterization of primes made by Don Zagier

"There are two facts about the distribution of prime numbers which I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts.

The first is that despite their simple definition and role as the building blocks of the natural numbers, the prime numbers... grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout.

The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behaviour, and that they obey these laws with almost military precision." Don Zagier, Bonn University inaugural lecture

This is taken from this site where you can find many more quotations from prominent mathematicians.

Here you can find some formulas for primes.