Largest Possible Remainder

October 16, 2015

The result of dividing a number n by a divisor d is a quotient q and a remainder r. Given a fixed n and a divisor d in the range 1 ≤ d < n, find the divisor that produces the largest possible remainder. For instance, given n = 20 and 1 ≤ d < 10, the largest remainder is 6 when the divisor d is 7.

Your task is to write a program that finds the largest possible remainder. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

9 Responses to “Largest Possible Remainder”

  1. wert310 said

    Emacs Lisp
    Using cute from srfi-26
    and range from standard prelude

    (defun lpr (n d)
      (reduce #'max (mapcar (cute #'mod n <>) (range 1 d 1))))
    
  2. Francesco said

    Haskell:

    f n d = maximum $ map (rem n) [1..d-1]
  3. FA said

    Scala dumm algo:

    (for(d<-1 to 20) yield (d,n%d)).toList.maxBy(_._2)
    
  4. Paul said

    Two versions in Python. The second (lpr) uses the fact that there are maxima close to n/2, n/3, … Ths version is a lot faster for larger n and d.
    count is from the itertools lib and isqrt is the integer square root.

    def lpr0(n, d, dmin=2, max_rem=0):
        for div in range(d, dmin-1, -1):
            r = n % div
            if r > max_rem:
                max_rem = r
            if max_rem >= div:
                break
        return max_rem
    
    def lpr(n, d):
        if d > isqrt(n):
            for i in count(2):
                if d > n // i:
                    max_rem = n % (n // i + 1)
                    return lpr0(n, n // i - 1, max_rem, max_rem)
        else:
            return lpr0(n, d)
    
  5. r. clayton said

    Two solutions, both in Racket Scheme.

  6. Mike said
    Let q, r = divmod(n, d). We want to find d that maximizes r, for 1 < d < b.
    ```
    An example:      n   d       q   r
              divmod(31, 27) =>  1,  4
                     31  26      1   5
                     31  25      1   6
                     . . .
                     31  17      1  14
                     31  16      1  15  <- smallest d that goes into 31 once
                     31  15      2   1  <- largest d that goes into 31 twice
    ```                     
    Observe that for a given q, r goes up as d goes down.  So for a given q, we just need to find the smallest value for d to get the largest r.  
    
    For n and d, 
        the quotient q = floor(n / d)
        the next larger quotient k = q + 1 = floor(n / d) + 1
        the larged divisor with the larger quotient f = floor(n / k)
        the smallest divisor for the quotient q is mid_d = f + 1
        the largest remainder for the given q is r = n % min_d
    
    
    So for n, d = 31, 27.  
        q = n // d = 31 // 27 = 1
        k = q + 1 = 1 + 1 = 2
        f = n // k = 31 // 2 = 15
        min_d = f + 1 = 15 + 1 = 16
        r = n % min_d = 31 % 16 = 15.
    
    This can be iterated by letting d = f and repeating until d < max_rem.
    
    def maxrem(n = 3100, d=999):
        max_rem = 0
    
        while d > max_rem:
            k = n // d + 1
            min_d = n // k + 1
            rem = n % min_d
            if rem > max_rem:
                max_rem = rem
            d = min_d - 1
    
        return max_rem
    
  7. ksluder said

    Racket (tail recursive using default parameters)

    
    #lang racket
    
    (define (largest-remainder n d (lr 0) (lrd 0)) ;;lr = largest remainder so far lrd = divisor with largest remainder
      (cond
        [(= d 0) (values lr lrd)] ;;catch cases like n = 6, d = 3
        [(> lr d) (values lr lrd)] ;;stop when d is < largest remainder
        [(> (modulo n d) lr)
         (largest-remainder n (sub1 d) (modulo n d) d)] ;;save new largest remainder
        [else 
         (largest-remainder n (sub1 d) lr lrd)])) ;;iterate with d-1
    
  8. […] Largest Possible Remainder problem in racket: […]

  9. Mayur Lokare said

    #include
    int main()
    {
    int i,num,temp,rem=0;
    printf(“Enter The Num\n”);
    scanf(“%d”,&num);
    for(i=2;irem)
    rem = num%i;
    printf(“Max remider = %d\n”,rem);
    return 0;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: