العربية
中国
Français
Deutsch
Ελληνική
हिन्दी
Italiano
日本語
Português
Русский
EspañolPRIMES IN ARITHMETIC PROGRESSION
In number theory, 'primes in arithmetic progression' refers to at least three prime numbers which 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.
Any given arithmetic progression of primes has a finite length. In 2004, Ben Green and 2006 Fields Medalist Terence Tao[1] settled an old conjecture by proving the Green-Tao theorem: The primes contain arbitrarily long arithmetic progressions.[2] It follows immediately that there are infinitely many AP-''k'' for any ''k''. It is an existence theorem and does not say how to compute long progressions.
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 2007, 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).
For prime ''q'', ''q''# denotes the primorial 2·3·5·7·...·''q''.
As of 2007, the longest known AP-''k'' is an AP-24 found by Jaroslaw Wroblewski on January 18 2007:[3]
:468395662504823 + 205619·23#·n, for ''n'' = 0 to 23. 23# = 223092870
Wroblewski reports 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] Later he found a larger AP24 together with Raanan Chermoni.
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''.
'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 known as of 2007 has 7535 digits.
The only known CPAP-10 as of 2007 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.
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]
The table shows the largest known case of ''k'' consecutive primes in arithmetic progression, for ''k'' = 3 to 10.
''x''''d'' 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.
''x''77 = 54538241683887582 668189703590110659057865934764 604873840781923513421103495579
''x''87 = 279872509634587186332039135 414046330728180994209092523040 703520843811319320930380677867
''x''99 = 158794709 618074229409987416174386945728 371523590452459863667791687440 944143462160821328735143564091
''x''155 = 57350 105119354903050490078730183582 516048510151198385480608646918 133804223879167823802443758585 361919599047776527963058419047 009660578164772858363185263809
★ Problems involving arithmetic progressions
★ Cunningham chain
★ Szemerédi's theorem
1. International Mathematical Union. ''IMU Prizes 2006''. Retrieved on 2007-06-17.
2. Ben Green and Terence Tao, ''The primes contain arbitrarily long arithmetic progressions''. Retrieved on 2007-06-17.
3. Jens Kruse Andersen, ''Primes in Arithmetic Progression Records''. Retrieved on 2007-09-04.
4.
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 2007-06-17.
★ Chris Caldwell, ''The Prime Glossary: arithmetic sequence'', ''The Top Twenty: Arithmetic Progressions of Primes'' and ''The Top Twenty: Consecutive Primes in Arithmetic Progression'', all from the Prime Pages.
★
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 |
| Largest known primes in AP |
| Consecutive primes in arithmetic progression |
| Largest known consecutive primes in AP |
| See also |
| Notes |
| References |
Properties
Any given arithmetic progression of primes has a finite length. In 2004, Ben Green and 2006 Fields Medalist Terence Tao[1] settled an old conjecture by proving the Green-Tao theorem: The primes contain arbitrarily long arithmetic progressions.[2] It follows immediately that there are infinitely many AP-''k'' for any ''k''. It is an existence theorem and does not say how to compute long progressions.
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 2007, 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 2007, the longest known AP-''k'' is an AP-24 found by Jaroslaw Wroblewski on January 18 2007:[3]
:468395662504823 + 205619·23#·n, for ''n'' = 0 to 23. 23# = 223092870
Wroblewski reports 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] Later he found a larger AP24 together with Raanan Chermoni.
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''.
| ''k'' | Primes for ''n'' = 0 to ''k''−1 | Digits | Year | Discoverer |
|---|---|---|---|---|
| 3 | (1769267·2340000 − 1) + (1061839·2456789 − 1769267·2340000)·''n'' | 137514 | 2007 | Jens Kruse Andersen, Jiong Sun, Daniel Heuer |
| 4 | (18271126 + 9548007''n'')·235000 + 1 | 10544 | 2007 | Jim Fougeron |
| 5 | ((49077426729 + 681402540''n'') · 205881·4001#/35·(205881·4001# + 1) + 6) · (205881·4001# − 1) + 7 | 5132 | 2007 | Ken Davis |
| 6 | (32649185 + 3884057''n'')·3739# + 1 | 1606 | 2006 | Ken Davis |
| 7 | (143850392 + 114858412''n'')·3011# + 1 | 1290 | 2006 | Ken Davis |
| 8 | (4941928071 + 176836494''n'')·2411# + 1 | 1037 | 2003 | Paul Underwood, Markus Frind |
| 9 | (805227062 + 54790161''n'')·941# + 1 | 401 | 2006 | Mike Oakes |
| 10 | (1079682357 + 109393276''n'')·607# + 1 | 260 | 2006 | Mike Oakes |
| 11 | (631346030 + 151515939''n'')·449# + 1 | 195 | 2006 | Jeff Anderson-Lee |
| 12 | (1366899295 + 54290654''n'')·401# + 1 | 173 | 2006 | Jeff Anderson-Lee |
| 13 | (1374042988 + 22886141''n'')·173# + 1 | 78 | 2006 | Mike Oakes |
| 14 | (1067385825 + 193936257''n'')·151# + 1 | 69 | 2007 | Jens Kruse Andersen |
| 15 | (358766428 + 17143877''n'')·101# + 1 | 48 | 2005 | Jens Kruse Andersen |
| 16 | (1723800454 + 529799''n'')·71# + 1 | 36 | 2006 | Mike Oakes |
| 17 | (1259891250 + 70154768''n'')·53# + 1 | 29 | 2007 | Jens Kruse Andersen |
| 18 | (1051673535 + 32196596''n'')·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 | 1925228725347080393 + 47#·''n'' | 20 | 2007 | Jaroslaw Wroblewski |
| 22 | 950203555027421 + 892·37#·''n'' | 18 | 2007 | Jaroslaw Wroblewski |
| 23 | 1564588127269043 + 1249750·23#·(''n''+1) | 16 | 2007 | Raanan Chermoni, Jaroslaw Wroblewski |
| 24 | 1564588127269043 + 1249750·23#·''n'' | 16 | 2007 | Raanan Chermoni, Jaroslaw Wroblewski |
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 known as of 2007 has 7535 digits.
The only known CPAP-10 as of 2007 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.
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.
| ''k'' | Primes for ''n'' = 0 to ''k''−1 | Digits | Year | Discoverer |
|---|---|---|---|---|
| 3 | 197418203 · 225000 − 6091 + 6090''n'' | 7535 | 2005 | David Broadhurst, François Morain |
| 4 | 18672891658 · 4099# + 1591788949 + 210''n'' | 1763 | 2003 | Jim Fougeron |
| 5 | 142661157626 · 2411# + 71427757 + 30''n'' | 1038 | 2002 | Jim Fougeron |
| 6 | 44770344615 · 859# + 1204600427 + 30''n'' | 370 | 2003 | Jens Kruse Andersen, Jim Fougeron |
| 7 | 194688251849 · 601# + ''x''155 + 210''n'' | 259 | 2003 | Jim Fougeron |
| 8 | 10097274767216 · 250# + ''x''99 + 210''n'' | 112 | 2003 | Jens Kruse Andersen |
| 9 | 73577019188277 · 199#·227·229 + ''x''87 + 210''n'' | 101 | 2005 | Hans Rosenthal, Jens Kruse Andersen |
| 10 | 507618446770482 · 193# + ''x''77 + 210''n'' | 93 | 1998 | Manfred Toplic, CP10 project |
''x''''d'' 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.
''x''77 = 54538241683887582 668189703590110659057865934764 604873840781923513421103495579
''x''87 = 279872509634587186332039135 414046330728180994209092523040 703520843811319320930380677867
''x''99 = 158794709 618074229409987416174386945728 371523590452459863667791687440 944143462160821328735143564091
''x''155 = 57350 105119354903050490078730183582 516048510151198385480608646918 133804223879167823802443758585 361919599047776527963058419047 009660578164772858363185263809
See also
★ Problems involving arithmetic progressions
★ Cunningham chain
★ Szemerédi's theorem
Notes
1. International Mathematical Union. ''IMU Prizes 2006''. Retrieved on 2007-06-17.
2. Ben Green and Terence Tao, ''The primes contain arbitrarily long arithmetic progressions''. Retrieved on 2007-06-17.
3. Jens Kruse Andersen, ''Primes in Arithmetic Progression Records''. Retrieved on 2007-09-04.
4.
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 2007-06-17.
References
★ Chris Caldwell, ''The Prime Glossary: arithmetic sequence'', ''The Top Twenty: Arithmetic Progressions of Primes'' and ''The Top Twenty: Consecutive Primes in Arithmetic Progression'', all from the Prime Pages.
★
This article provided by Wikipedia. To edit the contents of this article, click here for original source.
psst.. try this: add to faves
