Sylvester's sequence

From HandWiki
Revision as of 18:53, 6 March 2023 by Scavis (talk | contribs) (over-write)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Short description: Doubly exponential integer sequence
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 an integer sequence in which each term is the product of the previous terms, plus one. The first few terms of the sequence 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

[math]\displaystyle{ s_n = 1 + \prod_{i=0}^{n-1} s_i. }[/math]

The product of the empty set is 1, so s0 = 2.

Alternatively, one may define the sequence by the recurrence

[math]\displaystyle{ \displaystyle s_i = s_{i-1}(s_{i-1}-1)+1, }[/math] with 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

[math]\displaystyle{ s_n = \left\lfloor E^{2^{n+1}}+\frac{1}{2} \right\rfloor,\! }[/math]

for a number E that is approximately 1.26408473530530...[1] (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, [math]\displaystyle{ 2^{2^n} \!+ 1 }[/math], but they can also be defined by a product formula very similar to that defining Sylvester's sequence:

[math]\displaystyle{ F_n = 2 + \prod_{i=0}^{n-1} F_i. }[/math]

Connection with Egyptian fractions

The unit fractions formed by the reciprocals of the values in Sylvester's sequence generate an infinite series:

[math]\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. }[/math]

The partial sums of this series have a simple form,

[math]\displaystyle{ \sum_{i=0}^{j-1} \frac1{s_i} = 1 - \frac{1}{s_j-1} = \frac{s_j-2}{s_j-1}. }[/math]

This may be proved by induction, or more directly by noting that the recursion implies that

[math]\displaystyle{ \frac{1}{s_i-1}-\frac{1}{s_{i+1}-1} = \frac{1}{s_i}, }[/math]

so the sum telescopes

[math]\displaystyle{ \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}. }[/math]

Since this sequence of partial sums (sj − 2)/(sj − 1) converges to one, the overall series forms an infinite Egyptian fraction representation of the number one:

[math]\displaystyle{ 1 = \frac12 + \frac13 + \frac17 + \frac1{43} + \frac1{1807} + \cdots. }[/math]

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

[math]\displaystyle{ 1 = \tfrac12 + \tfrac13 + \tfrac16, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{42}, \quad 1 = \tfrac12 + \tfrac13 + \tfrac17 + \tfrac1{43} + \tfrac1{1806},\quad \dots. }[/math]

The sum of the first k terms of the infinite series provides the closest possible underestimate of 1 by any k-term Egyptian fraction.[2] 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.

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. This sequence provides an example showing that double-exponential growth is not enough to cause an integer sequence to be an irrationality sequence.[3]

To make this more precise, it follows from results of (Badea 1993) that, if a sequence of integers [math]\displaystyle{ a_n }[/math] grows quickly enough that

[math]\displaystyle{ a_n\ge a_{n-1}^2-a_{n-1}+1, }[/math]

and if the series

[math]\displaystyle{ A=\sum\frac1{a_i} }[/math]

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

[math]\displaystyle{ a_n= a_{n-1}^2-a_{n-1}+1 }[/math]

that can be used to define Sylvester's sequence.

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

[math]\displaystyle{ \lim_{n\rightarrow\infty} \frac{a_n}{a_{n-1}^2}=1. }[/math]

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

Divisibility and factorizations

If i < j, it follows from the definition that sj ≡ 1 (mod si ). 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. More strongly, no prime factor of a number in the sequence can be congruent to 5 modulo 6, and the sequence can be used to prove that there are infinitely many primes congruent to 7 modulo 12.[4]

Question, Web Fundamentals.svg Unsolved problem in mathematics:
Are all the terms in Sylvester's sequence squarefree?
(more unsolved problems in mathematics)

Much remains unknown about the factorization of the numbers in the Sylvester's sequence. 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. Using this technique he found that 1166 out of the first three million primes are divisors of Sylvester numbers,[5] and that none of these primes has a square that divides a Sylvester number. The set of primes which can occur as factors of Sylvester numbers is of density zero in the set of all primes:[6] indeed, the number of such primes less than x is [math]\displaystyle{ O(\pi(x) / \log\log\log x) }[/math].[7]

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

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

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

Applications

(Boyer Galicki) 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 sn and hence has double exponential growth with n.

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

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

D. R. 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 upper bound the size of certain groups.

See also

Notes

  1. ↑ (Graham Knuth) set this as an exercise; see also (Golomb 1963).
  2. ↑ This claim is commonly attributed to (Curtiss 1922), but (Miller 1919) appears to be making the same statement in an earlier paper. See also (Rosenman Underwood), (Salzer 1947), and (Soundararajan 2005).
  3. ↑ Guy (2004).
  4. ↑ Guy & Nowakowski (1975).
  5. ↑ This appears to be a typo, as Andersen finds 1167 prime divisors in this range.
  6. ↑ Jones (2006).
  7. ↑ Odoni (1985).
  8. ↑ All prime factors p of Sylvester numbers sn with p < 5×107 and n ≤ 200 are listed by Vardi. Ken Takusagawa lists the factorizations up to s9 and the factorization of s10. The remaining factorizations are from a list of factorizations of Sylvester's sequence maintained by Jens Kruse Andersen. Retrieved 2014-06-13.
  9. ↑ In their work, Seiden and Woeginger refer to Sylvester's sequence as "Salzer's sequence" after the work of (Salzer 1947) on closest approximation.
  10. ↑ Domaratzki et al. (2005).

References

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Sylvester%27s_sequence&oldid=2630148"