Maximising the remainder
Given a set of numbers that may be added any number of times to produce to produce a number. the only condition or rather motive is to maximise the remainder when divided by another known number.
Formally , set s has some numbers(given)
Sum S is sum of numbers in the set any number of times(including zero)
another number M is known
We have to find the maximum value of S%M which is possible
Do suggest some strategy to do this.
Formally , set s has some numbers(given)
Sum S is sum of numbers in the set any number of times(including zero)
another number M is known
We have to find the maximum value of S%M which is possible
Do suggest some strategy to do this.
Max(S % M) if S + 1 = M. How to get S puzzled from set s is a lower sum problem, like "Travelling Salesman" -- https://en.wikipedia.org/wiki/Travelling_salesman_problem
Edit: see strikethrough
Edit: see strikethrough
Last edited on
It's NP-Complete (TSP is NP-Hard, not that I really conceptually understand the difference...).
Ignore this post.
Last edited on
but you can get 'an' answer by looking at the value you will divide by.
if you are dividing by 100, for example, the max remainder is 99. you need some sum that gives this value, ideally this value itself (99%100 = 99). So your first attempt is just to cook up the desired value. If that won't work, you need the next one: 199 (yea, this is an easy example).
If I remember it, and boiling it way, way down...
np-complete means we have no known solution that covers every possible case.
np-hard means we can solve it given infinite computing resources, but the algorithm is like O(N!) or something.
where it gets ugly is if the numbers you can add up can NEVER match one of the ideal values. Then you would have to try again to make 98, 198, ... etc.
and then 97... for example if the only number you could add up was '5' you can only make 95 as your answer. Feels like using a prime factor on the target value (99) and comparing that with the add up values (and possibly THEIR factors) would bear fruit.
if you are dividing by 100, for example, the max remainder is 99. you need some sum that gives this value, ideally this value itself (99%100 = 99). So your first attempt is just to cook up the desired value. If that won't work, you need the next one: 199 (yea, this is an easy example).
If I remember it, and boiling it way, way down...
np-complete means we have no known solution that covers every possible case.
np-hard means we can solve it given infinite computing resources, but the algorithm is like O(N!) or something.
where it gets ugly is if the numbers you can add up can NEVER match one of the ideal values. Then you would have to try again to make 98, 198, ... etc.
and then 97... for example if the only number you could add up was '5' you can only make 95 as your answer. Feels like using a prime factor on the target value (99) and comparing that with the add up values (and possibly THEIR factors) would bear fruit.
Last edited on
| If that won't work, you need the next one: 199 |
Darn! I overlooked that. Now, take just one item i from the set s and solve integer ni * i = k * M - 1 for ni and k. Set the factor for all other elements of s to 0. Forget my hint to TSP and subset sum.
Edit: see above, marked in italic
Last edited on
This isn't the subset sum problem. If I understand the problem correctly, given a set of numbers si-sn and a number M, we want to find ki...kn such that: sum(si*ki) mod M is maximized.
If you can find a value of si that is coprime with M then I *think* the answer is easy. This assumes that if X and Y are coprime then there is a value k between 0 and Y-1 such that kX % Y == r for all value r between 0 and Y-1.
- Find a value of si that is coprime with M.
Set all the other values of k to 1, giving a constant for all the other si*ki terms. Call this sum K. Now you have
si*ki+K == M-1 mod M
si*ki == M-1-K mod M
Now just try all values 0 to M-1 for ki to solve.
If you can find a value of si that is coprime with M then I *think* the answer is easy. This assumes that if X and Y are coprime then there is a value k between 0 and Y-1 such that kX % Y == r for all value r between 0 and Y-1.
- Find a value of si that is coprime with M.
Set all the other values of k to 1, giving a constant for all the other si*ki terms. Call this sum K. Now you have
si*ki+K == M-1 mod M
si*ki == M-1-K mod M
Now just try all values 0 to M-1 for ki to solve.
Last edited on
**This assumes that if X and Y are coprime then there is a value k between 0 and Y-1 such that kX % Y == r for all value r between 0 and Y-1.**
thats ok if its the case is even if i could find one coprime with M i can get the remainder of M-1. but what about the other side of coin ,If i could not find even a single coprime then then my answer can be M-1 or something else as well thinking of set {2,3 }and M being 6 thus i can produce remainder 4,3,2 but most importantly 2+3=5 which will not always be the case like set being(6,4)and M=12 max remainder i can think of is 10
thats ok if its the case is even if i could find one coprime with M i can get the remainder of M-1. but what about the other side of coin ,If i could not find even a single coprime then then my answer can be M-1 or something else as well thinking of set {2,3 }and M being 6 thus i can produce remainder 4,3,2 but most importantly 2+3=5 which will not always be the case like set being(6,4)and M=12 max remainder i can think of is 10
yea... at that point, do you solve for m-2? and m-3... (the 99, 98, ... etc from my example?) or is there something smarter to do?
so you would try to solve your example for 11, fail, and then try to solve for 10, works, done.
or are you ?...
(12*X+11)%12 = 11 ... not possible with 6 & 4. 10 is the best you can do. I know this, and you know this, but I am drawing a blank on detecting it. This is the hard part of the algorithm, is knowing when to stop and try to seek the next answer.
so you would try to solve your example for 11, fail, and then try to solve for 10, works, done.
or are you ?...
(12*X+11)%12 = 11 ... not possible with 6 & 4. 10 is the best you can do. I know this, and you know this, but I am drawing a blank on detecting it. This is the hard part of the algorithm, is knowing when to stop and try to seek the next answer.
Last edited on
DarkX, care to share? I'm curious how to solve this.
If all the S values are coprime with M then maybe we can divide by the common factor solve again.
If all the S values are coprime with M then maybe we can divide by the common factor solve again.
How about Goldbach's conjecture in this context? Well, we dno't have a clue for the composition of set s. If it contains for example all primes and also the number 1, this could be a game changer. So I still have do not a clear idea how to attack the task for any set s.
Topic archived. No new replies allowed.