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 '19 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 '19 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 '19 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 '19 at 11:24
  • 1
    $\begingroup$ I would actually think that this is one of the problems that GAs are fast at solving; being a purely mathematical problem, with mono-dimensional solutions, that can be bounded in a finite space. $\endgroup$ – Alvin Sartor Dec 22 '19 at 9:03

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.