欧几里得–马林序列是否含所有素数 · 公开问题 32

问题

马林（Mullin，1963）问：定义 a₁ = 2，a_n+1 = P_n + 1（其中 P_n = a₁a₂⋯a_n）的最小素因子，这个序列是否包含每一个素数？这是把欧几里得「素数无穷」的证明逐步执行所得的确定性序列，它的每一项都由算法唯一决定——然而连它的全貌都没人知道。

主要概念

欧几里得式的「新素数机器」

P_n + 1 模任何已有的 a_i 都余 1，故其素因子全是新面孔——这保证序列各项两两不同（命题 1）。但「新素因子」不等于「每个素数迟早登场」：序列可能永久错过某些素数，就像 11 长期下落不明。

三个变体

（一）单调版（本问）：每次取最小素因子，序列确定。（二）任意版：每步任取 P_n+1 的一个素因子——问是否存在一种取法包含所有素数、或任何取法都必然漏掉。（三）加法版（欧几里得数 P_n+1 本身，问题 33）：乘积加 1 是否总无平方因子。三者共享欧几里得骨架而难度各异。

主要命题与证明

命题 1（完整证明）　欧几里得–马林序列的各项两两互异。

证明　对任意 i ≤ n，P_n + 1 ≡ 1 (mod a_i)，而 a_n+1 | P_n + 1，故 a_i ∤ a_n+1。若某项重复，即 a_n+1 = a_i，则 a_i 整除自己——矛盾。□

命题 2（前六项的完整演算）　a₁ = 2，a₂ = 3，a₃ = 7，a₄ = 43，a₅ = 13，a₆ = 53。

演算　P₁+1 = 3 → 3。P₂+1 = 2·3+1 = 7 → 7。P₃+1 = 42+1 = 43（素数）→ 43。P₄+1 = 2·3·7·43+1 = 1807 = 13·139 → 13。P₅+1 = 1806·13+1 = 23479 = 53·443 → 53。P₆+1 = 23478·53+1 = 1244335 = 5·248867 → 5。注意第 5、6 步：13 与 5 都「插队」出现在更大的 43、53 之后——单调性完全失效，序列不是递增的。□

命题 3（11 的归案）　Booker（2012）证明 11 确实在序列中：它恰是第 47 项。此前 11 是否出现悬置了近半个世纪——该步的计算需要分解一个 271 位的数 P₄₆+1（其时已知除 11 外无更小素因子）。

前九项为：2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, …。第八项之后增长陡然失控：每一项都是 «此前全部项之积加一» 的最小素因子，而那个数本身已 routinely 达到数百位，分解它需要整个 NFS 管线。

命题 4（任意版的两个极端，严格梗概）　（一）存在取法使序列含无穷多个素数——显然（任何取法都产生无穷多不同素数，命题 1）。（二）目前无法排除：任意版可能漏掉无穷多个素数，无论怎么取。事实上任意版与单调版之间没有已知的逻辑通道：单调版含所有素数 ⇏ 任意版含所有素数，反之亦然。两个方向都是独立的开放问题。

进展与文献

Mullin 1963 原始问题见 Canad. Math. Bull.；Booker 的 11 见 London Math. Soc. Newsletter 与后续注记（他给出 a₄₇ = 11 的完整分解链）。对任意版，Wagstaff 与 Pomerance 的启发式都预测「所有素数终将出现」，但预测所依赖的模型（把 P_n+1 的素因子当作随机分布）在第八项后已无计算对照——938 位之后的第九项之后的分解至今未全部完成。Jones（2002）证明了单调版的一个反向结果：对任意素数 p，都存在一个欧几里得式序列（变体定义）永远避开 p——「欧几里得机器可以精准绕开任何目标素数」，这使全含性猜想更加可疑。