Arithmetic Progression of Primes

Why are there infinitely many prime numbers?Top 20 Arithmetic Progression of Primes

by Chris Caldwell

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

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

Record Primes of this Type

rank prime digits who when comment
1 4125 · 21445206 – 2723880039837 · 21290000 – 1 435054 p199 Dec 2016 term 3, difference 4125 · 21445205 – 2723880039837 · 21290000
2 2415 · 21413628 – 1489088842587 · 21290000 – 1 425548 p199 Feb 2017 term 3, difference 2415 · 21413627 – 1489088842587 · 21290000
3 2985 · 21404275 – 770527213395 · 21290000 – 1 422733 p199 Jan 2017 term 3, difference 2985 · 21404274 – 770527213395 · 21290000
4 4704549881115 · 21290000 – 1 388342 L3494 Jun 2016 term 3, difference 496648444065 · 21290002
5 3572178694383 · 21290000 – 1 388342 L3494 Dec 2016 term 3, difference 104644852137 · 21290002
6 492590931 · 280000 – 1631979959 · 225001 – 1 24092 p199 Oct 2010 term 4, difference 164196977 · 280000 – 1631979959 · 225000
7 16481859 · 35023# – 1 15130 p364 Nov 2015 term 4, difference 4190788 · 35023#
8 1008075799 · 34687# + 1 15004 p252 Jul 2010 term 4, difference 2571033 · 34687#
9 263821581 · 245001 – 487069965 · 225002 – 1 13556 p199 Jun 2010 term 4, difference 87940527 · 245001 – 487069965 · 225001
10 4103163 · 245007 – 183009063 · 225003 – 1 13556 p199 Jun 2010 term 4, difference 1367721 · 245007 – 183009063 · 225002
11 1213266377 · 235000 + 4859 10546 c4 Mar 2014 ECPP, consecutive primes term 3, difference 2430
12 1043085905 · 235000 + 18197 10546 c4 Feb 2014 ECPP, consecutive primes term 3, difference 18198
13 109061779 · 235003 + 11855 10545 c4 Feb 2014 ECPP, consecutive primes term 3, difference 5928
14 350049825 · 235000 + 7703 10545 c4 Jan 2014 ECPP, consecutive primes term 3, difference 3852
15 146462479 · 235001 + 8765 10545 c4 Dec 2013 ECPP, consecutive primes term 3, difference 8766
16 248169307 · 17761# – 1 7657 p398 Mar 2017 term 5, difference 36694699 · 17761#
17 241918756 · 17761# – 1 7657 p398 Mar 2017 term 5, difference 27986390 · 17761#
18 1137592666 · 16301# + 1 7035 p155 Jul 2017 term 5, difference 18246788 · 16301#
19 1115724404 · 16301# + 1 7035 p155 Jul 2017 term 5, difference 14607376 · 16301#
20 1113222239 · 16301# + 1 7035 p155 Jul 2017 term 5, difference 37487668 · 16301#

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)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.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 4125 · 21445206 – 2723880039837 · 21290000 – 1 435054 p199 Dec 2016 term 3, difference 4125 · 21445205 – 2723880039837 · 21290000
2 2415 · 21413628 – 1489088842587 · 21290000 – 1 425548 p199 Feb 2017 term 3, difference 2415 · 21413627 – 1489088842587 · 21290000
3 2985 · 21404275 – 770527213395 · 21290000 – 1 422733 p199 Jan 2017 term 3, difference 2985 · 21404274 – 770527213395 · 21290000
4 116040452086 · 2371# + 1 1014 p308 Jan 2012 term 9, difference 6317280828 · 2371#
5 97336164242 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 6350457699 · 2371#
6 93537753980 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 3388165411 · 2371#
7 92836168856 · 2371# + 1 1014 p308 Apr 2013 term 9, difference 127155673 · 2371#
8 69318339141 · 2371# + 1 1014 p308 Jul 2011 term 9, difference 1298717501 · 2371#
9 4704549881115 · 21290000 – 1 388342 L3494 Jun 2016 term 3, difference 496648444065 · 21290002
10 3572178694383 · 21290000 – 1 388342 L3494 Dec 2016 term 3, difference 104644852137 · 21290002
11 3124777373 · 7001# + 1 3019 p155 Feb 2012 term 7, difference 481789017 · 7001#
12 2968802755 · 2459# + 1 1057 p155 Apr 2009 term 8, difference 359463429 · 2459#
13 6179783529 · 2411# + 1 1037 p102 Jun 2003 term 8, difference 176836494 · 2411#
14 115248484057 · 2371# + 1 1014 p308 Apr 2013 term 8, difference 7327002535 · 2371#
15 113236255068 · 2371# + 1 1014 p308 Apr 2013 term 8, difference 6601354956 · 2371#
16 112929231161 · 2371# + 1 1014 p308 Apr 2013 term 8, difference 6982118533 · 2371#
17 248169307 · 17761# – 1 7657 p398 Mar 2017 term 5, difference 36694699 · 17761#
18 241918756 · 17761# – 1 7657 p398 Mar 2017 term 5, difference 27986390 · 17761#
19 492590931 · 280000 – 1631979959 · 225001 – 1 24092 p199 Oct 2010 term 4, difference 164196977 · 280000 – 1631979959 · 225000
20 2996180304 · 7001# + 1 3019 p155 Feb 2012 term 6, difference 46793757 · 7001#

Source: https://primes.utm.edu/top20/page.php?id=14

 

 

Advertisements

Tagged: , , , , , ,

Leave a comment!

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: