# Patterns in prime numbers

#### roger

Hi,

I just wondered what patterns are known about the prime numbers ?

cheers

roger

#### roger

by pattern I mean any explicit formulas which give certain relations between primes.

#### BSMSMSTMSPHD

The Prime Number Theorem states that if you randomly select a number nearby some large number N, the chance of it being prime is about 1 / ln(N), where ln(N) denotes the natural logarithm of N. For example, near N = 10,000, about one in nine numbers is prime, whereas near N = 1,000,000,000, only one in every 21 numbers is prime.

In other words, the prime numbers "thin out" as one looks at larger and larger numbers, and the prime number theorem gives a precise description of exactly how much they thin out.

#### Zurtex

Science Advisor
Homework Helper
Well, one pattern I've noticed is they all have exactly 2 distinct divisors :shy:

#### JasonRox

##### ... to graduate school.
Homework Helper
Gold Member
There is a pattern. We just don't know what it is yet.

#### Hurkyl

Staff Emeritus
Science Advisor
Gold Member
There is a pattern. We just don't know what it is yet.
Then what do you mean by "pattern"?

We know exactly when primes occur, and we have efficient methods for telling if a given number is a prime. We even have explicit formulas for the n-th prime number.

#### JasonRox

##### ... to graduate school.
Homework Helper
Gold Member
Hurkyl said:
Then what do you mean by "pattern"?

We know exactly when primes occur, and we have efficient methods for telling if a given number is a prime. We even have explicit formulas for the n-th prime number.
By pattern, I mean formula.

Where is this explicit formula?

#### Helicobacter

JasonRox said:
There is a pattern. We just don't know what it is yet.
How do we know there is one?

Staff Emeritus
Science Advisor
Gold Member

#### Zurtex

Science Advisor
Homework Helper
f(x) = px where pi is the ith prime.

Patterns are more to do with spotting simple occurrences in real life, not much to do with mathematics.

Last edited:

#### -Job-

Science Advisor
Zurtex said:
Patterns are more to do with spotting simple occurrences in real life, not much to do with mathematics.
I don't agree with that statement.

#### JasonRox

##### ... to graduate school.
Homework Helper
Gold Member
Helicobacter said:
How do we know there is one?
It was proven that if an algorithm can be made so that a computer can spit out the sequence, then a formula exists. Hence, a pattern.

#### -Job-

Science Advisor
JasonRox said:
It was proven that if an algorithm can be made so that a computer can spit out the sequence, then a formula exists. Hence, a pattern.
That might not be very meaningful regarding the sequence of primes. For every algorithm there is an equivalent series of mathematical operations, or, if you combine these statements, a mathematical function. Hence, if an algorithm can "spit out" all the primes, then there is a mathematical function that produces that sequence. However this mathematical function can very well be infinite. This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.
In order to output the sequence of all the primes this algorithm would need infinite time, an infinite sequence of operations and thus be equivalent to an infinite mathematical function.
What pattern exists there then?
If instead we wanted to output the first 100 primes, than the above algorithm would take less than 1000 operations, the equivalent mathematical function have in the order of 1000 operations. Would the sequence have a pattern?
For every sequence there is an algorithm that outputs all the elements in that sequence, it may require infinite memory and infinite time, but it will output all the elements in that sequence, does every sequence have a pattern then?

My definition of a pattern is something that is repeated. Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern. If it requires more then i don't know, but it certainly isn't a simple pattern.

Last edited:

#### eljose

From..Wilson,s?..theorem we could find a formula to obtain primesifwe define:

$$g(x)=[\frac{(x-1)!+1}{x}]-\frac{(x-1)!+1}{x}$$

where for the factorial we know the recurrence $$(x+1)!=xx!$$

then every time g(x)=0 for an integer x we know that this x is prime......where [] is the "floor" function wich is always an integer...

#### Zurtex

Science Advisor
Homework Helper
-Job- said:
I don't agree with that statement.
Well define what a pattern is in mathematics for me then.

-Job- said:
. However this mathematical function can very well be infinite.
Lots of mathematical functions can be described as being 'infinitely long' take for example all taylor series, this does not make them less useful/

-Job- said:
This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.
That's a particularly inefficient way but o.k.

-Job- said:
In order to output the sequence of all the primes this algorithm would need infinite time, an infinite sequence of operations and thus be equivalent to an infinite mathematical function.
That makes no sense, it takes an infinite amount of time to output all natural numbers i.e {1, 2, 3..) on a computer, would you describe the mathematical function f(x) = x as being infinite?

-Job- said:
What pattern exists there then?
If instead we wanted to output the first 100 primes, than the above algorithm would take less than 1000 operations, the equivalent mathematical function have in the order of 1000 operations. Would the sequence have a pattern?
For every sequence there is an algorithm that outputs all the elements in that sequence, it may require infinite memory and infinite time, but it will output all the elements in that sequence, does every sequence have a pattern then?

My definition of a pattern is something that is repeated. Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern. If it requires more then i don't know, but it certainly isn't a simple pattern.
Most of that is so much gibberish I can't really make sense of. Algorithms exist that calculate if a number is a prime or not, much faster than O(n).

Last edited:

#### JasonRox

##### ... to graduate school.
Homework Helper
Gold Member
-Job- said:
That might not be very meaningful regarding the sequence of primes. For every algorithm there is an equivalent series of mathematical operations, or, if you combine these statements, a mathematical function. Hence, if an algorithm can "spit out" all the primes, then there is a mathematical function that produces that sequence. However this mathematical function can very well be infinite. This is the case with the sequence of primes. There is a very simple algorithm that outputs all the primes. Namely one that iterates through all the positive integers and divides each number by those that come before it (and are bigger than one), outputting a number when it is not divisable.
In order to output the sequence of all the primes this algorithm would need infinite time, an infinite sequence of operations and thus be equivalent to an infinite mathematical function.
What pattern exists there then?
If instead we wanted to output the first 100 primes, than the above algorithm would take less than 1000 operations, the equivalent mathematical function have in the order of 1000 operations. Would the sequence have a pattern?
For every sequence there is an algorithm that outputs all the elements in that sequence, it may require infinite memory and infinite time, but it will output all the elements in that sequence, does every sequence have a pattern then?

My definition of a pattern is something that is repeated. Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern. If it requires more then i don't know, but it certainly isn't a simple pattern.
I never said simple pattern.

Also, even if you give a computer the direct formula of a sequence, it requires more and more memory as n gets larger. So, your point is invalid.

#### Hurkyl

Staff Emeritus
Science Advisor
Gold Member
-Job- said:
I would say, if an algorithm can output any n elements of a sequence in O(n) time, with finite memory, then the sequence has a simple pattern.
Okay.

It's odd you would think that the sequence 1, 2, 3, 4, 5, 6, ... of positive integers, in order, doesn't have a simple pattern!

The list consisting of the first N integers has length $\Omega (N \lg N)$, so any algorithm for computing this sequence must take $\Omega(N \lg N)$ time.

If you don't allow the algorithm to review what it's already printed, it must require $\Omega(\lg N)$ memory to output the first N terms of this sequence. If you do allow the algorithm to review what it's already printed, I suspect it still takes $\Omega(\lg \lg N)$ memory, but I haven't worked out a proof yet.

-Job- said:
Yet, for every sequence of numbers without repetition, such as the primes, the digits of pi, etc, there is an algorithm capable of outputting that sequence.
That's not true! There are countably many algorithms, and uncountably many sequences. (Even if we only consisder sequences whose terms are either 0 or 1)

Last edited:

#### -Job-

Science Advisor
Also, even if you give a computer the direct formula of a sequence, it requires more and more memory as n gets larger. So, your point is invalid.
You're misinterpreting me. I said if the algorithm takes a finite amount of memory, meaning if the algorithm can be stored in a finite amount of memory, meaning that if you had an algorithm you'd be able to store it in a hard drive with finite capacity, meaning that the algorithm isn't infinitely large. I didn't mean memory usage at run time. For that i would bound it at about O(n).

Hurkyl said:
Okay.

It's odd you would think that the sequence 1, 2, 3, 4, 5, 6, ... of positive integers, in order, doesn't have a simple pattern!

The list consisting of the first N integers has length $\Omega (N \lg N)$, so any algorithm for computing this sequence must take $\Omega(N \lg N)$ time.
My definition, where i mentioned O(n) wasn't with respect to the number of bits (that was patent in my statement, i thought). So a list composed of the first n integers would require O(n).

That's not true! There are countably many algorithms, and uncountably many sequences. (Even if we only consisder sequences whose terms are either 0 or 1)
But an algorithm doesn't have to create a sequence. The sequence might be embedded in the algorithm, hence to print a sequence all we have to do is:
mySequence = [2, 3, 5, 7, 11, 13, 17, 19 ...];
while(true){
trace("f(" + i + ") = " + mySequence);
}
For an infinite sequence the algorithm is infinitely large (requires infinite memory) and takes infinite time (has to of course). However, for every sequence, there is an algorithm that prints all the elements in that sequence. Unless we choose to define algorithms as something finite. Do you see what i mean?

To reiterate more precisely:
If an algorithm of finite size can output the first N elements of a sequence in O(N) time with O(N) memory, or, in other words, in O(2^n) time and O(2^n) memory where n=log(N), then that sequence has a simple pattern.

This was an impulsive statement, so if it isn't very adequate i'm not going to cry over it.

#### matt grime

Science Advisor
Homework Helper
As you haven't defined 'simple' your statement is vacuous or tautological.

#### -Job-

Science Advisor
Let's make it the definition of "simple pattern" then, and work with that. :)

### The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving