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

数学において、素数フリー数列とは、素数を含まない整数の列のことである。より具体的には、通常はフィボナッチ数列と同じ再帰関係で定義される数列であるが、初期条件が異なるため、数列のすべての要素が合成数となり、すべてが共通の約数を持たないことになる数列を意味する。代数的に言えば、このタイプの数列は、最大公約数が1 に等しく、式から計算される数列に素数が存在しない ような2 つの合成数a ₁とa _{2を適切に選択することによって定義される。} ${\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)。

• グラハム、ロナルド L. ( 1964) 。「フィボナッチのような合成数列」(PDF)。数学雑誌。37 (5): 322–324。doi :10.2307/2689243。JSTOR  2689243。
• Knuth, Donald E. (1990). 「フィボナッチのような合成数列」.数学雑誌. 63 (1): 21–25. doi :10.2307/2691504. JSTOR  2691504. MR  1042933.
• Wilf, Herbert 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。
• Weisstein、Eric W.「Primefree Sequence」。MathWorld。