Difference between revisions of "Sylvester's sequence"

From Polymath Wiki
Jump to: navigation, search
m (I...made a gigantic slip, forgot what squarefree meant. Sorry.)
m (fix OEIS link)
 
Line 1: Line 1:
 
'''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
 
'''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 [http://www.research.att.com/~njas/sequences/A000058 A000058] in OEIS).
+
: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence [http://oeis.org/A000058 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.
 
The elements of this sequence are mutually coprime, so after factoring k of them, one is guaranteed to have at least k prime factors.

Latest revision as of 04:30, 30 September 2015

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.