## 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 3555 · 2^{1542813}- 4953427788675 · 2^{1290000}- 1464437 p363 Apr 2020 term 3, difference 3555 · 2 ^{1542812}- 4953427788675 · 2^{1290000}2 4125 · 2^{1445206}- 2723880039837 · 2^{1290000}- 1435054 p199 Dec 2016 term 3, difference 4125 · 2 ^{1445205}- 2723880039837 · 2^{1290000}3 2415 · 2^{1413628}- 1489088842587 · 2^{1290000}- 1425548 p199 Feb 2017 term 3, difference 2415 · 2 ^{1413627}- 1489088842587 · 2^{1290000}4 2985 · 2^{1404275}- 770527213395 · 2^{1290000}- 1422733 p199 Jan 2017 term 3, difference 2985 · 2 ^{1404274}- 770527213395 · 2^{1290000}5 9422094211005 · 2^{1290000}- 1388342 L3494 Apr 2020 term 3, difference 2227792035315 · 2 ^{1290001}6 1043945909 · 60013# + 125992 p155 Jul 2019 term 4, difference 7399459 · 60013# 7 1041073153 · 60013# + 125992 p155 May 2019 term 4, difference 10142823 · 60013# 8 1036053977 · 60013# + 125992 p155 Jun 2019 term 4, difference 10664254 · 60013# 9 1027676400 · 60013# + 125992 p155 Mar 2019 term 4, difference 6813491 · 60013# 10 1025139165 · 60013# + 125992 p115 Mar 2019 term 4, difference 6205834 · 60013# 11 664342014133 · 2^{39840}+ 112005 p408 Apr 2020 Consecutive primes term 3, difference 30 12 3428602715439 · 2^{35678}+ 1310753 c93 Apr 2020 Consecutive primes term 3, difference 6, ECPP 13 2683143625525 · 2^{35176}+ 1310602 c92 Dec 2019 Consecutive primes term 3, difference 6, ECPP 14 1213266377 · 2^{35000}+ 485910546 c4 Mar 2014 ECPP, consecutive primes term 3, difference 2430 15 1043085905 · 2^{35000}+ 1819710546 c4 Feb 2014 ECPP, consecutive primes term 3, difference 18198 16 400791048 · 24001# + 110378 p155 Nov 2018 term 5, difference 59874860 · 24001# 17 393142614 · 24001# + 110378 p155 Nov 2018 term 5, difference 54840724 · 24001# 18 221488788 · 24001# + 110377 p155 Jul 2018 term 5, difference 22703701 · 24001# 19 195262026 · 24001# + 110377 p155 Jul 2018 term 5, difference 10601738 · 24001# 20 184591880 · 24001# + 110377 p155 Jul 2018 term 5, difference 17881715 · 24001#

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 69285767989 · 5303# + 12271 p406 Aug 2019 term 8, difference 3026809034 · 5303# 2 3555 · 2^{1542813}- 4953427788675 · 2^{1290000}- 1464437 p363 Apr 2020 term 3, difference 3555 · 2 ^{1542812}- 4953427788675 · 2^{1290000}3 4125 · 2^{1445206}- 2723880039837 · 2^{1290000}- 1435054 p199 Dec 2016 term 3, difference 4125 · 2 ^{1445205}- 2723880039837 · 2^{1290000}4 2415 · 2^{1413628}- 1489088842587 · 2^{1290000}- 1425548 p199 Feb 2017 term 3, difference 2415 · 2 ^{1413627}- 1489088842587 · 2^{1290000}5 2985 · 2^{1404275}- 770527213395 · 2^{1290000}- 1422733 p199 Jan 2017 term 3, difference 2985 · 2 ^{1404274}- 770527213395 · 2^{1290000}6 116040452086 · 2371# + 11014 p308 Jan 2012 term 9, difference 6317280828 · 2371# 7 97336164242 · 2371# + 11014 p308 Apr 2013 term 9, difference 6350457699 · 2371# 8 93537753980 · 2371# + 11014 p308 Apr 2013 term 9, difference 3388165411 · 2371# 9 92836168856 · 2371# + 11014 p308 Apr 2013 term 9, difference 127155673 · 2371# 10 69318339141 · 2371# + 11014 p308 Jul 2011 term 9, difference 1298717501 · 2371# 11 9422094211005 · 2^{1290000}- 1388342 L3494 Apr 2020 term 3, difference 2227792035315 · 2 ^{1290001}12 2154675239 · 16301# + 17036 p155 Apr 2018 term 6, difference 141836149 · 16301# 13 3124777373 · 7001# + 13019 p155 Feb 2012 term 7, difference 481789017 · 7001# 14 116814018316 · 5303# + 12271 p406 Aug 2019 term 7, difference 10892863626 · 5303# 15 116746086504 · 5303# + 12271 p406 Aug 2019 term 7, difference 9726011684 · 5303# 16 116242725347 · 5303# + 12271 p406 Aug 2019 term 7, difference 10388428124 · 5303# 17 115624080541 · 5303# + 12271 p406 Aug 2019 term 7, difference 10462990078 · 5303# 18 1176100079 · 2591# + 11101 p252 Jun 2019 term 8, difference 60355670 · 2591# 19 2968802755 · 2459# + 11057 p155 Apr 2009 term 8, difference 359463429 · 2459# 20 6179783529 · 2411# + 11037 p102 Jun 2003 term 8, difference 176836494 · 2411#

- 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-2021 (all rights reserved)