Sylvester's sequence

From Polymath Wiki
Revision as of 20:18, 23 August 2010 by Zomega (Talk | contribs)

Jump to: navigation, search

Sylvester's sequence [math]a_1,a_2,a_3,\ldots[/math] is defined recursively by setting [math]a_1=2[/math] and [math]a_k = a_1 \ldots a_{k-1}+1[/math] 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 [math]a_k[/math] is [math]O(n / \log n \log\log\log n)[/math] rather than [math]O(n / \log n)[/math] (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 [math]k\log k \log \log \log k[/math] or so.

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

Proposed proof of the above conjecture: Let [math]n=a_1\ldots a_{k-2} \lt\math\gt. Then \ltmath\gt a_k=n^2+n+1 \lt\math\gt. Since \ltmath\gt n^2 \lt n^2+n+1 \lt (n+1)^2 \lt\math\gt, \ltmath\gt a_k \ltmath\gt cannot be a square, and the sequence is squarefree. * [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]][/math]