ピライ配列

ピライ数列は、貪欲表現で素数（および1）の和として記録的な数の項を持つ整数の列です。 1930年に最初に定義したSubbaya Sivasankaranarayana Pillaiにちなんで名付けられました。 ^[1]

ゴールドバッハの予想から、1 より大きいすべての整数は、最大で 3 つの素数の和として表すことができるということになります。しかし、そのような表現を見つけるには、部分集合の和の問題の例を解く必要があり、これは計算上困難です。代わりに、ピライは、を素数の和として表現するための次のより単純な貪欲アルゴリズムを検討しました。つまり、 の和に含まれる最初の素数を、最大で となる素数として選択し、次に について残りの和を再帰的に構築します。このプロセスが 0 に達すると、停止します。また、0 ではなく 1 に達した場合は、和に 1 を含める必要があり (素数でなくても)、停止します。たとえば、このアルゴリズムでは 122 は 113 + 7 + 2 と表されますが、より短い表現である 61 + 61 や 109 + 13 も可能です。 ${\displaystyle n}$${\displaystyle p}$${\displaystyle n}$${\displaystyle np}$

ピライ数列の番目の数は、素数（および1）の和として貪欲に表現するために項を必要とする最小の数である。これらの数は ${\displaystyle n}$${\displaystyle n}$

0、1、4、27、1354、401429925999155061、...（OEISのシーケンスA066352）

数列の各数は、前の数と素数 との和で、その前の素数 は、次の素数との差が より大きい最小の素数です。^[2]たとえば、数列の 27 は 4 + 23 で、4 より大きい最初の素数との差は 23 と 29 の間にあります。 ${\displaystyle a(n)}$${\displaystyle a(n-1)}$${\displaystyle p}$${\displaystyle a(n-1)}$

素数は大きくなるにつれて密度が低くなるため（素数定理によって定量化される）、ピライ数列のどの項よりも大きい素数ギャップが常に存在し、数列は項の数が無限に増えるまで続く。しかし、数列の項は非常に急速に増加する。数列の次の項を表現するには「数億桁」が必要であると推定されている。^[3]