Solving a system like $\lfloor x / a_i \rfloor = b_i \pmod M$

Question

Suppose I have a system of equations like this:

\begin{cases}
\lfloor x / 100 \rfloor = 4 \pmod 8 \\
\lfloor x / 101 \rfloor = 2 \pmod 8 \\
\lfloor x / 105 \rfloor = 3 \pmod 8 \\
\lfloor x / 106 \rfloor = 7 \pmod 8
\end{cases}

I'm looking for the smallest positive integer solution $x$. Actually, I'm somewhat interested in finding all $x$.

I can find solutions using a brute-force Python script:

for x in range(10**6):
    if x//100%8==4 and x//101%8==2 and x//105%8==3 and x//106%8==7:
        print(x)

This finds $589254 \leq x \leq 589259$ and $674074 \leq x \leq 674099$. There are more if I search past $10^6$.

Could I reasonably find these solutions by hand? Is there a more efficient way than trying all integers sequentially?

One thought I've had is that the first equation $\lfloor x/100 \rfloor = 4 \pmod 8$ says something like,

$$ \exists k_1 \in \mathbb Z: 400 \leq x + 800k_1 < 500$$

but how do I "intersect" two or more such statements?

Answer 1

You can find the minimum such $x$ via integer linear programming. For example, here is SAS code to do that:

data indata;
   input i d r m;
   datalines;
1 100 4 8
2 101 2 8
3 105 3 8
4 106 7 8
;

proc optmodel;
   /* declare parameters and read data */
   set OBS;
   num d {OBS};
   num r {OBS};
   num m {OBS};
   read data indata into OBS=[i] d r m;

   /* declare decision variables */
   var X >= 1 integer;
   var Q {OBS} >= 0 integer;

   /* declare objective */
   min Z = X;

   /* declare constraints */
   con C1 {i in OBS}:
      X >= d[i] * (r[i] + m[i] * Q[i]);
   con C2 {i in OBS}:
      X <= d[i] * (r[i] + m[i] * Q[i] + 1) - 1;

   /* call mixed integer linear programming solver */
   solve;
quit;

The resulting log is as follows:

NOTE: Problem generation will use 4 threads.
NOTE: The problem has 5 variables (0 free, 0 fixed).
NOTE: The problem has 0 binary and 5 integer variables.
NOTE: The problem has 8 linear constraints (4 LE, 0 EQ, 4 GE, 0 range).
NOTE: The problem has 16 linear constraint coefficients.
NOTE: The problem has 0 nonlinear constraints (0 LE, 0 EQ, 0 GE, 0 range).
NOTE: The OPTMODEL presolver is disabled for linear problems.
NOTE: The initial MILP heuristics are applied.
NOTE: The MILP presolver value AUTOMATIC is applied.
NOTE: The MILP presolver removed 0 variables and 4 constraints.
NOTE: The MILP presolver removed 8 constraint coefficients.
NOTE: The MILP presolver modified 0 constraint coefficients.
NOTE: The presolved problem has 5 variables, 4 constraints, and 8 constraint coefficients.
NOTE: The MILP solver is called.
NOTE: The parallel Branch and Cut algorithm is used.
NOTE: The Branch and Cut algorithm is using up to 4 threads.
          Node   Active   Sols    BestInteger      BestBound      Gap    Time
             0        1      0              .    742.0000000        .       0
             0        1      0              .  20246.0000000        .       0
             0        1      0              .  35595.0000000        .       0
             0        1      0              .  42000.0000000        .       0
             0        1      0              .  70278.0000000        .       0
             0        1      0              .         128674        .       0
             0        1      0              .         158867        .       0
             0        1      0              .         173922        .       0
             0        1      0              .         186042        .       0
             0        1      0              .         192506        .       0
             0        1      0              .         258800        .       0
NOTE: The MILP solver added 1 cuts with 2 cut coefficients at the root.
            62        0      1         589254         589254    0.00%       0
NOTE: Optimal.
NOTE: Objective = 589254.