Algorithm to find the smallest integer m which when divides n distinct integers leaves distinct remainders

The fastest approach is just to try it.

def distribute_remainders (numbers):
    m = len(numbers)
    while True:
        is_used = set()
        for x in numbers:
            if x % m in is_used:
                break
            else:
                is_used.add(x % m)
        if len(numbers) == len(is_used):
            return m
        else:
            m += 1

Testing remainders for a given number takes O(n). On average, it only takes log(n) tries until you run across a prime that will certainly work. So on average this is no worse than O(n log(n)) and probably is better.

What about a worst case? https://primes.utm.edu/notes/gaps.html says that a guaranteed upper bound to the next prime is still being improved, but the best records are around O(n^0.535). So worst case is O(n^1.535) and probably is closer to O(n^1.5).

By contrast if we try to be clever, there are O(n^2) gaps to look at. So we do worse than the very unlikely worst case before we've even enumerated them.

If we imagine the list sorted, we have numbers at a variety of distances from each other:

a     b    c      d  e    f...
 <---> <--> ...
 <--------> <-------> ...
       <---------> ...
       ...

To duplicate a remainder, one of those distances must be m or a multiple of m.

One possible solution is to start m at 2; and create a set of all divisors of all the distances, incrementing m by 1 every time one of the divisors matches it.

For example,

[2, 6, 8, 14]

m = 2

Distance   Divisors      m
4          4, 2          3
6          6, 2, 3       5
12         12, 6, 3, 2   5
2          2             5
8          8, 4, 2       5
6          6, 2, 3       5


Remainders mod 5:
[2, 1, 3, 4]