ユークリッド・マリン配列

ユークリッド・マリン数列は、互いに異なる素数の無限数列であり、各要素は、1の最小素因数とそれ以前のすべての要素の積の和である。この数列は、素数が無限に存在するというユークリッドの証明の考え方に基づいているため、古代ギリシャの数学者ユークリッドにちなんで名付けられ、また、1963年にこの数列について質問したアルバート・A・マリンにもちなんで名付けられている。 ^{[ 1 ]}

数列の最初の 51 要素は

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, 23003, 30693651606209, 37, 1741, 1313797957, 887, 71, 7127, 109, 23, 97, 159227, 643679794963466223081509857, 103, 1079990819, 9539, 3143065813, 29, 3847, 89, 19, 577, 223, 139703, 457, 9649, 61, 4357, 87991098722552272708281251793312351581099392851768893748012603709343, 107, 127, 3313, 227432689108589532754984915075774848386671439568260420754414940780761245893, 59, 31, 211... ( OEISのシーケンスA000945 )

これらは2012年9月時点で判明している唯一の元素である。 次の数を見つけるには、335桁の数（合成数であることがわかっている）の最小の素因数を見つける必要があります。

の${\displaystyle n}$シーケンスの 番目の要素、${\displaystyle a_{n}}$は、の最小素因数です。

${\displaystyle {\Bigl (}\prod _{i<n}a_{i}{\Bigr )}+1\,.}$

したがって、最初の要素は、空の積に 1 を加えた最小の素因数であり、それは 2 です。3 番目の要素は (2 × 3)  + 1 =  7 です。より分かりやすい例として、数列の 5 番目の要素である 13 があります。これは、2 つの素数 13 × 139 の積である (2  ×  3  ×  7  ×  43)  + 1  =  1806  + 1  = 1807 で計算されます。これら 2 つの素数のうち、13 が最小であるため、数列に含まれています。同様に、7 番目の要素である 5 は、(2 × 3 × 7 × 43 × 13 × 53) + 1 = 1244335 の結果であり、その素因数は 5 と 248867 です。これらの例は、数列が非常に大きな数から非常に小さな数に飛躍する理由を示しています。   

この数列は無限に長く、重複する要素を含みません。これは、素数が無限に存在するというユークリッドの証明方法を用いて証明できます。この証明は構成的であり、この数列はその構成方法の一種によって得られるものです。

マリン (1963)は、すべての素数がユークリッド-マリン数列に現れるかどうか、また現れない場合、与えられた素数が数列に含まれるかどうかをテストする問題が計算可能かどうかを問いかけた。ダニエル・シャンクス( 1991 )は、素数の分布がランダムであるという経験的な仮定に基づいて、すべての素数が数列に現れると推測した。 ^{[ 2 ]} しかし、他のドメイン上の同様の再帰的数列にはすべての素数が含まれていないが、^{[ 3 ]} これらの問題はどちらも元のユークリッド-マリン数列については未解決のままである。^{[ 4 ]}数列の要素として知られていない最小の素数は 41 である。 

2から97までの素数の位置は次のとおりです。

2:1、3:2、5:7、7:3、11:12、13:5、17:13、19:36、23:25、29:33、31:50、37:18、41:?、43:4、47:?、53:6、59:49、61:42、67:?、71:22、73:?、79:?、83:?、89:35、97:26 ( OEISのシーケンスA056756 )

ここで、 ？は、2012年時点でその位置（または位置が存在するかどうか）が不明であることを示します。^{[ 5 ]}

1の最大の素因数と前の数の積の和によって決定される関連する数列（最小の素因数ではなく）は、ユークリッド・マリン数列としても知られています。これはより速く増加しますが、単調ではありません。^{[ 6 ]}この数列の数は

2、3、7、43、139、50207、340999、2365347734339、4680225641471129、1368845206580129、889340324577880670089824574922371、… （ OEISのシーケンスA000946）。

この数列にはすべての素数が現れるわけではなく、^{[ 7 ]}欠落している素数の数列は、

5、11、13、17、19、23、29、31、37、41、47、53、59、61、67、71、73、... （ OEISの配列A216227）

無限であることが証明されている。^{[ 8 ] [ 9 ]}

また、各ステップで最小の素因数を選択する同じルールを使用し、 2とは異なる素数から始めることで、ユークリッド・マリン数列の修正版を生成することも可能である。 ^{[ 10 ]}

あるいは、各数を（因数分解するのではなく）前の数の積に 1 を加えたものとすると、シルベスターの数列が得られます。前の数の積に 1 を加えたもののすべての因数を繰り返し追加して構築された数列は、シルベスターの数列の素因数列と同じです。ユークリッド・マリン数列と同様に、これは素数の非単調数列ですが、すべての素数を含むわけではないことが知られています。^{[ 11 ]}

• ユークリッド数

• ワイススタイン、エリック・W.、「ユークリッド・マリン数列」、MathWorld