How to find divisor to maximise remainder?

This problem is equivalent to finding maximum of function f(x)=n%x in given range. Let's see how this function looks like:

It is obvious that we could get the maximum sooner if we start with x=k and then decrease x while it makes any sense (until x=max+1). Also this diagram shows that for x larger than sqrt(n) we don't need to decrease x sequentially. Instead we could jump immediately to preceding local maximum.

int maxmod(const int n, int k)
{
    int max = 0;

    while (k > max + 1 && k > 4.0 * std::sqrt(n))
    {
        max = std::max(max, n % k);
        k = std::min(k - 1, 1 + n / (1 + n / k));
    }

    for (; k > max + 1; --k)
        max = std::max(max, n % k);

    return max;
}

Magic constant 4.0 allows to improve performance by decreasing number of iterations of the first (expensive) loop.

Worst case time complexity could be estimated as O(min(k, sqrt(n))). But for large enough k this estimation is probably too pessimistic: we could find maximum much sooner, and if k is significantly greater than sqrt(n) we need only 1 or 2 iterations to find it.

I did some tests to determine how many iterations are needed in the worst case for different values of n:

    n        max.iterations (both/loop1/loop2)
10^1..10^2    11   2   11
10^2..10^3    20   3   20
10^3..10^4    42   5   42
10^4..10^5    94  11   94
10^5..10^6   196  23  196
up to 10^7   379  43  379
up to 10^8   722  83  722
up to 10^9  1269 157 1269

Growth rate is noticeably better than O(sqrt(n)).

waves hands around

No value of x which is a factor of n can produce the maximum n%x, since if x is a factor of n then n%x=0.

Therefore, you would like a procedure which avoids considering any x that is a factor of n. But this means you want an easy way to know if x is a factor. If that were possible you would be able to do an easy prime factorization.

Since there is not a known easy way to do prime factorization there cannot be an "easy" way to solve your problem (I don't think you're going to find a single formula, some kind of search will be necessary).

That said, the prime factorization literature has cunning ways of getting factors quickly relative to a naive search, so perhaps it can be leveraged to answer your question.

Not asymptotically faster, but faster, simply by going backwards and stopping when you know that you cannot do better.

Assume k is less than n (otherwise just output k).

int max = 0;
for(int i = k; i > 0 ; --i)
{
  int xx = n - (n / i) * i; // or int xx = n % i;
  if(max < xx)
    max = xx;
  if (i < max)
    break;   // all remaining values will be smaller than max, so break out!
}
cout << max << endl;

(This can be further improved by doing the for loop as long as i > max, thus eliminating one conditional statement, but I wrote it this way to make it more obvious)

Also, check Garey and Johnson's Computers and Intractability book to make sure this is not NP-Complete (I am sure I remember some problem in that book that looks a lot like this). I'd do that before investing too much effort on trying to come up with better solutions.

For k > n the problem is trivial (take x = n+1).

For k < n, think about the graph of remainders n % x. It looks the same for all n: the remainders fall to zero at the harmonics of n: n/2, n/3, n/4, after which they jump up, then smoothly decrease towards the next harmonic.

The solution is the rightmost local maximum below k. As a formula x = n//((n//k)+1)+1 (where // is integer division).