Twin Primes

Final Report

Executive Summary

Our project attempts to find the next largest set of twin primes. Twin primes are two consecutive odd numbers that are both primes. Many mathematicians and computer scientists around the world conduct this search. We began solving this problem by writing a program that finds primes using the Sieve of Eratosthenes, then using these base primes to search much larger numbers for primality. We search through an interval of our choosing, marking off all multiples of the base primes. Then we take the remaining numbers and check to see if they are prime using Fermat's Little Theorem. In this way, we find the prime numbers in our search interval and then are able to look within these prime numbers for twin primes. Our current working copy will work for numbers up to unsigned long max int. We are at this time incorporating some software provided for us by our mentor that allows us to work with integers larger than the max integer on the processor. Once implemented, this software will allow us to search for twin primes in extremely large numbers. Once we accomplish this step, we will then begin separating our intervals and changing our code to run on multiple processors. When one processor finds a set of twin primes, the other processors will make sure that they are searching in numbers higher than the most recently found set of twin primes, so that we are continually looking for bigger and bigger primes without searching unnecessary intervals.

Introduction

Our project is an attempt to find the next largest set of twin primes. Our program sifts through numbers searching for primes, and then checking those to find twin primes. Our program searches through very large numbers and will be able to run on multiple processors. We chose this program as a programming challenge to us, dealing with extremely large integers and working on multiple processors, with hopes for preparing ourselves for computer programming classes in college. Prime numbers have always been of curiosity to mathematicians, and they continue to search for them and study their relationships. Primes are sought after for many reasons. Prime numbers can be used to develop cryptography. Prime number programs are also used to test hardware and the computing strength of certain machines. Another advantage that comes from searching for large primes, twin primes, and other primes is simply the by products that are produced. Now we find better algorithms and computer programming methods, in the past, many great theorems were found when attempting to find larger and larger primes. Mathematicians study primes and their distribution. One reason they want to find larger primes is to test or prove their current theories, the more primes we find, the larger the scope of experimentation for our mathematical theorems. Our program attempts to find the next largest set of twin primes. Twin primes are two consecutive odd numbers that are both prime, such as 3,5 and 5,7.

Description

When attempting to find the next largest set of twin primes, we first wrote a program to find prime numbers up to a given number. We did this by dynamically creating an array of numbers, then using the Sieve of Eratosthenes found the prime numbers in that interval. Then we set a new, larger search interval, and used this base prime array to sieve out all the multiples of any of our base primes. After marking off the multiples of our base primes, we then began sending the remaining numbers to a function using Fermat's little theorem to test further for primality. After finding the prime numbers, we then begin searching for the twins within these primes. We are now incorporating some software that our mentor provided for us to work with large integers. Our next step is then to begin running our program on multiple processors.

Results

Right now our program can find the twin primes up to the maximum integer on the computer. We are continuing to incorporate the software our mentor provided for using larger integers, and will then begin separating the work load and using multiple processors to search faster through different intervals. Therefore we have not yet found the next largest set of twin primes, the attempt of our program.

Conclusions

Our conclusions are that primes numbers are not difficult to find, but the problems of working with larger integers has proven to be very difficult and time consuming. However, we have been making good progress in debugging our code and implementing our additional software.


Recommendations

We believe that it is important to understand your limitations. We are searching for large twin primes, and say that the purpose of our project is to find the next largest set of twin pr , owever computer programmers and mathematicians spend their entire careers looking for these same results, and it is highly unlikely that we will be able to go beyond the scope of professional programmers with years of experience and time put into their programs.

Acknowledgments


We have to give special thanks to Anna Johnston, our mentor from Sandia National Laboratories. She has inspired us with lots of advice and helpful ideas. She also provided us with the software to deal with large numbers, and has helped us to implement and debug this code.



Reference List

Burton, David M., Elementary Number Theory. Wm. C. Brown Publishers,
Dubuque, Iowa ©1989. pgs. 59-66, 107-127

Prata, Stephen, C++ Primer Plus. Third Edition, Sams Publishing,
Indianapolis, Indiana © 1998