## 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

`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;
}