◄ Index                                                                                                                                                                                               Modular Sieves ►

A Minimal Prime Generating Theorem that suggests the Prime Difference is

Bhupinder Singh Anand[1]

We define a minimal prime generating algorithm which suggests that the Prime Difference, d_P(n), is

Introduction

Do we necessarily discover the primes, as in the sieve of Eratosthenes, or can we also generate them sequentially?

In other words, given the first k primes, can we generate the prime difference, d_P(k), without directly testing any number larger than p(k) for primality?

We give an affirmative answer, and define two prime number generating algorithms based on the following theorems.

We show that one of these is a minimal prime generating algorithm, and conjecture that it suggests the prime difference is

1.1: A Prime Number Generating Theorem

Theorem 1: For any given natural number k, and all i ≤ k, let p(i) denote the i'th prime, and define the sequence {a_P(i): i = 1 to k} such that 0 < a_P(i) < p(i), and:

p(k) + a_P(i) ≡ 0 (mod p(i))

Let d_P(k) be such that, for all 0 < l < d_P(k), there is some i such that:

l ≡ a_P(i) (mod p(i)).

Then d_P(k) is the Prime Difference, defined by:

p(k+1) - p(k) = d_P(k).

Proof: For all 0 < l < d_P(k), there is some i such that:

p(k) + l ≡ 0 (mod p(i)).

Since, by Bertrand’s Postulate ([HW60], p343), p(k+1) < 2p(k) for all natural numbers k, it follows that:

d_P(k) < p(k)

Hence, p(k) + d_P(k) < p(k)², and so it is the prime p(k+1)□

1.2: A Minimal Prime Number Generating Theorem

Since a natural number, n, is prime if, and only if, it is not divisible by any prime p such that p² < n, the above is also a proof of the following minimal prime generating theorem.

Theorem 2: For any given natural number k, and all i ≤ k, let p(i) denote the i'th prime, and define the sequence {a_P(i): i = 1 to m} such that 0 < a_P(i) < p(i), p(m)² < p(k) < p(m+1)², and:

p(k) + a_P(i) ≡ 0 (mod p(i))

Let d_P(k) be such that, for all l < d_P(k), there is some i such that:

l ≡ a_P(i) (mod p(i)).

Then d_P(k) is the Prime Difference, defined by:

p(k+1) - p(k) = d_P(k).

2: Trim numbers

The significance of Theorem 1 is seen in the following algorithm.

We define Trim numbers recursively by t(1) = 2, and t(n+1) = t(n) + d_T(n), where p(i) is the i'th prime and:

(i)      d_T(1) = 1; a_T(2, 1) = 1:

(ii)     d_T(n) is the smallest even integer that does not occur in the n'th sequence:

{ a_T(n, 1), …, a_T(n, n-1)};

(iii)    j_i ≥ 0 is selected so that, for all 0 < i ≤ (n-1):

0 ≤ a_T(n+1, i) = {( a_T(n, i) - d_T(n) + j_i*p(i)} < p(i)

It follows that the Trim number t(n+1) is, thus, a prime unless all its prime divisors are less than d_T(n).

2.1: The Trim Number Algorithm

The following illustrates how Trim numbers are generated sequentially.