In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. Its first few terms are
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence A000058 in the OEIS). Sylvester's sequence is named after James Joseph Sylvester, who first investigated it in 1880. Its values grow doubly exponentially, and the sum of its reciprocals forms a series of unit fractions that converges to 1 more rapidly than any other series of unit fractions. The recurrence by which it is defined allows the numbers in the sequence to be 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 terms. Values derived from this sequence have also been used to construct finite Egyptian fraction representations of 1, Sasakian Einstein manifolds, and hard instances for online algorithms.
Formal definitions Formally, Sylvester's sequence can be defined by the formula
s n = 1 + ∏ i = 0 n − 1 s i . {\displaystyle s_{n}=1+\prod _{i=0}^{n-1}s_{i}.}
The product of the empty set is 1, so this formula gives s0 = 2, without need of a separate base case. Alternatively, one may define the sequence by the recurrence
s i = s i − 1 ( s i − 1 − 1 ) + 1 , {\displaystyle \displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,} with the base case s0 = 2. It is straightforward to show by induction that this is equivalent to the other definition.
Closed form formula and asymptotics The Sylvester numbers grow doubly exponentially as a function of n. Specifically, it can be shown that
s n = ⌊ E 2 n + 1 + 1 2 ⌋ , {\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,\!}
for a number E that is approximately 1.26408473530530... (sequence A076393 in the OEIS). This formula has the effect of the following algorithm:
s0 is the nearest integer to E 2; s1 is the nearest integer to E 4; s2 is the nearest integer to E 8; for sn, take E 2, 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 sn 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 Fn ; the Fermat numbers are usually defined by a doubly exponential formula, 2 2 n + 1 {\displaystyle 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 + ∏ i = 0 n − 1 F i . {\displaystyle F_{n}=2+\prod _{i=0}^{n-1}F_{i}.}
Connection with Egyptian fractions The unit fractions formed by the reciprocals of the values in Sylvester's sequence generate an infinite series:
∑ i = 0 ∞ 1 s i = 1 2 + 1 3 + 1 7 + 1 43 + 1 1807 + ⋯ . {\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 .}
The partial sums of this series have a simple form,
… excerpt ends here. Continue reading the full article.
