5
$\begingroup$

I have a set of integers [$c_1$, $c_2$, $c_3$, ... , $c_N$]. A non-negative integer D, greater than a certain threshold, divides each 𝑐𝑖 and leaves remainder 𝑟𝑖,i.e., $r_i$ can be written as $r_i=c_i Mod D$. For all these numbers in the set, I want to find a single value of $D$ that minimizes the sum of remainders i.e. minimize $Σr_i$.

If the integers have a common divisor, this problem is easy. If the integers are relatively co-prime however, then it is not clear how to solve it.

I was thinking about solving it with Genetic Algorithm, but Genetic Algorithm is kind of slow. I want to know is there any other way to solve this problem.

$\endgroup$
  • $\begingroup$ To clarify: Are all $c_i$ and $q_i$ values fixed for an instance of this problem? And D is a single real value? Also do you really want to minimize $\sum r_i$ or is it actually $\sum |r_i|$ (or is there constraint such that all $r_i$ are positive)? $\endgroup$ – Neil Slater Sep 27 at 11:12
  • $\begingroup$ Actually, I want to find a number D, that when divides each value $c_i$ leaves the sum of remainders to be minimum. all $𝑐_𝑖$ values are fixed for an instance of this problem and D is a single real value. I want to minimize $∑𝑟_i$. though alll remainders ($r_i$) should be non-negative. $\endgroup$ – Ramzah Rehman Sep 27 at 11:19
  • $\begingroup$ So how are you enforcing that all remainders are greater than zero? It puts a constraint on other values. You have not explained what $q$ is? $\endgroup$ – Neil Slater Sep 27 at 11:20
  • $\begingroup$ I have updated my comment. Well, Actually D divides $c_i$ with quotient $q_i$ and leaves remainder $r_i$, that's why I wrote $c_i = D * q_i + r_i$. there's no restriction on $q_i$, it can be any non-negative multiple of D. $\endgroup$ – Ramzah Rehman Sep 27 at 11:24
  • $\begingroup$ Something still sems wrong. Do you mean $r_i = c_i \text{mod} D$? It seems that $q_i$ is not a free value at all. $\endgroup$ – Neil Slater Sep 27 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.