Difference between revisions of "Sylvester's sequence"

Sylvester's sequence $a_1,a_2,a_3,\ldots$ is defined recursively by setting $a_1=2$ and $a_k = a_1 \ldots a_{k-1}+1$ for all subsequent k, thus the sequence begins

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence A000058 in OEIS).

The elements of this sequence are mutually coprime, so after factoring k of them, one is guaranteed to have at least k prime factors.

There is a connection to the finding primes project: It is a result of Odoni that the number of primes less than n that can divide any one of the $a_k$ is $O(n / \log n \log\log\log n)$ rather than $O(n / \log n)$ (the prime number theorem bound). If we then factor the first k elements of this sequence, we must get a prime of size at least $k\log k \log \log \log k$ or so.

It is also conjectured that this sequence is square-free; if so, $a_k, a_k-1$ form a pair of square-free integers, settling a toy problem in the finding primes project.