Answers.Body: <h3>Genetic Algorithm is not the best approach here:</h3>
  <ol>
  <li>GA is a stochastic methods and therefore will <strong>never guarantee</strong> the best possible solution.</li>
  <li>Your solution (GA individual) is modeled as a simple integer. GA is optimal to find a solution modeled as an array (like our genomes), so it can do mutation and crossover.</li>
  </ol>
  <h3>Good Approach:</h3>
  <blockquote>
  <p>The set |S|=N can be around 10000, and each element also has a value in tens of thousands.</p>
  </blockquote>
  <p>It certainly looks a lot, but for a computer, that's not so much. We can start with a brute-force and incrementally simplify it for better performance:</p>
  <h4>Brute Force:</h4>
  <p>You can try every single integer from D&gt;T until D&lt;max(S) and store the best candidate.</p>
  <pre><code># Fully functional python solution:
  import random
  import time
  
  # Let's start initializing a random T
  T = random.randint(1, 100)
  # And a S, with 10,000 integers fom T to 10,000
  S = [random.randint(T, 10000) for i in range(10000)]
  
  
  def LowestRemainder(List, Threshold):
      # Storing the all time lowest D and remainder
      Best_D_SoFar = Threshold+1
      lowestRemainderSoFar = sum(List)
      for d in range(Threshold+1, max(List)+1):
          remainder = sum(c%d for c in List)
          if remainder &lt; lowestRemainderSoFar:
              lowestRemainderSoFar = remainder
              Best_D_SoFar = d
      return Best_D_SoFar, lowestRemainderSoFar
  
  print(&quot;Looking for D &gt; %d, that minimizes the sum of all remainder in a list containing %d integers&quot; % (T, len(S)))
  # Keep track of time
  start_time = time.time()
  # call the function
  D, R = LowestRemainder(S, T)
  # stop the clock
  elapsed_time = time.time() - start_time
  print(&quot;Found D =&quot;, D, &quot;and lowest remainder =&quot;, R, &quot;in&quot;, elapsed_time, &quot;seconds&quot;)
  </code></pre>
  <p>I've tested a few times on my machine and it always runs in less than <strong>4 seconds</strong> (for the maximum</p>
  <p>But that's the brute-force baseline. So let's make it more efficient, by early interrupting the inner loop:</p>
  <pre><code>    # Remove this:
      # remainder = sum(c%d for c in List)
      
      # Add this instead:
        remainder = 0
        for c in List:
            remainder += c%d
            if remainder &gt; lowestRemainderSoFar:
                break
  </code></pre>
  <p>And done!</p>
  <h3>It now takes less than 0.2 seconds</h3>
  <p>(for the whole 10,000 sized array with random integers up to 10,000:)</p>
  <hr />
  <h2>Extra thoughts:</h2>
  <p>As the best solution is probably a low number (as discussed later), if it takes too long to finish, you can simply interrupt and you'll still have a good solution (not guaranteed to be optimal) just like with GA (and probably better, as you'll quickly exploit the best candidates, instead of exploring the space).</p>
  <h3>Factorization is our friend:</h3>
  <p>Suppose a solution <strong>D</strong>, with a score <strong>S</strong>.</p>
  <p>Now factorize the solution, finding the list of primes that composes D: [p1,p2,…].</p>
  <p>Now remove some p, generating a <strong>D'</strong> and you will notice that the <code>c mod(D) &gt;= c mod(D')</code> for any c, any D, and any p.</p>
  <p>That means, <strong>you don't need to explore any multiple of D, if D was already evaluated.</strong></p>
  <p>That will drastically drop the amount of trials!</p>
  <h4>No threshold scenario:</h4>
  <p>Using this factorization principle, in the simpler scenario where T=1 <em>(if T&lt;1, than D=1 is the best solution)</em>, we guarantee that the solution is a prime number! Also, you don't need to search until the biggest number <code>max(S)</code>, as the <code>sqrt(max(S))</code> will be enough.</p>
  <h4>With threshold scenario</h4>
  <p>It makes it a little harder to program, but still you just need to loop through co-primes.</p>
  <h4>Upper limit:</h4>
  <p>Once you hit the first candidate (d) larger than the smallest S (<code>d&gt;min(S)</code>), than this remainder will be min(S).</p>
  <p>If the best solution so far is already better than min(S), we can skip all the next candidates.</p>
  <p>This logic is cumulative. Once the candidate d is larger than the N lowest S, the sum of remainders will be at least the sum of all N lowest S. So, our loop could be something like:</p>
  <pre><code>if(sum([s&lt;d for s in S]) &gt; lowest):
    return d
  else:
    d = next_coprime()
  </code></pre>
  <p>In a list with thousand of elements, there's a high chance that the smallest element is found early. And even if it does not satisfy the finish condition, it will only accumulate more elements as d grows.</p>
  <h3>In summary:</h3>
  <p>Start with a baseline and restrict the boundaries until your code runs in the desirable time.</p>
  <h2>Example:</h2>
  <p>Inputs:</p>
  <ul>
  <li>S = [10, 19, 28]</li>
  <li>T = 3</li>
  </ul>
  <p>Process: Testing all d&gt;T, skip the multiples and stop on upper limit:</p>
  <ul>
  <li>d = 4 --&gt; remainders = [2,3,0] = 5</li>
  <li>d = 5 --&gt; remainders = [0,4,3] = 7</li>
  <li>d = 6 --&gt; remainders = [4,1,4] = 9</li>
  <li>d = 7 --&gt; remainders = [3,5,0] = 8</li>
  <li>d = 8 --&gt; is multiple of 4 (skip)</li>
  <li><strong>d = 9 --&gt; remainders = [1,1,1] = 3</strong></li>
  <li>d = 10--&gt; is multiple of 5 (skip)</li>
  <li>d = 11--&gt; <strong>11&gt;min(S)</strong> --&gt; remainders = [10,x,x] &gt; 3. <strong>DONE!</strong></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-08-14T00:03:15.350Z
Answers.LastActivityDate: 2021-08-14T16:41:04.570Z
Answers.LastEditDate: 2021-08-14T16:41:04.570Z
Answers.UserDisplayName: Andre Goulart
Body: <p>I have a set of fixed integers <span class="math-container">$S = \{c_1, \dots, c_N \}$</span>. I want to find a single integer <span class="math-container">$D$</span>, greater than a certain threshold <span class="math-container">$T$</span>, i.e. <span class="math-container">$D &gt; T \geq 0$</span>, that divides each <span class="math-container">$c_i$</span> and leaves remainder <span class="math-container">$r_i \geq 0$</span>, i.e. <span class="math-container">$r_i$</span> can be written as <span class="math-container">$r_i = c_i \text{ mod } D$</span>, such that the sum of remainders is minimized.</p>
  <p>In other words, this is my problem</p>
  <p><span class="math-container">\begin{equation}
  \begin{aligned}
  D^* \quad = \text{argmin}_D&amp;  \sum_i c_i \text{ mod } D \\
  \textrm{subject to} &amp;\quad D &gt; T
  \end{aligned}
  \end{equation}</span></p>
  <p>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.</p>
  <p>The set <span class="math-container">$|S| = N$</span> can be around <span class="math-container">$10000$</span>, and each element also has a value in tens of thousands.</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-12-22T09:03:39.340Z
Comments.Text: 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.
Comments.UserDisplayName: Alvin Sartor
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-23T17:38:34.027Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-07T00:31:17.647Z
Comments.Text: I am almost certain the answer here is just T (being the lower bound on N). The reason for this is factors are prime, and therefor mostly random. As N becomes larger, the possibility for a larger remainder also increases, but the possibility of N being a divisor (or even close divisor) remains the same. This is all speculation, but I'm only saying this based on some simulations I did where the sum of each N was strictly increasing with N. This excludes edge cases with very small sample sizes (like [10,20,30] and T=9), but once a sample size is large enough, it seems $D*=T$
Comments.UserDisplayName: Recessive
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-09T06:24:33.547Z
Comments.Text: Disregard "strictly increasing". Some values are less than others even in large sample sizes, but only slightly. It's more like "mostly increasing, with outliers that are a few percent smaller than the previous value"
Comments.UserDisplayName: Recessive
Tags: <machine-learning><genetic-algorithms><optimization><constrained-optimization>
Title: 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$?
UserDisplayName: Ramzah Rehman
ThreadText: # 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$?
  
  (Asked by: username_0 on 2019-09-27)
  
  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.
  
  **Tags:** machine-learning, genetic-algorithms, optimization, constrained-optimization
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: 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.  
  > **username_3**: I am almost certain the answer here is just T (being the lower bound on N). The reason for this is factors are prime, and therefor mostly random. As N becomes larger, the possibility for a larger remainder also increases, but the possibility of N being a divisor (or even close divisor) remains the same. This is all speculation, but I'm only saying this based on some simulations I did where the sum of each N was strictly increasing with N. This excludes edge cases with very small sample sizes (like [10,20,30] and T=9), but once a sample size is large enough, it seems $D*=T$  
  > **username_3**: Disregard "strictly increasing". Some values are less than others even in large sample sizes, but only slightly. It's more like "mostly increasing, with outliers that are a few percent smaller than the previous value"  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2021-08-14. Score: 1
  
  ### Genetic Algorithm is not the best approach here:
  
  1. GA is a stochastic methods and therefore will **never guarantee** the best possible solution.
  2. Your solution (GA individual) is modeled as a simple integer. GA is optimal to find a solution modeled as an array (like our genomes), so it can do mutation and crossover.
  
  ### Good Approach:
  
  > The set |S|=N can be around 10000, and each element also has a value in tens of thousands.
  
  It certainly looks a lot, but for a computer, that's not so much. We can start with a brute-force and incrementally simplify it for better performance:
  
  #### Brute Force:
  
  You can try every single integer from D>T until D<max(S) and store the best candidate.
  
  ```
  # Fully functional python solution:
  import random
  import time
  
  # Let's start initializing a random T
  T = random.randint(1, 100)
  # And a S, with 10,000 integers fom T to 10,000
  S = [random.randint(T, 10000) for i in range(10000)]
  
  def LowestRemainder(List, Threshold):
      # Storing the all time lowest D and remainder
      Best_D_SoFar = Threshold+1
      lowestRemainderSoFar = sum(List)
      for d in range(Threshold+1, max(List)+1):
          remainder = sum(c%d for c in List)
          if remainder < lowestRemainderSoFar:
              lowestRemainderSoFar = remainder
              Best_D_SoFar = d
      return Best_D_SoFar, lowestRemainderSoFar
  
  print("Looking for D > %d, that minimizes the sum of all remainder in a list containing %d integers" % (T, len(S)))
  # Keep track of time
  start_time = time.time()
  # call the function
  D, R = LowestRemainder(S, T)
  # stop the clock
  elapsed_time = time.time() - start_time
  print("Found D =", D, "and lowest remainder =", R, "in", elapsed_time, "seconds")
  
  ```
  
  I've tested a few times on my machine and it always runs in less than **4 seconds** (for the maximum
  
  But that's the brute-force baseline. So let's make it more efficient, by early interrupting the inner loop:
  
  ```
      # Remove this:
      # remainder = sum(c%d for c in List)
      
      # Add this instead:
        remainder = 0
        for c in List:
            remainder += c%d
            if remainder > lowestRemainderSoFar:
                break
  
  ```
  
  And done!
  
  ### It now takes less than 0.2 seconds
  
  (for the whole 10,000 sized array with random integers up to 10,000:)
  
  ---
  
  ## Extra thoughts:
  
  As the best solution is probably a low number (as discussed later), if it takes too long to finish, you can simply interrupt and you'll still have a good solution (not guaranteed to be optimal) just like with GA (and probably better, as you'll quickly exploit the best candidates, instead of exploring the space).
  
  ### Factorization is our friend:
  
  Suppose a solution **D**, with a score **S**.
  
  Now factorize the solution, finding the list of primes that composes D: [p1,p2,…].
  
  Now remove some p, generating a **D'** and you will notice that the `c mod(D) >= c mod(D')` for any c, any D, and any p.
  
  That means, **you don't need to explore any multiple of D, if D was already evaluated.**
  
  That will drastically drop the amount of trials!
  
  #### No threshold scenario:
  
  Using this factorization principle, in the simpler scenario where T=1 *(if T<1, than D=1 is the best solution)*, we guarantee that the solution is a prime number! Also, you don't need to search until the biggest number `max(S)`, as the `sqrt(max(S))` will be enough.
  
  #### With threshold scenario
  
  It makes it a little harder to program, but still you just need to loop through co-primes.
  
  #### Upper limit:
  
  Once you hit the first candidate (d) larger than the smallest S (`d>min(S)`), than this remainder will be min(S).
  
  If the best solution so far is already better than min(S), we can skip all the next candidates.
  
  This logic is cumulative. Once the candidate d is larger than the N lowest S, the sum of remainders will be at least the sum of all N lowest S. So, our loop could be something like:
  
  ```
  if(sum([s<d for s in S]) > lowest):
    return d
  else:
    d = next_coprime()
  
  ```
  
  In a list with thousand of elements, there's a high chance that the smallest element is found early. And even if it does not satisfy the finish condition, it will only accumulate more elements as d grows.
  
  ### In summary:
  
  Start with a baseline and restrict the boundaries until your code runs in the desirable time.
  
  ## Example:
  
  Inputs:
  
  * S = [10, 19, 28]
  * T = 3
  
  Process: Testing all d>T, skip the multiples and stop on upper limit:
  
  * d = 4 --> remainders = [2,3,0] = 5
  * d = 5 --> remainders = [0,4,3] = 7
  * d = 6 --> remainders = [4,1,4] = 9
  * d = 7 --> remainders = [3,5,0] = 8
  * d = 8 --> is multiple of 4 (skip)
  * **d = 9 --> remainders = [1,1,1] = 3**
  * d = 10--> is multiple of 5 (skip)
  * d = 11--> **11>min(S)** --> remainders = [10,x,x] > 3. **DONE!**
  
  
  ---
  
  