Primes in arithmetic progression

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, the phrase primes in arithmetic progression refers to at least three prime numbers that are consecutive terms in an arithmetic progression. For example the sequence of primes (3, 7, 11), which is given by a_n = 3 + 4*n for 0 \le n \le 2.

According to the Green-Tao theorem, there exist arbitrarily long sequences of primes in arithmetic progression. Sometimes (not in this article) the phrase may also be used about primes which belong to an arithmetic progression which also contains composite numbers. For example, it can be used about primes in an arithmetic progression of the form a*n + b, where a and b are coprime, which according to Dirichlet's theorem on arithmetic progressions contains infinitely many primes, along with infinitely many composites.

For integer k ≥ 3, an AP-k (also called PAP-k) is k primes in arithmetic progression. An AP-k can be written as k primes of the form a·n + b, for fixed integers a (called the common difference) and b, and k consecutive integer values of n. An AP-k is usually expressed with n = 0 to k − 1. This can always be achieved by defining b to be the first prime in the arithmetic progression.

Properties[edit]

Any given arithmetic progression of primes has a finite length. In 2004, Ben J. Green and Terence Tao settled an old conjecture by proving the Green–Tao theorem: The primes contain arbitrarily long arithmetic progressions.[1] It follows immediately that there are infinitely many AP-k for any k.

If an AP-k does not begin with the prime k, then the common difference is a multiple of the primorial k# = 2·3·5·...·j, where j is the largest prime ≤ k.

Proof: Let the AP-k be a·n + b for k consecutive values of n. If a prime p does not divide a, then modular arithmetic says that p will divide every p'th term of the arithmetic progression. (From H.J. Weber, Cor.10 in ``Exceptional Prime Number Twins, Triplets and Multiplets," arXiv:1102.3075[math.NT]. See also Theor.2.3 in ``Regularities of Twin, Triplet and Multiplet Prime Numbers," arXiv:1103.0447[math.NT],Global J.P.A.Math 8(2012), in press.) If the AP is prime for k consecutive values, then a must therefore be divisible by all primes pk.

This also shows that an AP with common difference a cannot contain more consecutive prime terms than the value of the smallest prime that does not divide a.

If k is prime then an AP-k can begin with k and have a common difference which is only a multiple of (k−1)# instead of k#. (From H. J. Weber, ``Less Regular Exceptional and Repeating Prime Number Multiplets," arXiv:1105.4092[math.NT], Sect.3.) For example the AP-3 with primes {3, 5, 7} and common difference 2# = 2, or the AP-5 with primes {5, 11, 17, 23, 29} and common difference 4# = 6. It is conjectured that such examples exist for all primes k. As of 2009, the largest prime for which this is confirmed is k = 17, for this AP-17 found by Phil Carmody in 2001:

17 + 11387819007325752·13#·n, for n = 0 to 16.

It follows from widely believed conjectures, such as Dickson's conjecture and some variants of the prime k-tuple conjecture, that if p > 2 is the smallest prime not dividing a, then there are infinitely many AP-(p−1) with common difference a. For example, 5 is the smallest prime not dividing 6, so there is expected to be infinitely many AP-4 with common difference 6, which is called a sexy prime quadruplet. When a = 2, p = 3, it is the twin prime conjecture, with an "AP-2" of 2 primes (b, b + 2).

Largest known primes in AP[edit]

For prime q, q# denotes the primorial 2·3·5·7·...·q.

As of June 2014, the longest and largest known AP-k is an AP-26, found on February 23, 2014 by Bryan Little[2] with a Nvidia GTX 580 GPU using modified AP26 software. It is the third known AP-26:

136926916457315893 + 44121555·23#·n, for n = 0 to 25. (23# = 223092870)

The second known AP-26 was found by James Fry on March 16, 2012:[2]

3486107472997423 + 1666981·23#·n, for n = 0 to 25. (23# = 223092870)

The first known AP-26 was found on April 12, 2010 by Benoãt Perichon on a PlayStation 3 with software by Jaroslaw Wroblewski and Geoff Reynolds, ported to the PlayStation 3 by Bryan Little, in a distributed PrimeGrid project:[2]

43142746595714191 + 23681770·23#·n, for n = 0 to 25. (23# = 223092870) (sequence A204189 in OEIS)

By the time the first AP-26 was found the search was divided into 131,436,182 segments by PrimeGrid[3] and processed by 32/64bit CPUs, Nvidia CUDA GPUs, and Cell microprocessors around the world.

Before that, the record was an AP-25 found by Raanan Chermoni and Jaroslaw Wroblewski on May 17, 2008:[2]

6171054912832631 + 366384·23#·n, for n = 0 to 24. (23# = 223092870)

The AP-25 search was divided into segments taking about 3 minutes on Athlon 64 and Wroblewski reported "I think Raanan went through less than 10,000,000 such segments"[4] (this would have taken about 57 cpu years on Athlon 64).

The earlier record was an AP-24 found by Jaroslaw Wroblewski alone on January 18, 2007:

468395662504823 + 205619·23#·n, for n = 0 to 23.

For this Wroblewski reported he used a total of 75 computers: 15 64-bit Athlons, 15 dual core 64-bit Pentium D 805, 30 32-bit Athlons 2500, and 15 Durons 900.[5]

The following table shows the largest known AP-k with the year of discovery and the number of decimal digits in the ending prime. Note that the largest known AP-k may be the end of an AP-(k+1). Some record setters choose to first compute a large set of primes of form c·p#+1 with fixed p, and then search for AP's among the values of c that produced a prime. This is reflected in the expression for some records. The expression can easily be rewritten as a·n + b.

Largest known AP-k as of June 2014[2]
k Primes for n = 0 to k−1 (except where noted) Digits Year Discoverer
3 (8175435610410 + 32289415560495·n)·2666666-1 200701 2011 David Broadhurst, Tony Gott, Ulrich Fries
4 (1631979959·225000-1) + (164196977·280000-1631979959·225000n 24092 2010 David Broadhurst
5 (82751511 + 20333209·n)·16229# + 1 7009 2009 Ken Davis
6 (234043271 + 481789017·n)·7001#+1 (n = 1 to 6) 3019 2012 Ken Davis
7 (234043271 + 481789017·n)·7001#+1 3019 2012 Ken Davis
8 (452558752 + 359463429·n)·2459# + 1 1057 2009 Ken Davis
9 (65502205462 + 6317280828·n)·2371#+1 1014 2012 Ken Davis, Paul Underwood
10 (3186700865 + 61959394·n)·653#+1 (n = 1 to 10) 283 2010 Ken Davis
11 (3186700865 + 61959394·n)·653#+1 283 2010 Ken Davis
12 (1366899295 + 54290654·n)·401# + 1 173 2006 Jeff Anderson-Lee
13 (1296982250 + 14976848·n)·191#+1 85 2010 Mike Oakes
14 (145978014 + 253131151·n)·157# + 1 71 2009 Mike Oakes
15 (237375311 + 118560155·n)·109# + 1 54 2009 Mike Oakes
16 (263013824 + 18107251·n)·83# + 1 (n = 1 to 16) 42 2009 Mike Oakes
17 (263013824 + 18107251·n)·83# + 1 42 2009 Mike Oakes
18 1029+999 + 1806448944300798320195·19#·(n-2) (n = 1 to 18) 30 2014 Jaroslaw Wroblewski
19 1029+999 + 1806448944300798320195·19#·(n-2) 30 2014 Jaroslaw Wroblewski
20 3533531731191494525351461 + 61#·n 25 2014 Jaroslaw Wroblewski
21 5547796991585989797641 + 29#·n 22 2014 Jaroslaw Wroblewski
22 22231637631603420833 + 8·41#·n (n = 1 to 22) 20 2014 Jaroslaw Wroblewski
23 22231637631603420833 + 8·41#·n 20 2014 Jaroslaw Wroblewski
24 154915016996669203 + 46919728·23#·n 18 2014 Bryan Little
25 136926916457315893 + 44121555·23#·n (n = 1 to 25) 18 2014 Bryan Little
26 136926916457315893 + 44121555·23#·n 18 2014 Bryan Little

Consecutive primes in arithmetic progression[edit]

Consecutive primes in arithmetic progression refers to at least three consecutive primes which are consecutive terms in an arithmetic progression. Note that unlike an AP-k, all the other numbers between the terms of the progression must be composite. For example, the AP-3 {3, 7, 11} does not qualify, because 5 is also a prime.

For an integer k ≥ 3, a CPAP-k is k consecutive primes in arithmetic progression. It is conjectured there are arbitrarily long CPAP's. This would imply infinitely many CPAP-k for all k. The middle prime in a CPAP-3 is called a balanced prime. The largest proven as of 2009 has 7535 digits.

The first known CPAP-10 was found in 1998 by Manfred Toplic in the distributed computing project CP10 which was organized by Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony and Paul Zimmermann.[6] This CPAP-10 has the smallest possible common difference, 7# = 210. The only other known CPAP-10 as of 2009 was found by the same people in 2008.

If a CPAP-11 exists then it must have a common difference which is a multiple of 11# = 2310. The difference between the first and last of the 11 primes would therefore be a multiple of 23100. The requirement for at least 23090 composite numbers between the 11 primes makes it appear extremely hard to find a CPAP-11. Dubner and Zimmermann estimate it would be at least 1012 times harder than a CPAP-10.[7]

Largest known consecutive primes in AP[edit]

The table shows the largest known case of k consecutive primes in arithmetic progression, for k = 3 to 10.

Largest known CPAP-k as of June 2014[8]
k Primes for n = 0 to k−1 Digits Year Discoverer
3 1213266377 · 235000 − 1 + 2430n 10546 2014 David Broadhurst
4 62037039993 · 7001# + 7811555723 + 30n 3021 2013 David Broadhurst
5 406463527990 · 2801# + 1633050283 + 30n 1209 2013 David Broadhurst
6 44770344615 · 859# + 1204600427 + 30n 370 2003 Jens Kruse Andersen, Jim Fougeron
7 4785544287883 · 613# + x253 + 210n 266 2007 Jens Kruse Andersen
8 10097274767216 · 250# + x99 + 210n 112 2003 Jens Kruse Andersen
9 73577019188277 · 199#·227·229 + x87 + 210n 101 2005 Hans Rosenthal, Jens Kruse Andersen
10 1180477472752474 · 193# + x77 + 210n 93 2008 Manfred Toplic, CP10 project

xd is a d-digit number used in one of the above records to ensure a small factor in unusually many of the required composites between the primes.
x77 = 54538241683887582 668189703590110659057865934764 604873840781923513421103495579
x87 = 279872509634587186332039135 414046330728180994209092523040 703520843811319320930380677867
x99 = 158794709 618074229409987416174386945728 371523590452459863667791687440 944143462160821328735143564091
x253 = 1617599298905 320471304802538356587398499979 836255156671030473751281181199 911312259550734373874520536148 519300924327947507674746679858 816780182478724431966587843672 408773388445788142740274329621 811879827349575247851843514012 399313201211101277175684636727

See also[edit]

Notes[edit]

  1. ^ Green, Ben; Tao, Terence (2008), The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics 167: 481–547, arXiv:math.NT/0404188, doi:10.4007/annals.2008.167.481 .
  2. ^ a b c d e Jens Kruse Andersen, Primes in Arithmetic Progression Records. Retrieved 2014-06-13.
  3. ^ John, AP26 Forum. Retrieved 2013-10-20.
  4. ^ Wroblewski, Jaroslaw (2008-05-17). "AP25". primenumbers mailing list. http://tech.groups.yahoo.com/group/primenumbers/message/19359. Retrieved 2008-05-17.
  5. ^ Wroblewski, Jaroslaw (2007-01-18). "AP24". primeform mailing list. http://tech.groups.yahoo.com/group/primeform/message/8248. Retrieved 2007-06-17.
  6. ^ H. Dubner, T. Forbes, N. Lygeros, M. Mizony, H. Nelson, P. Zimmermann, Ten consecutive primes in arithmetic progression, Mathematics of Computation 71 (2002), 1323-1328.
  7. ^ Manfred Toplic, The nine and ten primes project. Retrieved on 2007-06-17.
  8. ^ Jens Kruse Andersen, The Largest Known CPAP's. Retrieved on 2014-06-13.

References[edit]