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.
Programming Praxis 
Emacs Lisp
Using cute from srfi-26
and range from standard prelude
Haskell:
Scala dumm algo:
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)Two solutions, both in Racket Scheme.
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_remRacket (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[…] Largest Possible Remainder problem in racket: […]
#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;
}