8
$\begingroup$

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{equation} \begin{aligned} D^* \quad = \text{argmin}_D& \sum_i c_i \text{ mod } D \\ \textrm{subject to} &\quad D > T \end{aligned} \end{equation}

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.

$\endgroup$
2
  • 2
    $\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
  • $\begingroup$ 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. $\endgroup$ – nbro Jan 23 at 17:38

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.