Remainder Problem
The following problem can be solved using PyQBPP. Find the minimum non-negative integer $x$ such that
- the remainder when $x$ is divided by 3 is 2,
- the remainder when $x$ is divided by 5 is 3, and
- the remainder when $x$ is divided by 7 is 5.
Since 3, 5, and 7 are pairwise coprime, it is enough to search $x$ within one period:
\[0\leq x \leq 3\times 5\times 7 -1\]Introduce non-negative integers $d_3$, $d_5$, and $d_7$ (quotients) and rewrite the remainder conditions as linear equalities:
\[\begin{aligned} x - 3d_3 &= 2 \\ x - 5d_5 &=3 \\ x - 7d_7 &= 5 \end{aligned}\]We want to minimize $x$ subject to these constraints. From the range $x$ above, we can bound the quotient variables as
\[\begin{aligned} 0&\leq d_3 \leq 5\times 7-1 \\ 0&\leq d_5 \leq 3\times 7-1 \\ 0&\leq d_7 \leq 3\times 5-1 \end{aligned}\]PyQBPP program
The following program finds a solution $x$ for this remainder problem:
import pyqbpp as qbpp
x = qbpp.var("x", integer=(0, 3 * 5 * 7 - 1))
d3 = qbpp.var("d3", integer=(0, 5 * 7 - 1))
d5 = qbpp.var("d5", integer=(0, 3 * 7 - 1))
d7 = qbpp.var("d7", integer=(0, 3 * 5 - 1))
c3 = x - 3 * d3
c5 = x - 5 * d5
c7 = x - 7 * d7
f = x + 1000 * (qbpp.cons(c3 == 2) + qbpp.cons(c5 == 3) + qbpp.cons(c7 == 5))
f.simplify()
solver = qbpp.EasySolver(f)
sol = solver.search(time_limit=1.0)
print(f"x = {sol(x)}")
print(f"{sol(x)} - 3 * {sol(d3)} = {sol(c3)}")
print(f"{sol(x)} - 5 * {sol(d5)} = {sol(c5)}")
print(f"{sol(x)} - 7 * {sol(d7)} = {sol(c7)}")
print(f"violated constraints = {f.cons(sol)}")
x and the quotients d3, d5, and d7 are native integer variables, which are not expanded into binary variables and are searched as integers. The left-hand sides of the three equalities are c3, c5, and c7, and each equality is declared as a constraint with qbpp.cons(). When a constraint is violated, the square of the violation multiplied by the weight is added to the energy.
We then minimize x with a large weight (1000) so that satisfying the constraints is prioritized over reducing x.
Finally, the Easy Solver searches for a low-energy solution of f within the time limit (1.0 second) specified as a keyword argument, and the obtained values and the number of violated constraints f.cons(sol) are printed as follows:
x = 68
68 - 3 * 22 = 2
68 - 5 * 13 = 3
68 - 7 * 9 = 5
violated constraints = 0
Therefore,
\[\begin{aligned} x &\equiv 68 & (\bmod 105) \end{aligned}\]and the minimum solution is $x=68$.