Does the algorithm of the Greeks produce all prime numbers?
up vote
31
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 algorithms
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
asked Dec 2 at 22:19
Zidane
23625
|
show 3 more comments
up vote
31
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 algorithms
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
asked Dec 2 at 22:19
Zidane
23625
24
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♦
Dec 2 at 22:28
2
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
Dec 2 at 22:33
8
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
Dec 3 at 0:21
7
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
Dec 3 at 2:17
3
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11
|
show 3 more comments
up vote
31
down vote
favorite
up vote
31
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 algorithms
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
asked Dec 2 at 22:19
Zidane
23625
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 algorithms
nt.number-theory prime-numbers algorithms
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
asked Dec 2 at 22:19
Zidane
23625
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
asked Dec 2 at 22:19
Zidane
23625
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
edited Dec 4 at 0:58
Konstantinos Kanakoglou
3,01021033
3,01021033
asked Dec 2 at 22:19
Zidane
23625
asked Dec 2 at 22:19
Zidane
23625
asked Dec 2 at 22:19
Zidane
23625
23625
24
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♦
Dec 2 at 22:28
2
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
Dec 2 at 22:33
8
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
Dec 3 at 0:21
7
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
Dec 3 at 2:17
3
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11
|
show 3 more comments
24
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♦
Dec 2 at 22:28
2
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
Dec 2 at 22:33
8
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
Dec 3 at 0:21
7
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
Dec 3 at 2:17
3
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11
24
24
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♦
Dec 2 at 22:28
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♦
Dec 2 at 22:28
2
2
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
Dec 2 at 22:33
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
Dec 2 at 22:33
8
8
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
Dec 3 at 0:21
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
Dec 3 at 0:21
7
7
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
Dec 3 at 2:17
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
Dec 3 at 2:17
3
3
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11
|
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
29
down vote
accepted
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 37 do appear within the first 50 terms of the sequence.
answered Dec 2 at 22:26
user44191
2,5231026
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
29
down vote
accepted
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 37 do appear within the first 50 terms of the sequence.
answered Dec 2 at 22:26
user44191
2,5231026
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
add a comment |
up vote
29
down vote
accepted
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 37 do appear within the first 50 terms of the sequence.
answered Dec 2 at 22:26
user44191
2,5231026
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
add a comment |
up vote
29
down vote
accepted
up vote
29
down vote
accepted
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 37 do appear within the first 50 terms of the sequence.
answered Dec 2 at 22:26
user44191
2,5231026
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 37 do appear within the first 50 terms of the sequence.
answered Dec 2 at 22:26
user44191
2,5231026
edited Dec 3 at 21:32
answered Dec 2 at 22:26
user44191
2,5231026
answered Dec 2 at 22:26
user44191
2,5231026
answered Dec 2 at 22:26
user44191
2,5231026
2,5231026
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
add a comment |
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
Any idea what the euristic expected asymptotic growth of the least missed prime $p_n$ at step $n$ would be? (Sorry for this sentence's violence to the English language.)
– Yaakov Baruch
Dec 3 at 14:07
1
1
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
@YaakovBaruch I don't have an answer for you, but I do see multiple references to a heuristic argument by Daniel Shanks in the Bulletin of the Institute of Combinatorics and its Applications (specifically, in 1991). Unfortunately, I can't find the argument itself.
– user44191
Dec 3 at 19:10
2
2
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
The OEIS A000945 b-file gives $p_{50}=31$
– Henry
Dec 3 at 21:32
add a comment |
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
24
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♦
Dec 2 at 22:28
2
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
Dec 2 at 22:33
8
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
Dec 3 at 0:21
7
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
Dec 3 at 2:17
3
@Acccumulation Which is exactly how empty products are treated, yes.
– Johannes Hahn
Dec 4 at 1:11