Most frequent remainder when 1000 is divided by all integers from 1 to 1000

Question

Divide 1000 by each integer from 1 to 1000 and record their remainders.

Among the 1000 remainders recorded, what number do you see most frequently?

Answer 1

If you prefer a brute force computational method the following C code will yield an answer of 10.

int main(int argc, char *argv) { // array to keep track of the number of each divisor present int divisor[1001] = {0};

/* counts how many of each divisor there are */ for(int i = 1; i <= 1000; i++) { divisor[1000%i] = divisor[1000%i] + 1; }

int max = 0; int maxdivisor = 0;

/* finds most abundant divisor */ for(int i = 0; i <= 1000; i++) { if(b[i] > max) { max = divisor[i]; maxdivisor = i; } }

printf("%d",maxdivisor);

return 0; }

Answer 2

Same experiment for 5041. Guess why. $5040 = 7! = 2^4 \cdot 3^2 \cdot 5 \cdot 7 \; . $

59 rem      1
21 rem     25
18 rem     49
16 rem     91
15 rem     73
14 rem     43
14 rem     19
14 rem    121
13 rem    145
12 rem      9
12 rem     61
12 rem    181
12 rem    169
12 rem    127
11 rem     85
11 rem     81
11 rem     41
11 rem    241
11 rem    113
10 rem     97
10 rem    361
10 rem     36
10 rem    289
10 rem    253
10 rem    211

Let's see, a divisor $n$ of $990$ gives a remainder of $10$ as long as $n$ itself is larger than 10. $$ 990 = 2 \cdot 3^2 \cdot 5 \cdot 11 $$ has 24 divisors, of which 7 are no larger than 10: 1,2,3,5,6,9,10. Then 24 - 7 = 17.

For comparison, 1000 has 16 divisors, so the remainder $0$ occurs 16 times.

17 rem     10
16 rem      0
12 rem     40
10 rem     20
 9 rem     64
 9 rem     28
 9 rem     16
 9 rem     12
 8 rem      8
 8 rem     76
 8 rem      4
 8 rem     34
 7 rem     48
 7 rem      1
 6 rem     88
 6 rem     80