余り問題

以下の問題は PyQBPP を使って解くことができます。 次の条件を満たす最小の非負整数 $x$ を求めます:

• $x$ を 3 で割った余りが 2、
• $x$ を 5 で割った余りが 3、
• $x$ を 7 で割った余りが 5。

3、5、7 は互いに素であるため、1周期内で $x$ を探索すれば十分です:

\[0\leq x \leq 3\times 5\times 7 -1\]

非負整数 $d_3$、$d_5$、$d_7$（商）を導入し、余りの条件を線形等式として書き直します:

\[\begin{aligned} x - 3d_3 &= 2 \\ x - 5d_5 &=3 \\ x - 7d_7 &= 5 \end{aligned}\]

これらの制約の下で $x$ を最小化したいです。 上記の $x$ の範囲から、商の変数を以下のように制限できます:

\[\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 プログラム

以下のプログラムは、この余り問題の解 $x$ を求めます:

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 と商 d3、d5、d7 はネイティブ整数変数で、バイナリ変数に展開されずに整数のまま探索されます。 3つの等式の左辺を c3、c5、c7 とし、各等式を qbpp.cons() で制約として宣言します。 制約を破ると、違反量の2乗に重みを掛けた値がエネルギーに加わります。

大きな重み（1000）を使って x を最小化することで、x の削減よりも制約の充足が優先されます。

最後に、Easy Solver がキーワード引数で指定された制限時間（1.0秒）内で f の低エネルギー解を探索し、得られた値と、破った制約の本数 f.cons(sol) は以下のように出力されます:

x = 68
68 - 3 * 22 = 2
68 - 5 * 13 = 3
68 - 7 * 9 = 5
violated constraints = 0

したがって、

\[\begin{aligned} x &\equiv 68 & (\bmod 105) \end{aligned}\]

最小の解は $x=68$ です。