คุยกับผู้ใช้:พ.น.บุญรอด/ทดลองเขียน

Image:Sylvester-square.svg|thumb|300px|Graphical demonstration of the convergence of the sum 1/2 + 1/3 + 1/7 + 1/43 + ... to 1. Each row of k squares of side length 1/k has total area 1/k, and all the squares together exactly cover a larger square with area 1. Squares with side lengths 1/1807 or smaller are too small to see in the figure and are not shown.

ในวิชาทฤษฎีจำนวน ลำดับซิลเวสเตอร์ เป็นลำดับของจำนวนเต็มซึ่งแต่ละจำนวนเกิดจากผลคูณของจำนวนทั้งหมดในลำดับก่อนหน้านี้ทั้งหมดบวกด้วย 1 ซึ่งพจน์แรกๆ ของลำดับนี้ได้แก่ 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (ลำดับ  A000058).

ลำดับนี้ตั้งชื่อตามโจเซฟ โจนส์ ซิลเวสเตอร์ ซึ่งได้investigateขึ้นในปี พ.ศ. 2423 โดยที่ค่าของลำดับนั้นเพิ่มขึ้นอย่างDouble exponential function และผลบวกของส่วนกลับของแต่ละพจน์มีค่าเข้าใกล้ 1 more rapidly than any other series of unit fractions with the same sum. The recurrence relation|recurrence by which it is defined allows the numbers in the sequence to be integer factorization|factored more easily than other numbers of the same magnitude, but, due to the rapid growth of the sequence, complete prime factorizations are known only for a few of its members. Values derived from this sequence have also been used to construct finite Egyptian fraction representations of 1, Sasakian manifold|Sasakian Einstein manifolds, and hard instances for online algorithms.

Formal definitions

Formally, Sylvester's sequence can be defined by the formula

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

The empty product|product of an empty set is 1, so s₀ = 2.

Alternatively, one may define the sequence by the recurrence relation|recurrence

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

It is straightforward to show by induction that this is equivalent to the other definition.

Connection with Egyptian fractions

The unit fractions formed by the Multiplicative inverse|reciprocals of the values in Sylvester's sequence generate an Series (mathematics)|infinite series:

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

The partial sums of this series have a simple form,

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

as may be proved by induction. Clearly this identity is true for j = 0, as both sides are zero. For larger j, expanding the left side of the identity using the induction hypothesis produces

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

as was to be proved. Since this sequence of partial sums (s_j-2)/(s_j-1) converges to one, the overall series forms an infinite Egyptian fraction representation of the number one:

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

One can find finite Egyptian fraction representations of one, of any length, by truncating this series and subtracting one from the last denominator:

$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$

The sum of the first k terms of the infinite series provides the closest possible underestimate of 1 by any k-term Egyptian fraction. For example, the first four terms add to 1805/1806, and therefore any Egyptian fraction for a number in the open interval (1805/1806,1) requires at least five terms.

It is possible to interpret the Sylvester sequence as the result of a greedy algorithm for Egyptian fractions, that at each step chooses the smallest possible denominator that makes the partial sum of the series be less than one. Alternatively, the terms of the sequence after the first can be viewed as the denominators of the odd greedy expansion of 1/2.

Closed form formula and asymptotics

The Sylvester numbers grow double exponential function|doubly exponentially as a function of n. Specifically, it can be shown that

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

for a number E that is approximately 1.264. This formula has the effect of the following algorithm:

s₀ is the nearest integer to E²; s₁ is the nearest integer to E⁴; s₂ is the nearest integer to E⁸; for s_n, take E², square it n more times, and take the nearest integer.

This would only be a practical algorithm if we had a better way of calculating E to the requisite number of places than calculating s_n and taking its repeated square root.

The double-exponential growth of the Sylvester sequence is unsurprising if one compares it to the sequence of Fermat numbers F_n; the Fermat numbers are usually defined by a doubly exponential formula, $2^{2^{n}}+1$, but they can also be defined by a product formula very similar to that defining Sylvester's sequence:

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

Uniqueness of quickly growing series with rational sums

As Sylvester himself observed, Sylvester's sequence seems to be unique in having such quickly growing values, while simultaneously having a series of reciprocals that converges to a rational number.

To make this more precise, it follows from results of Badea (1993) that, if a sequence of integers $a_{n}$ grows quickly enough that

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

and if the series

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

converges to a rational number A, then, for all n after some point, this sequence must be defined by the same recurrence

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

that can be used to define Sylvester's sequence.

Paul Erdős|Erdős (1980) Erdős conjecture|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.

Divisibility and factorizations

If i < j, it follows from the definition that s_j ≡ 1 (mod s_i). Therefore, every two numbers in Sylvester's sequence are relatively prime. The sequence can be used to prove that there are infinitely many prime numbers, as any prime can divide at most one number in the sequence.

Some effort has been expended in an attempt to factor the numbers in Sylvester's sequence, but much remains unknown about their factorization. For instance, it is not known if all numbers in the sequence are Square-free integer|squarefree, although all the known terms are.

As Vardi (1991) describes, it is easy to determine which Sylvester number (if any) a given prime p divides: simply compute the recurrence defining the numbers modulo p until finding either a number that is congruent to zero (mod p) or finding a repeated modulus. Via this technique he found that 1166 out of the first three million primes are divisors of Sylvester numbers, and that none of these primes has a square that divides a Sylvester number. A general result of Jones (2006) implies that the set of prime factors of Sylvester numbers has density zero in the set of all primes.

The following table shows known factorizations of these numbers, (except the first four, which are all prime):

n	Factors of sn
4	13 × 139
5	3263443, which is prime
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9119521 × 6212157481
8	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × P68
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 × C6649
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
18	50201023123 × 139263586549 × C53339
19	C106721
20	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

As is customary, Pn and Cn denote prime and composite numbers n digits long.

Applications

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

As Galambos and Woeginger (1995) describe, Brown (1979) and Liang (1980) used values derived from Sylvester's sequence to construct lower bound examples for online algorithm|online bin packing algorithms. Seiden and Woeginger (2005) similarly use the sequence to lower bound the performance of a two-dimensional cutting stock algorithm.

Znám's problem concerns sets of numbers such that each number in the set divides but is not equal to the product of all the other numbers, plus one. Without the inequality requirement, the values in Sylvester's sequence would solve the problem; with that requirement, it has other solutions derived from recurrences similar to the one defining Sylvester's sequence. Solutions to Znám's problem have applications to the classification of surface singularities (Brenton and Hill 1988) and to the theory of nondeterministic finite automata (Domaratzki et al. 2005).

Curtiss (1922) 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 lower bound the size of certain groups.

See also

• Cahen's constant
• Primary pseudoperfect number

References

• Badea, Catalin (1993). "A theorem on irrationality of infinite series and applications". Acta Arithmetica. 63: 313–323. MR1218459.

• Badea, Catalin (1995). "On some criteria for irrationality for series of positive rationals: a survey" (PDF).

• 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 MR2178969.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)

• Brenton, Lawrence and 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. MR0936356.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)

• 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. {{cite journal}}: Cite journal ต้องการ |journal= (help)

• Curtiss, D. R. (1922). "On Kellogg's diophantine problem". American Mathematical Monthly. 29: 380–387.

• Domaratzki, Michael; Ellul, Keith; Jeffrey Shallit (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. {{cite journal}}: ข้อความ "Shallit, Jeffrey; Wang, Ming-Wei" ถูกละเว้น (help)CS1 maint: multiple names: authors list (ลิงก์)

• Paul Erdős (1980). Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève. MR0592420. {{cite book}}: ข้อความ "Erdős, Paul and Ronald Graham" ถูกละเว้น (help); ข้อความ "Graham, Ronald L." ถูกละเว้น (help)

• Galambos, Gábor; Woeginger, Gerhard J. (1995). "On-line bin packing — A restricted survey". Mathematical Methods of Operations Research. 42 (1). doi:10.1007/BF01415672. MR1346486.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)

• Golomb, Solomon W. (1963). "On certain nonlinear recurring sequences". American Mathematical Monthly. 70 (4): 403–405. MR0148605.

• Ron Graham (1989). Concrete Mathematics (2nd ed. ed.). Addison-Wesley. pp. Exercise 4.37. ISBN 0-201-55802-5. {{cite book}}: |edition= has extra text (help); ข้อความ "Graham, R.; Donald Knuth" ถูกละเว้น (help); ข้อความ "Knuth, D. E.; Patashnik, O." ถูกละเว้น (help)

• Jones, Rafe (2006). "The density of prime divisors in the arithmetic dynamics of quadratic polynomials". arXiv:math.NT/0612415. {{cite journal}}: Cite journal ต้องการ |journal= (help)

• 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.

• Rosenman, Martin (1933). "Problem 3536". American Mathematical Monthly. 40 (3): 180.

• Salzer, H. E. (1947). "The approximation of numbers as sums of reciprocals". American Mathematical Monthly. 54 (3): 135–142. 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.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)

• Soundararajan, K. (2005). "Approximating 1 from below using n Egyptian fractions". arXiv:math.CA/0502247. {{cite journal}}: Cite journal ต้องการ |journal= (help)

• Sylvester, J. J. (1880). "On a point in the theory of vulgar fractions". American Journal of Mathematics. 3 (4): 332–335.

• Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. pp. 82–89. ISBN 0-201-52989-0.

External links

• Irrationality of Quadratic Sums, from K. S. Brown's MathPages.

• เอริก ดับเบิลยู. ไวส์สไตน์, "Sylvester's Sequence" จากแมทเวิลด์.

Category:Number theory Category:Integer sequences Category:Egyptian fractions Category:Mathematical series Category:Recurrence relations ca:Seqüència de Sylvester he:סדרת סילבסטר sl:Sylvestrovo zaporedje tr:Sylvester'ın dizisi zh:西爾維斯特數列