In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
, Sylvester's sequence is an
integer sequence
In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers.
An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
in which each term of the sequence 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 .
Sylvester's sequence is named after
James Joseph Sylvester
James Joseph Sylvester (3 September 1814 – 15 March 1897) was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory, and combinatorics. He played a leadership ...
, who first investigated it in 1880. Its values grow
doubly exponentially, and the sum of its
reciprocal
Reciprocal may refer to:
In mathematics
* Multiplicative inverse, in mathematics, the number 1/''x'', which multiplied by ''x'' gives the product 1, also known as a ''reciprocal''
* Reciprocal polynomial, a polynomial obtained from another pol ...
s 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 factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
izations are known only for a few of its terms. Values derived from this sequence have also been used to construct finite
Egyptian fraction
An Egyptian fraction is a finite sum of distinct unit fractions, such as
\frac+\frac+\frac.
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from ea ...
representations of 1,
Sasakian Einstein manifold
In differential geometry and mathematical physics, an Einstein manifold is a Riemannian or pseudo-Riemannian differentiable manifold whose Ricci tensor is proportional to the metric. They are named after Albert Einstein because this condition ...
s, and hard instances for
online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
s.
Formal definitions
Formally, Sylvester's sequence can be defined by the formula
:
The
product of the empty set is 1, so ''s''
0 = 2.
Alternatively, one may define the sequence by the
recurrence
:
with ''s''
0 = 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
:
for a number ''E'' that is approximately 1.26408473530530... . This formula has the effect of the following
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
:
:''s''
0 is the nearest
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
to ''E''
2; ''s''
1 is the nearest integer to ''E''
4; ''s''
2 is the nearest integer to ''E''
8; for ''s
n'', 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 ''s''
''n'' and taking its repeated
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
.
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,
, but they can also be defined by a product formula very similar to that defining Sylvester's sequence:
:
Connection with Egyptian fractions
The
unit fractions formed by the
reciprocals of the values in Sylvester's sequence generate an
infinite series:
:
The
partial sums of this series have a simple form,
:
This may be proved by induction, or more directly by noting that the recursion implies that
:
so the sum
telescopes
A telescope is a device used to observe distant objects by their emission, absorption, or reflection of electromagnetic radiation. Originally meaning only an optical instrument using lenses, curved mirrors, or a combination of both to observ ...
:
Since this sequence of partial sums (''s''
''j'' − 2)/(''s''
''j'' − 1) converges to one, the overall series forms an infinite
Egyptian fraction
An Egyptian fraction is a finite sum of distinct unit fractions, such as
\frac+\frac+\frac.
That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators differ from ea ...
representation of the number one:
:
One can find finite Egyptian fraction representations of one, of any length, by truncating this series and subtracting one from the last denominator:
:
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
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
(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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
. This sequence provides an example showing that double-exponential growth is not enough to cause an integer sequence to be an
irrationality sequence.
To make this more precise, it follows from results of that, if a sequence of integers
grows quickly enough that
:
and if the series
:
converges to a rational number ''A'', then, for all ''n'' after some point, this sequence must be defined by the same recurrence
:
that can be used to define Sylvester's sequence.
conjectured that, in results of this type, the inequality bounding the growth of the sequence could be replaced by a weaker condition,
:
surveys progress related to this conjecture; see also .
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 number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s, 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.
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 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
divisor
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
s of Sylvester numbers, 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: indeed, the number of such primes less than ''x'' is
.
The following table shows known factorizations of these numbers (except the first four, which are all prime):
As is customary, P''n'' and C''n'' denote prime numbers and unfactored
composite numbers ''n'' digits long.
Applications
use the properties of Sylvester's sequence to define large numbers of
Sasakian Einstein manifold
In differential geometry and mathematical physics, an Einstein manifold is a Riemannian or pseudo-Riemannian differentiable manifold whose Ricci tensor is proportional to the metric. They are named after Albert Einstein because this condition ...
s having the
differential topology
In mathematics, differential topology is the field dealing with the topological properties and smooth properties of smooth manifolds. In this sense differential topology is distinct from the closely related field of differential geometry, which ...
of odd-dimensional
spheres
The Synchronized Position Hold Engage and Reorient Experimental Satellite (SPHERES) are a series of miniaturized satellites developed by MIT's Space Systems Laboratory for NASA and US Military, to be used as a low-risk, extensible test bed for the ...
or
exotic sphere
In an area of mathematics called differential topology, an exotic sphere is a differentiable manifold ''M'' that is homeomorphic but not diffeomorphic to the standard Euclidean ''n''-sphere. That is, ''M'' is a sphere from the point of view of a ...
s. They show that the number of distinct Sasakian Einstein
metrics on a
topological sphere
A sphere () is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. A sphere is the set of points that are all at the same distance from a given point in three-dimensional space.. That given point is the ce ...
of dimension 2''n'' − 1 is at least proportional to ''s''
''n'' and hence has double exponential growth with ''n''.
As describe, and used values derived from Sylvester's sequence to construct lower bound examples for
online
In computer technology and telecommunications, online indicates a state of connectivity and offline indicates a disconnected state. In modern terminology, this usually refers to an Internet connection, but (especially when expressed "on line" ...
bin packing algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s. similarly use the sequence to lower bound the performance of a two-dimensional cutting stock algorithm.
[In their work, Seiden and Woeginger refer to Sylvester's sequence as "Salzer's sequence" after the work of on closest approximation.]
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.
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
In number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number.
...
, and uses the same property to
upper bound the size of certain
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
.
See also
*
Cahen's constant
*
Primary pseudoperfect number
*
Leonardo number
Notes
References
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
Irrationality of Quadratic Sums from K. S. Brown's MathPages.
*
{{good article
Egyptian fractions
Integer sequences
Mathematical series
Number theory
Recurrence relations