Arithmetic Progressions of Primes

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.

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

2^{2^{2^{2^{2^{2^{2^{2^100k}}}}}}}

Obviously this is not optimal! It is conjectured that it actually occurs before 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.)

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 k primes all less than N, then

where

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

Record Primes of this Type

AP-3

rank prime digits who when comment

1 6325241166627 · 2^1290000 - 1 388342 L3573 Sep 2021 term 1, difference 1455 · 2^2683953 - 6325241166627 · 2^1290000
2 5606879602425 · 2^1290000 - 1 388342 L3573 Sep 2021 term 1, difference 33 · 2^2939063 - 5606879602425 · 2^1290000
3 2723880039837 · 2^1290000 - 1 388342 L3829 May 2016 term 1, difference 4125 · 2^1445205 - 2723880039837 · 2^1290000 [p199]
4 1938662032575 · 2^1290000 - 1 388341 L927 Apr 2015 term 1, difference 10032831585 · 2^1290001 [p199]
5 1781450041395 · 2^1290000 - 1 388341 L3203 Jan 2015 term 1, difference 69718264533 · 2^1290002 [p199]

AP-4

rank prime digits who when comment

1 263093407 · 2⁹⁹⁹⁰¹ - 1 30082 p364 Sep 2022 term 1, difference 928724769 · 2⁹⁹⁹⁰¹
2 11600483 · 60919# + 1 26382 p364 Apr 2022 term 1, difference 1809778 · 60919#
3 6727153 · 60919# + 1 26382 p364 Apr 2022 term 1, difference 5210718 · 60919#
4 1021747532 · 60013# + 1 25992 p155 Jul 2019 term 1, difference 7399459 · 60013#
5 1010644684 · 60013# + 1 25992 p155 May 2019 term 1, difference 10142823 · 60013#

AP-5

rank prime digits who when comment

1 440012137 · 30941# + 1 13338 p364 May 2022 term 1, difference 18195056 · 30941#
2 173779718 · 24001# + 1 10377 p155 Nov 2018 term 1, difference 54840724 · 24001#
3 161291608 · 24001# + 1 10377 p155 Nov 2018 term 1, difference 59874860 · 24001#
4 152855074 · 24001# + 1 10377 p155 Jul 2018 term 1, difference 10601738 · 24001#
5 130673984 · 24001# + 1 10377 p155 Jul 2018 term 1, difference 22703701 · 24001#

AP-6

rank prime digits who when comment

1 2738129976 · 24499# + 1 10593 p422 Sep 2021 term 1, difference 56497325 · 24499#
2 1445494494 · 16301# + 1 7035 p155 Apr 2018 term 1, difference 141836149 · 16301#
3 44003657 · 7759# - 1 3343 p398 Aug 2017 term 1, difference 12009836 · 7759#
4 2899532512 · 7001# + 1 3019 p155 Feb 2012 term 1, difference 3093612 · 7001#
5 2762211519 · 7001# + 1 3019 p155 Feb 2012 term 1, difference 46793757 · 7001#

AP-7

rank prime digits who when comment

1 2554152639 · 7927# - 1 3407 p364 Jun 2022 term 1, difference 577051223 · 7927#
2 234043271 · 7001# + 1 3018 p155 Feb 2012 term 1, difference 481789017 · 7001#
3 95155954689 · 5303# + 1 2271 p406 Aug 2019 term 1, difference 435232416 · 5303#
4 93211701488 · 5303# + 1 2271 p406 Aug 2019 term 1, difference 817534485 · 5303#
5 93210502047 · 5303# + 1 2271 p406 Aug 2019 term 1, difference 387018369 · 5303#

AP-8

rank prime digits who when comment

1 48098104751 · 5303# + 1 2270 p406 Aug 2019 term 1, difference 3026809034 · 5303#
2 753610389 · 2591# + 1 1100 p252 Jun 2019 term 1, difference 60355670 · 2591#
3 452558752 · 2459# + 1 1056 p155 Apr 2009 term 1, difference 359463429 · 2459#
4 4941928071 · 2411# + 1 1037 p102 Jun 2003 term 1, difference 176836494 · 2411#
5 36475500616 · 2399# + 1 1034 p41 Feb 2025 term 1, difference 319817325 · 2399#

AP-9

rank prime digits who when comment

1 91818923472 · 2371# + 1 1014 p308 Apr 2013 term 1, difference 127155673 · 2371#
2 66432430692 · 2371# + 1 1014 p308 Apr 2013 term 1, difference 3388165411 · 2371#
3 65502205462 · 2371# + 1 1014 p308 Jan 2012 term 1, difference 6317280828 · 2371#
4 58928599133 · 2371# + 1 1014 p308 Aug 2011 term 1, difference 1298717501 · 2371#
5 46532502650 · 2371# + 1 1014 p308 Apr 2013 term 1, difference 6350457699 · 2371#

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 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)² 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)/D_k) (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:

We use the natural log in calculating this weight.
The D_k's begin 1.32032363, 2.85824860, 4.15118086, 10.1317949, 17.2986123, and 53.9719483 for 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 1103 · 2^3558177 - 503 · 2^1092022 - 1 1071122 p423 Dec 2022 term 3, difference 1103 · 2^3558176 - 503 · 2^1092022
2 2109 · 2^3423798 - 3027 · 2⁹⁸⁸⁶⁵⁸ + 1 1030670 CH13 Jan 2023 term 3, difference 2109 · 2^3423797 - 3027 · 2⁹⁸⁸⁶⁵⁸
3 2895 · 2^3422031 - 143157 · 2^2144728 + 1 1030138 p423 Jan 2023 term 3, difference 2895 · 2^3422030 - 143157 · 2^2144728
4 33 · 2^2939064 - 5606879602425 · 2^1290000 - 1 884748 p423 Sep 2021 term 3, difference 33 · 2^2939063 - 5606879602425 · 2^1290000
5 1455 · 2^2683954 - 6325241166627 · 2^1290000 - 1 807954 p423 Sep 2021 term 3, difference 1455 · 2^2683953 - 6325241166627 · 2^1290000
6 69285767989 · 5303# + 1 2271 p406 Aug 2019 term 8, difference 3026809034 · 5303#
7 3020616601 · 24499# + 1 10593 p422 Sep 2021 term 6, difference 56497325 · 24499#
8 116040452086 · 2371# + 1 1014 p308 Jan 2012 term 9, difference 6317280828 · 2371#
9 97336164242 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 6350457699 · 2371#
10 93537753980 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 3388165411 · 2371#
11 92836168856 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 127155673 · 2371#
12 69318339141 · 2371# + 1 1014 p308 Aug 2011 term 9, difference 1298717501 · 2371#
13 6016459977 · 7927# - 1 3407 p364 Jun 2022 term 7, difference 577051223 · 7927#
14 2154675239 · 16301# + 1 7036 p155 Apr 2018 term 6, difference 141836149 · 16301#
15 3124777373 · 7001# + 1 3019 p155 Feb 2012 term 7, difference 481789017 · 7001#
16 512792361 · 30941# + 1 13338 p364 May 2022 term 5, difference 18195056 · 30941#
17 116814018316 · 5303# + 1 2271 p406 Aug 2019 term 7, difference 10892863626 · 5303#
18 116746086504 · 5303# + 1 2271 p406 Aug 2019 term 7, difference 9726011684 · 5303#
19 116242725347 · 5303# + 1 2271 p406 Aug 2019 term 7, difference 10388428124 · 5303#
20 66258958955 · 5303# + 1 2271 p406 Aug 2019 term 7, difference 3026809034 · 5303#

Additional Primes in Arithmetic Progression Records

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
Green, Ben and Tao, 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. Green and T. Tao, "A bound for progressions of length k in the primes," (2004) Available from http://people.maths.ox.ac.uk/greenbj/papers/back-of-an-envelope.pdf.
GT2006a
Green, Benjamin and Tao, 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, 1994. New York, NY, 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. 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, 1994. pp. xvi+398, ISBN 0-19-853479-5; 0-19-852376-9. MR 96g:11001 (Annotation available)

Arithmetic Progressions of Primes

Definitions and Notes

Record Primes of this Type

Weighted Record Primes of this Type

Related Pages

References