A Practical Prime Number Producing Formula Presented in Algorithmic Form

Robert A. Warren 

The prime number formula presented here is the best of my simple formulas. This formula uses small primes to produce larger, guaranteed-to-be-prime numbers (positive integers only) of less than about 1,000. The formula produces only prime numbers as output (N values) in the range of magnitude greater than 1 but less than K. I refer to this as “the range of guaranteed primality.” The formula is based on my original prime number theorem, which may be stated as,

Given two natural numbers, N and K, where K > N and N > 1, if N has no prime factor < sqrt( K), then N is prime.

I have more advanced formulas that make the generation of large primes easier, but they are not included here, partly because the formulas require the presentation of much more theory 

As for the simpler formula that is described here, a proof of this easy-to-prove theorem on which it is based is included at the end of this paper. Below each numerical example is an informal proof of the primality of the N value produced by my formula in that example. If the informal proof is read first, the significance of my theorem should be more easily seen.                                                                                                                                     

In the numerical examples, (P_g+1)² = K.

P_g is the largest prime factor < sqrt ( K). We remember that P_{g+1 =} sqrt ( K).

Prime Number Formula: Steps of the Algorithm

1. List a series of consecutive small prime numbers, starting with the smallest prime in the number system (2).

2. Label the primes. Label the largest prime P_g+1, and label the next largest prime P_g. Label the smallest prime P₁, the next consecutive prime P₂, etc., up to P_g.

3. Divide the primes P₁ through P_g into two groupings. The primes may be divided up in any way, with any number of primes in each grouping. No prime may be put in both groupings. A grouping may consist of as few as one prime.

4. Multiply the primes in each grouping together to form a product of all the primes in that grouping. We will call these product A and product B. Any prime in each product may be raised to any integral power greater than 1.

5. Find (P_g+1)², which is the upper limit of the range of guaranteed primality.

6. Find N, which is the absolute value of the difference of product A and product B. It can easily be proven that the difference of A and B cannot contain as a factor, any prime factor of either A or B. If N is greater than 1 but less than (P_g+1)², then N is guaranteed by the theorem to be prime.

If N is greater than (P_g+1)², then N is not guaranteed to be prime, but is likely to be prime nonetheless. In other words, the output of this formula is prime rich for values of N greater than (P_g+1)².

My theorem also guarantees A+ B to be prime if it is smaller than (P_g+1)², but A + B is seldom small enough to be so guaranteed. It can easily be proven that the sum of A and B cannot contain as a factor any prime in either A or B.

Numerical Example #1 of the Use of the Prime Number Producing Formula.

List a series of consecutive small prime numbers, starting with the smallest prime in the number system (2).

Our series is: 2, 3, 5, 7, 11, 13 and 17.

Step Two:

the primes. Label the largest prime P_g+1, and label the next largest prime P_g.

Label the smallest prime P₁, the next consecutive prime P₂, etc, up to P_g.

P₁ = 2       P₄ = 7       P_g+1 = 17

P₂ = 3       P₅ = 11

P₃ = 5       P_g = 13

Step Three:

Divide the primes P₁ through P_g up into two groupings. The primes may be divided up in any way, with any number of primes in each grouping. No prime may be put in both groupings. A grouping may consist of as few as one prime.

We will arbitrarily divide up the primes into the following two groupings.

G₁ = {2, 3, 11}

G₂ = {5, 7, 13}

 Step Four:

Multiply the primes in each grouping together to form a product of all the primes in each grouping. We will call these products, product A and product B. Any prime in each product may be raised to any integral power greater than 1.

Let A = the product of the primes in G₁. 

Let B = the product of the primes in G₂.

A = (2)³(3)(11) = 264

B = (5)(7)(13) = 455

 Step Five:

Find (P_g+1)² , which is the upper limit of the range of guaranteed primality.

(P_g+1)² = (17)² = 289

Step Six:

Find N, which is the absolute value of the difference of A and B. It can easily be proven that the difference of A and B cannot contain as a factor, any prime factor of either A or B. If N is greater than 1 but less than (P_g+1)², then N is guaranteed by the theorem to be prime.

N = |A – B| = | 264 - 455 | = 191

Since N = 191 is less than (P_g+1)² = 289 and greater than 1, 191 is within the range of guaranteed primality and thus should be prime.

Checking 191 in a number table verifies that it is prime.

Informal Proof for Example #1:  

Any integer less than (17)² = 289, but greater than 1, must either be a prime or be a composite with a prime factor less than 17. Since no integer with a prime factor less than 17 can be produced by the configuration of the prime number producing formula of Example #1, all integers produced by the formula in this configuration that are greater than 1, but less than 289, must be prime.

Numerical Example #2 of the Use of the Prime Number Producing Formula.

Step One:

List a series of consecutive small prime numbers, starting with the smallest prime in the number system (2).

Our series is: 2, 3, 5, 7, 11, 13 and 17.

Step Two:

Label the primes. Label the largest prime P_g+1, and label the next largest prime P_g .

Label the smallest prime P_1, the next consecutive prime P_2, etc, up to P_g.

P₁ = 2        P₄ = 7        P_g+1 = 17

P₂ = 3        P₅ = 11

P₃ = 5       P_g = 13

Step Three: 

Divide the primes P₁ through P_g up into two groupings. The primes may be divided up in any way, with any number of primes in each grouping. No prime may be put in both groupings. A grouping may consist of as few as one prime.

We will arbitrarily divide up the primes into the following two groupings.

G₁ = {3, 13}

G₂ = {2, 5, 7, 11}

Step Four:

Multiply the primes in each grouping together to form a product of all the primes in each grouping. We will call these products, product A and product B. Any prime in each product may be raised to any integral power greater than 1.

Let A = the product of the primes in G₁.

Let B = the product of the primes in G₂.

A = (3)(13)² = 507

B = (2)(5)(7)(11) = 770

Step Five:

Find (P_g+1)² , which is the upper limit of the range of guaranteed primality.

(P_g+1)² = (17)² = 289

 Step Six:

Find N, which is the absolute value of the difference of A and B. It can easily be proven that  the difference of A and B cannot contain as a factor, any prime factor of either A or B. If N is greater than 1 but less than (P_g+1)², then N is guaranteed by the author’s theorem to be prime.

N = |A – B| = | 507 - 770 | = 263 

Since N = 263 is less than (P_g+1)² = 289 and greater than 1, 263 is within the range of guaranteed primality and thus should be prime.

Checking 263 in a number table verifies that it is prime.

Informal Proof for Example #2:

Any integer less than (17)² = 289, but greater than 1, must either be a prime or be a composite with a prime factor less than 17.  Since no integer with a prime factor less than 17 can be produced by the configuration of the prime number producing formula of Example #2, all integers produced by the formula in this configuration that are greater than 1, but less than 289, must be prime.

Numerical Example #3 of the Use of the Prime Number Producing Formula.

Step One:

List a series of consecutive small prime numbers, starting with the smallest prime in the number system (2).

Our series is: 2, 3, 5, 7, 11, 13, 17 and 19.

Step Two:

Label the primes. Label the largest prime P_g+1, and label the next largest prime P_g.

Label the smallest prime P_1, the next consecutive prime P_2, etc, up to P_g.

P₁ = 2       P₄ = 7       P_g = 17

P₂ = 3       P₅ = 11      P_g+1 = 19

P₃ = 5       P₆ = 13

 Step Three:

Divide the primes P₁ through P_g up into two groupings. The primes may be divided up in any way, with any number of primes in each grouping. No prime may be put in both groupings. A grouping may consist of as few as one prime.

We will arbitrarily divide up the primes into the following two groupings.

G₁ = {3, 7, 17}

G₂ = {2, 5, 11, 13}

Step Four:

Multiply the primes in each grouping together to form a product of all the primes in each grouping. We will call these products, product A and product B. Any prime in each product may be raised to any integral power greater than 1.

Let A = the product of the primes in G₁.

Let B = the product of the primes in G₂.

A = (3)²(7)(17) = 1071

B = (2)(5)(11)(13) = 1430

Step Five:

Find (P_g+1)², which is the upper limit of the range of guaranteed primality.

(P_g+1)² = (19)² = 361

 Step Six:

Find N, which is the absolute value of the difference of A and B. It can easily be proven that the difference of A and B cannot contain as a factor, any prime factor of either A or B. If N is greater than 1 but less than (P_g+1)², then N is guaranteed by the author’s theorem to be prime.

N = |A – B| = | 1071 - 1430 | = 359

Since N = 359 is less than (P_g+1)² = 361 and greater than 1 , 359 is within the range of guaranteed primality and thus should be prime.

Checking 359 in a number table verifies that it is prime.

Informal Proof for Example #3:

Any integer less than (19)² = 361, but greater than 1, must either be a prime or be a composite with a prime factor less than 19.  Since no integer with a prime factor less than 19 can be produced by the configuration of the prime number producing formula of Example #3, all integers produced by the formula in this configuration that are greater than 1, but less than 361, must be prime.

Generalized Form of the Informal Proof:

Any integer less than (P_g+1)², but greater than 1, must either be a prime or be a composite with a prime factor less than P_g+1.  Since no integer with a prime factor less than P_g+1 can be produced by the prime number producing formula, all integers produced by the formula that are greater than 1, but less than (P_g+1)², must be prime.

The Author’s Prime Number Theorem and Its Formal Proof

In this derivation all literal quantities represent only positive real numbers.

Given two natural numbers, N and K, where K > N and N > 1.

Theorem 1 (a well known theorem):  If  N is a composite number,  then N has at least one prime factor  <sqrt( N).

If  K > N,  then  sqrt( K)  > sqrt( N).

Theorem 2: If N is a composite number, then N has at least one prime factor < sqrt (K).

Theorem 3: If N has no prime factor < sqrt( K) , then N is not composite.

Theorem 4: Given two natural numbers, N and K, where K > N and N > 1, if N has no prime factor < sqrt( K), then N is prime.  

References

Two articles on prime numbers and prime number formulas that the reader should find helpful in understanding this paper are the following:

Underwood Dudly, “Formulas for Primes,” Mathematics Magazine, 17-22, 1983.

A. Dewdney, “How to Pan for primes in Numerical Gravel,” Scientific American, 121, July 1988   

Appendix. Some Special Techniques that Make the Generation of Larger Primes Easier

These techniques modify the original algorithm, but they make finding N values small enough to be guaranteed prime a lot easier.

Technique #1:  Leaving 2 and 5 out of A and B.

Leaving 2 and 5 out of the two products allows either or both 2 and 5 to appear as factors of N. If one or both of these primes is a factor of an integer, this fact shows up in the last digit of the integer, which will be either even or 5. Dividing all the 2's and 5’s out of the integers (N values) produced by my algorithm will leave factors that are guaranteed prime if they are less than (P_g+1)² , but greater than one.

Technique #2: Multiplying A by a factor and / or multiplying B by a factor.

This technique involves multiplying A by a factor, which is a prime larger than P_g, or a product of primes, each prime being larger than P_g, and/or multiplying B by the same kind of factor. Each multiplier for A must contain no prime factor contained in the multiplier for B, and vice versa.

These techniques will not change the fact that the N values produced will contain no prime factor (except for 2 and 5) smaller than P_g+1. These techniques produce some impressive results, as shown below.

In the calculations below, the first integer below the dotted line is N, the absolute value of the difference of the two products, while the integer immediately below this is the prime factor obtained after all 2’s and 5’s have been divided out of N. For the calculations in the grouping immediately below,
P_g+1 = 29 and (P_g+1)² = 841.