シルベスター数列

シルベスター数の逆数和 1/2 + 1/3 + 1/7 + 1/43 +… が1に収束することのグラフィカルな実演。各行は一辺が 1/k である正方形 k 個からなり、従って面積は 1/k となり、それら正方形の全体は一辺が1の正方形をちょうど被覆する。一辺 1/1807、あるいはそれ以下の正方形は小さすぎて図中で見ることはできない。

数論において、シルベスター数列 (テンプレート:Lang-en) とは、各項がそれまでの項の総積に1を足したものであるような数列である。最初のいくつかの項は次のようになる：

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

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

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

形式的定義

シルベスター数列の第テンプレート:Mvar 項は次の式で定義される：

s_{n} = 1 + \prod_{i = 0}^{n - 1} s_{i} .

0個の項の積 (空積) は 1 であるため、テンプレート:Math である。

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

s_{i} = s_{i - 1} (s_{i - 1} - 1) + 1, (s_{0} = 2)

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

シルベスター数列はテンプレート:Mvar の関数として、二重指数関数的に増加する。具体的には

s_{n} = ⌊ E^{2^{n + 1}} + \frac{1}{2} ⌋

という形式で書くことができる。ここでテンプレート:Mvar はおよそ 1.2640847353...である^[1] (テンプレート:OEIS)。

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

エジプト式分数との関係

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

\sum_{i = 0}^{\infty} \frac{1}{s_{i}} = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \dots .

について考える。この級数の部分和は次のような単純な形で書ける：

\sum_{i = 0}^{j - 1} \frac{1}{s_{i}} = 1 - \frac{1}{s_{j} - 1} = \frac{s_{j} - 2}{s_{j} - 1} .

これは、帰納法によって、またはより直接的に、任意のテンプレート:Mvar に対する次の等式

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

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

\sum_{i = 0}^{j - 1} \frac{1}{s_{i}} = \sum_{i = 0}^{j - 1} (\frac{1}{s_{i} - 1} - \frac{1}{s_{i + 1} - 1}) = \frac{1}{s_{0} - 1} - \frac{1}{s_{j} - 1} = 1 - \frac{1}{s_{j} - 1} .

部分和がテンプレート:Math で1に収束することから、級数全体が1に収束することがわかる。従って私たちは、これによって無限の長さを持つ1のエジプト式分数表示を得たことになる。

1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \dots

このとき、級数を適当な長さで切って、最後の分母を1小さいものに置き換えることで、任意の長さを持つ1のエジプト式分数表示を得ることができる。

1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{6}, 1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{42}, 1 = \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1806}, \dots .

また、無限級数の最初のテンプレート:Mvar 項の和は、テンプレート:Mvar 項からなるエジプト式分数表示のうち1未満で最も大きいものを提供する^[3]。例えば、最初の4項の和は 1805/1806 となるため、開区間テンプレート:Math に含まれる数のエジプト式分数表示は少なくとも5つの項が必要になる。

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

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

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

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

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

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

a_{n} = a_{n - 1}^{2} - a_{n - 1} + 1

となる。

エルデシュとグラハムは、数列テンプレート:Math が $\lim_{n \to \infty} \frac{a_{n}}{a_{n - 1}^{2}} = 1 .$ を満たすとき、逆数和が有理数となるならば、十分大きな全てのテンプレート:Mvar に対して $a_{n} = a_{n - 1}^{2} - a_{n - 1} + 1$ が成り立つと予想した^[4]。テンプレート:Harvtxt ではこの予想についていくつかの結果が纏められている。

因数分解 (可除性)

テンプレート:Math のとき、定義からテンプレート:Math が成り立つ。従って、任意の2つのシルベスター数は互いに素である。任意の素数に対して、それで割り切れるシルベスター数が高々1つとなるため、これを用いて素数が無限に存在することを証明できる。より強い事実として、シルベスター数の素因数に6を法として5と合同である数 (テンプレート:Math と表せるような素数) は存在しないこと、12を法として7と合同である素数が無限に存在することがシルベスター数列を用いて証明できるテンプレート:Sfnp。テンプレート:Unsolvedシルベスター数の素因数分解については、多くのことが未解決のままである。例えば、全ての数が平方因子をもたない整数であるかどうか不明である (既知の数は全て平方因子を持たないことがわかっている)。

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

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

テンプレート:Mvar	テンプレート:Math の因数
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桁)

応用

テンプレート:正確性テンプレート:Harvtxt ではシルベスター数列の性質を使って、奇数次元の球面またはテンプレート:仮リンクに対する非同値な佐々木・アインシュタイン多様体^{[注 2]}の族を与えている^[5]。彼らは論文中で、テンプレート:Math 次元の球面またはエキゾチック球面上で少なくとも $\frac{1}{3} (s_{m - 1} - 1)$ 個の非同値な佐々木・アインシュタイン多様体の族を与える方法を示し、従ってそれらの数はテンプレート:Mvar に対して二重指数関数的な増加を見せる。

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

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

テンプレート:Harvtxt は単位分数のテンプレート:Mvar 項和で1に最も近い近似が、完全数の約数の数に下界を与えることが記されている。テンプレート:Harvtxt では同じ性質がテンプレート:Mvar 個の部分群を持つ群の位数の上界を与えるために使われている。

脚注

補注

↑ 数列の増加速度と級数の無理性については、例えば数列テンプレート:Math が十分に速く増加するとき、 $\sum_{k} \frac{1}{a_{k} a_{k + 1}}$ が無理数となることが知られているテンプレート:Harv。
↑ テンプレート:仮リンクでもあるアインシュタイン多様体
↑ 論文中でSeidenとWoegingerは、シルベスター数列をテンプレート:Harvtxt の仕事にちなんで「Salzer's sequence」という名前で言及している。

出典

テンプレート:Reflist

参考文献

テンプレート:Refbegin

テンプレート:Refend

外部リンク

テンプレート:Cite web2

↑ テンプレート:Harvtxt
↑ テンプレート:Harvtxt, テンプレート:Harvtxt
↑ テンプレート:Harvtxt、テンプレート:Harvtxt あるいはテンプレート:Harvtxt を参照。
↑ テンプレート:Harvtxt
↑ テンプレート:Harvtxt、特に Prop. 44–Prop. 48
↑ テンプレート:Harvtxt

[4] 数列の増加速度と級数の無理性については、例えば数列テンプレート:Math が十分に速く増加するとき、 $\sum_{k} \frac{1}{a_{k} a_{k + 1}}$ が無理数となることが知られているテンプレート:Harv。

[6] テンプレート:仮リンクでもあるアインシュタイン多様体

[8] 論文中でSeidenとWoegingerは、シルベスター数列をテンプレート:Harvtxt の仕事にちなんで「Salzer's sequence」という名前で言及している。

[1] テンプレート:Harvtxt

[2] テンプレート:Harvtxt, テンプレート:Harvtxt

[3] テンプレート:Harvtxt、テンプレート:Harvtxt あるいはテンプレート:Harvtxt を参照。

[5] テンプレート:Harvtxt

[7] テンプレート:Harvtxt、特に Prop. 44–Prop. 48

[9] テンプレート:Harvtxt

[1]

[2]

[3]

[注 1]

[4]

[注 2]

[5]

[注 3]

[6]

シルベスター数列

目次

形式的定義

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

エジプト式分数との関係

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

因数分解 (可除性)

応用

関連項目

脚注

補注

出典

参考文献

外部リンク

ナビゲーションメニュー

シルベスター数列

形式的定義

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

エジプト式分数との関係

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

因数分解 (可除性)

応用

関連項目

脚注

補注

出典

参考文献

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー