シルベスター数列

合計 1/2 + 1/3 + 1/7 + 1/43 + ... の 1 への収束のグラフィカルなデモンストレーション。一辺の長さが 1/ kのk個の正方形の各行の総面積は 1/ kであり、すべての正方形を合わせると面積 1 のより大きな正方形が正確にカバーされます。一辺の長さが 1/1807 以下の正方形は小さすぎて図では見えないため、表示されていません。

数論では、シルベスター数列は、数列の各項が前の項の積に 1 を加えた整数列です。数列の最初の数項は、

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443（ オンライン整数列大辞典の数列 A000058 ） .

シルベスターのシーケンスは、1880 年に最初に調査したジェームズ ジョセフ シルベスターにちなんで名付けられました。その値は2 倍に指数関数的に増加し、その逆数の合計は、他の単位分数の系列よりも速く 1 に収束する一連の単位分数を形成します。それが定義される再帰により、数列内の数を同じ大きさの他の数よりも簡単に因数分解することができますが、数列が急速に成長するため、完全な素因数分解はその数項についてのみ知られています。このシーケンスから派生した値は、1 の有限エジプト分数表現、ササキアンアインシュタイン多様体、およびオンライン アルゴリズムのハード インスタンスの構築にも使用されています。

正式な定義

正式には、シルベスターの数列は次の式で定義できます。

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

空集合の積は 1 なので、 s ₀ = 2 です。

あるいは、再帰によってシーケンスを定義することもできます

$\displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,$ s ₀ = 2 で。

これが他の定義と同等であることを帰納法で示すのは簡単です。

閉形式の公式と漸近線

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

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

約 1.26408473530530... オンライン整数列大辞典の数列 A076393 のシーケンス ある数Eの場合。この式には、次のアルゴリズムの効果があります。

■ ₀はE ²に最も近い整数です。 s ₁はE ⁴に最も近い整数です。 s ₂はE ⁸に最も近い整数です。 s _{n に対して}、 E ²を取り、それをさらにn回二乗し、最も近い整数を取ります。

これは、必要な桁数までEを計算する方法が、 s _nを計算してその平方根の繰り返しを取るよりも優れている場合にのみ、実用的なアルゴリズムになります。

シルベスター数列の二重指数関数的増加は、それをフェルマー数F _nの数列と比較すれば驚くべきことではありません。フェルマー数は通常、二重指数関数式で定義されます。 $2^{2^{n}}+1$ですが、シルベスターの数列を定義するものと非常によく似た積の公式によって定義することもできます。

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

この級数の部分和は単純な形をしています。

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

これは、帰納法によって、またはより直接的に、再帰が

${\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}\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 の無限エジプト分数表現を形成します。

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

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

$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 の最も近い過小評価を提供します。 たとえば、最初の 4 つの項は 1805/1806 に加算されるため、開区間(1805/1806、 1) 少なくとも 5 つの用語が必要です。

シルベスター数列は、各ステップで、級数の部分和が 1 未満になる最小の分母を選択するエジプト分数の貪欲なアルゴリズムの結果として解釈することができます。あるいは、最初の数列の後の項は、1/2 の奇数貪欲展開の分母と見なすことができます。

有理和を持つ急速に成長するシリーズの一意性

シルベスター自身が観察したように、シルベスターの数列は、有理数に収束する一連の逆数を同時に持ちながら、急速に増加する値を持つという点で独特のようです。このシーケンスは、二重指数関数的成長が整数シーケンスを不合理シーケンスにするのに十分ではないことを示す例を提供します。

これをより正確にするために、 Badea (1993)の結果から、整数のシーケンスが$a_{n}$十分に急速に成長する

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

そしてシリーズなら

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

有理数Aに収束する場合、ある点以降のすべてのn に対して、この数列は同じ再帰によって定義されなければなりません

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

シルベスターのシーケンスを定義するために使用できます。

Erdős & Graham (1980) conjectured that, in results of this type, the inequality bounding the growth of the sequence could be replaced by a weaker condition,

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

Badea (1995) surveys progress related to this conjecture; see also Brown (1979).

割り切れる可能性と因数分解

i < jの場合、定義からs _j ≡ 1 (mod s _i ) となります。したがって、シルベスターの数列のすべての 2 つの数は互いに素です。数列を使用して、無限に多くの素数が存在することを証明できます。これは、素数は数列内の最大 1 つの数を分割できるためです。より厳密には、数列内の数の素因数は 6 を法として 5 と合同になることはできず、この数列を使用して、12 を法として 7 と合同である素数が無数にあることを証明することができます

mathematicsの未解決問題

Are all the terms in Sylvester's sequence squarefree?

シルベスター数列における数の素因数分解については、多くのことが不明なままです。たとえば、シーケンス内のすべての数がsquarefreeであるかどうかはわかっていませんが、既知の項はすべてあります。

Vardi (1991)が説明しているように、与えられた素数pがどのシルベスター数 (存在する場合) で割り切れるかを判断するのは簡単です: 単純に p を法とする数を定義する再帰を計算して、ゼロに合同な数 (mod p )を見つけるか、見つけます。繰り返されるモジュラス。この手法を使用して、彼は最初の 300 万個の素数のうち 1,166 個がシルベスター数の約数であることを発見し 、これらの素数のどれもシルベスター数を分割する平方を持たないことを発見しました。シルベスター数の因数として発生する素数の集合は、すべての素数の集合の中で密度ゼロです実際、 xより小さいそのような素数の数は$O(\pi (x)/\log \log \log x)$ .

次の表は、これらの数の既知の因数分解を示しています (すべて素数である最初の 4 つを除く):

n	s nの因数
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 × P156
11	73 ×C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
18	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
20	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

通常、P nと C nはn桁の長さの素数と因数分解されていない合成数を表します。

アプリケーション

Boyer, Galicki & Kollár (2005) use the properties of Sylvester's sequence to define large numbers of Sasakian Einstein manifolds having the differential topology of odd-dimensional spheres or exotic spheres. They show that the number of distinct Sasakian Einstein metrics on a topological sphere of dimension 2n − 1 is at least proportional to s_n and hence has double exponential growth with n.

Galambos & Woeginger (1995)が説明しているように、 Brown (1979)とLiang (1980)は Sylvester のシーケンスから導出された値を使用して、オンラインビン パッキングアルゴリズムの下限の例を作成しました。 Seiden & Woeginger (2005)も同様に、シーケンスを使用して、2 次元切削素材アルゴリズムのパフォーマンスを下限にしています。

Znám の問題は、セット内の各数値が除算されますが、他のすべての数値の積に 1 を加えたものには等しくない数値のセットに関する問題です。不等式の要件がなければ、シルベスターの数列の値で問題が解決します。その要件により、シルベスターのシーケンスを定義するものと同様の繰り返しから派生した他のソリューションがあります。 Znám の問題の解決策は、表面特異点の分類 (Brenton and Hill 1988) および非決定論的有限オートマトンの理論への応用があります。

 ([[#CITEREF|]]) describes an application of the closest approximations to one by k-term sums of unit fractions, in lower-bounding the number of divisors of any perfect number, and Miller (1919) uses the same property to upper bound the size of certain groups.

関連項目

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

参考文献

 

• Badea, Catalin (1993). “A theorem on irrationality of infinite series and applications”. Acta Arithmetica 63 (4): 313–323. doi:10.4064/aa-63-4-313-323. MR1218459. 
• Badea, Catalin (1995年). “On some criteria for irrationality for series of positive rationals: a survey”. 2008年9月11日時点のオリジナルよりアーカイブ。
• Boyer, Charles P.; Galicki, Krzysztof; Kollár, János (2005). “Einstein metrics on spheres”. Annals of Mathematics 162 (1): 557–580. arXiv:math.DG/0309408. doi:10.4007/annals.2005.162.557. MR2178969. 
• Brenton, Lawrence; Hill, Richard (1988). “On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities”. Pacific Journal of Mathematics 133 (1): 41–67. doi:10.2140/pjm.1988.133.41. MR0936356. http://projecteuclid.org/euclid.pjm/1102689567. 
• Brown, D. J. (1979). A lower bound for on-line one-dimensional bin packing algorithms. Tech. Rep. R-864. Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign. 
• Curtiss, D. R. (1922). “On Kellogg's diophantine problem”. American Mathematical Monthly 29 (10): 380–387. doi:10.2307/2299023. JSTOR 2299023. 
• Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei (2005). “Non-uniqueness and radius of cyclic unary NFAs”. International Journal of Foundations of Computer Science 16 (5): 883–896. doi:10.1142/S0129054105003352. MR2174328. http://www.cs.umanitoba.ca/~mdomarat/pubs/DESW_dcfs.ps. 
• Erdős, Paul; Graham, Ronald L. (1980). Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève. MR0592420 
• Galambos, Gábor; Woeginger, Gerhard J. (1995). “On-line bin packing — A restricted survey”. Mathematical Methods of Operations Research 42 (1): 25. doi:10.1007/BF01415672. MR1346486. 
• Golomb, Solomon W. (1963). “On certain nonlinear recurring sequences”. American Mathematical Monthly 70 (4): 403–405. doi:10.2307/2311857. JSTOR 2311857. MR0148605. 
• Graham, R.; Knuth, D. E.; Patashnik, O. (1989). Concrete Mathematics (2nd ed.). Addison-Wesley. Exercise 4.37. ISBN 0-201-55802-5 
• Guy, Richard K. (2004). “E24 Irrationality sequences”. Unsolved Problems in Number Theory (3rd ed.). Springer-Verlag. p. 346. ISBN 0-387-20860-7. Zbl 1058.11001. https://books.google.com/books?id=1AP2CEGxTkgC&pg=PA346 
• Guy, Richard; Nowakowski, Richard (1975). “Discovering primes with Euclid”. Delta (Waukesha) 5 (2): 49–63. MR0384675. 
• Jones, Rafe (2006). “The density of prime divisors in the arithmetic dynamics of quadratic polynomials”. Journal of the London Mathematical Society 78 (2): 523–544. arXiv:math.NT/0612415. Bibcode: 2006math.....12415J. doi:10.1112/jlms/jdn034. 
• Liang, Frank M. (1980). “A lower bound for on-line bin packing”. Information Processing Letters 10 (2): 76–79. doi:10.1016/S0020-0190(80)90077-0. MR0564503. 
• Miller, G. A. (1919). “Groups possessing a small number of sets of conjugate operators”. Transactions of the American Mathematical Society 20 (3): 260–270. doi:10.2307/1988867. JSTOR 1988867. 
• Odoni, R. W. K. (1985). “On the prime divisors of the sequence w_n+1 =1+w₁⋯w_n”. Journal of the London Mathematical Society. Series II 32: 1–11. doi:10.1112/jlms/s2-32.1.1. Zbl 0574.10020. 
• Rosenman, Martin; Underwood, F. (1933). “Problem 3536”. American Mathematical Monthly 40 (3): 180–181. doi:10.2307/2301036. JSTOR 2301036. 
• Salzer, H. E. (1947). “The approximation of numbers as sums of reciprocals”. American Mathematical Monthly 54 (3): 135–142. doi:10.2307/2305906. JSTOR 2305906. MR0020339. 
• Seiden, Steven S.; Woeginger, Gerhard J. (2005). “The two-dimensional cutting stock problem revisited”. Mathematical Programming 102 (3): 519–530. doi:10.1007/s10107-004-0548-1. MR2136225. 
• Soundararajan, K. (2005). Approximating 1 from below using n Egyptian fractions. arXiv:math.CA/0502247. 
• Sylvester, J. J. (1880). “On a point in the theory of vulgar fractions”. American Journal of Mathematics 3 (4): 332–335. doi:10.2307/2369261. JSTOR 2369261. 
• Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. pp. 82–89. ISBN 0-201-52989-0 

外部リンク

• KS Brown の MathPages からの二次和の不合理性。
• Weisstein, Eric W. "Sylvester's Sequence". mathworld.wolfram.com (英語).