Computing All the Prime Numbers from Here to Infinity

This past summer, two students at Tennessee Technology University published a paper that presents a unique computational method for generating a potentially infinite number of prime numbers. Normally when we cover this kind of topic, we would quote the abstract and translate the meat of the paper into English, but the authors, Jonathan Dugas and Brian O’Connor, broke with the traditional presentation of almost indecipherable hieroglyphics that is inherent in these kinds of papers and simply described what they set out to do in the paper’s introduction so we didn’t have to!

… what if there exists an equation that can indefinitely generate prime numbers as well as some composite numbers and what if there is a periodicity to the composite numbers? An equation could then be written to eliminate the composite numbers. Then, in essence, there would exist a mathematical method for generating primes indefinitely, which avoids the need for finding a sequential order to the prime numbers. The purpose of this work is to present such a method, which is in agreement with the prime number theorem and to prove the validity of that method by computation.

Dugas and O’Connor go on to describe the computational method that they developed to sieve through all the integers within a given range to identify the prime numbers among them. The basic equation they developed allowed them to generate all of the prime numbers from 5 on up, as well as composite numbers (numbers that may be factored into prime numbers) that are not factorable by the prime numbers of 2 or 3.

They then exploited the presence of sequences in the composite numbers they generated to eliminate them from the set produced by their basic equation, leaving only prime numbers behind.

In practice, their method is potentially an improvement of the Sieve of Eratosthenes, which can be an effective method for sifting out the prime numbers within a given range of integers.

Dugas and O’Connor’s improved sieve went a bit farther in correctly determining all the prime numbers between the integers one and one billion. All 50,847,534 of them (partially listed here). To do the math, they only needed a Dell laptop with an Intel Core i7 processor to run their code written in C++.

Dugas and O’Connor touch on the key to determining prime numbers using their computational approach:

The results of this work validate the notion that prime numbers are not random. The sequential order to the prime numbers is determinable by a connection to composite numbers which are not divisible by 2 or 3. Although it is difficult to prove by a method other than computation, the sequences presented generate prime numbers indefinitely; however, they do generate composite numbers not divisible by 2 or 3. There is a periodicity to the composite numbers, which allows them to be eliminated using basic mathematical functions and operations. Given the presented sets of sequences for determining primes and eliminating composites hold true for all values of (N), one must first understand the sequence to the composites not divisible by 2 or 3 to understand the sequence to the prime numbers; the sequence to primes is disguised as a sequence to composites.

That’s a bold statement, where the ball is now in the mathematicians’ (and computer scientists’) court. It will be interesting to see if Dugas and O’Connor’s approach holds, or if it turns out to be a rediscovery of an approach that has previously been explored.

As for its potential, the algorithm might be used to identify prime numbers between the known Mersenne primes, where the largest prime number found to date consists of over 22 million digits, which took 31 days to determine that it was a prime number on another PC running with an Intel Core i7 processor back in 2016.

References

Dugas, Jonathan M. and O’Connor, Brian M. Sequences for Determination of Prime Numbers by Elimination of Composites. Journal of Mathematics and Statistics. Volume 13, Issue 3, Pages 177-185. [PDF Document]. DOI:10.3844/jmssp.2017.177.185. 14 July 2017.