# Given a list of integers $\{c_1, \dots, c_N \}$, how do I find an integer $D$ that minimizes the sum of remainders $\sum_i c_i \text{ mod } D$?

I have a set of fixed integers $$S = \{c_1, \dots, c_N \}$$. I want to find a single integer $$D$$, greater than a certain threshold $$T$$, i.e. $$D > T \geq 0$$, that divides each $$c_i$$ and leaves remainder $$r_i \geq 0$$, i.e. $$r_i$$ can be written as $$r_i = c_i \text{ mod } D$$, such that the sum of remainders is minimized.

In other words, this is my problem

\begin{aligned} D^* \quad = \text{argmin}_D& \sum_i c_i \text{ mod } D \\ \textrm{subject to} &\quad D > T \end{aligned}

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.

The set $$|S| = N$$ can be around $$10000$$, and each element also has a value in tens of thousands.

I was thinking about solving it with a genetic algorithm (GA), but it is kind of slow. I want to know is there any other way to solve this problem.

• 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
• Hello. This is an old post, but how did you solve this problem in the end? You may want to provide a formal answer below, if you found a good solution to this problem. – nbro Jan 23 at 17:38