Sylvester's sequence
Sylvester's sequence is an integer sequence in number theory, defined recursively starting with e_0 = 2 and e_{n} = e_{n-1}^2 - e_{n-1} + 1 for n \geq 1, or equivalently, each term is the product of all preceding terms plus one.[1] The first few terms are 2, 3, 7, 43, 1807, 3263443, 10650056950807, and so on, forming a strictly increasing sequence of positive integers.[1] Named after the mathematician James Joseph Sylvester, the sequence was introduced in his 1880 paper on the theory of vulgar (common) fractions, where it arose in the study of Egyptian fraction representations. A defining property of Sylvester's sequence is that the sum of the reciprocals of its terms equals exactly 1: \sum_{n=0}^{\infty} \frac{1}{e_n} = 1.[2] This makes it the expansion of 1 obtained by the greedy algorithm for Egyptian fractions, in which each subsequent denominator is the smallest integer such that its unit fraction does not exceed the current remainder.[2] The terms are pairwise coprime, meaning \gcd(e_i, e_j) = 1 for all i \neq j, which follows directly from the recursive construction since each term is congruent to 1 modulo the product of earlier terms.[3] The sequence exhibits doubly exponential growth, with e_n \approx E^{2^{n+1}} where E \approx 1.2640847353 is a constant related to the infinite product over the terms.[4] This rapid growth has connections to Euclid's proof of the infinitude of primes, as the terms resemble Euclid numbers (products of prior primes plus one, but here generalized to prior terms).[4] Sylvester's sequence appears in various number-theoretic contexts, including conjectures on primality (e.g., early terms are prime, but later ones are composite and square-free up to large indices) and irrationality criteria for series.[2][3]History and Overview
Historical Development
James Joseph Sylvester introduced what is now known as Sylvester's sequence in 1880 while serving as a professor of mathematics at Johns Hopkins University. In his paper "On a Point in the Theory of Vulgar Fractions," published in the American Journal of Mathematics—a journal he helped establish at the university—Sylvester explored the sequence in the context of representing rational numbers as sums of unit fractions, known as Egyptian fractions.[5] This work formed part of his broader investigations into Diophantine approximations, which sought precise rational approximations to real numbers and their applications to number theory problems. Sylvester's formal definition of the sequence was novel, though it built on earlier ideas in greedy expansions for Egyptian fractions and proofs of the infinitude of primes. For instance, Fibonacci described a greedy algorithm for decomposing rationals into unit fractions in his 1202 treatise Liber Abaci, which prioritizes the largest possible unit fraction at each step.[6] Similarly, Euclid's ancient proof of infinitely many primes in Elements (c. 300 BCE) employed a recursive construction akin to the sequence's growth, generating new primes from products of previous ones plus one.[4] Sylvester's contribution distinguished itself by explicitly defining the sequence to achieve the greedy expansion of unity into distinct unit fractions, emphasizing its role in Diophantine analysis.[5] Following its introduction, the sequence received further attention in the early 20th century, particularly in studies of Diophantine equations and fraction approximations. In 1922, David Raymond Curtiss examined properties of the sequence in relation to Kellogg's Diophantine problem, applying it to bound the number of divisors in Egyptian fraction sums and highlighting its utility in approximation theory.[7] This work underscored the sequence's enduring relevance in number theory, bridging Sylvester's initial insights with later developments in analytic techniques.[8]Basic Concept and Motivation
Sylvester's sequence emerges from the ancient problem of representing rational numbers, particularly 1, as sums of distinct unit fractions—a practice known as Egyptian fractions, which avoids common denominators to simplify arithmetic in early mathematical systems. The motivation lies in finding efficient decompositions that use the minimal number of terms while ensuring the fractions are distinct and positive. This leads naturally to the greedy algorithm, which at each step selects the largest possible unit fraction less than or equal to the remaining value, thereby minimizing the number of terms required for an exact representation.[9] The sequence itself consists of positive integers constructed such that each subsequent term is one greater than the product of all preceding terms, a property that guarantees pairwise coprimality among the terms—meaning any two share no common prime factors greater than 1. This coprimality is crucial for applications in fraction expansions, as it prevents overlaps in denominators and facilitates unique decompositions. Introduced by James Joseph Sylvester in his 1880 paper on vulgar fractions, the sequence provides a canonical example of how such constructions can yield elegant solutions to decomposition problems.[9] Conceptually, Sylvester's sequence is intimately linked to the greedy algorithm applied specifically to the fraction 1, where the denominators generated by successive greedy choices form the sequence itself. This process arises organically when seeking the "underapproximation" that keeps partial sums strictly less than 1 until the infinite limit, producing an infinite series of unit fractions whose reciprocals sum precisely to 1. For instance, the reciprocals of the first few terms—starting with 1/2, then adding 1/3, 1/7, and 1/43—yield partial sums like 0.5, approximately 0.833, 0.976, and 0.999, progressively approaching 1 without exceeding it, illustrating the sequence's role in bounding the expansion.[9]Definition and Construction
Recursive Definition
Sylvester's sequence \{s_n\}_{n=1}^\infty is defined recursively by the initial term s_1 = 2 and the relation s_{n+1} = s_n(s_n - 1) + 1 for n \geq 1.[5] This recurrence can equivalently be expressed as s_{n+1} = 1 + \prod_{k=1}^n s_k, which highlights the multiplicative growth inherent in the construction.[4] To establish that all terms s_n are integers greater than 1, proceed by induction. The base case holds since s_1 = 2 is an integer greater than 1. Assuming s_n is an integer greater than 1, then s_n - 1 \geq 1 is a positive integer, so s_{n+1} = s_n(s_n - 1) + 1 is the sum of the product of two positive integers and 1, yielding an integer greater than s_n > 1. Thus, by induction, all s_n are integers exceeding 1. Consecutive terms are coprime, as \gcd(s_n, s_{n+1}) = \gcd\left(s_n, s_n(s_n - 1) + 1\right) = \gcd(s_n, 1) = 1, since s_n(s_n - 1) + 1 \equiv 1 \pmod{s_n}.[4] The recursion further ensures mutual coprimality among all terms: for m < n, s_n \equiv 1 \pmod{s_m} because each subsequent term is constructed as 1 plus a multiple of the prior product including s_m, implying \gcd(s_m, s_n) = 1. This property arises directly from the iterative form, guaranteeing that no prime divides more than one term in the sequence.Initial Terms and Examples
The Sylvester's sequence is defined with initial term s_1 = 2, and each subsequent term given by s_{n+1} = 1 + \prod_{k=1}^n s_k. The first few terms are s_2 = 3, s_3 = 7, s_4 = 43, s_5 = 1807, and s_6 = 3263443, demonstrating the sequence's extremely rapid growth even in its early stages.[1] For instance, the fourth term can be computed explicitly as s_4 = 1 + 2 \times 3 \times 7 = 43.[1] A key property of the sequence is that all terms are pairwise coprime, meaning \gcd(s_m, s_n) = 1 for any distinct indices m and n. This can be verified with simple examples, such as \gcd(s_3, s_4) = \gcd(7, 43) = 1 or \gcd(s_2, s_5) = \gcd(3, 1807) = 1.[1] This coprimality underpins connections to Egyptian fractions, where the reciprocal terms form a representation of unity. For example, the partial sum of the first three reciprocals is \frac{1}{2} + \frac{1}{3} + \frac{1}{7} = \frac{21}{42} + \frac{14}{42} + \frac{6}{42} = \frac{41}{42} = 1 - \frac{1}{2 \times 3 \times 7}, showing how the sum accumulates closely toward 1 while leaving a small remainder.[1]Core Mathematical Properties
Closed-Form Expression
A closed-form expression for the general term of Sylvester's sequence, starting with s_1 = 2, s_2 = 3, s_3 = 7, and so on, is given by s_n = \left\lfloor E^{2^n} + \frac{1}{2} \right\rfloor, where E \approx 1.2640847353053011 is Vardi's constant, the unique real number greater than 1 satisfying \sum_{n=1}^\infty E^{-2^n} = 1.[1][4] This formula arises from the double-exponential growth of the sequence defined by the recurrence s_{n+1} = s_n(s_n - 1) + 1. For large n, s_{n+1} \approx s_n^2, so taking natural logarithms yields \ln s_{n+1} \approx 2 \ln s_n. The precise growth is \ln s_n \approx 2^n \ln E, refined through the exact product form s_n = 1 + \prod_{k=1}^{n-1} s_k and the property that \sum_{n=1}^\infty \frac{1}{s_n} = 1, which determines the base E via the infinite sum condition above, ensuring the floor function captures the integer terms precisely.[10] Verification for small values confirms the expression: for n=1, \left\lfloor E^2 + \frac{1}{2} \right\rfloor = \left\lfloor 1.59791 + 0.5 \right\rfloor = \left\lfloor 2.09791 \right\rfloor = 2; for n=2, \left\lfloor E^4 + \frac{1}{2} \right\rfloor = \left\lfloor 2.55392 + 0.5 \right\rfloor = \left\lfloor 3.05392 \right\rfloor = 3; for n=3, \left\lfloor E^8 + \frac{1}{2} \right\rfloor = \left\lfloor 6.52264 + 0.5 \right\rfloor = \left\lfloor 7.02264 \right\rfloor = 7. The constant E is irrational, as established by applying the subspace theorem to the growth rate \alpha = \ln E of the sequence, proving \alpha (and thus E = e^\alpha) cannot be rational.[10]Asymptotic Growth
The terms of Sylvester's sequence grow double-exponentially with n, a property arising from the quadratic recurrence relation that approximately squares each successive term for large values. More precisely, \log s_n \approx 2^n \log E, where E \approx 1.2640847353053011 is the Vardi constant, highlighting the exponential growth in the logarithmic scale.[11][12] This leads to the asymptotic relation s_n \sim E^{2^n} as n \to \infty, with relative error o(1), meaning s_n / E^{2^n} \to 1. Tight bounds follow from the closed-form approximation: |s_n - E^{2^n}| < \frac{1}{2}.[4][13] The extraordinarily rapid growth has practical implications for computation; terms beyond s_6 = 3{,}263{,}443 or s_7 \approx 1.065 \times 10^{13} cannot be calculated directly using standard fixed-precision arithmetic and require big-integer implementations to handle the increasing digit lengths.[4]Connections to Egyptian Fractions
Unit Fraction Expansion of 1
Sylvester's sequence yields an explicit infinite Egyptian fraction representation of unity as the sum of distinct unit fractions whose denominators are the terms of the sequence itself:$1 = \sum_{n=1}^{\infty} \frac{1}{s_n},
where s_1 = 2 and s_{n+1} = s_n(s_n - 1) + 1 for n \geq 1. [14] This decomposition arises from the recursive construction of the sequence, ensuring that each $1/s_n is a unit fraction with integer denominator greater than the previous ones. [5] The equality holds in the limit due to a telescoping partial sum formula, which can be established by induction on the recurrence relation. [14] Let S_n = \sum_{k=1}^n \frac{1}{s_k}. For the base case n=1, S_1 = \frac{1}{2}, and s_2 - 1 = 2, so S_1 = 1 - \frac{1}{s_2 - 1}. [5] Assume S_n = 1 - \frac{1}{s_{n+1} - 1}. Then
S_{n+1} = S_n + \frac{1}{s_{n+1}} = 1 - \frac{1}{s_{n+1} - 1} + \frac{1}{s_{n+1}}.
Since s_{n+1} - 1 = s_n (s_n - 1) = \prod_{k=1}^n s_k by the defining property of the sequence, [5]
S_{n+1} = 1 - \frac{1}{s_{n+1} - 1} + \frac{1}{s_{n+1}} = 1 - \frac{s_{n+1} - (s_{n+1} - 1)}{s_{n+1} (s_{n+1} - 1)} = 1 - \frac{1}{s_{n+1} (s_{n+1} - 1)} = 1 - \frac{1}{s_{n+2} - 1},
as s_{n+2} - 1 = s_{n+1} (s_{n+1} - 1). [14] Thus, S_n = 1 - \frac{1}{s_{n+1} - 1} holds for all n. Given the doubly exponential growth of s_n, s_{n+1} \to \infty as n \to \infty, so S_n \to 1. [5] The denominators s_n in this expansion are distinct positive integers, as the sequence is strictly increasing for n \geq 1. [5] Moreover, the terms s_n are pairwise coprime, ensuring no common factors across denominators and reinforcing the distinctness in the unit fraction representation. [14] This property follows directly from the recursive definition, where each s_{n+1} \equiv 1 \pmod{s_n} and similarly modulo earlier terms. [5]