Primes in arithmetic progression
Encyclopedia
In number theory
, the phrase primes in arithmetic progression refers to at least three prime number
s 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.
settled an old conjecture
by proving the Green–Tao theorem: The primes contain arbitrarily long
arithmetic progressions. 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.
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. , the largest prime for which this is confirmed is k = 17, for this AP-17 found by Phil Carmody in 2001:
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).
2·3·5·7·...·q.
, 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:
Before that the record was an AP-25 found by Raanan Chermoni and Jaroslaw Wroblewski on May 17, 2008:
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" (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:
For this Wroblewski reported he used a total of 75 computers: 15 64-bit Athlon
s, 15 dual core 64-bit Pentium D
805, 30 32-bit Athlons 2500, and 15 Duron
s 900.
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.
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 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. 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.
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
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, the phrase primes in arithmetic progression refers to at least three prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
s that are consecutive terms in an arithmetic progression
Arithmetic progression
In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant...
, for example the primes (3, 7, 11) (it does not matter that 5 is also prime).
There are arbitrarily long
Arbitrarily large
In mathematics, the phrase arbitrarily large, arbitrarily small, arbitrarily long is used in statements such as:which is shorthand for:This should not be confused with the phrase "sufficiently large"...
, 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
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 words, there are infinitely many primes which are...
states: If a and b are coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
, then the arithmetic progression a·n + b contains infinitely many primes.
For integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
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
Any given arithmetic progression of primes has a finite length. In 2004, Ben J. Green and Terence TaoTerence Tao
Terence Chi-Shen Tao FRS is an Australian mathematician working primarily on harmonic analysis, partial differential equations, combinatorics, analytic number theory and representation theory...
settled an old conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
by proving the Green–Tao theorem: The primes contain arbitrarily long
Arbitrarily large
In mathematics, the phrase arbitrarily large, arbitrarily small, arbitrarily long is used in statements such as:which is shorthand for:This should not be confused with the phrase "sufficiently large"...
arithmetic progressions. 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
Primorial
In mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than multiplying successive positive integers, only successive prime numbers are multiplied...
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 arithmeticModular arithmeticIn mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus....
says that p will divide every pth 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. , 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
It follows from widely believed conjectures, such as Dickson's conjecture
Dickson's conjecture
In number theory, a branch of mathematics, Dickson's conjecture is the conjecture stated by that for a finite set of linear forms , , ..., with , there are infinitely many positive integers for which they are all prime, unless there is a congruence condition preventing this...
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
Sexy prime
In mathematics, a sexy prime is a prime number that differs from another prime number by six. For example, the numbers 5 and 11 are both sexy primes, because they differ by 6...
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 primorialPrimorial
In mathematics, and more particularly in number theory, primorial is a function from natural numbers to natural numbers similar to the factorial function, but rather than multiplying successive positive integers, only successive prime numbers are multiplied...
2·3·5·7·...·q.
, 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
PrimeGrid
PrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
project:
- 43142746595714191 + 23681770·23#·
Before that the record was an AP-25 found by Raanan Chermoni and Jaroslaw Wroblewski on May 17, 2008:
- 6171054912832631 + 366384·23#·
The AP-25 search was divided into segments taking about 3 minutes on Athlon 64
Athlon 64
The Athlon 64 is an eighth-generation, AMD64-architecture microprocessor produced by AMD, released on September 23, 2003. It is the third processor to bear the name Athlon, and the immediate successor to the Athlon XP...
and Wroblewski reported "I think Raanan went through less than 10,000,000 such segments" (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#·
For this Wroblewski reported he used a total of 75 computers: 15 64-bit Athlon
Athlon
Athlon is the brand name applied to a series of x86-compatible microprocessors designed and manufactured by Advanced Micro Devices . The original Athlon was the first seventh-generation x86 processor and, in a first, retained the initial performance lead it had over Intel's competing processors...
s, 15 dual core 64-bit Pentium D
Pentium D
The Pentium D brand refers to two series of desktop dual-core 64-bit x86-64 microprocessors with the NetBurst microarchitecture manufactured by Intel. Each CPU comprised two dies, each containing a single core, residing next to each other on a multi-chip module package. The brand's first processor,...
805, 30 32-bit Athlons 2500, and 15 Duron
Duron
The AMD Duron was an x86-compatible microprocessor manufactured by AMD. It was released on June 19, 2000 as a low-cost alternative to AMD's own Athlon processor and the Pentium III and Celeron processor lines from rival Intel...
s 900.
The following table shows the largest known AP-k with the year of discovery and the number of decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
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.
| 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 has 7535 digits.
The first known CPAP-10 was found in 1998 by Manfred Toplic in the distributed computing
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
project CP10 which was organized by Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony and Paul Zimmermann. 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.
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.| 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
- Cunningham chainCunningham chainIn mathematics, a Cunningham chain is a certain sequence of prime numbers. Cunningham chains are named after mathematician A. J. C. Cunningham. They are also called chains of nearly doubled primes....
- The Karatsuba phenomenon
- Szemerédi's theoremSzemerédi's theoremIn number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
- PrimeGridPrimeGridPrimeGrid is a distributed computing project for searching for prime numbers of world-record size. It makes use of the Berkeley Open Infrastructure for Network Computing platform...
- Problems involving arithmetic progressionsProblems involving arithmetic progressionsProblems involving arithmetic progressions are of interest in number theory, combinatorics, and computer science, both from theoretical and applied points of view.-Largest progression-free subsets:...