Sum of Mods --- A Problem.
Sanjoy Baruah
Consider the following (language recognition) problem:
INSTANCE.
{(ai,bi), 1 <= i <= n, where ai, bi, are Naturals, and ai <= bi},
a natural number K.
QUESTION.
Does there exist a natural number x such that
(SUM : i : 1 <= i <= n : ((x - ai) mod bi)) < K?
Given an instance, is there a computationally efficient method of
testing whether the instance belongs to this language (i.e., if such
an x exists)? The only method I can think of involves actually trying
out each number in (0, lcm{b1,...,bn}). However, attempts to prove the
problem NP hard have come up short.
Any suggestions?
Sanjoy
Always mount a scratch monkey.
> INSTANCE.
> {(ai,bi), 1 <= i <= n, where ai, bi, are Naturals, and ai <= bi},
> a natural number K.
>
> QUESTION.
> Does there exist a natural number x such that
> (SUM : i : 1 <= i <= n : ((x - ai) mod bi)) < K?
If all the bi are relatively prime, there is in fact an x such that the
remainders when x is divided by each bi are whatever you like, with the
range from 0 to bi-1. This is the Chinese Remainder Theorem.
You can simply select x such that x mod bi == ai. Then (x-ai) mod bi is
zero, so the sum over all the i's is zero.
First, you need to be able to find a multiplicative inverse modulo a number:
To find a' such that a'a == 1 modulo b ("==" is for congruence):
Let
m[0] = b, n[0] = 0,
m[1] = a, and n[1] = 1.
Note that n[0]*a == m[0] modulo b, and n[1]*a == m[1] modulo b. We will
preserve this identity.
While m[i] is not zero, do the following for increasing i's (starting
with i=1, obviously):
Find q and r such that m[i-1] = q*m[i] + r. (That is,
q is the quotient when m[i-1] is divided by m[i], and
r is the remainder.)
Let m[i+1] = r.
Let n[i+1] = n[i-1] - q*n[i].
(Note that a*n[i+1] = a*n[i-1] - a*q*n[i] == m[i-1] - q*m[i] =
r = m[i+1], so we have maintained the identity.)
We are done when m[i] is zero. At this point, m[i-1] is the greatest
common divisor of a and b. If m[i-1] is 1, then n[i-1]*a == 1 modulo b.
You clearly don't really need arrays to implement the above; it's just
easier to describe that way. You just need the last two elements of m and
n and the new m and n. I believe the algorithm is logarithmic, at least in
maximum execution time, because on each iteration, q will be at least one, so
you always make a good bit of progress. (Except for the first iteration, if b
is less than a.) I think Fibonnacci numbers are the worst case, e.g. for 21
and 13, the algorithm runs through 8, 5, 3, 2, 1, and 0.
Next, you need to use the above to take all the ai's and bi's to produce one
number that has the remainder of ai when divided by bi:
Let y1' be the inverse of y1 modulo y2 (or, if y1 and y2 are
not relatively prime, let y1' be the n[i-1] produced by the above
algorithm).
Then y1'*(y1/gcd(y1,y2))*(x2-x1)+x1 is congruent to x1 modulo y1 and
x2 modulo y2, if y1 and y2 are relatively prime. If they are not,
the expression still satisfies the congruences if any number does.
If no number satisfies the congruences, the expression is "close".
If any of the bi's are not relatively prime, you may not be able to find an
x for which the sum is exactly zero; you'll have to play with the above to
see how close you can get.
-- edp (Eric Postpischil)
"Always mount a scratch monkey."
e...@jareth.enet.dec.com