算數數列中的質數

在數論中，算數數列中的質數的研究範圍包括任何包含至少三個在等差數列中彼此相鄰的質數的數列。一個這樣的序列的例子是${\displaystyle (3,7,11)}$，而這序列可由${\displaystyle a_{n}=3+4n}$在${\displaystyle 0\leq n\leq 2}$時給出。

根據格林-陶定理，在質數構成的數列中，存在任意長（英语：Arbitrarily large）的等差數列。

有時這概念也可用以指涉同時包含合數的等差數列中出現的質數，像例如說，這概念也可用以指稱有著${\displaystyle an+b}$這樣形式且${\displaystyle a}$與${\displaystyle b}$互質的等差數列；而根據狄利克雷定理，這樣的數列包含無限多的質數，也包含無限多的合數。

對於大於3的正整數${\displaystyle k}$而言，AP-k（又作PAP-k）指的是任意等差數列中任意${\displaystyle k}$個彼此相鄰的質數。一個AP-k可寫成${\displaystyle an+b}$這樣變數${\displaystyle n}$為${\displaystyle k}$個連續數值的形式，其中${\displaystyle a}$（公差）與${\displaystyle b}$是固定數。一般以${\displaystyle n=0}$至${\displaystyle k}$來表達一個AP-k，這總可藉由將${\displaystyle b}$給定義成算術數列中的第一個質數達成。

在本文中，以${\displaystyle q\#=2\times 3\times 5\times 7\times \cdots \times q}$代表對於質數${\displaystyle q}$的質數階乘，以${\displaystyle x\#=2\times 3\times 5\times 7\times \cdots \times q}$代表對於所有不大於${\displaystyle x}$的質數（其中${\displaystyle q}$是不大於${\displaystyle x}$的最大質數）的質數階乘。

任何由質數構成的等差數列，其長度皆有限。在2004年，本·格林（英语：Ben_Green_(mathematician)）和陶哲軒藉由證明格林-陶定理解決了一個懸宕多年的舊猜想，也就是質數集合中包含任意長度等差數列的猜想。^[1]由此可立即推得說，對於任意${\displaystyle k}$而言，都存在有無限多個AP-k。

假若一個AP-k不以質數${\displaystyle k}$起始，那其公差就是形如${\displaystyle k\#=2\times 3\times 5\cdots \times j}$這樣的質數階乘，其中${\displaystyle j}$不大於${\displaystyle k}$的質數中最大的質數。

證明：設要證明的AP-k的形式為${\displaystyle an+b}$，其中${\displaystyle n}$是變數，其數值為${\displaystyle k}$個連續正整數。若${\displaystyle a}$不能為質數${\displaystyle p}$除盡，那根據模算數，在這等差序列中，每隔${\displaystyle p}$項就會有一項被${\displaystyle p}$除盡。^[2][3]因此若AP對於連續${\displaystyle k}$個值都是質數，那麼${\displaystyle a}$就必然為所有不大於${\displaystyle k}$的質數${\displaystyle p\leq k}$所除盡。

這也顯示了一個包含公差${\displaystyle a}$的AP，其連續的質數項的數量，不能超過最小且不能除盡${\displaystyle a}$的質數的值。

若${\displaystyle k}$是一個質數，那麼AP-k就可以${\displaystyle k}$起始並包含大小僅為而${\displaystyle (k-1)\#}$非${\displaystyle k\#}$的公差。^[4]像例如包含${\displaystyle (3,5,7)}$這三項的AP-3，其公差為${\displaystyle 2\#=2}$；而包含${\displaystyle (5,11,17,23,29)}$這五項的AP-5，其公差為${\displaystyle 4\#=6}$。目前有猜想認為，對所有為質數的${\displaystyle k}$，都有如此的例子。截至截至2018年 (2018-Missing required parameter 1=month!)^[update]為止，已確認有此性質的最大質數是${\displaystyle k=19}$，而相關的AP-19如下，由Wojciech Iżykowski於2013年發現：

${\displaystyle 19+4244193265542951705\cdot 17\#\cdot n}$，其中${\displaystyle n}$的值為0到18。^[5]

這猜想可由迪克森猜想或質數k元組猜想等廣泛認為正確的猜想得出，在其中，若${\displaystyle p>2}$是最小不能為${\displaystyle a}$所除盡的數，那就存在有無限多公差為${\displaystyle a}$的AP-${\displaystyle p-1}$。像例如5是不能除盡6的最小質數，因此可期望說有無限多的AP-4，其公差為6，而這樣的數組又稱為六質數四胞胎；而當${\displaystyle a=2}$且${\displaystyle p=3}$時，這即是孿生質數猜想，在此情況下，此AP-2會包含${\displaystyle b}$跟${\displaystyle b+2}$這兩個質數。

此處的最後項最小化^[6]

最小AP-k

k	從${\displaystyle n=0}$到${\displaystyle k-1}$間的質數形式
3	${\displaystyle 3+2n}$
4	${\displaystyle 5+6n}$
5	${\displaystyle 5+6n}$
6	${\displaystyle 7+30n}$
7	${\displaystyle 7+150n}$
8	${\displaystyle 199+210n}$
9	${\displaystyle 199+210n}$
10	${\displaystyle 199+210n}$
11	${\displaystyle 110437+13860n}$
12	${\displaystyle 110437+13860n}$
13	${\displaystyle 4943+60060n}$
14	${\displaystyle 31385539+420420n}$
15	${\displaystyle 115453391+4144140n}$
16	${\displaystyle 53297929+9699690n}$
17	${\displaystyle 3430751869+87297210n}$
18	${\displaystyle 4808316343+717777060n}$
19	${\displaystyle 8297644387+4180566390n}$
20	${\displaystyle 214861583621+18846497670n}$
21	${\displaystyle 5749146449311+26004868890n}$
22	${\displaystyle 19261849254523+784801917900n}$
23	${\displaystyle 403185216600637+2124513401010n}$

截至2019年9月 (2019-09)^[update]為止，已知最長的AP-k是AP-27，同時也已知數個AP-26的例子。這些數列的第一個是由Benoît Perichon在2010年4月12日以一台PlayStation 3發現的，他用的軟體由Jarosław Wróblewski及Geoff Reynolds所開發、由Bryan Little轉平台到PlayStation 3上，並作為PrimeGrid（英语：PrimeGrid）計畫的一部分發布。以下是他發現的質數序列：^[5]

${\displaystyle 43142746595714191+23681770\cdot 23\#\cdot n}$，其中${\displaystyle n}$的值為0到25。（OEIS數列A204189）

在發現第一個AP-26時，PrimeGrid（英语：PrimeGrid）將整個搜尋分成131,436,182個段落，^[7]並交由全球各地的32跟64位元CPA、Nvidia CUDA GPU以及Cell微處理器等進行搜尋。

在此之前，已知最長的數列是由Raanan Chermoni和Jarosław Wróblewski在2008年5月17日發現的一個AP-25：^[5]

${\displaystyle 6171054912832631+366384\cdot 23\#\cdot n}$，其中${\displaystyle n}$的值為0到24。（另外${\displaystyle 23\#=223092870}$）

對這AP-25的搜尋是在一台CPU為Athlon 64的電腦上進行的，搜尋的部分首先分成段落，並花了大約3分鐘。對此Wróblewski說道：「我認為Raanan搜尋的段落少於10,000,000個。」（而用Athlon 64的CPU大概要花57個CPU年才能完成完整的搜尋）^[8]

更早以前的紀錄，是一個由在2007年1月18日由Jarosław Wróblewski獨自發現的AP-24：

${\displaystyle 468395662504823+205619\cdot 23\#\cdot n}$，其中${\displaystyle n}$的值為0到23。

對此Wróblewski回報說他用了75台電腦，其中15台裝載64位元的Athlon中央處理器，15台裝載64位元的Pentium D 805中央處理器；30台裝載32位元的Athlon 2500中央處理器，以及15台裝載Duron 900中央處理器。^[9]

下表顯示了歷來最大已知的AP-k及其發現年分和末項質數的數字位數。

應當注意的是，最大已知的AP-k可能會以已知的AP-(k+1)結尾。

一些記錄創造者首先先計算大量形如${\displaystyle c\cdot p\#+1}$且${\displaystyle p}$固定的質數然後再開始對不同的${\displaystyle c}$尋找能生出質數的AP。這反映在一些紀錄的表現形式中，而這些紀錄可輕易地重寫成${\displaystyle a\cdot n+b}$的形式。

截至2023年12月 (2023-12)^[update]為止，最大已知的AP-k^[5]

k	從${\displaystyle n=0}$的值為0到${\displaystyle n=k-1}$的質數形式	位數	年分	發現者
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）一般涉及的是三個彼此相鄰，在等差數列中也彼此為相鄰項的質數。和AP-k不同的是，在此所有其他相鄰質數中間的所有其他的、那些不在等差數列中的數，都必須是合成數。像是${\displaystyle (3,7,11)}$這個AP-3數列就不合定義，因為5也是質數。

對於大於3的正整數${\displaystyle k}$而言，CPAP-k指的是等差數列中${\displaystyle k}$個彼此在等差數列外也相鄰的質數。目前有猜想認為存在有任意長度的CPAP，也就是說，對於任意的${\displaystyle k}$都有無限多個CPAP-k。CPAP-3的中間項又稱為平衡質數，截至2022年 (2022-Missing required parameter 1=month!)^[update]為止，已知最大的平衡質數有15004位數。

第一個已知的CPAP-10在1998年由Manfred Toplic在參與分布式計算計畫CP10時發現，而CP10這項分布式計算計畫是由Harvey Dubner、Tony Forbes、Nik Lygeros、Michel Mizony和Paul Zimmermann等人組織發起的。^[10]這個CP10有著最小可能的公差${\displaystyle 7\#=210}$；而截至2018年 (2018-Missing required parameter 1=month!)^[update]為止，只有另一個CPAP-10是已知的，且是由同一人在2008年發現的。

若CPAP-11存在，則其公差必然為${\displaystyle 11\#=2310}$的倍數，也因此其中第一項和最後一項質數的差會是23100的倍數，這代表在這11個質數之間，至少會有23090個合成數，因此要找到CPAP-11會是極為困難的。Dubner和Zimmermann估計說，找到CPAP-11的難度，至少會是找到CPAP-10的${\displaystyle 10^{12}}$倍。^[11]

目前只知道當${\displaystyle k\leq 6}$時，相應的CPAP-k的首次出現處。（OEIS數列A006560）

最小CPAP-k^[12]

k	從${\displaystyle n=0}$的值為0到${\displaystyle n=k-1}$的質數形式
3	3 + 2n
4	251 + 6n
5	9843019 + 30n
6	121174811 + 30n

此表顯示等差數列中已知最大的${\displaystyle k}$個相鄰質數，分別從${\displaystyle k=3}$到${\displaystyle k=10}$。

截至2024年6月 (2024-06)^[update]為止最大已知的CPAP-k^[13][14]

k	從${\displaystyle n=0}$的值為0到${\displaystyle n=k-1}$的質數形式	位數	年分	發現者
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

${\displaystyle x_{d}}$指的是一個在上述紀錄用以保證在不尋常多地、依條件要求的合成數中都會有小因數的d位數字。

• 坎寧安鏈（英语：Cunningham chain）
• 塞邁雷迪定理
• PrimeGrid（英语：PrimeGrid）
• 等差數列相關的問題（英语：Problems involving arithmetic progressions）

• 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.
• 埃里克·韦斯坦因. 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.