Does the algorithm of the Greeks produce all prime numbers?
up vote
9
down vote
favorite
Let ${cal P}$ be the set of prime numbers. Define a subset ${cal P}'={p_1,p_2,p_3,cdots}$ of ${cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${cal P}$ dividing $1+p_1cdots p_n$. Is there any obstruction to ${cal P}'={cal P}$ ?
nt.number-theory prime-numbers
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
9
down vote
favorite
Let ${cal P}$ be the set of prime numbers. Define a subset ${cal P}'={p_1,p_2,p_3,cdots}$ of ${cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${cal P}$ dividing $1+p_1cdots p_n$. Is there any obstruction to ${cal P}'={cal P}$ ?
nt.number-theory prime-numbers
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
6
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
2
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago
add a comment |
up vote
9
down vote
favorite
up vote
9
down vote
favorite
Let ${cal P}$ be the set of prime numbers. Define a subset ${cal P}'={p_1,p_2,p_3,cdots}$ of ${cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${cal P}$ dividing $1+p_1cdots p_n$. Is there any obstruction to ${cal P}'={cal P}$ ?
nt.number-theory prime-numbers
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Let ${cal P}$ be the set of prime numbers. Define a subset ${cal P}'={p_1,p_2,p_3,cdots}$ of ${cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${cal P}$ dividing $1+p_1cdots p_n$. Is there any obstruction to ${cal P}'={cal P}$ ?
nt.number-theory prime-numbers
nt.number-theory prime-numbers
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Zidane
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 4 hours ago
Zidane
811
asked 4 hours ago
Zidane
811
811
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Zidane is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
6
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
2
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago
add a comment |
6
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
2
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago
6
6
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
2
2
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
9
down vote
According to Booker - A variant of the Euclid-Mullin sequence containing every prime, as of 2016, this question remains open.
One of the central questions in this area was posed by Mullin [6] in 1963: Does the Euclid–Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [9] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open.
The OEIS contains a decent amount of information. For example, the primes up to 29 do appear within the first 50 terms of the sequence.
edited 23 mins ago
LSpice
2,76822527
answered 3 hours ago
user44191
2,169723
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
According to Booker - A variant of the Euclid-Mullin sequence containing every prime, as of 2016, this question remains open.
One of the central questions in this area was posed by Mullin [6] in 1963: Does the Euclid–Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [9] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open.
The OEIS contains a decent amount of information. For example, the primes up to 29 do appear within the first 50 terms of the sequence.
edited 23 mins ago
LSpice
2,76822527
answered 3 hours ago
user44191
2,169723
add a comment |
up vote
9
down vote
According to Booker - A variant of the Euclid-Mullin sequence containing every prime, as of 2016, this question remains open.
One of the central questions in this area was posed by Mullin [6] in 1963: Does the Euclid–Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [9] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open.
The OEIS contains a decent amount of information. For example, the primes up to 29 do appear within the first 50 terms of the sequence.
edited 23 mins ago
LSpice
2,76822527
answered 3 hours ago
user44191
2,169723
add a comment |
up vote
9
down vote
up vote
9
down vote
According to Booker - A variant of the Euclid-Mullin sequence containing every prime, as of 2016, this question remains open.
One of the central questions in this area was posed by Mullin [6] in 1963: Does the Euclid–Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [9] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open.
The OEIS contains a decent amount of information. For example, the primes up to 29 do appear within the first 50 terms of the sequence.
edited 23 mins ago
LSpice
2,76822527
answered 3 hours ago
user44191
2,169723
According to Booker - A variant of the Euclid-Mullin sequence containing every prime, as of 2016, this question remains open.
One of the central questions in this area was posed by Mullin [6] in 1963: Does the Euclid–Mullin sequence contain every prime number? Despite a compelling heuristic argument of Shanks [9] that the answer is yes, even the broader question of whether there is any Euclid sequence containing every prime number remains open.
The OEIS contains a decent amount of information. For example, the primes up to 29 do appear within the first 50 terms of the sequence.
edited 23 mins ago
LSpice
2,76822527
answered 3 hours ago
user44191
2,169723
edited 23 mins ago
LSpice
2,76822527
edited 23 mins ago
LSpice
2,76822527
edited 23 mins ago
LSpice
2,76822527
2,76822527
answered 3 hours ago
user44191
2,169723
answered 3 hours ago
user44191
2,169723
answered 3 hours ago
user44191
2,169723
2,169723
add a comment |
add a comment |
Zidane is a new contributor. Be nice, and check out our Code of Conduct.
Zidane is a new contributor. Be nice, and check out our Code of Conduct.
Zidane is a new contributor. Be nice, and check out our Code of Conduct.
Zidane is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f316743%2fdoes-the-algorithm-of-the-greeks-produce-all-prime-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
I don't think I would call this "the algorithm of the Greeks", since Eratosthenes produced an algorithm which definitely captures all the primes.
– Todd Trimble♦
3 hours ago
This and variations have been considered. There is no nice (and known to me) alternate characterization of any of these variants. You should check the OEIS for more information. Gerhard "Should Always Check The OEIS" Paseman, 2018.12.02.
– Gerhard Paseman
3 hours ago
2
In the spirit of mathoverflow.net/questions/45951/sexy-vacuity, let me point out that the special case $p_1 = 2$ is unnecessary here — the single general case “$p_n$ is the smallest prime dividing $1 + p_1 cdots p_{n-1}$” suffices to define the whole sequence.
– Peter LeFanu Lumsdaine
1 hour ago
Note that this is not an algorithm at all, just a recursively defined sequence. An algorithm also needs to specify the way to compute it; especially in this case how to compute the smallest prime divisor.
– YCor
2 mins ago