Mixing
Longest sequence of consecutive integers which are not coprime with $n!$
$begingroup$
For any integer $n$, the factorial $n!$ is the product of all positive integers up to and including $n$. Then in the sequence
$$n!+2,n!+3,... ,n!+n$$
the first term is divisible by $2$, the second term is divisible by $3$, and so on. Thus, this is a sequence of $(n − 1)$ consecutive composite integers, which definitely not coprime with $n!$.
Question: Is this the longest sequence of consecutive integers which are not coprime with $n!$ (less than $n!$)?
On the other words, is $(n-1)$ is the length of the longest sequence of consecutive integers which less than $n$ factorial and not coprime with it? Or can we find longer?
number-theory elementary-number-theory factorial
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
$endgroup$
add a comment |
$begingroup$
For any integer $n$, the factorial $n!$ is the product of all positive integers up to and including $n$. Then in the sequence
$$n!+2,n!+3,... ,n!+n$$
the first term is divisible by $2$, the second term is divisible by $3$, and so on. Thus, this is a sequence of $(n − 1)$ consecutive composite integers, which definitely not coprime with $n!$.
Question: Is this the longest sequence of consecutive integers which are not coprime with $n!$ (less than $n!$)?
On the other words, is $(n-1)$ is the length of the longest sequence of consecutive integers which less than $n$ factorial and not coprime with it? Or can we find longer?
number-theory elementary-number-theory factorial
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
$endgroup$
$begingroup$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17
add a comment |
$begingroup$
For any integer $n$, the factorial $n!$ is the product of all positive integers up to and including $n$. Then in the sequence
$$n!+2,n!+3,... ,n!+n$$
the first term is divisible by $2$, the second term is divisible by $3$, and so on. Thus, this is a sequence of $(n − 1)$ consecutive composite integers, which definitely not coprime with $n!$.
Question: Is this the longest sequence of consecutive integers which are not coprime with $n!$ (less than $n!$)?
On the other words, is $(n-1)$ is the length of the longest sequence of consecutive integers which less than $n$ factorial and not coprime with it? Or can we find longer?
number-theory elementary-number-theory factorial
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
$endgroup$
For any integer $n$, the factorial $n!$ is the product of all positive integers up to and including $n$. Then in the sequence
$$n!+2,n!+3,... ,n!+n$$
the first term is divisible by $2$, the second term is divisible by $3$, and so on. Thus, this is a sequence of $(n − 1)$ consecutive composite integers, which definitely not coprime with $n!$.
Question: Is this the longest sequence of consecutive integers which are not coprime with $n!$ (less than $n!$)?
On the other words, is $(n-1)$ is the length of the longest sequence of consecutive integers which less than $n$ factorial and not coprime with it? Or can we find longer?
number-theory elementary-number-theory factorial
number-theory elementary-number-theory factorial
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
edited Jan 10 at 1:51
Eevee Trainer
5,7571936
5,7571936
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
asked Jan 10 at 1:42
Ocean YuOcean Yu
389
389
$begingroup$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17
add a comment |
$begingroup$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17
$begingroup$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
It is apparent that $n!pm k$ are composite and not coprime to $n!$ for $2le kle n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! pm 1$ happen to be composite.
$n! pm 1$ are both composite for $n=5,8,9,10,13dots$; however, $n! pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$
By careful choice, examples of $n$ can be manufactured where $n!pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5mid (n+4)$, $7mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.
What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
$endgroup$
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
add a comment |
$begingroup$
Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7quad &quad {7!-2,;7!-3,;7!-4,;7!-5,;7!-6,;7!-7,;7!-8,;7!-9,;7!-10}$$
which is a string of length $9$ (and all terms are less than $7!$)
answered Jan 10 at 2:04
lulululu
40.7k24879
$endgroup$
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
add a comment |
$begingroup$
In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).
The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.
As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.
To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.
I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
$endgroup$
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%2f3068141%2flongest-sequence-of-consecutive-integers-which-are-not-coprime-with-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
It is apparent that $n!pm k$ are composite and not coprime to $n!$ for $2le kle n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! pm 1$ happen to be composite.
$n! pm 1$ are both composite for $n=5,8,9,10,13dots$; however, $n! pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$
By careful choice, examples of $n$ can be manufactured where $n!pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5mid (n+4)$, $7mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.
What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
$endgroup$
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
add a comment |
$begingroup$
It is apparent that $n!pm k$ are composite and not coprime to $n!$ for $2le kle n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! pm 1$ happen to be composite.
$n! pm 1$ are both composite for $n=5,8,9,10,13dots$; however, $n! pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$
By careful choice, examples of $n$ can be manufactured where $n!pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5mid (n+4)$, $7mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.
What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
$endgroup$
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
add a comment |
$begingroup$
It is apparent that $n!pm k$ are composite and not coprime to $n!$ for $2le kle n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! pm 1$ happen to be composite.
$n! pm 1$ are both composite for $n=5,8,9,10,13dots$; however, $n! pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$
By careful choice, examples of $n$ can be manufactured where $n!pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5mid (n+4)$, $7mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.
What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
$endgroup$
It is apparent that $n!pm k$ are composite and not coprime to $n!$ for $2le kle n$. Of course, $n!$ is itself composite and not coprime to itself. Longer runs of composite numbers (up to lengths roughly $2n$) can occur when one or especially both of $n! pm 1$ happen to be composite.
$n! pm 1$ are both composite for $n=5,8,9,10,13dots$; however, $n! pm 1$ whether or not composite will be relatively prime to $n!$ and such longer runs do not satisfy the requirement in the original question of containing only "not coprime" numbers. For example, the run $114,dots,126$ identified in a previous answer surrounds $5!=120$ but includes $5!-1=7cdot 17$ and $5!+1=11^2$. Each of $7,11,17$ is relatively prime to $5!$
By careful choice, examples of $n$ can be manufactured where $n!pm k$ continues to afford composite, not coprime, values for consecutive integers even when $k>n$. For example, if $n$ is odd, then $n!pm (n+1)$ will be divisible by $2$ (as will every value of $k=n+2i+1$). We can further identify values of $n$ such that $n$ is odd and $3mid (n+2)$. The Chinese Remainder Theorem says this process can be repeated to find values of $n$ that meet those requirements and further meet $5mid (n+4)$, $7mid (n+6)$, etc. to extend the runs of consecutive numbers not coprime to $n!$ by a few with each step. An example of this kind of extension was given in a previous answer.
What is apparent, however, is that every time we look to make the run of "not coprime" numbers a few longer, the values of $n$ and hence $n!$ grow very rapidly, quickly outstripping our ability to calculate by hand or even with simple calculators.
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
answered Jan 10 at 19:39
Keith BackmanKeith Backman
1,2691812
1,2691812
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
add a comment |
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
$begingroup$
Is there any research showing the low bound to this question? Of course one can get as long as he wish which 'not coprime' with n!, but it will reach so big that out of calculation. What I am interesting is, the bound in range of <n!.
$endgroup$
– Ocean Yu
Jan 14 at 5:49
add a comment |
$begingroup$
Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7quad &quad {7!-2,;7!-3,;7!-4,;7!-5,;7!-6,;7!-7,;7!-8,;7!-9,;7!-10}$$
which is a string of length $9$ (and all terms are less than $7!$)
answered Jan 10 at 2:04
lulululu
40.7k24879
$endgroup$
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
add a comment |
$begingroup$
Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7quad &quad {7!-2,;7!-3,;7!-4,;7!-5,;7!-6,;7!-7,;7!-8,;7!-9,;7!-10}$$
which is a string of length $9$ (and all terms are less than $7!$)
answered Jan 10 at 2:04
lulululu
40.7k24879
$endgroup$
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
add a comment |
$begingroup$
Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7quad &quad {7!-2,;7!-3,;7!-4,;7!-5,;7!-6,;7!-7,;7!-8,;7!-9,;7!-10}$$
which is a string of length $9$ (and all terms are less than $7!$)
answered Jan 10 at 2:04
lulululu
40.7k24879
$endgroup$
Starting with $x=7$ and noting that $8,9,10$ all have factors in common with $7!$, we quickly get the counterexample $$n=7quad &quad {7!-2,;7!-3,;7!-4,;7!-5,;7!-6,;7!-7,;7!-8,;7!-9,;7!-10}$$
which is a string of length $9$ (and all terms are less than $7!$)
answered Jan 10 at 2:04
lulululu
40.7k24879
edited Jan 10 at 2:09
answered Jan 10 at 2:04
lulululu
40.7k24879
answered Jan 10 at 2:04
lulululu
40.7k24879
answered Jan 10 at 2:04
lulululu
40.7k24879
40.7k24879
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
add a comment |
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
@RolfHoyer Yes. My guess, and it is just a guess, is that that is the answer, at least most of the time.
$endgroup$
– lulu
Jan 10 at 2:11
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
thanks. that's correct. it is the counterexample. What is the longest one? Is 2n is the limited longest?
$endgroup$
– Ocean Yu
Jan 10 at 2:13
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
@OceanYu Bertrand's postulate tells us that there is a prime between $n$ and $2n$ so my method can't get a string as long as $2n$, However, that doesn't prove that there isn't one.
$endgroup$
– lulu
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
Looks like the longest sequence is not that easy to find in practice. for $n=12$ there are sequences of length 12.
$endgroup$
– Rolf Hoyer
Jan 10 at 2:15
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
$begingroup$
@RolfHoyer Ah, good. I think that example would be worth posting as a separate answer.
$endgroup$
– lulu
Jan 10 at 2:16
add a comment |
$begingroup$
In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).
The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.
As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.
To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.
I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
$endgroup$
add a comment |
$begingroup$
In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).
The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.
As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.
To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.
I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
$endgroup$
add a comment |
$begingroup$
In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).
The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.
As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.
To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.
I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
$endgroup$
In general I think it's hard to determine to find the longest possible sequence of consecutive values coprime to $n!$ (equivalently the longest possible sequence of consecutive values all divisible by a prime less than or equal to $n$).
The answer given by lulu can be used to generate a sequence of length $p-2$, where $p$ is the least prime greater than $n$. But this bound is not sharp.
As an example, for the value $n=12$ the longest such sequence is of length 13. An example is given by the range from 114 to 126.
To see that no sequence of length 14 is possible, note that in any sequence of fourteen values there are exactly 7 even values, at most 1 odd value divisible by each of 7 and 11, at most 2 odd values divisible by 5, and at most 3 odd values divisible by 3. This adds up to 14, so such a sequence is only possible if no odd values are divisible by more than one of 3,5,7,11. However, the existence of 3 odd values divisible by 3 requires both the largest and smallest odd values to be divisible by 3, and the existence of 2 odd values divisible by 5 requires either the largest or smallest odd value to be divisible by 5.
I don't see a general method to prove such a sharp bound for arbitrary $n$ that avoids getting in the weeds to this extent, so I think there might not be a nice answer in general.
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
answered Jan 10 at 2:33
Rolf HoyerRolf Hoyer
11.2k31629
11.2k31629
add a comment |
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%2f3068141%2flongest-sequence-of-consecutive-integers-which-are-not-coprime-with-n%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$
Not following...the example you wrote does not contain any numbers smaller than $n!$, so what does that condition mean? Did you mean to write $n!-i$ instead of $n!+i$?
$endgroup$
– lulu
Jan 10 at 2:06
$begingroup$
Well if $n+1$ is composite then $n! + (n+1)$ isn't coprime either. (Although it will be if $n+1 $ is prime). $n! + k$ will only be coprime with $n!$ if all the prime factors of $k$ are larger than $n$. So the first term that isn't coprime will be $n! + p$ where $p$ is the first prime greater than $n$.
$endgroup$
– fleablood
Jan 10 at 20:17