Sylvester's sequence

From Wikipedia, the free encyclopedia

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.

In number theory, Sylvester's sequence is a sequence of integers in which each member of the sequence is the product of the previous members, plus one. That is, it is the sequence defined by the formula

$s_n = 1 + \prod_{i = 0}^{n - 1} s_i.$

The product of an empty set is 1, so s₀ = 2. The first few terms of the sequence are:

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence A000058 in OEIS).

Alternatively, we may define the sequence by the recurrence

$\displaystyle s_i = s_{i-1}(s_{i-1}-1)+1.$

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

Sylvester's sequence is named after James Joseph Sylvester, who first investigated it in 1880.

1 Connection with Egyptian fractions
2 Closed form formula and asymptotics
3 Uniqueness of quickly growing series with rational sums
4 Divisibility and factorizations
5 See also
6 References
7 External links

[edit] Connection with Egyptian fractions

We can prove by induction that

$\sum_{i=0}^{j-1} \frac1{s_i} = \frac{s_j-2}{s_j-1}.$

Clearly this is true for j = 0, as both sides are zero. For larger j, we can use the induction hypothesis to expand

$\sum_{i=0}^{j-1} \frac1{s_i} = \frac1{s_{j-1}}+\sum_{i=0}^{j-2} \frac1{s_i} = \frac1{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}.$

Therefore, the infinite series of unit fractions formed by the reciprocals of the Sylvester sequence converges to form an infinite Egyptian fraction representation of the number one:

$1 = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{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.

It is possible to view the Sylvester sequence as determined by 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.

[edit] Closed form formula and asymptotics

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

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

for a number E that is approximately 1.264 (Graham, Knuth, and Patashnik 1989); 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 growth is unsurprising if one compares them to the sequence of Fermat numbers F_n; the Fermat numbers are usually defined by a doubly exponential formula, $2^{2^n}+1$ , but thay 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$

Boyer et al. (2005) use Sylvester's sequence to define large numbers of Sasakian Einstein manifolds having the topology of odd-dimensional hyperspheres. They show that the number of distinct manifolds of this type, for a hypersphere of dimension 2n-1, is at least proportional to s_n'.

[edit] 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\ge a_{n-1}^2-a_{n-1}+1,$

and if the series

$A=\sum\frac1{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.

Erdős (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.

[edit] 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 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.

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

Factors of s_n
n	Factorization
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 × C1626
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15	17881 × 97822786011310111 × C6649
16	128551 × C13336
17	635263 × 1286773 × 21269959 × C26661
18	139263586549 × C53349

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

[edit] See also

[edit] References

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

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

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 MR 2178969.

Erdős, Paul and 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. MR 0592420.