info prev up next book cdrom email home

Sylvester's Sequence

The sequence defined by $e_0=2$ and the Recurrence Relation

e_n=1+\prod_{i=0}^{n-1} e_i = {e_{n-1}}^2-e_{n-1}+1.
\end{displaymath} (1)

This sequence arises in Euclid's proof that there are an Infinite number of Primes. The proof proceeds by constructing a sequence of Primes using the Recurrence Relation
e_{n+1}=e_0e_1\cdots e_n+1
\end{displaymath} (2)

(Vardi 1991). Amazingly, there is a constant
E\approx 1.264084735306
\end{displaymath} (3)

such that
e_n=\left\lfloor{E^{2^{n+1}}+{\textstyle{1\over 2}}}\right\rfloor
\end{displaymath} (4)

(Vardi 1991, Graham et al. 1994). The first few numbers in Sylvester's sequence are 2, 3, 7, 43, 1807, 3263443, 10650056950807, ... (Sloane's A000058). The $e_n$ satisfy
\sum_{n=0}^\infty {1\over e_n}=1.
\end{displaymath} (5)

In addition, if $0<x<1$ is an Irrational Number, then the $n$th term of an infinite sum of unit fractions used to represent $x$ as computed using the Greedy Algorithm must be smaller than $1/e_n$.

The $n$ of the first few Prime $e_n$ are 0, 1, 2, 3, 5, .... Vardi (1991) gives a lists of factors less than $5\times
10^7$ of $e_n$ for $n\leq 200$ and shows that $e_n$ is Composite for $6\leq n\leq 17$. Furthermore, all numbers less than $2.5\times 10^{15}$ in Sylvester's sequence are Squarefree, and no Squareful numbers in this sequence are known (Vardi 1991).

See also Euclid's Theorems, Greedy Algorithm, Squarefree, Squareful


Graham, R. L.; Knuth, D. E.; and Patashnik, O. Research problem 4.65 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

Sloane, N. J. A. Sequence A000058/M0865 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Vardi, I. ``Are All Euclid Numbers Squarefree?'' and ``PowerMod to the Rescue.'' §5.1 and 5.2 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 82-89, 1991.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein