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 arithmetic function, integer-valued functions. German mathematician Carl Friedrich Gauss (1777â ...
, 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, 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
Series may refer to:
People with the name
* Caroline Series (born 1951), English mathematician, daughter of George Series
* George Series (1920–1995), English physicist
Arts, entertainment, and media
Music
* Series, the ordered sets used in ...
of
unit fraction
A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, etc ...
s that converges to 1 more rapidly than any other series of unit fractions. The
recurrence
Recurrence and recurrent may refer to:
*''Disease recurrence'', also called relapse
*''Eternal recurrence'', or eternal return, the concept that the universe has been recurring, and will continue to recur, in a self-similar form an infinite number ...
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 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 i ...
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
Recurrence and recurrent may refer to:
*''Disease recurrence'', also called relapse
*''Eternal recurrence'', or eternal return, the concept that the universe has been recurring, and will continue to recur, in a self-similar form an infinite number ...
:
with ''s''
0 = 2.
It is straightforward to show by
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
:
:''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 language ...
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 .
E ...
.
The double-exponential growth of the Sylvester sequence is unsurprising if one compares it to the sequence of
Fermat number
In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form
:F_ = 2^ + 1,
where ''n'' is a non-negative integer. The first few Fermat numbers are:
: 3, 5, 17, 257, 65537, 42949672 ...
s ''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 fraction
A unit fraction is a rational number written as a fraction where the numerator is one and the denominator is a positive integer. A unit fraction is therefore the reciprocal of a positive integer, 1/''n''. Examples are 1/1, 1/2, 1/3, 1/4, 1/5, etc ...
s formed by the
reciprocals of the values in Sylvester's sequence generate an
infinite series
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, math ...
:
:
The
partial sums
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, math ...
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 observe ...
:
Since this sequence of partial sums (''s''
''j'' − 2)/(''s''
''j'' − 1) converges to one, the overall series forms an infinite
Egyptian fraction 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
In mathematics, the greedy algorithm for Egyptian fractions is a greedy algorithm, first described by Fibonacci, for transforming rational numbers into Egyptian fractions. An Egyptian fraction is a representation of an irreducible fraction as a sum ...
, 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
In number theory, the odd greedy expansion problem asks whether a greedy algorithm for finding Egyptian fractions with odd denominators always succeeds. , it remains unsolved.
Description
An Egyptian fraction represents a given rational number as ...
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 ration ...
. This sequence provides an example showing that double-exponential growth is not enough to cause an integer sequence to be an
irrationality sequence
In mathematics, a sequence of positive integers ''a'n'' is called an irrationality sequence if it has the property that for every sequence ''x'n'' of positive integers, the sum of the series
: \sum_^\infty \frac
exists (that is, it conve ...
.
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
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 199 ...
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
In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
. 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 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 ...
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
In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-fr ...
, 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 i ...
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 spheres. They show that the number of distinct Sasakian Einstein
metrics
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathema ...
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" or ...
bin packing
The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has ma ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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
In number theory, Znám's problem asks which sets of integers have the property that each integer in the set is a proper divisor of the product of the other integers in the set, plus 1. Znám's problem is named after the Slovak mathematician Šte ...
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
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state tr ...
.
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.
T ...
, and uses the same property to
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
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
In mathematics, and particularly in number theory, ''N'' is a primary pseudoperfect number if it satisfies the Egyptian fraction equation
:\frac + \sum_\frac = 1,
where the sum is over only the prime divisors of ''N''.
Properties
Equivalentl ...
*
Leonardo number
The Leonardo numbers are a sequence of numbers given by the recurrence:
:
L(n) =
\begin
1 & \mbox n = 0 \\
1 & \mbox n = 1 \\
L(n - 1) + L(n - 2) + 1 & \mbox n > 1 \\
\end
Edsger ...
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