Difference between revisions of "Sylvester's sequence"

From Polymath Wiki
Jump to: navigation, search
(Proposed simple proof the sequence is square-free, which would tie up a loose end in the primes project. Hope this helps someone. This is my first edit.)
Line 8: Line 8:
  
 
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.
 
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} <\math>. Then <math> a_k=n^2+n+1 <\math>. Since <math> n^2 < n^2+n+1 < (n+1)^2 <\math>, <math> a_k <math> cannot be a square, and the sequence is squarefree.
  
 
* [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]]
 
* [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]]

Revision as of 20:18, 23 August 2010

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]