primes in arithmetic progression

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.{{citation|doi=10.4007/annals.2008.167.481|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=Terence Tao|arxiv=math.NT/0404188 |title=The primes contain arbitrarily long arithmetic progressions|journal=Annals of Mathematics|volume=167|year=2008|issue=2|pages=481–547|mr=2415379|s2cid=1883951}} 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\backslash \#=2\backslash cdot\; 3\backslash cdot\; 5\backslash cdots\; j$, where $j$ is the largest prime $\backslash leq\; k$.

:Proof: Let the AP-$k$ be $an+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\backslash leq\; 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)\backslash \#$ instead of $k\backslash \#$. (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 $\backslash \{3,5,7\backslash \}$ and common difference $2\backslash \#=2$, or the AP-5 with primes $\backslash \{5,11,17,23,29\backslash \}$ and common difference $4\backslash \#-6$. It is conjectured that such examples exist for all primes $k$. {{As of|2018}}, the largest prime for which this is confirmed is $k=19$, for this AP-19 found by Wojciech Iżykowski in 2013:

:$19\; +\; 4244193265542951705\backslash cdot\; 17\backslash \#\backslash cdot\; n$, for $n=0$ to $18$.

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)$.

We minimize the last term.{{Cite web |title=A133277 - OEIS |url=https://oeis.org/A133277 |access-date=2024-11-05 |website=oeis.org}}

For a prime $q$, $q\backslash \#$ denotes the primorial $2\backslash cdot\; 3\backslash cdot\; 5\backslash cdot\; 7\backslash cdots\; q$.

{{As of|2019|9}}, 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:

:43142746595714191 + 23681770·23#·n, for n = 0 to 25. (23# = 223092870) {{OEIS|id=A204189}}

By the time the first AP-26 was found the search was divided into 131,436,182 segments by PrimeGridJohn, [http://www.primegrid.com/forum_thread.php?id=1158&nowrap=true#22787 AP26 Forum]. Retrieved 2013-10-20. 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:

:$6171054912832631\; +\; 366384\backslash cdot\; 23\backslash \#\backslash cdot\; n$, for $n=0$ to $24$. ($23\backslash \#\; =\; 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"{{cite mailing list | url = http://tech.groups.yahoo.com/group/primenumbers/message/19359 | archive-url = https://archive.today/20120529015657/http://tech.groups.yahoo.com/group/primenumbers/message/19359 | url-status = dead | archive-date = May 29, 2012 | title = AP25 | mailing-list = primenumbers | date = 2008-05-17 | access-date=2008-05-17 | last = Wróblewski |first = Jarosław }} (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\backslash cdot\; 23\backslash \#\backslash cdot\; 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.{{cite mailing list | url = http://tech.groups.yahoo.com/group/primeform/message/8248 | archive-url = https://archive.today/20120529015657/http://tech.groups.yahoo.com/group/primeform/message/8248 | url-status = dead | archive-date = May 29, 2012 | title = AP24 | mailing-list = primeform | date = 2007-01-18 | access-date=2007-06-17 | last = Wróblewski |first = Jarosław }}

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\backslash cdot\; p\backslash \#+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 $an+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$, 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\backslash geq\; 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|lc=on}} 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.H. Dubner, T. Forbes, N. Lygeros, M. Mizony, H. Nelson, P. Zimmermann, [https://www.ams.org/mcom/2002-71-239/S0025-5718-01-01374-6/home.html Ten consecutive primes in arithmetic progression], Mathematics of Computation 71 (2002), 1323–1328. 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 10¹² times harder than a CPAP-10.Manfred Toplic, [http://www.manfred-toplic.com/cp09.html The nine and ten primes project]. Retrieved on 2007-06-17.

The first occurrence of a CPAP-$k$ is only known for $k\backslash leq\; 6$ {{OEIS|A006560}}.

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.

• Cunningham chain
• Szemerédi's theorem
• PrimeGrid
• Prime number theorem for arithmetic progressions
• Problems involving arithmetic progressions

{{reflist}}

• Chris Caldwell, [http://primes.utm.edu/glossary/page.php?sort=ArithmeticSequence The Prime Glossary: arithmetic sequence], [http://primes.utm.edu/top20/page.php?id=14 The Top Twenty: Arithmetic Progressions of Primes] and [http://primes.utm.edu/top20/page.php?id=13 The Top Twenty: Consecutive Primes in Arithmetic Progression], all from the Prime Pages.
• {{MathWorld|title=Prime Arithmetic Progression|urlname=PrimeArithmeticProgression}}
• Jarosław Wróblewski, [http://www.math.uni.wroc.pl/~jwr/AP26/AP26v3.pdf 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.

{{Prime number classes}}

Category:Prime numbers