Mixing
Condition on $n$ for no sequence to exist
$begingroup$
I've an integer $ngeq3$. What's the minimum possible value of $n$ so that no sequence $a_0,a_1,...,a_{n-1}$ exists where for all i:-
$1leq a_ileq10^9$ and all $a_i$s are distinct
gcd$(a_i,a_{(i+1)mod n})>1$
- gcd$(a_i,a_{(i+1)mod n},a_{(i+2)mod n})=1$.
What I thought was that all I've to do is to find prime numbers, until $p_i*p_{i+1}>10^9$. Then, I can assign these consecutive products to my $a_i$s, that is, $a_i=p_i*p_{i+1}$ for $0leq ileq n-2$ and $a_{n-1}=p_{n-1}*p_0$ ($p_0=2$). However, I'm not getting the correct answer using this. Can someone please tell me what did I miss in these? Thanks:)
sequences-and-series number-theory elementary-number-theory prime-numbers
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
$endgroup$
add a comment |
$begingroup$
I've an integer $ngeq3$. What's the minimum possible value of $n$ so that no sequence $a_0,a_1,...,a_{n-1}$ exists where for all i:-
$1leq a_ileq10^9$ and all $a_i$s are distinct
gcd$(a_i,a_{(i+1)mod n})>1$
- gcd$(a_i,a_{(i+1)mod n},a_{(i+2)mod n})=1$.
What I thought was that all I've to do is to find prime numbers, until $p_i*p_{i+1}>10^9$. Then, I can assign these consecutive products to my $a_i$s, that is, $a_i=p_i*p_{i+1}$ for $0leq ileq n-2$ and $a_{n-1}=p_{n-1}*p_0$ ($p_0=2$). However, I'm not getting the correct answer using this. Can someone please tell me what did I miss in these? Thanks:)
sequences-and-series number-theory elementary-number-theory prime-numbers
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
$endgroup$
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57
add a comment |
$begingroup$
I've an integer $ngeq3$. What's the minimum possible value of $n$ so that no sequence $a_0,a_1,...,a_{n-1}$ exists where for all i:-
$1leq a_ileq10^9$ and all $a_i$s are distinct
gcd$(a_i,a_{(i+1)mod n})>1$
- gcd$(a_i,a_{(i+1)mod n},a_{(i+2)mod n})=1$.
What I thought was that all I've to do is to find prime numbers, until $p_i*p_{i+1}>10^9$. Then, I can assign these consecutive products to my $a_i$s, that is, $a_i=p_i*p_{i+1}$ for $0leq ileq n-2$ and $a_{n-1}=p_{n-1}*p_0$ ($p_0=2$). However, I'm not getting the correct answer using this. Can someone please tell me what did I miss in these? Thanks:)
sequences-and-series number-theory elementary-number-theory prime-numbers
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
$endgroup$
I've an integer $ngeq3$. What's the minimum possible value of $n$ so that no sequence $a_0,a_1,...,a_{n-1}$ exists where for all i:-
$1leq a_ileq10^9$ and all $a_i$s are distinct
gcd$(a_i,a_{(i+1)mod n})>1$
- gcd$(a_i,a_{(i+1)mod n},a_{(i+2)mod n})=1$.
What I thought was that all I've to do is to find prime numbers, until $p_i*p_{i+1}>10^9$. Then, I can assign these consecutive products to my $a_i$s, that is, $a_i=p_i*p_{i+1}$ for $0leq ileq n-2$ and $a_{n-1}=p_{n-1}*p_0$ ($p_0=2$). However, I'm not getting the correct answer using this. Can someone please tell me what did I miss in these? Thanks:)
sequences-and-series number-theory elementary-number-theory prime-numbers
sequences-and-series number-theory elementary-number-theory prime-numbers
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
edited Jan 7 at 18:58
Ankita Gupta
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
asked Jan 7 at 18:47
Ankita GuptaAnkita Gupta
213
213
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57
add a comment |
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n geq 720,000$).
Edit: it turns out we can take $p=3401$, leading to $n geq 5,781,700$.
Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.
answered Jan 7 at 19:01
MindlackMindlack
3,37717
$endgroup$
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
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: "69"
};
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',
autoActivateHeartbeat: false,
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%2fmath.stackexchange.com%2fquestions%2f3065340%2fcondition-on-n-for-no-sequence-to-exist%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
$begingroup$
For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n geq 720,000$).
Edit: it turns out we can take $p=3401$, leading to $n geq 5,781,700$.
Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.
answered Jan 7 at 19:01
MindlackMindlack
3,37717
$endgroup$
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
add a comment |
$begingroup$
For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n geq 720,000$).
Edit: it turns out we can take $p=3401$, leading to $n geq 5,781,700$.
Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.
answered Jan 7 at 19:01
MindlackMindlack
3,37717
$endgroup$
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
add a comment |
$begingroup$
For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n geq 720,000$).
Edit: it turns out we can take $p=3401$, leading to $n geq 5,781,700$.
Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.
answered Jan 7 at 19:01
MindlackMindlack
3,37717
$endgroup$
For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n geq 720,000$).
Edit: it turns out we can take $p=3401$, leading to $n geq 5,781,700$.
Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.
answered Jan 7 at 19:01
MindlackMindlack
3,37717
edited Jan 7 at 19:09
answered Jan 7 at 19:01
MindlackMindlack
3,37717
answered Jan 7 at 19:01
MindlackMindlack
3,37717
answered Jan 7 at 19:01
MindlackMindlack
3,37717
3,37717
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
add a comment |
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
Where exactly should I put $p_2p_4$ and all those, because the condition 2 and 3 might be a problem if I'm not wrong
$endgroup$
– Ankita Gupta
Jan 7 at 19:03
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
No it won’t be a problem, I think.
$endgroup$
– Mindlack
Jan 7 at 19:04
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
Ok, I'll check that out. Thanks a lot
$endgroup$
– Ankita Gupta
Jan 7 at 19:05
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
$begingroup$
I got it. Thanks
$endgroup$
– Ankita Gupta
Jan 7 at 19:15
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
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%2fmath.stackexchange.com%2fquestions%2f3065340%2fcondition-on-n-for-no-sequence-to-exist%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
$begingroup$
Hi & welcome to MSE. One thing I want to make sure is I believe you intend your condition #$2$ to be for all $i$, not just for some $i$, is that correct?
$endgroup$
– John Omielan
Jan 7 at 18:57
$begingroup$
Yes, point 1,2 and 3 all for all i
$endgroup$
– Ankita Gupta
Jan 7 at 18:57