プライムフリーシーケンス

素数を含まない整数列

数学において、素数を含まない数列とは、素数を含まない整数列のことである。より具体的には、フィボナッチ数列と同じ漸化式で定義される数列を指すが、初期条件が異なるため、数列のすべての要素が共通の約数を持たない合成数となる。代数的に言えば、このタイプの数列は、最大公約数が1となるような2つの合成数a ₁とa ₂を適切に選択することで定義され、式から計算される数列には素数が存在しない。 ${\displaystyle \mathrm {gcd} (a_{1},a_{2})}$ ${\displaystyle n>2}$

${\displaystyle a_{n}=a_{n-1}+a_{n-2}}$。

このタイプの最初の素数フリーシーケンスは、 1964 年にロナルド グラハムによって公開されました。

ウィルフのシーケンス

ハーバート・ウィルフによって発見された素数のない数列は、最初の項を持つ

${\displaystyle a_{1}=20615674205555510,a_{2}=3794765361567513}$（ OEISの配列A083216）

この数列のすべての項が合成数であることの証明は、有限の素数集合の元を法とするフィボナッチ数列の周期性に基づいています。各素数について、数列中の数が で割り切れる位置は周期的なパターンで繰り返され、集合内の異なる素数には重なり合うパターンがあり、その結果、数列全体の被覆集合が形成されます。 ${\displaystyle p}$ ${\displaystyle p}$

非自明性

素数のない数列の最初の項が互いに素であるという要件は、問題が非自明であるための必須条件です。最初の項が素因数を共有する場合（例えば、ある数と両方が1より大きい数に対して と を設定する場合）、乗法の分配法則、そしてより一般的には、数列内の後続のすべての値は の倍数になります。この場合、数列内のすべての数は合成数になりますが、その理由は自明です。 ${\displaystyle p}$ ${\displaystyle a_{1}=xp}$ ${\displaystyle a_{2}=yp}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle a_{3}=(x+y)p}$ ${\displaystyle p}$

最初の項の順序も重要です。ポール・ホフマンによるポール・エルデシュの伝記『数字だけを愛した男』では、ウィルフ数列が引用されていますが、最初の項が入れ替わっています。結果として得られる数列は、最初の100項ほどは素数を含まないように見えますが、138番目の項は45桁の素数です。^[1] ${\displaystyle 439351292910452432574786963588089477522344721}$

その他のシーケンス

他にもいくつかのプライムフリーシーケンスが知られています。

${\displaystyle a_{1}=331635635998274737472200656430763,a_{2}=1510028911088401971189590305498785}$（ OEISの配列A083104 ；Graham 1964）、

${\displaystyle a_{1}=62638280004239857,a_{2}=49463435743205655}$（OEISの配列A083105; Knuth 1990）、および

${\displaystyle a_{1}=407389224418,a_{2}=76343678551}$(OEISの配列A082411; Nicol 1999)。

このタイプの数列のうち、最も小さい初期項を持つ数列は

${\displaystyle a_{1}=106276436867,a_{2}=35256392432}$(OEIS の配列 A221286; Vsemirnov 2004)。

注記

1. Sloane, N. J. A. (編). 「シーケンスA108156」.整数シーケンスのオンライン百科事典. OEIS財団.

参考文献

• グラハム, ロナルド L. (1964). 「フィボナッチ数列のような合成数列」(PDF) .数学雑誌. 37 (5): 322– 324. doi :10.2307/2689243. JSTOR  2689243.
• ドナルド・E.・クヌース(1990). 「フィボナッチ数列のような合成数列」.数学雑誌. 63 (1): 21– 25. doi :10.2307/2691504. JSTOR  2691504. MR  1042933.
• ウィルフ, ハーバート・S. (1990). 「編集者への手紙」.数学雑誌. 63 : 284. doi :10.1080/0025570X.1990.11977539. JSTOR  2690956.
• Nicol, John W. (1999). 「フィボナッチ数列のような合成数列」(PDF) . Electronic Journal of Combinatorics . 6 (1): 44. doi :10.37236/1476. MR  1728014.
• Vsemirnov, M. (2004). 「合成数の新たなフィボナッチ数列」(PDF) . Journal of Integer Sequences . 7 (3): 04.3.7. Bibcode :2004JIntS...7...37V. MR  2110778.

外部リンク

• 問題31：フィボナッチ数列 - すべての合成数列。素数パズルと問題のつながり。
• 「Primefreeシーケンス」。PlanetMath。
• ワイスタイン、エリック・W.「プライムフリーシーケンス」。MathWorld。

「https://en.wikipedia.org/w/index.php?title=Primefree_sequence&oldid=1317975736」から取得