Primes in arithmetic progression

Primes in arithmetic progression

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 primes (3, 7, 11) (it does not matter that 5 is also prime).

There are arbitrarily long, but not infinitely long, sequences of primes in arithmetic progression. Sometimes (not in this article) the term may also be used about primes which belong to a given arithmetic progression but are not necessarily consecutive terms. Dirichlet's theorem on arithmetic progressions states: If a and b are coprime, then the arithmetic progression a·n + b contains infinitely many primes.

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.

Contents

Properties

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. If the AP is prime for k consecutive values, then a must therefore be divisible by all primes p ≤ k.

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

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

As of April 2010, the longest known AP-k is an AP-26, found on April 12, 2010 by Benoãt Perichon with software by Jaroslaw Wroblewski and Geoff Reynolds in a distributed PrimeGrid project:[2]

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

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"[3] (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.[4]

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 April 2010[2]
k Primes for n = 0 to k−1 Digits Year Discoverer
3 (11347·2508209 − 1) + (103939·2514229 − 11347·2508209)·n 154804 2010 David Broadhurst, Thomas Ritschel, Lei Zhou
4 (100997770 + 3624707n)·27751# + 1 11961 2008 Ken Davis
5 (82751511 + 20333209n)·16229# + 1 7009 2009 Ken Davis
6 (19303382 + 41724940n)·5011# + 1 2153 2009 Ken Davis
7 (1246733996 + 35777939n)·3109# + 1 1328 2009 Mike Oakes
8 (452558752 + 359463429n)·2459# + 1 1057 2009 Ken Davis
9 (190556231 + 138880294n)·997# + 1 425 2009 Ken Davis
10 (565429078 + 147743546n)·641# + 1 274 2009 Mike Oakes
11 (197477410 + 146636n)·457# + 1 196 2009 Jeff Anderson-Lee
12 (1366899295 + 54290654n)·401# + 1 173 2006 Jeff Anderson-Lee
13 (1374042988 + 22886141n)·173# + 1 78 2006 Mike Oakes
14 (145978014 + 253131151n)·157# + 1 71 2009 Mike Oakes
15 (237375311 + 118560155n)·109# + 1 54 2009 Mike Oakes
16 (281121075 + 18107251n)·83# + 1 42 2009 Mike Oakes
17 (263013824 + 18107251n)·83# + 1 42 2009 Mike Oakes
18 (1051673535 + 32196596n)·53# + 1 29 2007 Jens Kruse Andersen
19 62749659973280668140514103 + 107·61#·n 27 2007 Jaroslaw Wroblewski
20 178284683588844176017 + 53#·n 21 2007 Jaroslaw Wroblewski
21 28112131522731197609 + 19#·n 20 2008 Jaroslaw Wroblewski
22 1351906725737537399 + 43#·n 19 2008 Jaroslaw Wroblewski
23 117075039027693563 + 6548·23#·n 19 2008 Raanan Chermoni, Jaroslaw Wroblewski
24 28806475189976381 + 36028618·23#·n 18 2010 John Petterson, PrimeGrid
25 18626565939034793 + 30821486·23#·n 18 2010 Chris Wingate, PrimeGrid
26 43142746595714191 + 23681770·23#·n 18 2010 Benoãt Perichon, PrimeGrid

Consecutive primes in arithmetic progression

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, they must be consecutive among all primes, not just among the terms of the progression. 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.[5] 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.[6]

Largest known consecutive primes in AP

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 May 2009[7]
k Primes for n = 0 to k−1 Digits Year Discoverer
3 197418203 · 225000 − 6091 + 6090n 7535 2005 David Broadhurst, François Morain
4 25900 + 469721931951 + 2880n 1777 2007 Ken Davis
5 142661157626 · 2411# + 71427757 + 30n 1038 2002 Jim Fougeron
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

Notes

  1. ^ Green, Ben; Tao, Terence (2008), "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics 167: 481–547, arXiv:math.NT/0404188 .
  2. ^ a b c Jens Kruse Andersen, Primes in Arithmetic Progression Records. Retrieved on 2010-04-13.
  3. ^ Wroblewski, Jaroslaw (2008-05-17). "AP25". primenumbers mailing list. http://tech.groups.yahoo.com/group/primenumbers/message/19359. Retrieved 2008-05-17. 
  4. ^ Wroblewski, Jaroslaw (2007-01-18). "AP24". primeform mailing list. http://tech.groups.yahoo.com/group/primeform/message/8248. Retrieved 2007-06-17. 
  5. ^ 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.
  6. ^ Manfred Toplic, The nine and ten primes project. Retrieved on 2007-06-17.
  7. ^ Jens Kruse Andersen, The Largest Known CPAP's. Retrieved on 2009-05-07.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Arithmetic progression — In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. For instance, the sequence 3, 5, 7, 9, 11, 13... is an arithmetic… …   Wikipedia

  • Problems involving arithmetic progressions — are of interest in number theory,cite journal|author=Samuel S. Wagstaff, Jr.|authorlink= url= title=Some Questions About Arithmetic Progressions journal=The American Mathematical Monthly volume=86|issue=7|pages=579–582|year=1979… …   Wikipedia

  • Theoreme de la progression arithmetique — Théorème de la progression arithmétique Johann Peter Gustav Lejeune Dirichlet, auteur du théorème En mathématiques, et plus particulièrement en théorie des nombres, le théorème de la progression arithmétique, dû au mathématicien allemand Gustav… …   Wikipédia en Français

  • Théorème de la progression arithmétique — Pour les articles homonymes, voir Théorème de Dirichlet. Johann Peter Gustav Lejeune Dirichlet, auteur du théorème En mathématiques, et plus particulièrement en théorie des nombres, le …   Wikipédia en Français

  • Dirichlet's theorem on arithmetic progressions — In number theory, Dirichlet s theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n ≥ 0. In other… …   Wikipedia

  • Erdős conjecture on arithmetic progressions — Erdős conjecture on arithmetic progressions, often incorrectly referred to as the Erdős–Turán conjecture, is a conjecture in additive combinatorics due to Paul Erdős. It states that if the sum of the reciprocals of the members of a set A of… …   Wikipedia

  • Green–Tao theorem — In mathematics, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, [Ben Green and Terence Tao, [http://arxiv.org/abs/math.NT/0404188 The primes contain arbitrarily long arithmetic progressions] ,8 Apr 2004.] states that the… …   Wikipedia

  • Теорема Грина — В теории чисел теорема Грина Тао, доказанная Беном Д. Грином и Теренсом Тао в 2004 году[1], утверждает, что последовательность простых чисел содержит арифметические прогрессии произвольной длины. Другими словами, существуют арифметические… …   Википедия

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Balanced prime — A balanced prime is a prime number that is equal to the arithmetic mean of the nearest primes above and below. Or to put it algebraically, given a prime number p n, where n is its index in the ordered set of prime numbers,:p n = p {n 1} + p {n +… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”