Difference between revisions of "Sylvester's sequence"
(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.) |
m (fix OEIS link) |
||
| (2 intermediate revisions by one other user not shown) | |||
| 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:// | + | : 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. | ||
| 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. | ||
| − | |||
| − | |||
| − | |||
* [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]] | * [[wikipedia:Sylvester's_sequence|The Wikipedia entry for this sequence]] | ||
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.
