How to solve this kind of system of integer inequalities?

Question

I am trying to directly solve the following integer system of inequalities for all $(i, k)$ given $(a, b)$:

\begin{align*} v &= 2^{k-1} \text{ if } k > 0 \text{ else }0 \\ v &≤ i \\ v &< b \\ 0 &≤ i < a + v \\ 0 &≤ k < b \\ i &= 0 \pmod v \\ \end{align*}

For reference, if you have Mathematica, you can try using it to see some sample solutions:

With[{an = ..., bn = ...},
    Solve[
        With[{v = Piecewise[{{2^(k - 1), k > 0}}, 0]},
             {i >= v,
              Mod[i, Piecewise[{{v, v != 0}}, 1]] == 0,
              i < v + an,
              v < bn,
              k < bn,
              i >= 0,
              k >= 0}],
        {i, k},
        Integers]]

What I am currently doing is trying out all potential values of $i$, then solving it for all possible $k$.

What I would like to do is to find a way to iterate though all the solutions directly, instead of trying out numbers and seeing which ones work. In other words, I want a "nice" function $f_{a,b}(i_1, j_1) = (i_2, j_2)$ that can give me a new solution given a previous one, and which eventually lists all the solutions to the system.

However, I'm not sure how to do this given that there are 2 unknowns.

Is there a systematic technique for solving this kind of system directly, or do I have to just try out all potential values for $i$ or $j$ and filter out the ones that don't satisfy the constraints?

Answer 1

Since we are dealing with integer values, this problem is classified as integer programming. There are some techniques for these types of problems, but I highly doubt that any of them would be applicable to this specific one, since the equations and constraints are nonlinear. There is no general technique for solving nonlinear optimization/feasibility problems other than simplifying the equations and constraints as much as possible (And yes, there are some for some types).

As I see it, the main problem is, your statement is way too complex and can be simplified a great deal. Let's walk through this problem step by step.

First get rid of the trivial cases. If $b=0$ there is no solution (assuming the unknowns are non-negative, which is the default case in integer programming). Since $v=2^{k-1}$ if $k>0$ and $v=0$ elsewhere, then if $k=0$ (e.g. $b=1$), surely $v\le i$ for all integer $i$. And $0\le i<a$ implies a subset of the solutions of $(i,k)$ as: $$\{(0,0),(1,0),...,(a-1,0)\}$$ Now taking $i\ge v$ into account, it is safe to assume that both $i,k$ are non-zero, i.e. there is no solution for $a=0$ or $b=0$.

If $b=1$ then $k=0$ and we have got the whole solution. So from now on, $b>1$.

Let's simplify the inequalities a little bit. From $i\equiv 0\mod{v}$ one can say that $i=jv$ where $j$ is a positive integer. Also note that since $v=2^{k-1}<b$ and $b>1$, it is safe to remove the $k<b$ constraint. With this change of variable, the problem simplifies to: $$\text{Find positive pair }(j,k)\\ \begin{align} 2^{k-1}&<b\\ 2^{k-1}j&<a+2^{k-1} \end{align} $$ For $j=1$ we would only have: $2^{k-1}<b$. Hence another subset of the solution for $(j,k)$ would be $$\{(1,1),(1,2),...,(1,k_0)\}$$ where $k_0$ is the greatest integer less than $\log_2 b+1$.

If $j>1$ then $2^{k-1}(j-1)<a$. Therefore $j-1<\frac{a}{b}$, and the algorithm of finding the rest of the solution can be structured as follows:

for (k = 1; k < log2(b) + 1; k++)
    for (j = 2; j < (float) a / b + 1; j++)
        i = j * 2 ^ (k - 1)
        append (i, k) to the solution