Chinese remainder theorem search

[bendykst]

I have been thinking about this for some time, but I can't find an answer. I'm hoping someone smarter than me will be able to figure this out.

=======================
From Wikipedia:
In the Chinese remainder theorem, there exists an integer x which is the solution of the system of congruences:

% = (modulus)

x%n1 = a1%n1
x%n2 = a2%n2
...
x%nk = ak%nk
for positive pairwise coprime integers {n1...nk} and positive integers {a1..ak}.
=================================

There are infinitely many solutions for each system, but for our purposes, let x be the smallest positive integer which solves the system.

So, here's the puzzle: Say instead of a single integer a1 or a2, we have a set of integers, so that each n has an associated set of integers. From this we generate a set of solutions, picking one integer from each set for each n.

I.E.
x%3 = { (1), 2} %3
x%5 = { 3, (4) } %5
x%7 = { (1), 3, 5 } %7

Gives x=64

while

x%3 = { 1, (2)} %3
x%5 = { 3, (4) } %5
x%7 = { 1, 3, (5)} %7

Gives x=89

Is there an efficient way to find the smallest x? We could generate all the solutions and do a search, but this could take until the heat death of the universe for some applications.

[bendykst]

Related puzzle, say we have a structure as described above, a list of n's with associated sets. We partition this into two new structures with roughly the same number of n's. Is there an efficient way to find solutions common to both sets?

[Amb*]

Maybe this should be in Visitor Submitted Puzzles?

[Antrax]

It's not really a puzzle, it's just a question about mathematics. I'll give it some thought later, I looked at it yesterday but I was too tired to make any progress.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Pablo]

[L'lanmal]

[Zahariel]

If we take N as the product of n1 through nk, L'lanmal's solution uses Theta(N) space and O(Nk) time (but this isn't a very tight bound on time unless the ai are very small). I think k is at worst proportional to log(n), but I don't remember how to prove it.

The cartesian product method of constructing all the solutions and then picking the smallest one has worst case time behavior approximately O(N*k*log ² (N)), since solving a CRT problem is O(k*log ² (N)) (I had to look this up, it's equal to running Euclid's algorithm k times) and you're doing it a number of times equal to the product of the sizes of the ai, which might be arbitrarily close to N but normally isn't. So L'lanmal wins there in the worst case. However, this solution only uses O(k) space if that's important, which might as well be constant since the problem statement uses more than that in general.

Basically L'lanmal's solution is clearly better if the ai are relatively large (compared to ni), but if you know (from real-world domain knowledge) that each ai is approximately a constant size c rather than proportional to ni then the cartesian product algorithm gets O(kc ^k log ² (N)), which is much better in addition to not taking all the space in the universe. (L'lanmal's still has pretty much O(N) behavior even if you know that the ai are usually all of [ni] except for a constant number of elements, so that still blows.) I'm not sure if there's another solution that beats both of them, but I sort of doubt it. This looks like a typical time/space tradeoff. Sieve methods are space-hungry, but have very very reliable time behavior, whereas the cartesian product method uses practically no space but might take all the time ever in the worst case.

A conceivably better method might just be linear search. This takes essentially no space and O(Nk*log(N)) time, but if the ai are very large you're likely to find a solution a lot quicker than that. Sometimes the simple solutions are the best. Actually, I'm pretty sure you can't do better than this in the general case, but the cartesian product is cheaper if the sets are always very small.

Note: I'm doing all these analyses in my head, so if I blew it, sorry. I believe the only gratuitous approximation I'm making is rounding log(nk) up to log(N), but that's fine for figuring out an O bound anyway.