1
$\begingroup$

I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:

$k_1 * a_1 + b_1 = x$

$k_2 * a_2 + b_2 = x$

$\dots$

$k_n * a_n + b_n = x$

Additional info where $r \in \{ 1,2,\dots , n \}$:

  • $a_r$ is prime
  • $0 \leq b_r < a_r $
  • $k_r b_r, U, n, \in N_0$ and $(a_r\in N)$

I'm looking for an algorithm that computes the largest $x$ which satisfies all of the given equations such that for the given upper bound $U$ the additional constraint $x \leq U$ holds. If there is no such $x$ a simple "no solution" as output is fine.

First Example:

Given data: $a_1 = 3, a_2 = 5$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 3 + 1 = x$

$k_2 * 5 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is 7 (set $k_1 = 2$ and $k_2=1$)

Second Example:

Given data: $a_1 = 11, a_2 = 17$ and $b_1 = 1, b_2 = 2$ and $U = 20$

The $n$ equations with substituted values:

$k_1 * 11 + 1 = x$

$k_2 * 17 + 2 = x$

The solution (largest $x$ which satisfies the equations and is $\leq U$ is "no soluton" (there is no way to set $k_1$ and $k_2$ such that the equations are equal)

I'm struggling to come up with an algorithm which solves this efficiently. Currently my best approach is to compute all values of x which satisfy the first equation, then I compute all values of $x$ which satisfy the second equation and so on until I have $n$ sets, set $i$ represents the values of $x$ which satisfy equation $i$. Then I simply intersect all of them, if the result is an empty set then I output "no solution" otherwise I output the max element of the resulting set. This approach is very inefficient :/

What do you think about my approach how could I compute the largest x which satisfies all of the constraints above more efficiently?

Note: the reason I know that there is a more efficient solution is because I have encountered this problem during a programming competition. I'm expecting that the solution will use elementary number theory since prime numbers are involved. I just don't know how else to approach this.

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Is this an ongoing competition? Can you name the competition where you saw it, and link to the original problem if possible, to give proper credit to the source of the problem? $\endgroup$ – D.W. Jul 5 '17 at 0:06
  • $\begingroup$ @D.W. The programming competition was at hosted by my school, it's not ongoing. I don't have the problem statement, this is what I had left in my notes, all relevant information are contained in this post. $\endgroup$ – Anna Vopureta Jul 5 '17 at 12:10
2
$\begingroup$

You want a solution $x$ such that

$$x \equiv b_i \pmod{a_i}$$

for all $i$. By the Chinese remainder theorem, this is either impossible or it is equivalent to

$$x \equiv b \pmod{a}$$

where $a = \text{lcm}(a_1,\dots,a_n)$ and $b$ can be computed using the Chinese remainder theorem. In other words, the solutions are all of the form $b$, $b+a$, $b+2a$, $b+3a$, etc. From there it is easy to find the largest solution $x$ such that $x\le U$.

$\endgroup$
  • $\begingroup$ The Chinese remainder theorem does seem applicable to this problem, thanks for pointing this out, it's a huge clue. How does this approach behave for cases where there is no solution, how would I go about detecting a "no solution"? I added such a case to the post. $\endgroup$ – Anna Vopureta Jul 5 '17 at 17:45
  • 1
    $\begingroup$ @AnnaVopureta, I'll let you work that out for yourself. I suggest you study the CRT. Once you understand the CRT, you should be able to figure out for yourself how to detect whether a solution exists or not. $\endgroup$ – D.W. Jul 5 '17 at 17:49
  • $\begingroup$ Aha ok, if the smallest x which satisfies all of the equations is >U then the there is no solution to my problem? $\endgroup$ – Anna Vopureta Jul 5 '17 at 18:55
  • $\begingroup$ Also, is there an alternative solution in the case where a1, a2 ,..., an are prime but not coprime (it is possible that a1 = a2 for example)? In such a case the CRT would not be applicable as far as I know. $\endgroup$ – Anna Vopureta Jul 5 '17 at 19:00
  • $\begingroup$ @AnnaVopureta, you can generalize it to handle that case. I suggest that you study the CRT, and spend more time thinking about this problem. You might want to think about the special case where $n=2$, for starters, and if you're still stuck, ask a specific question about the math on Mathematics. $\endgroup$ – D.W. Jul 5 '17 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.