DERIVING PRIME NUMBER Pn+1 FROM Pn USING SET NOTATION

​

I've always been fascinated by prime numbers. Here follows my work on this topic. A more descriptive version of this, including an implementation using SQL, can be found in my published book Deriving Prime Numbers by Set Theory: With Programming Examples in SQL

​

STEPHEN PETER SMITH

               

Abstract. Given the prime number Pn (where n ε ℤ)  the prime number Pn+1 can be derived using set notation. In this paper we set out such a formula to derive Pn+1 from Pn.

 

 

1. Introduction

 

When viewing prime numbers as a set it can be stated the set of prime numbers is the set of all numbers minus the set of non prime numbers. This can be expressed as follows:

 

{Prime Numbers} = {All Numbers} – {Non Prime Numbers}

 

A known implementation of this is Eratosthenes’s sieve [1]. This generates the set of prime numbers by using the fact that non prime numbers have at least one prime factor. This can be demonstrated by taking the first twenty numbers and applying the sieve:

 

1) Start with: {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

​

2) Delete the non prime number 1: {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

 

3) Take the lowest number, 2, and given it has no factors, (other than 1 and itself) delete all the multiples of 2 from the set: {2,3,5,7,9,11,13,15,17,19}

 

4) This reveals 3 as prime, therefore delete all multiples of 3: {2,3,5,7,11,13,17,19}

 

5) This is repeated for 5 and so on.

​

​

This has derived the set of prime numbers below twenty by removing the set of non prime numbers ≤ 20.

​

2. Theorem

​

Using the above Pn+1 can be expressed as:

​

Pn+1 = min{{All Numbers} – {Set of prime numbers P1 to Pn and their multiples} – {1}}

​

Given Erdős [2] proved that for any number there is at least a prime number between it and twice its value, {All Numbers} can be restricted to {All Numbers between 1 and twice Pn}. This can further be expressed as:

 

{x ε ℤ | 1 ≤ x < 2.Pn}

 

Thus

 

Pn+1 = min{{All Numbers} – {Set of prime numbers P1 to Pn and their multiples} – {1}}

 

Becomes:

 

Pn+1 = min{{x ε ℤ | 1  ≤ x < 2.Pn} – {Set of prime numbers P1 to Pn and their multiples} – {1}}

 

This can be further simplified to:

 

Pn+1 = min{{x ε ℤ | 2 ≤ x < 2.Pn} – {Set of prime numbers P1 to Pn and their multiples}}

 

Similarly {Set of prime numbers P1 to Pn and their multiples} can be expressed as:

 

x ε ℤ | 2 ≤ x < 2. Pn | x ≡ Py = 0 | y ε ℤ | 1 ≤ y ≤ n

 

From this Pn+1 can be derived:

 

Pn+1 = min{{x ε ℤ | 2 ≤ x < 2.Pn} – { x ε ℤ | 2 ≤ x < 2.Pn | x ≡ Py = 0 | y ε ℤ | 1 ≤ y ≤ n }}

 

3. Conclusion

 

By use of the work of Eratosthenes and Erdős’s a set formula to calculate Pn+1 from Pn has been derived.

 

The formula is dependent on the prime numbers P1 to Pn-1. Deriving Pn+1 solely from Pn, without reference to its predecessors, remains unsolved.

 

4. References

 

[1] http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes (04/02/2013)

[2] http://en.wikipedia.org/wiki/Bertrand's_postulate (04/02/2013)

 

5. Notation

 

{}             Set of

ℤ              Set of all integers

|              Where

min{}     The lowest value element of the set

≡              The modulus operator

<              Less than

≤              Less than or equal to

=              Equal to

ε              is an element of