## Arithmetic Progressions of Primes |

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:
*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*!
*k*!+1.
But either way, there is a world of difference between what we know to be true (there are infinitely long arithmetic progressions of primes), and what we have computed: the longest is just over two dozen terms! (See Jens Kruse Andersen's excellent pages linked below.)
*k*=3 [GH79]. Green and Tao have recently proven it for *k*=4 [GT2006a].

Recall that the prime number theorem states that for any given

Dirichlet's Theorem on Primes in Arithmetic Progressions- If
aandbare relatively prime positive integers, then the arithmetic progressiona,a+b,a+2b,a+3b, ... contains infinitely many primes.

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]:

2Obviously this is not optimal! It is conjectured that it actually occurs before^{2222222100k}

It is also possible to put this into a quantitative form and heuristically estimate how many there should be. For example, Grosswald [GH79] suggested that if *N _{k}* is the number of arithmetic
progressions of

where

He was able to prove this for the case

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.]

rank prime digits who when comment 1 4704549881115 · 2^{1290000}- 1388342 L3494 Jun 2016 term 3, difference 496648444065 · 2 ^{1290002}2 3532235829429 · 2^{1290000}- 1388342 L3494 Jan 2016 term 3, difference 656129614401 · 2 ^{1290001}3 3264529598685 · 2^{1290000}- 1388342 L3494 Jan 2016 term 3, difference 221561854755 · 2 ^{1290002}4 3219238907205 · 2^{1290000}- 1388342 p199 Sep 2015 term 3, difference 683912203455 · 2 ^{1290001}5 2724961865247 · 2^{1290000}- 1388342 p199 Oct 2015 term 3, difference 222119028825 · 2 ^{1290002}6 2339196157659 · 2^{1290000}- 1388342 p199 Sep 2015 term 3, difference 69718264533 · 2 ^{1290002}7 2258157308997 · 2^{1290000}- 1388342 p199 Oct 2015 term 3, difference 477145708425 · 2 ^{1290001}8 492590931 · 2^{80000}- 1631979959 · 2^{25001}- 124092 p199 Oct 2010 term 4, difference 164196977 · 2 ^{80000}- 1631979959 · 2^{25000}9 16481859 · 35023# - 115130 p364 Nov 2015 term 4, difference 4190788 · 35023# 10 1008075799 · 34687# + 115004 p252 Jul 2010 term 4, difference 2571033 · 34687# 11 263821581 · 2^{45001}- 487069965 · 2^{25002}- 113556 p199 Jun 2010 term 4, difference 87940527 · 2 ^{45001}- 487069965 · 2^{25001}12 4103163 · 2^{45007}- 183009063 · 2^{25003}- 113556 p199 Jun 2010 term 4, difference 1367721 · 2 ^{45007}- 183009063 · 2^{25002}13 1213266377 · 2^{35000}+ 485910546 c4 Mar 2014 ECPP, consecutive primes term 3, difference 2430 14 1043085905 · 2^{35000}+ 1819710546 c4 Feb 2014 ECPP, consecutive primes term 3, difference 18198 15 109061779 · 2^{35003}+ 1185510545 c4 Feb 2014 ECPP, consecutive primes term 3, difference 5928 16 350049825 · 2^{35000}+ 770310545 c4 Jan 2014 ECPP, consecutive primes term 3, difference 3852 17 146462479 · 2^{35001}+ 876510545 c4 Dec 2013 ECPP, consecutive primes term 3, difference 8766 18 1016730525 · 16301# + 17035 p155 Jun 2016 term 5, difference 7078086 · 16301# 19 16267# · 118917167 - 17026 p364 Dec 2015 term 5, difference 18797279 · 16267# 20 110650531 · 16267# - 17026 p364 Dec 2015 term 5, difference 18149866 · 16267#

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(and multiply it by the expected number of potential candidates to test before we find one of lengthn)^{2}log logn

sqrt(2(We then take the log one more time just to reduce the size of these numbers.k-1)/D) (log_{k}n)^{(2+k/2)}log logn.

Notes:

- We use the natural log in calculating this weight.
- The
*D*'s begin 1.32032363, 2.85824860, 4.15118086, 10.1317949, 17.2986123, and 53.9719483 for_{k}*k*= 3, 4, 5, 6, 7, and 8. They continue 148.551629, 336.034327, 1312.31971, 2364.59896, 7820.60003, 22938.9086, 55651.4626, 91555.1112, 256474.860, 510992.010, 1900972.58, 6423764.31, 18606666.2, 38734732.7, 153217017., 568632503.5, 1941938595 ... [GH79].

rank prime digits who when comment 1 116040452086 · 2371# + 11014 p308 Jan 2012 term 9, difference 6317280828 · 2371# 2 97336164242 · 2371# + 11014 p308 Apr 2013 term 9, difference 6350457699 · 2371# 3 93537753980 · 2371# + 11014 p308 Apr 2013 term 9, difference 3388165411 · 2371# 4 92836168856 · 2371# + 11014 p308 Apr 2013 term 9, difference 127155673 · 2371# 5 69318339141 · 2371# + 11014 p308 Jul 2011 term 9, difference 1298717501 · 2371# 6 4704549881115 · 2^{1290000}- 1388342 L3494 Jun 2016 term 3, difference 496648444065 · 2 ^{1290002}7 3532235829429 · 2^{1290000}- 1388342 L3494 Jan 2016 term 3, difference 656129614401 · 2 ^{1290001}8 3264529598685 · 2^{1290000}- 1388342 L3494 Jan 2016 term 3, difference 221561854755 · 2 ^{1290002}9 3219238907205 · 2^{1290000}- 1388342 p199 Sep 2015 term 3, difference 683912203455 · 2 ^{1290001}10 2724961865247 · 2^{1290000}- 1388342 p199 Oct 2015 term 3, difference 222119028825 · 2 ^{1290002}11 2339196157659 · 2^{1290000}- 1388342 p199 Sep 2015 term 3, difference 69718264533 · 2 ^{1290002}12 2258157308997 · 2^{1290000}- 1388342 p199 Oct 2015 term 3, difference 477145708425 · 2 ^{1290001}13 3124777373 · 7001# + 13019 p155 Feb 2012 term 7, difference 481789017 · 7001# 14 2968802755 · 2459# + 11057 p155 Apr 2009 term 8, difference 359463429 · 2459# 15 6179783529 · 2411# + 11037 p102 Jun 2003 term 8, difference 176836494 · 2411# 16 115248484057 · 2371# + 11014 p308 Apr 2013 term 8, difference 7327002535 · 2371# 17 113236255068 · 2371# + 11014 p308 Apr 2013 term 8, difference 6601354956 · 2371# 18 112929231161 · 2371# + 11014 p308 Apr 2013 term 8, difference 6982118533 · 2371# 19 492590931 · 2^{80000}- 1631979959 · 2^{25001}- 124092 p199 Oct 2010 term 4, difference 164196977 · 2 ^{80000}- 1631979959 · 2^{25000}20 2996180304 · 7001# + 13019 p155 Feb 2012 term 6, difference 46793757 · 7001#

- Jens Kruse Andersen's excellent Primes in Arithmetic Progression Records

- BH77
C. BayesandR. 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. DubnerandH. Nelson, "Seven consecutive primes in arithmetic progression,"Math. Comp.,66(1997) 1743--1749.MR 98a:11122(Abstract available)- GH79
E. GrosswaldandP. 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
Green, BenandTao, Terence, "The primes contain arbitrarily long arithmetic progressions,"Ann. of Math. (2),167:2 (2008) 481--547. (http://dx.doi.org/10.4007/annals.2008.167.481)MR 2415379- GT2004b
B. GreenandT. Tao, "A bound for progressions of lengthkin the primes," (2004) Available from http://people.maths.ox.ac.uk/greenbj/papers/back-of-an-envelope.pdf.- GT2006a
Green, BenjaminandTao, Terence, "Linear equations in primes,"Ann. of Math. (2),171:3 (2010) 1753--1850. (http://dx.doi.org/10.4007/annals.2010.171.1753)MR 2680398- Guy94 (section A6)
R. K. Guy,Unsolved problems in number theory, Springer-Verlag, New York, NY, 1994. ISBN 0-387-94289-0.MR 96e:11002[An excellent resource! Guy briefly describes many open questions, then provides numerous references. See his newer editions of this text.]- LP67
L. J. LanderandT. 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, 1994. New York, pp. xvi+398, ISBN 0-19-853479-5; 0-19-852376-9.MR 96g:11001(Annotation available)

Chris K. Caldwell
© 1996-2016 (all rights reserved)