Algorithm to find the smallest integer m which when divides n distinct integers leaves distinct rema-CodePudding

As the title says, I need an algorithm to find the smallest integer m which when divides n distinct integers leaves distinct remainders.

I know m has to be atleast n and further such an m always exist (m = max(all integers) 1), but I don't understand how to proceed with finding the smallest m. Any help is appreciated!

Thanks

CodePudding user response：

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.

CodePudding user response：

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]