Prime Arithmetic Progression

Prime Phyllotaxis Spirals | Maxwell's DemonPrime Arithmetic Progression

By MathWorld

An arithmetic progression of primes is a set of primes of the form p_1+kd for fixed p_1 and d and consecutive k, i.e., {p_1,p_1+d,p_1+2d,...}. For example, 199, 409, 619, 829, 1039, 1249, 1459, 1669, 1879, 2089 is a 10-term arithmetic progression of primes with difference 210.

It had long been conjectured that there exist arbitrarily long sequences of primes in arithmetic progression (Guy 1994). As early as 1770, Lagrange and Waring investigated how large the common difference of an arithmetic progression of n primes must be. In 1923, Hardy and Littlewood (1923) made a very general conjecture known as the k-tuple conjecture about the distribution of prime constellations, which includes the hypothesis that there exist infinitely long prime arithmetic progressions as a special case. Important additional theoretical progress was subsequently made by van der Corput (1939), who proved than there are infinitely many triples of primes in arithmetic progression, and Heath-Brown (1981), who proved that there are infinitely many four-term progressions consisting of three primes and a number that is either a prime or semiprime.

However, despite all this labor, proof of the general result for arbitrarily long sequences of primes has remained an open conjecture (Guy 1994, p. 15). Thanks to new work by Ben Green and Terence Tao, the conjecture seems to finally have been settled in the positive. In a recently published in preprint, Green and Tao (2004) use an important result known as Szemerédi’s theorem in combination with recent work by Goldston and Yildirim, a clever “transference principle,” and 48 pages of dense and technical mathematics, to apparently establish the fundamental theorem that the prime numbers do contain arithmetic progressions of length k for all k (Weisstein 2004). The proof, however, is nonconstructive.

Let P be an increasing arithmetic progression of n primes with minimal difference d>0. If a prime p<=n does not divide d, then the elements of P must assume all residues modulo p, specifically, some element of P must be divisible by p. Since P contains only primes, this element must be equal to p.

Let the number of primes of the form p_1+kd less than x be denoted pi_(d,p_1)(x). Then


where Li(x) is the logarithmic integral and phi(x) is the totient function.

Let n# denote the primorial of n. Then if d<n#, some prime p<=n does not divide d, and that prime p is in P. Thus, in order to determine if P has d<n#, it is only necessary to check a finite number of possible P (those with d<n# and containing prime p<=n) to see if they contain only primes. If not, then d>=n#. If d=n#, then the elements of P cannot be made to cover all residues of any prime p. The k-tuple conjecture then asserts that there are infinitely many arithmetic progressions of primes with difference d.

A computation shows that the smallest possible common difference for a set of n or more primes in arithmetic progression for n=1, 2, 3, … is 0, 1, 2, 6, 6, 30, 150, 210, 210, 210, 2310, 2310, 30030, 30030, 30030, 30030, 510510, … (OEIS A033188, Ribenboim 1989, Dubner and Nelson 1997). The values up to n=18 are rigorous, while the remainder are lower bounds which assume the validity of the k-tuple conjecture and are simply given by n#. The smallest first terms of arithmetic progressions of n primes with minimal differences are 2, 2, 3, 5, 5, 7, 7, 199, 199, 199, 60858179, 147692845283, 14933623, 834172298383, … (OEIS A033189; Wilson).

Smaller first terms are possible for nonminimal n-term progressions. Examples include the 8-term progression 11+1210230k for k=0, 1, …, 7, the 12-term progression 23143+30030k for k=0, 1, …, 11 (Golubev 1969, Guy 1994), and the 13-term arithmetic progression 766439+510510k for k=0, 1, …, 12 (Guy 1994).

The following table summarizes the largest known arithmetic progressions of n primes for small n, where

k primes for n=0, 1, …, k-1 digits reference
3 P_3 137514 J. K. Anderson et al. (2007)
4 (100997770+3624707n)27751#+1 11961 K. Davis (2008)
5 1/5(2799788209+13265760n)16001#+1 6913 D. Broadhurst (2008)
6 (32649185+3884057n)3739#+1 1606 K. Davis (2006)
7 (143850392+114858412n)3011#+1 1290 K. Davis (2006)
8 (4941928071+176836494n)2411#+1 1037 P. Underwood (2003)
9 (805227062+54790161n)941#+1 401 M. Oakes (2006)

A more complete table is maintained by Andersen.

The smallest sequence of six consecutive primes in arithmetic progression is


for k=0, 1, …, 5 (Lander and Parkin 1967, Dubner and Nelson 1997).

The largest known case of three consecutive primes in arithmetic progression is 1205·2^(16165)-869+870k for k=0, 1, 2, found by T. Alm, H. Rosenthal, J. K. Andersen, and R. Ballinger in 2003.

The largest known sequence of cons

This beats the record of nine consecutive primes set on January 15, 1998 by the same investigators,

 99679432066701086484490653695853 561638982364080991618395774048585 529071475461114799677694651+210k

for k=0, 1, …, 8 (two sequences of nine are now known), the progression of eight consecutive primes given by

 43804034644029893325717710709965 599930101479007432825862362446333 961919524977985103251510661+210k

for k=0, 1, …, 7, discovered by Harvey Dubner, Tony Forbes, et al. on November 7, 1997 (several are now known), and the progression of seven given by

 1089533431247059310875780378922957732 908036492993138195385213105561742150 447308967213141717486151+210k,

for k=0, 1, …, 6, discovered by H. Dubner and H. K. Nelson on Aug. 29, 1995 (Peterson 1995, Dubner and Nelson 1997).




Tagged: , , , , ,

Leave a comment!

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: