シルベスター数列

数論において、シルベスター数列 (英語: Sylvester's sequence) とは、各項がそれまでの項の総積に1を足したものであるような数列である。最初のいくつかの項は次のようになる：

「シルベスター数列」という名称は、1880年にこの数列を最初に調査したジェームス・ジョセフ・シルベスターに由来している。数列の各項の値はシルベスター数 (英: Sylvester number) と呼ばれることもある。

シルベスター数列の値は二重指数関数的に増加し、その逆数の和は他の単位分数の級数よりも速く1に収束する。シルベスター数列を定義する漸化式は、各項の数の素因数分解をより容易にさせるが、数列の増加速度が急速であるために、完全な素因数分解はいくつかの項に対してしか知られていない。

シルベスター数は1のエジプト式分数表現、佐々木・アインシュタイン多様体、オンラインアルゴリズムの実装などに応用されている。

形式的定義

シルベスター数列の第 n 項は次の式で定義される：

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

0個の項の積 (空積) は 1 であるため、s₀ = 2 である。

あるいは、次のような漸化式で定義してもよい：

${\textstyle \displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,\quad (s_{0}=2)}$

閉形式での表現とフェルマー数

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

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

という形式で書くことができる。ここで E はおよそ 1.2640847353...である^[1] (オンライン整数列大辞典の数列 A076393)。

シルベスター数列が二重指数関数的増加を示すことは、フェルマー数列 F_n と比較すると驚くべきことではない。フェルマー数は通常、二重指数関数による表式 ${\textstyle F_{n}=2^{2^{n}}+1}$ によって定義されるが、これはシルベスター数列のような総積を使った漸化式によっても定義が可能である^[2]：

エジプト式分数との関係

シルベスター数列の逆数和による無限級数

${\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}}.}$

これは、帰納法によって、またはより直接的に、任意の i に対する次の等式

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

から、級数の畳み込みを行うことによって示される：

${\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}}.}$

部分和が 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未満で最も大きいものを提供する^[3]。例えば、最初の4項の和は 1805/1806 となるため、開区間 (1805/1806, 1) に含まれる数のエジプト式分数表示は少なくとも5つの項が必要になる。

シルベスター数列は、各ステップごとにその部分和が1以下となるような最小の分母を選ぶ貪欲法の結果として見ることもできる。あるいは、(初項である1/2を除外して、) 1/2の奇数貪欲法によるエジプト式分数展開 (Odd greedy expansion) だと考えることもできる。

有理逆数和を持つ急速増加列としての一意性

シルベスター数の逆数和が有理数である1に収束することから、数列が二重指数関数的に増加することは、その逆数和による級数が無理数となること、さらに数列が irrationality sequence^{[定訳なし]} となることの十分条件ではないことがわかる^{[注 1]}。

一方で Badea (1993) の結果から、シルベスター数列 (の漸化式) は、二重指数関数的な増加を持ち逆数和が有理数に収束するような数列に対する、ある種の唯一性を持っている。つまり、数列 {a_n} が不等式

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

を満たし、逆数和が有理数に収束するならば、十分に大きなすべての n に対して、その漸化式はシルベスター数列と同じ

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

となる。

エルデシュとグラハムは、数列 {a_n} が

を満たすとき、逆数和が有理数となるならば、十分大きな全ての n に対して ${\textstyle a_{n}=a_{n-1}^{2}-a_{n-1}+1}$ が成り立つと予想した^[4]。Badea (1995) ではこの予想についていくつかの結果が纏められている。

因数分解 (可除性)

i < j のとき、定義から s_j ≡ 1 (mod s_i) が成り立つ。従って、任意の2つのシルベスター数は互いに素である。任意の素数に対して、それで割り切れるシルベスター数が高々1つとなるため、これを用いて素数が無限に存在することを証明できる。より強い事実として、シルベスター数の素因数に6を法として5と合同である数 (p = 6k + 5 と表せるような素数) は存在しないこと、12を法として7と合同である素数が無限に存在することがシルベスター数列を用いて証明できる^[5]。

数学の未解決問題

シルベスター数列の全ての数は無平方数か？

シルベスター数の素因数分解については、多くのことが未解決のままである。例えば、全ての数が平方因子をもたない整数であるかどうか不明である (既知の数は全て平方因子を持たないことがわかっている)。

Vardi (1991)が説明しているように、与えられた素数 p で割り切れるシルベスター数がどれかを決定することは簡単である：p を法として0に合同となる数か、周期的な列のいずれかが見つかるまで、法 p の下でのシルベスター数列を計算すればよい。この方法を使って、Vardiは最初の300万個の素数のうち1166個がシルベスター数の素因数であること^{[注 2]}、それらの数の平方がシルベスター数の因数にならないことを突き止めた。シルベスター数の因数として現れる素数の集合は、全ての素数の集合に対して密度0 (Natural density の意味で) である^[7]。実際、x より小さいそのような数は ${\textstyle O(x/(\log x\cdot \log \log \log x))}$ のオーダーとなる^[8]。

次の表は、シルベスター数の既知の因数分解を示している。ただし最初の4つは全て素数であるため除いている。また、一部の数は大きすぎるため桁数のみを表しており、特に明記されていなければそれらの数は素数とは限らない (unfactoredである)^{[注 3]}。

n	sn の因数
4	13 × 139
5	3263443 (素数)
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9119521 × 6212157481
8	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851
10	2287 × 2271427 × 21430986826194127130578627950810640891005487 × (156桁の素数)
11	73 × (416桁)
12	2589377038614498251653 × 2872413602289671035947763837 × (785桁)
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × (1600桁)
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × (3293桁)
15	17881 × 97822786011310111 × 54062008753544850522999875710411 × (6618桁)
16	128551 × 115220560101116343072340969000241209 × (13300桁)
17	635263 × 1286773 × 21269959 × (26661桁)
18	50201023123 × 139263586549 × 60466397701555612333765567 × (53313桁)
19	775608719589345260583891023073879169 × (106685桁)
20	352867 × 6210298470888313 × (213419桁)
21	387347773 × 1620516511 × (426863桁)
22	91798039513 × 7919244169465663354953966404923 × (853719桁)

応用

Boyer, Galicki & Kollár (2005) ではシルベスター数列の性質を使って、奇数次元の球面またはエキゾチック球面（英語版）に対する非同値な佐々木・アインシュタイン多様体^{[注 4]}の族を与えている^[11]。彼らは論文中で、2m－3 次元の球面またはエキゾチック球面上で少なくとも ${\textstyle {\tfrac {1}{3}}(s_{m-1}-1)}$ 個の非同値な佐々木・アインシュタイン多様体の族を与える方法を示し、従ってそれらの数は m に対して二重指数関数的な増加を見せる。

Galambos & Woeginger (1995)が説明しているように、 Brown (1979)とLiang (1980)はオンラインのビンパッキングアルゴリズムについて、アルゴリズムの評価の下界を与えるためにシルベスター数列の値を利用した。Seiden & Woeginger (2005) でも同様に、2次元カッティングストック問題に対して、3-stageギロチンカット解の下界を与えるためにシルベスター数列が用いられている^{[注 5]}。

Známの問題（英語版）は、集合の各要素がそれぞれ他の数の総積に1を足した数の真の約数であるような集合についての問題である。「真の」約数であるという条件を除くと、シルベスター数列の値はこの問題を解決する。本来の条件の下では、シルベスター数列を定めるものと同様の再帰的な手続きによって、問題の解を得ることができる^[要出典]。Známの問題の解は表面特異点の分類^[12]や、unary n-cyclic 正規言語を通して非決定性有限オートマトンの理論^[13]への応用が存在する。

Curtiss (1922) は単位分数の k 項和で1に最も近い近似が、完全数の約数の数に下界を与えることが記されている。Miller (1919) では同じ性質が k 個の部分群を持つ群の位数の上界を与えるために使われている。

関連項目

• カエン定数（英語: Cahen's constant）
• Primary pseudoperfect number - オンライン整数列大辞典の数列 A054377
• レオナルド数（英語: Leonardo number）- オンライン整数列大辞典の数列 A001595

脚注

補注

出典

参考文献

外部リンク

• Andersen, Jens Kruse (2007–20). "Factorization of Sylvester's sequence". 2022年4月7日時点のオリジナルよりアーカイブ。2022年9月4日閲覧。

• Takusagawa, Ken (19 January 2006a). "factoring Sylvester's sequence". Ken's blog. 2022年8月18日時点のオリジナルよりアーカイブ。2022年9月4日閲覧。
• Takusagawa, Ken (2 April 2006b). "Sylvester 10th factored". Ken's blog. 2022年8月18日時点のオリジナルよりアーカイブ。2022年9月4日閲覧。