The Top Twenty--a Prime Page Collection

Arithmetic Progressions of Primes

This page : Definition(s) | Records | Weighted Records | References | Related Pages | RSS 2.0 Feed
  View this page in:   language help

The Prime Pages

The Prime Pages keeps a list of the 5000 largest known primes, plus a few each of certain selected archivable forms and classes. These forms are defined in this collection's home page. This page is about one of those forms. Comments and suggestions requested.

(up) Definitions and Notes

Are there infinitely many primes in most arithmetic progressions?  Certainly not if the common difference has a prime factor in common with one of the terms (for example: 6, 9, 12, 15, ...).  In 1837, Dirichlet proved that in all other cases the answer was yes:
Dirichlet's Theorem on Primes in Arithmetic Progressions
If a and b are relatively prime positive integers, then the arithmetic progression a, a+b, a+2b, a+3b, ... contains infinitely many primes.
Recall that the prime number theorem states that for any given n, there are asymptotically n/log n primes less than n.  Similarly it can be proven that the sequence a + k*b (k = 1,2,3,...) contains asymptotically n/(phi(b) log n) primes less than n.  This estimate does not depend on the choice of a!

Dirichlet's theorem does not say that there are arbitrarily many consecutive terms in this sequence which are primes (which is what we'd like).  But Dickson's conjecture does suggests that given any positive integer n, then for each "acceptable" arithmetic progression there are n consecutive terms which are prime.  In 1939, van der Corput showed that there are infinitely many triples of primes in arithmetic progression [Corput1939].  In 2004, Green and Tao [GT2004a] showed that there are indeed arbitrarily long sequences of primes and that a k-term sequence of primes occurs before [GT2004b]:

22222222100k
Obviously this is not optimal!  It is conjectured that it actually occurs before k!+1.

But either way, there is a world of difference betwen what we know to be true (there are infinitely long arithemetic progressions of primes), and what we have computed: the longest is just over two dozent terms! (See Jens Kruse Andersen's excellent pages linked below.)

It is also possible to put this into a quantative form and heuristically estimate how many there should be.  For example, Grosswald [GH79] suggested that if Nk is the number of arithmetic progressions of k primes all less than N, then

N_k~D_k*N^2/(2(k-1)(log N)^k)
where
Ugly Hardy-Littlewood type product
He was able to prove this for the case k=3 [GH79].  Green and Tao have recently proven it for k=4 [GT2006a].

In our heuristics pages we also give asymptotic estimates for the number with fixed length k and fixed difference d.  The first table shows the largest known primes in arithmetic sequence (but just the third term and beyond for each sequence).

[ See all such primes on the list.]

(up) Record Primes of this Type

rankprime digitswhowhencomment
11061839 · 2456790-1769267 · 2340000-1 137514 p97 Aug 2007 term 3, difference 1061839 · 2456789-1769267 · 2340000
217 · 2429319-197 · 2202534-1 129240 p162 Feb 2005 term 3, difference 17 · 2429318-197 · 2202534
345 · 2368554-405769059 · 2180009-1 110948 p108 Dec 2003 term 3, difference 45 · 2368553-405769059 · 2180009
428782838101 · 2333333-1 100354 L453 Dec 2007 term 3, difference 3371818539 · 2^333335 [g282]
526273597661 · 2333333-1 100354 L329 Nov 2007 term 3, difference 38478921 · 2^333341 [g282]
6111871891 · 27751#+1 11961 p155 Jan 2008 term 4, difference 3624707 · 27751#
7103098395 · 27751#+1 11961 p155 Oct 2007 term 4, difference 809963 · 27751#
8102293041 · 27751#+1 11961 p155 Sep 2007 term 4, difference 412064 · 27751#
946915147 · 235000+1 10544 p43 Jul 2007 term 4, difference 9548007 · 235000
10409331735 · 233333+1 10043 p155 Aug 2007 term 4, difference 104086947 · 233333
11197418203 · 225000+6089 7535 FE4 Feb 2005 ECPP, consecutive primes term 3, difference 6090
1287 · 224582+2579 7402 c31 Nov 2004 ECPP, consecutive primes term 3, difference 1290
132852851249 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 2653152 · 16001#
142399771561 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 86574302 · 16001#
151638535589 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 2003735 · 16001#
164811 · 220219+1 6091 DM Oct 1996 Consecutive primes term 3, difference 3738 [c36]
17(84055657369 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+13 5132 p179 Apr 2006 Consecutive primes term 3, difference 6
18(61310346529 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+13 5132 p179 Oct 2005 Consecutive primes term 3, difference 6
19(51803036889 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+7 5132 p179 Feb 2007 term 5, difference (681402540 · 205881 · 4001# · (205881 · 4001#+1) · (205881 · 4001#-1)/35)
20(50105157104 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+7 5132 p179 Feb 2007 term 5, difference (378234360 · 205881 · 4001# · (205881 · 4001#+1) · (205881 · 4001#-1)/35)

(up) Weighted Record Primes of this Type

The difficulty of finding such sequences depends on their length.  For example, it will be a long time before a an arithmetic sequence of twenty titanic primes is known!  Just for the fun of it, let's attempt to rank these sequences by how long they are.

To rank them, we might take the usual estimate of how hard it is to prove primality of a number the size of n

log(n)2 log log n
and multiply it by the expected number of potential candidates to test before we find one of length k (by the heuristic estimate above):
sqrt(2(k-1)/Dk) (log n)(2+k/2) log log n.
We then take the log one more time just to reduce the size of these numbers.

Notes:

  1. We use the natural log in calculating this weight.
  2. The Dk's begin 1.32032, 2.858525, 4.15118, 10.1318, 17.2986 and 53.9720 for k = 3, 4, 5, 6, 7, and 8 and continue 148.552, 336.034, 511.422, 1312.32, 2364.60, 7820.61, 22939, 55651, 91555, 256480, 510990, 1901000, ... [GH79].

rankprime digitswhowhencomment
16179783529 · 2411#+1 1037 p102 Jun 2003 term 8, difference 176836494 · 2411#
21061839 · 2456790-1769267 · 2340000-1 137514 p97 Aug 2007 term 3, difference 1061839 · 2456789-1769267 · 2340000
317 · 2429319-197 · 2202534-1 129240 p162 Feb 2005 term 3, difference 17 · 2429318-197 · 2202534
445 · 2368554-405769059 · 2180009-1 110948 p108 Dec 2003 term 3, difference 45 · 2368553-405769059 · 2180009
528782838101 · 2333333-1 100354 L453 Dec 2007 term 3, difference 3371818539 · 2^333335 [g282]
626273597661 · 2333333-1 100354 L329 Nov 2007 term 3, difference 38478921 · 2^333341 [g282]
72852851249 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 2653152 · 16001#
82399771561 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 86574302 · 16001#
91638535589 · 16001#/5+1 6913 p199 Jun 2008 term 5, difference 2003735 · 16001#
10833000864 · 3011#+1 1290 p155 Feb 2006 term 7, difference 114858412 · 3011#
11821752479 · 3011#+1 1290 p155 Feb 2006 term 7, difference 114379137 · 3011#
12797311599 · 3011#+1 1290 p155 Dec 2006 term 7, difference 98881303 · 3011#
13489855608 · 3011#+1 1290 p155 Feb 2006 term 7, difference 1679489 · 3011#
141730304995 · 3001#+1 1287 p73 Oct 2004 term 7, difference 230408192 · 3001#
15(51803036889 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+7 5132 p179 Feb 2007 term 5, difference (681402540 · 205881 · 4001# · (205881 · 4001#+1) · (205881 · 4001#-1)/35)
16(50105157104 · 205881 · 4001# · (205881 · 4001#+1)+210) · (205881 · 4001#-1)/35+7 5132 p179 Feb 2007 term 5, difference (378234360 · 205881 · 4001# · (205881 · 4001#+1) · (205881 · 4001#-1)/35)
17111871891 · 27751#+1 11961 p155 Jan 2008 term 4, difference 3624707 · 27751#
18103098395 · 27751#+1 11961 p155 Oct 2007 term 4, difference 809963 · 27751#
19102293041 · 27751#+1 11961 p155 Sep 2007 term 4, difference 412064 · 27751#
2052069470 · 3739#+1 1606 p155 Apr 2006 term 6, difference 3884057 · 3739#

(up) Related Pages

(up) References

BH77
C. Bayes and R. Hudson, "The segmented sieve of Eratosthenes and primes in arithmetic progression," Nordisk Tidskr. Informationsbehandling (BIT), 17:2 (1977) 121--127.  MR 56:5405
Chowla44
S. Chowla, "There exists an infinity of 3--combinations of primes in A. P.," Proc. Lahore Phil. Soc., 6 (1944) 15--16.  MR 7,243l
Corput1939
A. G. van der Corput, "Über Summen von Primzahlen und Primzahlquadraten," Math. Ann., 116 (1939) 1--50.
DN97
H. Dubner and H. Nelson, "Seven consecutive primes in arithmetic progression," Math. Comp., 66 (1997) 1743--1749.  MR 98a:11122 (Abstract available)
GH79
E. Grosswald and P. Hagis, Jr., "Arithmetic progression consisting only of primes," Math. Comp., 33:148 (October 1979) 1343--1352.  MR 80k:10054 (Abstract available)
Grosswald82
E. Grosswald, "Arithmetic progressions that consist only of primes," J. Number Theory, 14 (1982) 9--31.  MR 83k:10081
GT2004a
B. Green and T. Tao, "The primes contain arbitrarily long arithmetic progressions," Ann. Math., preprint. Available from http://arxiv.org/abs/math/0404188v6.
GT2004b
B. Green and T. Tao, "A bound for progressions of length k in the primes," (2004) preprint.
GT2006a
B. Green and T. Tao, "Linear equations in primes," (2006) preprint. Available from http://arxiv.org/abs/math/0606088.
Guy94 (section A6)
R. K. Guy, Unsolved problems in number theory, Springer-Verlag, New York, NY, ISBN 0-387-94289-0. 1994.  MR 96e:11002 [An excellent resource! Guy briefly describes many open questions, then provides numerous references.]
LP67
L. J. Lander and T. R. Parkin, "On first appearance of prime differences," Math. Comp., 21:99 (1967) 483-488.  MR 37:6237
Rose94 (Chpt 13)
H. E. Rose, A course in number theory, second edition, Clarendon Press, New York, pp. xvi+398, ISBN 0-19-853479-5; 0-19-852376-9. 1994.  MR 96g:11001 (Annotation available)
Chris Caldwell © 1996-2008 (all rights reserved)