# How to solve this kind of system of integer inequalities?

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?

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