Primes in arithmetic progression: Difference between revisions

Revision as of 18:56, 5 November 2022

Latest revision as of 02:34, 27 August 2025

(36 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Set of prime numbers linked by a linear relationship}}

In [[number theory]], '''primes in arithmetic progression''' are any [[sequence]] of at least three [[prime number]]s that are consecutive terms in an [[arithmetic progression]]. An example is the sequence of primes (3, 7, 11), which is given by <math>a_n = 3 + 4n</math> for <math>0 \le n \le 2</math>.

According to the [[Green–Tao theorem]], there exist [[arbitrarily large|arbitrarily long]] sequencesarithmetic of primesprogressions in arithmeticthe progressionsequence 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 <math>an + b</math>, where ''a'' and ''b'' are [[Coprime integers|coprime]] which according to [[Dirichlet's theorem on arithmetic progressions]] contains infinitely many primes, along with infinitely many composites.

For any [[integer]] ''<math>k'' ≥\geq 3</math>, an '''AP-''k''''' (also called '''PAP-''k''''') is any sequence of ''<math>k''</math> primes in arithmetic progression. An AP-''<math>k''</math> can be written as ''<math>k''</math> primes of the form ''a''·''n'' <math>an+ ''b''</math>, for fixed integers ''<math>a''</math> (called the common difference) and ''<math>b''</math>, and ''<math>k''</math> consecutive integer values of ''<math>n''</math>. An AP-''k'' is usually expressed with ''<math>n'' = 0</math> to ''<math>k''&nbsp;&minus;&nbsp;-1</math>. This can always be achieved by defining ''<math>b''</math> 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 Tao]] settled an old [[conjecture]] by proving the [[Green–Tao theorem]]: Thethe primes contain [[arbitrarily large|arbitrarily long]] arithmetic progressions.<ref>{{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}}</ref> It follows immediately that there are infinitely many AP-''<math>k''</math> for any ''<math>k''</math>.

If an AP-''<math>k''</math> does not begin with the prime ''<math>k''</math>, then the common difference is a multiple of the [[primorial]] ''<math>k''\# = 2·\cdot 3·\cdot 5·...·''\cdots j''</math>, where ''<math>j''</math> is the largest prime ≤<math>\leq ''k''</math>.

:''Proof:'': Let the AP-''<math>k''</math> be ''a''·''n'' <math>an+ ''b''</math> for ''<math>k''</math> consecutive values of ''<math>n''</math>. If a prime ''<math>p''</math> does not divide ''<math>a''</math>, then [[modular arithmetic]] says that ''<math>p''</math> will divide every ''<math>p'''</math>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 ''<math>k''</math> consecutive values, then ''<math>a''</math> must therefore be divisible by all primes ''<math>p''\leq &le; ''k''</math>.

This also shows that an AP with common difference ''<math>a''</math> cannot contain more consecutive prime terms than the value of the smallest prime that does not divide ''<math>a''</math>.

If ''<math>k''</math> is prime then an AP-''<math>k''</math> can begin with ''<math>k''</math> and have a common difference which is only a multiple of <math>(''k''&minus;-1)\#</math> instead of ''<math>k''\#</math>. (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 <math>\{3, 5, 7\}</math> and common difference <math>2\# = 2</math>, or the AP-5 with primes <math>\{5, 11, 17, 23, 29\}</math> and common difference <math>4\# = 6</math>. It is conjectured that such examples exist for all primes ''<math>k''</math>. {{As of|2018}}, the largest prime for which this is confirmed is ''<math>k'' = 19</math>, for this AP-19 found by Wojciech Iżykowski in 2013:

:<math>19 + 4244193265542951705·\cdot 17\#·\cdot n</math>, for ''<math>n'' = 0</math> to <math>18</math>.<ref name="APrecords" />

It follows from widely believed conjectures, such as [[Dickson's conjecture]] and some variants of the [[First Hardy–Littlewood conjecture|prime k-tuple conjecture]], that if ''<math>p'' > 2</math> is the smallest prime not dividing ''<math>a''</math>, then there are infinitely many AP-(''<math>p''&minus;-1</math>) with common difference ''<math>a''</math>. 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 ''<math>a'' = 2</math>, ''<math>p'' = 3</math>, it is the [[twin prime conjecture]], with an "AP-2" of 2 primes <math>(''b'', ''b'' + 2)</math>.

== Minimal primes in AP ==

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

{| class="wikitable"

Line 82 ⟶ 83:

! 21

| 5749146449311 + 26004868890''n''

|-

! 22

| 19261849254523 + 784801917900''n''

|-

! 23

| 403185216600637 + 2124513401010''n''

|}

== Largest known primes in AP ==

For a prime ''<math>q''</math>, ''<math>q''\#</math> denotes the [[primorial]] <math>2·\cdot 3·\cdot 5·\cdot 7·...·''\cdots q''</math>.

{{As of|2019|9}}, the longest known AP-''<math>k''</math> 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:<ref name="APrecords" />

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

Line 93 ⟶ 100:

Before that, the record was an AP-25 found by Raanan Chermoni and Jarosław Wróblewski on May 17, 2008:<ref name="APrecords" />

:<math>6171054912832631 + 366384·\cdot 23\#·''\cdot n''</math>, for ''<math>n'' = 0</math> to <math>24</math>. (<math>23\# = 223092870</math>)

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"<ref>{{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 }}</ref> (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:

:<math>468395662504823 + 205619·\cdot 23\#·''\cdot n''</math>, for ''<math>n'' = 0</math> to <math>23</math>.

For this Wróblewski 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.<ref>{{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 }}</ref>

The following table shows the largest known AP-''<math>k''</math> with the year of discovery and the number of [[decimal]] digits in the ending prime. Note that the largest known AP-''<math>k''</math> may be the end of an AP-(''<math>k''+1</math>). Some record setters choose to first compute a large set of primes of form ''<math>c''·''\cdot p''\#+1</math> with fixed ''<math>p''</math>, and then search for AP's among the values of ''<math>c''</math> that produced a prime. This is reflected in the expression for some records. The expression can easily be rewritten as ''a''·''n'' <math>an+ ''b''</math>.

{| class="wikitable"

|+ Largest known AP-''k'' {{as of|20222025|095|lc=ono1}}<ref name="APrecords">Jens Kruse Andersen and Norman Luhn, [https://www.pzktupel.de/JensKruseAndersen/aprecords.htm''Primes in Arithmetic Progression Records'']. Retrieved 20202023-0812-3111.</ref>

|-

! ''k'' !! Primes for ''n'' = 0 to ''k''&minus;1 !! Digits !! Year !! Discoverer

|-

! 3

| (5606879602425503·2^{12900001092022}−1) + (331103·2^{29390633558176} − 5606879602425503·2^{12900001092022})·''n'' ||align="right" | 8847481071122 || 20212022 || Ryan Propper, Serge Batalov

|-

! 4

| (263093407 2874926 + 9287247691475275·''n'')·2⁹⁹⁹⁰¹74719#−1 ||align="right" | 3008332315 || 20222025 || Serge Batalov

|-

! 5

| (440012137 108992777  + 1819505620571563·''n'')·3094132003#+1 ||align="right" | 1333813773 || 20222025 || Serge Batalov

|-

! 6

Line 127 ⟶ 134:

|-

! 9

| (65502205462 13088317669 + 63172808286383832302·''n'')·23712399# + 1 ||align="right" | 10141034 || 20122025 || Ken Davis, PaulNorman UnderwoodLuhn

|-

! 10

Line 166 ⟶ 173:

|-

! 22

| 22231637631603420833 + 8·41#·(''n'' + 1) ||align="right" | 20 || 2014 || Jarosław Wróblewski

|-

! 23

Line 172 ⟶ 179:

|-

! 24

| 180688902040348237230885165611851841 + 262290685297206938·23#·(''n''+1) ||align="right" | 19 || 20222023 || Rob Gahan, PrimeGrid

|-

! 25

| 180688902040348237290969863970949269 + 262290685322359616·23#·''n'' ||align="right" | 19 || 20222024 || Rob Gahan, PrimeGrid

|-

! 26

| 36621451562941339233313669346314209 + 267460371331326280·23#·''n'' ||align="right" | 19 || 20222024 || Rob Gahan, PrimeGrid

|-

! 27

| 224584605939537911605185576317848261 + 81292139155368778·23#·''n'' ||align="right" | 1819 || 20192023 || RobMichael GahanKwok, 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-''<math>k''</math>, 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 ''<math>k'' ≥\geq 3</math>, a '''CPAP-''k''''' is ''<math>k''</math> consecutive primes in arithmetic progression. It is conjectured there are arbitrarily long CPAP's. This would imply infinitely many CPAP-''<math>k''</math> for all ''<math>k''</math>. 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.<ref>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.</ref> 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.

Line 195 ⟶ 202:

== Minimal consecutive primes in AP ==

The first occurrence of a CPAP-''<math>k''</math> is only known for ''<math>k'' ≤\leq 6</math> {{OEIS|A006560}}.

{| class="wikitable"

|+ Minimal CPAP-''k''<ref name="minitable">Jens Kruse Andersen" and Norman Luhn, [https://www.pzktupel.de/JensKruseAndersen/mini.html''The minimal & the smallest known CPAP-k'']. Retrieved 2022-12-20.</ref>

|-

! ''k'' !! Primes for ''n'' = 0 to ''k''&minus;1

Line 216 ⟶ 223:

== Largest known consecutive primes in AP ==

The table shows the largest known case of ''<math>k''</math> consecutive primes in arithmetic progression, for ''<math>k'' = 3</math> to <math>10</math>.

{| class="wikitable"

|+ Largest known CPAP-''k'' {{as of|20222024|0406|lc=on}},<ref name="Kruse AndersenCPAPrecords">Jens Kruse Andersen and Norman Luhn, [httphttps://primerecordswww.pzktupel.dkde/cpapJensKruseAndersen/CPAP.htm ''The Largest Known CPAP's'']. Retrieved on 20202022-0112-2820.</ref>,<ref name="Chris K. Caldwell">Chris K. Caldwell, [https://primes.utm.edu/top20/page.php?id=13''The Largest Known CPAP's'']. Retrieved on 2021-01-28.</ref>

|-

! ''k'' !! Primes for ''n'' = 0 to ''k''&minus;1 !! Digits !! Year !! Discoverer

|-

! 3

| 2494779036241 17484430616589 · 2 2^4980054201 +− 17 + 6''n'' || align="right" | 1500416330 || 20222024 || Serge Batalov

|-

! 4

| 62399583639 35734184537 · 9923 11677#/3 -− 33994216079 + 306''n'' || align="right" | 42855002 || 20212024 || Serge Batalov

|-

! 5

Line 251 ⟶ 258:

<small>

''x''₁₀₆ = 115376 22283279672627497420 78637565852209646810 56709682233916942487 50925234318597647097 08315833909447378791<br>

''x''₁₅₃ = 9656383640115 03965472274037609810 69585305769447451085 87635040605371157826 98320398681243637298 57205796522034199218 09817841129732061363 55565433981118807417 = ''x''₂₅₃ %[[modulo]] 379#<br>

''x''₂₅₃ = 1617599298905 320471304802538356587398499979 836255156671030473751281181199 911312259550734373874520536148 519300924327947507674746679858 816780182478724431966587843672 408773388445788142740274329621 811879827349575247851843514012 399313201211101277175684636727<br>

</small>

Line 259 ⟶ 266:

*[[Szemerédi's theorem]]

*[[PrimeGrid]]

*[[Prime_number_theorem#Prime_number_theorem_for_arithmetic_progressions|Prime number theorem for arithmetic progressions]]

*[[Problems involving arithmetic progressions]]