Difference between revisions of "Sylvester's sequence"

From Polymath1Wiki
Jump to: navigation, search
(New page: 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 sequenc...)
 
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 A000058 in OEIS).
+
: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sequence [http://www.research.att.com/~njas/sequences/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.
Line 9: Line 9:
 
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.
  
# [http://en.wikipedia.org/wiki/Sylvester%27s_sequence The Wikipedia entry for this sequence]
+
* [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]]

Revision as of 16:58, 19 August 2009

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.