In number theory, primes in arithmetic progression are any sequence of at least three prime numbers that are consecutive terms in an arithmetic progression. An example is the sequence of primes (3, 7, 11), which is given by for .
According to the Green–Tao theorem, there exist arbitrarily long arithmetic progressions in the sequence of primes. Sometimes 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 , 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 any sequence of 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
editAny 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 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#. (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 2018[update], the largest prime for which this is confirmed is k = 19, for this AP-19 found by Wojciech Iżykowski in 2013:
- 19 4244193265542951705·17#·n, for n = 0 to 18.[2]
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).
Minimal primes in AP
editWe minimize the last term.[3]
| k | Primes for n = 0 to k−1 |
|---|---|
| 3 | 3 2n |
| 4 | 5 6n |
| 5 | 5 6n |
| 6 | 7 30n |
| 7 | 7 150n |
| 8 | 199 210n |
| 9 | 199 210n |
| 10 | 199 210n |
| 11 | 110437 13860n |
| 12 | 110437 13860n |
| 13 | 4943 60060n |
| 14 | 31385539 420420n |
| 15 | 115453391 4144140n |
| 16 | 53297929 9699690n |
| 17 | 3430751869 87297210n |
| 18 | 4808316343 717777060n |
| 19 | 8297644387 4180566390n |
| 20 | 214861583621 18846497670n |
| 21 | 5749146449311 26004868890n |
| 22 | 19261849254523 784801917900n |
| 23 | 403185216600637 2124513401010n |
Largest known primes in AP
editFor prime q, q# denotes the primorial 2·3·5·7·...·q.
As of September 2019[update], the longest known AP-k is an AP-27. Several examples are known for AP-26. The first to be discovered was found on April 12, 2010, by Benoît Perichon on a PlayStation 3 with software by Jarosław Wróblewski and Geoff Reynolds, ported to the PlayStation 3 by Bryan Little, in a distributed PrimeGrid project:[2]
By the time the first AP-26 was found the search was divided into 131,436,182 segments by PrimeGrid[4] 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 Jarosław Wróblewski 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 Wróblewski reported "I think Raanan went through less than 10,000,000 such segments"[5] (this would have taken about 57 cpu years on Athlon 64).
The earlier record was an AP-24 found by Jarosław Wróblewski alone on January 18, 2007:
- 468395662504823 205619·23#·n, for n = 0 to 23.
For this Wróblewski 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.[6]
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 | (503·21092022−1) (1103·23558176 − 503·21092022)·n | 1071122 | 2022 | Ryan Propper, Serge Batalov |
| 4 | (263093407 928724769·n)·299901−1 | 30083 | 2022 | Serge Batalov |
| 5 | (440012137 18195056·n)·30941# 1 | 13338 | 2022 | Serge Batalov |
| 6 | (1445494494 141836149·n)·16301# 1 | 7036 | 2018 | Ken Davis |
| 7 | (2554152639 577051223·n)·7927# 1 | 3407 | 2022 | Serge Batalov |
| 8 | (48098104751 3026809034·n)·5303# 1 | 2271 | 2019 | Norman Luhn, Paul Underwood, Ken Davis |
| 9 | (65502205462 6317280828·n)·2371# 1 | 1014 | 2012 | Ken Davis, Paul Underwood |
| 10 | (20794561384 1638155407·n)·1050# 1 | 450 | 2019 | Norman Luhn |
| 11 | (16533786790 1114209832·n)·666# 1 | 289 | 2019 | Norman Luhn |
| 12 | (15079159689 502608831·n)·420# 1 | 180 | 2019 | Norman Luhn |
| 13 | (50448064213 4237116495·n)·229# 1 | 103 | 2019 | Norman Luhn |
| 14 | (55507616633 670355577·n)·229# 1 | 103 | 2019 | Norman Luhn |
| 15 | (14512034548 87496195·n)·149# 1 | 68 | 2019 | Norman Luhn |
| 16 | (9700128038 75782144·(n 1))·83# 1 | 43 | 2019 | Norman Luhn |
| 17 | (9700128038 75782144·n)·83# 1 | 43 | 2019 | Norman Luhn |
| 18 | (33277396902 139569962·(n 1))·53# 1 | 31 | 2019 | Norman Luhn |
| 19 | (33277396902 139569962·n)·53# 1 | 31 | 2019 | Norman Luhn |
| 20 | 23 134181089232118748020·19#·n | 29 | 2017 | Wojciech Izykowski |
| 21 | 5547796991585989797641 29#·n | 22 | 2014 | Jarosław Wróblewski |
| 22 | 22231637631603420833 8·41#·(n 1) | 20 | 2014 | Jarosław Wróblewski |
| 23 | 22231637631603420833 8·41#·n | 20 | 2014 | Jarosław Wróblewski |
| 24 | 230885165611851841 297206938·23#·n | 19 | 2023 | Rob Gahan, PrimeGrid |
| 25 | 290969863970949269 322359616·23#·n | 19 | 2024 | Rob Gahan, PrimeGrid |
| 26 | 233313669346314209 331326280·23#·n | 19 | 2024 | Rob Gahan, PrimeGrid |
| 27 | 605185576317848261 155368778·23#·n | 19 | 2023 | Michael Kwok, PrimeGrid |
Consecutive primes in arithmetic progression
editConsecutive 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 known as of 2022[update] has 15004 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.[7] This CPAP-10 has the smallest possible common difference, 7# = 210. The only other known CPAP-10 as of 2018 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.[8]
Minimal consecutive primes in AP
editThe first occurrence of a CPAP-k is only known for k ≤ 6 (sequence A006560 in the OEIS).
| k | Primes for n = 0 to k−1 |
|---|---|
| 3 | 3 2n |
| 4 | 251 6n |
| 5 | 9843019 30n |
| 6 | 121174811 30n |
Largest known consecutive primes in AP
editThe 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 | 17484430616589 · 254201 - 7 6n | 16330 | 2024 | Serge Batalov |
| 4 | 35734184537 · 11677#/3 - 9 6n | 5002 | 2024 | Serge Batalov |
| 5 | 2738129459017 · 4211# 3399421517 30n | 1805 | 2022 | Serge Batalov |
| 6 | 533098369554 · 2357# 3399421517 30n | 1012 | 2021 | Serge Batalov |
| 7 | 145706980166212 · 1069# x253 420 210n | 466 | 2021 | Serge Batalov |
| 8 | 8081110034864 · 619# x253 210 210n | 272 | 2021 | Serge Batalov |
| 9 | 7661619169627 · 379# x153 210n | 167 | 2021 | Serge Batalov |
| 10 | 189382061960492204 · 257# x106 210n | 121 | 2021 | Serge Batalov |
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.
x106 = 115376 22283279672627497420 78637565852209646810 56709682233916942487 50925234318597647097 08315833909447378791
x153 = 9656383640115 03965472274037609810 69585305769447451085 87635040605371157826 98320398681243637298 57205796522034199218 09817841129732061363 55565433981118807417 = x253 % 379#
x253 = 1617599298905 320471304802538356587398499979 836255156671030473751281181199 911312259550734373874520536148 519300924327947507674746679858 816780182478724431966587843672 408773388445788142740274329621 811879827349575247851843514012 399313201211101277175684636727
See also
editNotes
edit- ^ Green, Ben; Tao, Terence (2008), "The primes contain arbitrarily long arithmetic progressions", Annals of Mathematics, 167 (2): 481–547, arXiv:math.NT/0404188, doi:10.4007/annals.2008.167.481, MR 2415379, S2CID 1883951
- ^ a b c d Jens Kruse Andersen and Norman Luhn, Primes in Arithmetic Progression Records. Retrieved 2023-12-11.
- ^ "A133277 - OEIS". oeis.org. Retrieved 2024-11-05.
- ^ John, AP26 Forum. Retrieved 2013-10-20.
- ^ Wróblewski, Jarosław (2008-05-17). "AP25". primenumbers (Mailing list). Archived from the original on May 29, 2012. Retrieved 2008-05-17.
- ^ Wróblewski, Jarosław (2007-01-18). "AP24". primeform (Mailing list). Archived from the original on May 29, 2012. Retrieved 2007-06-17.
- ^ 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.
- ^ Manfred Toplic, The nine and ten primes project. Retrieved on 2007-06-17.
- ^ Jens Kruse Andersen and Norman Luhn, The minimal & the smallest known CPAP-k. Retrieved 2022-12-20.
- ^ Jens Kruse Andersen and Norman Luhn, The Largest Known CPAP's. Retrieved on 2022-12-20.
- ^ Chris K. Caldwell, The Largest Known CPAP's. Retrieved on 2021-01-28.
References
edit- 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.
- Weisstein, Eric W. "Prime Arithmetic Progression". MathWorld.
- Jarosław Wróblewski, How to search for 26 primes in arithmetic progression?
- P. Erdős and P. Turán, On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.