PRIMES IN ARITHMETIC PROGRESSION

From http://www.eng.um.edu.mt/~andebo/numbers/numcom12.htm

A series of numbers is said to be in arithmetic progression (AP) if the difference between each term and the preceding one is constant. Thus the sequence 5, 10, 15, 20, 25, 30 forms an AP of 6 terms with a common difference of 5. Can you write a program on your home computer using your favourite programming language to find AP’s made up solely of prime numbers? A large store of prime numbers on your hard disk would be found very useful in problems of this kind as stated earlier in the fourth article in this series. Refer to this article for hints on how to write a computer program to find prime numbers. Alternatively you can install mathematical software which can generate prime numbers.

Before you start writing the program to search for such sequences, it is worth noting the following. In these prime AP’s, if n is the number of terms in the sequence, then the product of all the primes less than or equal to n must divide the common difference provided that the first term is not equal to n. If the first term happens to be equal to n then the product of all the primes less than n must divide the common difference. Using this knowledge in your program will speed up your search for such sequences. Remember that a little bit of theory can save a lot of computation!

Let us look at some examples. Consider the following sequence made up of seven primes: 7, 157, 307, 457, 607, 757, 907. Note that this can be expressed as: 7 + k x 150 with k = 0, 1, 2, ……6. In this sequence the first term happens to be equal to the number of terms ( 7 ) and therefore the product of the primes 2, 3 and 5 ( i.e. 30 ) must divide the common difference (150) which it obviously does. Notice that 2 x 3 x 5 x 7 ( = 210 ) does not divide the common difference. Let us take a longer sequence. This time the number of terms is eleven and the sequence is given by: 110437 + k x 13860 with k = 0, 1, 2, 3…….10. Now the first term is not equal to the number of terms and therefore we can multiply all the primes less than or equal to 11 together i.e. 2 x 3 x 5 x 7 x 11 obtaining 2310 as a divisor of the common difference. Indeed 13860 divided by 2310 equals 6.

A marathon computation on primes in AP, totalling 14000 hours of computer time, deserves mentioning. It was carried out by P.A.Pritchard using two DEC VAX-11/780 machines at Cornell University, USA. Many long sequences of primes in AP were found, the longest having 19 terms. The search ran in the background so as not to interfere with the computers’ normal jobs. The 14000 hours were accumulated over the period 6th October, 1982 to 18th March, 1984 [1] . Incidentally the longest known sequence of primes in AP consists of 22 primes. This was found in 1993 using more than 60 computers.

One can also search for AP’s made up of consecutive primes such as 251, 257, 263, 269. By writing a simple program on your home computer you should find plenty of sequences made up of 3 or 4 terms but those with 5 or more primes are extremely difficult to find. In fact the first sequence consisting of five consecutive primes was found as late as 1967, twenty years after the appearance of the first electronic computer. That same year a sequence of six primes was also found but finding seven consecutive primes in AP had to wait until 1995 when Harvey Dubner and Harry Nelson found one such sequence. The record consists of ten primes discovered in 1998 by Dubner, Forbes, Lygeros, Mizony, Zimmermann and Toplic with the help of scores of number / computer enthusiasts distributed worldwide. Using the Internet, a large number of PC’s around the world were thus used collectively in one massive search. The primes in this sequence of ten are 93-digit numbers and the common difference is 210 which is 2 x 3 x 5 x 7. According to Dubner and his team, searching for eleven consecutive primes in AP is beyond present computer power and so they expect the ten-primes record to hold for a long time.

Reference: [1] P.A. Pritchard, Mathematics of Computation, Vol.45, No.171, July 1985, pages 263-267, “Long Arithmetic Progressions of Primes: Some Old, Some New”.

************************************************************************************
Back to list of articles.