# Question about minimizing sum of remainders

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.

• 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)? – Neil Slater Sep 27 '19 at 11:12
• 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. – Ramzah Rehman Sep 27 '19 at 11:19
• 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? – Neil Slater Sep 27 '19 at 11:20
• 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. – Ramzah Rehman Sep 27 '19 at 11:24
• 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. – Alvin Sartor Dec 22 '19 at 9:03