AiS Challenge Team interim report

Team Number: 047

School Name: Magdalena High School

Area of Science: Computer Science

Project Title: Twin Prime

Problem Definition:
Primes have been studied by thousands of years by mathematicians around the world. Euclid Proved that there are infinitely many primes, and Eratosthenes, another ancient Greek, developed a method of finding all primes called the Sieve of Eratosthenes.

Twin primes are two consecutive odd numbers that are both prime. It is believed that there are infinitely many pairs of twin primes, starting with 3,5 and 5,7. Mathematicians are continually searching for larger and larger twin primes and study the distance between pairs. We do know that the sum of the inverses of twin primes is limited, though the sum of the inverses of primes has been proven to grow without bound. There is a hypothesis that the sum of the inverses of twin primes is equal to the number Brun’s Constant, named after the author of hypothesis.

Mathematicians and computer scientists have found 8494836459690 twin primes to date, the largest one being 3180323612107001±1 which consists of 32220 digits, and was found by Underbakke, Carmody, and PrimeForm in 2001.

Problem Solution:
The goal of out project is to continue that search by creating a program that will search for twin primes on multiple processors in a given interval. The output from this search will be sent to the screen and to file, and while running our program will increment to the next interval when a twin primes is found in the current interval. Therefore the program will search for the next largest known twin primes.

Progress to Date:
At this time, we have developed a program that will find twin primes in a given interval. We start by finding an array of base primes, which will consist of the primes up to 65535, found using the Sieve of Eratosthenes. Then we use this array of base primes to sieve through an array containing all numbers in the given interval. After finding all multiples of the base primes in the search interval, the remaining numbers are send to function called Fermat. In this function, the program uses the Fermat method of factorization to attempt to find factors, which would eliminate the possibility of primality. Then all the numbers remaining are prime. We then search through the primes to find twins. When the twin primes have been found, they are printed to a screen and will be printed to a file. We are now beginning to incorporate the GMP library to use with storing and manipulating large integers and afterwards will integrate MPI commands in our program so that it can be run on multiple processors.

Expected Resulted:
We expect to find very large twin primes in intervals of huge numbers. We are attempting to find the largest known pair of twin primes. Our program will start at a given interval, and move on to the next interval when a set of twin primes is found in order to search for the next highest pair. Therefore our program will find the next largest known set of twin primes.

Team Members

Team Mail

Sponsoring Teacher(s)

Project Mentor(s)