シルベスターのシーケンス

数論において、シルベスター数列は各項が前の項の積に1を加えたものである 整数列である。その最初の数項は

2、3、7、43、1807、3263443、10650056950807、113423713055421844361000443（OEISの配列A000058）。

シルベスター数列は、1880年に初めて調査したジェームズ・ジョセフ・シルベスターにちなんで名付けられました。 ^[1]その値は二重指数関数的に増加し、その逆数の和は他のどの単位分数列よりも急速に1に収束する単位分数列を形成します。[ 2 ]それが定義^されている再発性により、数列の数は、同じ大きさの他の数よりも簡単に因数分解できますが、 ^[3]数列の急速な増加のため、完全な素因数分解は数項のみで知られています。^[4]この数列から導出された値は、1の有限エジプト分数表現、ササキアン・アインシュタイン多様体、^[5]およびオンラインアルゴリズムのハードインスタンスの構築にも使用されています。^[6]

正式には、シルベスター数列は式^{[7]で定義される。}

${\displaystyle s_{n}=1+\prod _{i=0}^{n-1}s_{i}.}$

空集合の積は1なので^[8]、この式はs ₀ = 2となり、別の基本ケースは必要ありません。

あるいは、繰り返しによってシーケンスを定義することもできる^[3]

${\displaystyle \displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,}$基本ケースではs ₀ = 2 です。

これが他の定義と同等であることを帰納的に証明するのは簡単です。 ^[9]

シルベスター数はnの関数として2倍指数的に増加する。具体的には、

${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,\!}$

数Eはおよそ1.26408473530530... ^[10]（OEISのシーケンスA076393 ）である。この式は次のアルゴリズムの効果を持つ。

s _{0 は}E ²に最も近い整数です。s _{1 は}E ⁴に最も近い整数です。s _{2 は}E ⁸に最も近い整数です。 s _nについては、E ²を取り、それをさらにn回二乗し、最も近い整数を取ります。

このアルゴリズムは、 snを_計算してその繰り返し平方根を取るよりも、 Eを必要な桁数まで計算するより良い方法があれば実用的なものとなるだろう。^[11]

シルベスター数列の二重指数関数的増加は、フェルマー数列 F _nと比較すれば驚くようなものではない。フェルマー数は通常、二重指数式で定義されるが、シルベスター数列を定義するものと非常によく似た積式で定義することもできる。^[12]${\displaystyle 2^{2^{n}}\!+1}$

${\displaystyle F_{n}=2+\prod _{i=0}^{n-1}F_{i}.}$

シルベスター数列の値の逆数によって形成される単位分数は、無限級数を生成する：^[13]

${\displaystyle \sum _{i=0}^{\infty }{\frac {1}{s_{i}}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .}$

この級数の部分和は単純な形をしており、

${\displaystyle \sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={\frac {s_{j}-2}{s_{j}-1}},}$

これはすでに最小の項で表されている。^{[14]これは帰納法で}証明できるが、より直接的には再帰法が次のことを意味することに注意することで証明 できる。

${\displaystyle {\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}={\frac {1}{s_{i}}},}$

合計は[ ^14]

${\displaystyle \sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=\sum _{i=0}^{j-1}\left({\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}\right)={\frac {1}{s_{0}-1}}-{\frac {1}{s_{j}-1}}=1-{\frac {1}{s_{j}-1}}.}$

この部分和の列 ( s _j − 2)/( s _j − 1) は 1 に収束するため、全体の列は数 1 の 無限エジプト分数表現を形成します。

${\displaystyle 1={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .}$

この数列を切り捨て、最後の分母から 1 を引くと、任意の長さの 1 の有限エジプト分数表現を見つけることができます。

${\displaystyle 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{6}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{42}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{43}}+{\tfrac {1}{1806}},\quad \dots .}$

無限級数の最初のk項の和は、任意のk項エジプト分数による1の可能な限り最も近い過小評価を提供します。^{[2]たとえば、最初の4項を加算すると1805/1806になるため、}開区間(1805/1806, 1)の数値のエジプト分数には少なくとも5項が必要です。

シルベスター数列は、エジプト分数の貪欲アルゴリズムの結果として解釈することができ、各ステップで数列の部分和が1未満になるような最小の分母を選択します。^[15]

シルベスター自身が観察したように、シルベスターの数列は、このように急速に増加する値を持ちながら、同時に有理数に収束する逆数の列を持つという点でユニークであるように思われる。この数列は、二重指数関数的増加だけでは整数数列を無理数列にするのに十分ではないことを示す例を提供している。^[16]

これをより正確に言うと、Badea (1993)の結果から、整数列が十分に速く成長し、 ${\displaystyle a_{n}}$

${\displaystyle a_{n}\geq a_{n-1}^{2}-a_{n-1}+1,}$

そしてシリーズ

${\displaystyle A=\sum {\frac {1}{a_{i}}}}$

が有理数Aに収束する場合、ある点以降のすべての nに対して、この数列は同じ再帰によって定義される必要がある。

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

シルベスターのシーケンスを定義するために使用することができます。^[17]

エルデシュとグラハム（1980）は、このタイプの結果では、シーケンスの成長を制限する不等式は、より弱い条件に置き換えられる可能性があると推測しました。 ^[18]

${\displaystyle \lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.}$

Badea（1995）はこの予想に関連する進歩を調査している。またBrown（1979）も参照。^[19]

i < jの場合、定義からs _j ≡ 1 (mod s _i  ) となる。したがって、シルベスターの数列のすべての 2 つの数は互いに素である。この数列は、任意の素数が数列内の最大 1 つの数しか割り切れないことから、素数が無限に存在することを証明するために使用できる。さらに強いことは、数列内の数の素因数は5 を法として 6 と一致することはできず、数列は 7 を法として 12 と一致する素数が無限に存在することを証明するために使用できる。^[20]

シルベスターの数列の因数分解については、まだ多くのことがわかっていない。例えば、数列のすべての数が平方数であるかどうかはわかっていないが、既知の項はすべて平方数である。^[21]

Vardi (1991) が述べているように、与えられた素数pがどのシルベスター数を割り切れるか (もしあれば) は簡単に判定できる。つまり、 pを法として数を定義する再発式を、ゼロと合同な数 (mod p ) または繰り返される法数を見つけるまで計算するだけだ。^[3]この手法を使用して、彼は最初の 300 万個の素数のうち 1166 個がシルベスター数の約数であること、 ^[22]これらの素数のいずれもシルベスター数を割り切れる平方数を持たないことを発見した。シルベスター数の因数として現れる素数の集合は、すべての素数の集合の中で密度が 0 である。^{[23]実際、} x未満のそのような素数の数はである。^[24]${\displaystyle O(\pi (x)/\log \log \log x)}$

次の表は、これらの数の既知の因数分解を示しています（最初の4つはすべて素数です）。^[4]

慣例どおり、P nと C n は、長さn桁の素数と因数分解されていない合成数 を表します。

Boyer、Galicki、Kollár (2005) は、シルベスター数列の特性を利用して、奇数次元球面またはエキゾチック球面の微分位相を持つ多数のササキアン・アインシュタイン多様体を定義しました。 彼らは、次元2 n − 1の位相球面上の異なるササキアン・アインシュタイン計量の数は少なくともs nに比例し  、したがって_nとともに二重指数関数的に増加することを示しました。^[5]

Galambos & Woeginger (1995) が述べているように、Brown (1979) と Liang (1980) は、シルベスターのシーケンスから導出された値を使用して、オンラインビンパッキングアルゴリズムの下限の例を構築しました。^[6] Seiden & Woeginger (2005) も同様に、2次元カッティングストックアルゴリズムのパフォーマンスの下限値としてシーケンスを使用しています。^[25]

ズナームの問題は、集合内の各数が他のすべての数の積に 1 を加えた数を割り切るが、等しくない数の集合に関する問題である。不等式の要件がなければ、シルベスター数列の値でこの問題は解決できる。その要件がある場合、シルベスター数列を定義するものと同様の再帰から導かれる他の解が存在する。ズナームの問題の解は、表面特異点の分類 (Brenton and Hill 1988) や非決定性有限オートマトン理論に応用されている。^[26]

カーティス（1922）は、任意の完全数の約数の数の下限値を求める際に、k項分数の1による和に最も近い近似値を適用することを説明しており、ミラー（1919）は同じ性質を利用して、特定の群のサイズの上限値を決定している。^[27]

• カーエン定数
• 一次擬似完全数
• レオナルド数

• KS Brown の MathPages からの、二次和の無理数。
• ワイスタイン、エリック・W.「シルベスターのシーケンス」。マスワールド。