No. of ways for $(((n mod i) mod j) mod k) mod n$
$begingroup$
Consider $3$ integers, $i, j, k$ all between $1$ and $m$, both exclusive. Consider
$$(((n mod i)mod j)mod k)mod n$$
where $n$ is another positive integer. Suppose the maximum value of the above expression in $L$. Find the number of ways to choose the triple $(i,j,k)$ so as to get $L$.
My try:-
Since in the end we have $mod n$, $L$ can be $n-1$ at max. But, the thing is if it can even achieve that value! For instance, if we take both $n$, $m$ to be $4$, I checked by hit and trial that $L$ will be $1$. This got me thinking, is there a general representation for these "concatenated" mods? I've no more idea on how to proceed. Even if a hint will do. Thanks :)
combinatorics number-theory elementary-number-theory modular-arithmetic
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
$endgroup$
add a comment |
$begingroup$
Consider $3$ integers, $i, j, k$ all between $1$ and $m$, both exclusive. Consider
$$(((n mod i)mod j)mod k)mod n$$
where $n$ is another positive integer. Suppose the maximum value of the above expression in $L$. Find the number of ways to choose the triple $(i,j,k)$ so as to get $L$.
My try:-
Since in the end we have $mod n$, $L$ can be $n-1$ at max. But, the thing is if it can even achieve that value! For instance, if we take both $n$, $m$ to be $4$, I checked by hit and trial that $L$ will be $1$. This got me thinking, is there a general representation for these "concatenated" mods? I've no more idea on how to proceed. Even if a hint will do. Thanks :)
combinatorics number-theory elementary-number-theory modular-arithmetic
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
$endgroup$
$begingroup$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41
add a comment |
$begingroup$
Consider $3$ integers, $i, j, k$ all between $1$ and $m$, both exclusive. Consider
$$(((n mod i)mod j)mod k)mod n$$
where $n$ is another positive integer. Suppose the maximum value of the above expression in $L$. Find the number of ways to choose the triple $(i,j,k)$ so as to get $L$.
My try:-
Since in the end we have $mod n$, $L$ can be $n-1$ at max. But, the thing is if it can even achieve that value! For instance, if we take both $n$, $m$ to be $4$, I checked by hit and trial that $L$ will be $1$. This got me thinking, is there a general representation for these "concatenated" mods? I've no more idea on how to proceed. Even if a hint will do. Thanks :)
combinatorics number-theory elementary-number-theory modular-arithmetic
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
$endgroup$
Consider $3$ integers, $i, j, k$ all between $1$ and $m$, both exclusive. Consider
$$(((n mod i)mod j)mod k)mod n$$
where $n$ is another positive integer. Suppose the maximum value of the above expression in $L$. Find the number of ways to choose the triple $(i,j,k)$ so as to get $L$.
My try:-
Since in the end we have $mod n$, $L$ can be $n-1$ at max. But, the thing is if it can even achieve that value! For instance, if we take both $n$, $m$ to be $4$, I checked by hit and trial that $L$ will be $1$. This got me thinking, is there a general representation for these "concatenated" mods? I've no more idea on how to proceed. Even if a hint will do. Thanks :)
combinatorics number-theory elementary-number-theory modular-arithmetic
combinatorics number-theory elementary-number-theory modular-arithmetic
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
edited Jan 9 at 4:42
Ankita Gupta
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
asked Jan 8 at 10:42
Ankita GuptaAnkita Gupta
213
213
$begingroup$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41
add a comment |
$begingroup$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41
$begingroup$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A partial result in the case $n=m$.
Take $i=j=k=p$ where $p$ is the smallest integer greater than $n/2$. Then the result is $n-p$, the greatest integer lower than $n/2$.
Furthermore, if $i geq p$, then $n$ mod $i$ is less than $n-i leq n-p$ so the final result is kot greater than $n-p$.
If $i < p$, then $n$ mod $i$ is not greater than $p-1$ ($n$ odd) or $p-2$ ($p$ even) ie $n-p$.
A more careful study should yield the equality cases (I think it is $i=p,n-p$ and $j,k geq n-p$).
answered Jan 8 at 11:16
MindlackMindlack
4,910211
$endgroup$
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
add a comment |
$begingroup$
In every case the maximum remainder is N mod ((N/2)+1).
This will be the maximum value L. Therefore L = N mod((N/2)+1)
Case 1: if N = M
Here i has to be (N/2)+1, because only that will yield remainder as L. If i has any other value, the remainder will always be less than L.
Now j,k should be 1 more than (N mod i) (so that the remainder remains L) till M.
Therefore j,k = (N mod i)+1 ...... M (Let this count be c)
hence total number of ways = c^2
Case 2: if M > N
Subcase 1: i = (N/2)+1 will give remainder as L
j,k = (N mod i)+1 ...... M (Let this count be c)
Total count = c^2
Subcase 2: j = (N/2)+1 but for this to happen we have to ensure that (N mod i) = N
Therefore to make N mod i = N , i = N+1 ...... M
k = (N mod j)+1 ...... M (Let this count be c)
Total count = (M-N)*c
Subcase 3: k = (N/2)+1 but for this to happen
((N mod i) mod j) = N, Therefore i,j = N+1 ...... M
Total count = (M-N)^2
Hence total number of ways if M>N : c^2 + (M-N)*c + (M-N)^2
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
$endgroup$
add a comment |
Your Answer
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%2f3066023%2fno-of-ways-for-n-mod-i-mod-j-mod-k-mod-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A partial result in the case $n=m$.
Take $i=j=k=p$ where $p$ is the smallest integer greater than $n/2$. Then the result is $n-p$, the greatest integer lower than $n/2$.
Furthermore, if $i geq p$, then $n$ mod $i$ is less than $n-i leq n-p$ so the final result is kot greater than $n-p$.
If $i < p$, then $n$ mod $i$ is not greater than $p-1$ ($n$ odd) or $p-2$ ($p$ even) ie $n-p$.
A more careful study should yield the equality cases (I think it is $i=p,n-p$ and $j,k geq n-p$).
answered Jan 8 at 11:16
MindlackMindlack
4,910211
$endgroup$
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
add a comment |
$begingroup$
A partial result in the case $n=m$.
Take $i=j=k=p$ where $p$ is the smallest integer greater than $n/2$. Then the result is $n-p$, the greatest integer lower than $n/2$.
Furthermore, if $i geq p$, then $n$ mod $i$ is less than $n-i leq n-p$ so the final result is kot greater than $n-p$.
If $i < p$, then $n$ mod $i$ is not greater than $p-1$ ($n$ odd) or $p-2$ ($p$ even) ie $n-p$.
A more careful study should yield the equality cases (I think it is $i=p,n-p$ and $j,k geq n-p$).
answered Jan 8 at 11:16
MindlackMindlack
4,910211
$endgroup$
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
add a comment |
$begingroup$
A partial result in the case $n=m$.
Take $i=j=k=p$ where $p$ is the smallest integer greater than $n/2$. Then the result is $n-p$, the greatest integer lower than $n/2$.
Furthermore, if $i geq p$, then $n$ mod $i$ is less than $n-i leq n-p$ so the final result is kot greater than $n-p$.
If $i < p$, then $n$ mod $i$ is not greater than $p-1$ ($n$ odd) or $p-2$ ($p$ even) ie $n-p$.
A more careful study should yield the equality cases (I think it is $i=p,n-p$ and $j,k geq n-p$).
answered Jan 8 at 11:16
MindlackMindlack
4,910211
$endgroup$
A partial result in the case $n=m$.
Take $i=j=k=p$ where $p$ is the smallest integer greater than $n/2$. Then the result is $n-p$, the greatest integer lower than $n/2$.
Furthermore, if $i geq p$, then $n$ mod $i$ is less than $n-i leq n-p$ so the final result is kot greater than $n-p$.
If $i < p$, then $n$ mod $i$ is not greater than $p-1$ ($n$ odd) or $p-2$ ($p$ even) ie $n-p$.
A more careful study should yield the equality cases (I think it is $i=p,n-p$ and $j,k geq n-p$).
answered Jan 8 at 11:16
MindlackMindlack
4,910211
answered Jan 8 at 11:16
MindlackMindlack
4,910211
answered Jan 8 at 11:16
MindlackMindlack
4,910211
answered Jan 8 at 11:16
MindlackMindlack
4,910211
4,910211
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
add a comment |
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
Okay! And how about when n and m are not equal?
$endgroup$
– Ankita Gupta
Jan 8 at 11:54
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
When $n < m$, we can choose $i=j=k=n$ and $L=n$. The rest is an exercise for you for now. ;)
$endgroup$
– Mindlack
Jan 9 at 0:37
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Yeah I'm trying. But just for the record, $L=n$ is not possible, as I said that there's mod n in the end
$endgroup$
– Ankita Gupta
Jan 9 at 4:42
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
$begingroup$
Oh right, my mistake. Then I would say that when $m>n$ you cannot do better than when $m=n$ for pretty much the same reason. When $n > m$, I do not know yet.
$endgroup$
– Mindlack
Jan 9 at 9:01
add a comment |
$begingroup$
In every case the maximum remainder is N mod ((N/2)+1).
This will be the maximum value L. Therefore L = N mod((N/2)+1)
Case 1: if N = M
Here i has to be (N/2)+1, because only that will yield remainder as L. If i has any other value, the remainder will always be less than L.
Now j,k should be 1 more than (N mod i) (so that the remainder remains L) till M.
Therefore j,k = (N mod i)+1 ...... M (Let this count be c)
hence total number of ways = c^2
Case 2: if M > N
Subcase 1: i = (N/2)+1 will give remainder as L
j,k = (N mod i)+1 ...... M (Let this count be c)
Total count = c^2
Subcase 2: j = (N/2)+1 but for this to happen we have to ensure that (N mod i) = N
Therefore to make N mod i = N , i = N+1 ...... M
k = (N mod j)+1 ...... M (Let this count be c)
Total count = (M-N)*c
Subcase 3: k = (N/2)+1 but for this to happen
((N mod i) mod j) = N, Therefore i,j = N+1 ...... M
Total count = (M-N)^2
Hence total number of ways if M>N : c^2 + (M-N)*c + (M-N)^2
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
$endgroup$
add a comment |
$begingroup$
In every case the maximum remainder is N mod ((N/2)+1).
This will be the maximum value L. Therefore L = N mod((N/2)+1)
Case 1: if N = M
Here i has to be (N/2)+1, because only that will yield remainder as L. If i has any other value, the remainder will always be less than L.
Now j,k should be 1 more than (N mod i) (so that the remainder remains L) till M.
Therefore j,k = (N mod i)+1 ...... M (Let this count be c)
hence total number of ways = c^2
Case 2: if M > N
Subcase 1: i = (N/2)+1 will give remainder as L
j,k = (N mod i)+1 ...... M (Let this count be c)
Total count = c^2
Subcase 2: j = (N/2)+1 but for this to happen we have to ensure that (N mod i) = N
Therefore to make N mod i = N , i = N+1 ...... M
k = (N mod j)+1 ...... M (Let this count be c)
Total count = (M-N)*c
Subcase 3: k = (N/2)+1 but for this to happen
((N mod i) mod j) = N, Therefore i,j = N+1 ...... M
Total count = (M-N)^2
Hence total number of ways if M>N : c^2 + (M-N)*c + (M-N)^2
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
$endgroup$
add a comment |
$begingroup$
In every case the maximum remainder is N mod ((N/2)+1).
This will be the maximum value L. Therefore L = N mod((N/2)+1)
Case 1: if N = M
Here i has to be (N/2)+1, because only that will yield remainder as L. If i has any other value, the remainder will always be less than L.
Now j,k should be 1 more than (N mod i) (so that the remainder remains L) till M.
Therefore j,k = (N mod i)+1 ...... M (Let this count be c)
hence total number of ways = c^2
Case 2: if M > N
Subcase 1: i = (N/2)+1 will give remainder as L
j,k = (N mod i)+1 ...... M (Let this count be c)
Total count = c^2
Subcase 2: j = (N/2)+1 but for this to happen we have to ensure that (N mod i) = N
Therefore to make N mod i = N , i = N+1 ...... M
k = (N mod j)+1 ...... M (Let this count be c)
Total count = (M-N)*c
Subcase 3: k = (N/2)+1 but for this to happen
((N mod i) mod j) = N, Therefore i,j = N+1 ...... M
Total count = (M-N)^2
Hence total number of ways if M>N : c^2 + (M-N)*c + (M-N)^2
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
$endgroup$
In every case the maximum remainder is N mod ((N/2)+1).
This will be the maximum value L. Therefore L = N mod((N/2)+1)
Case 1: if N = M
Here i has to be (N/2)+1, because only that will yield remainder as L. If i has any other value, the remainder will always be less than L.
Now j,k should be 1 more than (N mod i) (so that the remainder remains L) till M.
Therefore j,k = (N mod i)+1 ...... M (Let this count be c)
hence total number of ways = c^2
Case 2: if M > N
Subcase 1: i = (N/2)+1 will give remainder as L
j,k = (N mod i)+1 ...... M (Let this count be c)
Total count = c^2
Subcase 2: j = (N/2)+1 but for this to happen we have to ensure that (N mod i) = N
Therefore to make N mod i = N , i = N+1 ...... M
k = (N mod j)+1 ...... M (Let this count be c)
Total count = (M-N)*c
Subcase 3: k = (N/2)+1 but for this to happen
((N mod i) mod j) = N, Therefore i,j = N+1 ...... M
Total count = (M-N)^2
Hence total number of ways if M>N : c^2 + (M-N)*c + (M-N)^2
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
answered Jan 9 at 8:59
AKSHAY KHANNAAKSHAY KHANNA
11
11
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%2f3066023%2fno-of-ways-for-n-mod-i-mod-j-mod-k-mod-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$
Do $i,j,k$ have to be different?
$endgroup$
– TonyK
Jan 8 at 23:39
$begingroup$
@TonyK no, there's no such condition on them
$endgroup$
– Ankita Gupta
Jan 9 at 4:41