How to solve a linear diophantine equation with six unknowns with constraints?

Question

I would like to solve this linear diophantine equation: $$ 40x_1+296x_2+945x_3+2048x_4+4500x_5+8640x_6=616103 $$ All the answers have to be an integer number in the interval $\{[10] \cup [29,95]\}$.

As a first step, I started by finding a particular solution of the equation without taking the constraints into account. I used the following procedure:

• Find a particular solution for $x_6$: $$ gcd(40,296,945,2048,4500)w_6+8640x_6=616103 $$ I found $x_6=71$ and $w_6=2663$. I can also determine a general solution: $X_6=71-n_6$ and $W_6=2663+8640n_6$.
• Use $w_6$ to find the other solutions by repeating the same procedure: $$ 40x_1+296x_2+945x_3+2048x_4+4500x_5=gcd(40,296,945,2048,4500)w_6 = 2663 $$ $$ gcd(40,296,945,2048)w_5+4500x_5=2663 $$ $$ ... $$

That way, I could determine one particular solution of this equation: $$ x_1=6876450, x_2=-916860, x_3=-3885, x_4=1, x_5=1, x_6=71 $$ I also introduce some intermediate variables to compute a general solution: $$X_6=71-n_6, W_6=2663+8640n_6$$ $$X_5=1+n_5,W_5=-1837-4500n_5$$ $$X_4=1+n_4,W_4=-3885-2018n_4$$ $$X_3=-3885+8n_3,W_3=458430-945n_3$$ $$X_2=-916860-5n_2$$ $$X_1=6876450+37n_2$$

Now, I'm stuck with my general solutions and I don't know what I can do to fit my particular solutions with the constraints. Here are the thoughts I got to solve this problem and the associated issue:

• I wanted to find what values of $n_2$ make $x_1$ in the interval defined above. I found $n_2=\{-185849,-185848\}$ that gives $x_1=\{37,74\}$ but $x_2$ is out of the interval with these values.
• I wanted to rewrite the equation that way: $$40\cdot(6876450+37n_2)+296\cdot(-916860-5n_2)+945\cdot(-3885+8n_3)+2048\cdot(1+n_4)+4500\cdot(1+n_5)+8640\cdot(71-n_6)=616103$$ However, I can't because $n_2$, $n_3$, $n_4$, $n_5$ and $n_6$ are not independent and the choice of the value of $n_6$, for instance, has an impact on $w_6$ that has an impact on all general solutions.

What can I do to find a solution that corresponds to the constraints?

Answer 1

Not a 'real' answer, but it was too big for a comment.

I wrote and ran some Mathematica code:

In[1]:=FullSimplify[
 Solve[{40*x1 + 296*x2 + 945*x3 + 2048*x4 + 4500*x5 + 8640*x6 == 
    616103, 1 <= x1 <= x2 <= x3 <= x4 <= x5 <= x6 <= 1000}, {x1, x2, 
   x3, x4, x5, x6}, PositiveIntegers]]

Running the code gives:

Out[1]={{x1 -> 1, x2 -> 2, x3 -> 3, x4 -> 12, x5 -> 27, x6 -> 54}, {x1 -> 1, 
  x2 -> 2, x3 -> 7, x4 -> 12, x5 -> 30, x6 -> 52}, {x1 -> 1, x2 -> 2, 
  x3 -> 11, x4 -> 12, x5 -> 33, x6 -> 50}, {x1 -> 1, x2 -> 3, x3 -> 3,
   x4 -> 5, x5 -> 9, x6 -> 65}, {x1 -> 1, x2 -> 5, x3 -> 7, x4 -> 36, 
  x5 -> 40, x6 -> 41}, {x1 -> 1, x2 -> 6, x3 -> 19, x4 -> 29, 
  x5 -> 31, x6 -> 46}, {x1 -> 1, x2 -> 6, x3 -> 23, x4 -> 29, 
  x5 -> 34, x6 -> 44}, {x1 -> 1, x2 -> 6, x3 -> 27, x4 -> 29, 
  x5 -> 37, x6 -> 42}, {x1 -> 1, x2 -> 8, x3 -> 11, x4 -> 15, 
  x5 -> 37, x6 -> 47}, {x1 -> 1, x2 -> 8, x3 -> 15, x4 -> 15, 
  x5 -> 40, x6 -> 45}, {x1 -> 1, x2 -> 12, x3 -> 15, x4 -> 32, 
  x5 -> 32, x6 -> 45}, {x1 -> 1, x2 -> 12, x3 -> 19, x4 -> 32, 
  x5 -> 35, x6 -> 43}, {x1 -> 1, x2 -> 12, x3 -> 23, x4 -> 32, 
  x5 -> 38, x6 -> 41}, {x1 -> 1, x2 -> 18, x3 -> 19, x4 -> 35, 
  x5 -> 39, x6 -> 40}, {x1 -> 1, x2 -> 25, x3 -> 27, x4 -> 31, 
  x5 -> 31, x6 -> 44}, {x1 -> 1, x2 -> 25, x3 -> 31, x4 -> 31, 
  x5 -> 34, x6 -> 42}, {x1 -> 1, x2 -> 31, x3 -> 31, x4 -> 34, 
  x5 -> 38, x6 -> 39}, {x1 -> 2, x2 -> 3, x3 -> 3, x4 -> 15, x5 -> 39,
   x6 -> 47}, {x1 -> 2, x2 -> 3, x3 -> 7, x4 -> 15, x5 -> 42, 
  x6 -> 45}, {x1 -> 2, x2 -> 4, x3 -> 7, x4 -> 8, x5 -> 24, 
  x6 -> 56}, {x1 -> 2, x2 -> 7, x3 -> 7, x4 -> 32, x5 -> 34, 
  x6 -> 45}, {x1 -> 2, x2 -> 7, x3 -> 11, x4 -> 32, x5 -> 37, 
  x6 -> 43}, {x1 -> 2, x2 -> 7, x3 -> 15, x4 -> 32, x5 -> 40, 
  x6 -> 41}, {x1 -> 2, x2 -> 8, x3 -> 19, x4 -> 25, x5 -> 25, 
  x6 -> 50}, {x1 -> 2, x2 -> 8, x3 -> 23, x4 -> 25, x5 -> 28, 
  x6 -> 48}, {x1 -> 2, x2 -> 10, x3 -> 11, x4 -> 11, x5 -> 31, 
  x6 -> 51}, {x1 -> 2, x2 -> 14, x3 -> 19, x4 -> 28, x5 -> 29, 
  x6 -> 47}, {x1 -> 2, x2 -> 14, x3 -> 23, x4 -> 28, x5 -> 32, 
  x6 -> 45}, {x1 -> 2, x2 -> 14, x3 -> 27, x4 -> 28, x5 -> 35, 
  x6 -> 43}, {x1 -> 2, x2 -> 20, x3 -> 23, x4 -> 31, x5 -> 36, 
  x6 -> 42}, {x1 -> 2, x2 -> 20, x3 -> 27, x4 -> 31, x5 -> 39, 
  x6 -> 40}, {x1 -> 3, x2 -> 3, x3 -> 11, x4 -> 25, x5 -> 27, 
  x6 -> 50}, {x1 -> 3, x2 -> 3, x3 -> 15, x4 -> 25, x5 -> 30, 
  x6 -> 48}, {x1 -> 3, x2 -> 3, x3 -> 19, x4 -> 25, x5 -> 33, 
  x6 -> 46}, {x1 -> 3, x2 -> 3, x3 -> 23, x4 -> 25, x5 -> 36, 
  x6 -> 44}, {x1 -> 3, x2 -> 5, x3 -> 7, x4 -> 11, x5 -> 36, 
  x6 -> 49}, {x1 -> 3, x2 -> 5, x3 -> 11, x4 -> 11, x5 -> 39, 
  x6 -> 47}, {x1 -> 3, x2 -> 9, x3 -> 11, x4 -> 28, x5 -> 31, 
  x6 -> 47}, {x1 -> 3, x2 -> 9, x3 -> 15, x4 -> 28, x5 -> 34, 
  x6 -> 45}, {x1 -> 3, x2 -> 9, x3 -> 19, x4 -> 28, x5 -> 37, 
  x6 -> 43}, {x1 -> 3, x2 -> 9, x3 -> 23, x4 -> 28, x5 -> 40, 
  x6 -> 41}, {x1 -> 3, x2 -> 11, x3 -> 11, x4 -> 14, x5 -> 43, 
  x6 -> 44}, {x1 -> 3, x2 -> 15, x3 -> 15, x4 -> 31, x5 -> 38, 
  x6 -> 42}, {x1 -> 3, x2 -> 16, x3 -> 23, x4 -> 24, x5 -> 26, 
  x6 -> 49}, {x1 -> 3, x2 -> 22, x3 -> 23, x4 -> 27, x5 -> 30, 
  x6 -> 46}, {x1 -> 3, x2 -> 22, x3 -> 27, x4 -> 27, x5 -> 33, 
  x6 -> 44}, {x1 -> 4, x2 -> 4, x3 -> 7, x4 -> 28, x5 -> 36, 
  x6 -> 45}, {x1 -> 4, x2 -> 4, x3 -> 11, x4 -> 28, x5 -> 39, 
  x6 -> 43}, {x1 -> 4, x2 -> 5, x3 -> 11, x4 -> 21, x5 -> 21, 
  x6 -> 54}, {x1 -> 4, x2 -> 5, x3 -> 15, x4 -> 21, x5 -> 24, 
  x6 -> 52}, {x1 -> 4, x2 -> 5, x3 -> 19, x4 -> 21, x5 -> 27, 
  x6 -> 50}, {x1 -> 4, x2 -> 7, x3 -> 7, x4 -> 7, x5 -> 30, 
  x6 -> 53}, {x1 -> 4, x2 -> 11, x3 -> 11, x4 -> 24, x5 -> 25, 
  x6 -> 51}, {x1 -> 4, x2 -> 11, x3 -> 15, x4 -> 24, x5 -> 28, 
  x6 -> 49}, {x1 -> 4, x2 -> 11, x3 -> 19, x4 -> 24, x5 -> 31, 
  x6 -> 47}, {x1 -> 4, x2 -> 11, x3 -> 23, x4 -> 24, x5 -> 34, 
  x6 -> 45}, {x1 -> 4, x2 -> 17, x3 -> 19, x4 -> 27, x5 -> 35, 
  x6 -> 44}, {x1 -> 4, x2 -> 17, x3 -> 23, x4 -> 27, x5 -> 38, 
  x6 -> 42}, {x1 -> 5, x2 -> 6, x3 -> 7, x4 -> 24, x5 -> 30, 
  x6 -> 49}, {x1 -> 5, x2 -> 6, x3 -> 11, x4 -> 24, x5 -> 33, 
  x6 -> 47}, {x1 -> 5, x2 -> 6, x3 -> 15, x4 -> 24, x5 -> 36, 
  x6 -> 45}, {x1 -> 5, x2 -> 6, x3 -> 19, x4 -> 24, x5 -> 39, 
  x6 -> 43}, {x1 -> 5, x2 -> 7, x3 -> 15, x4 -> 17, x5 -> 18, 
  x6 -> 56}, {x1 -> 5, x2 -> 12, x3 -> 15, x4 -> 27, x5 -> 40, 
  x6 -> 42}, {x1 -> 5, x2 -> 13, x3 -> 15, x4 -> 20, x5 -> 22, 
  x6 -> 53}, {x1 -> 5, x2 -> 13, x3 -> 19, x4 -> 20, x5 -> 25, 
  x6 -> 51}, {x1 -> 5, x2 -> 19, x3 -> 19, x4 -> 23, x5 -> 29, 
  x6 -> 48}, {x1 -> 5, x2 -> 19, x3 -> 23, x4 -> 23, x5 -> 32, 
  x6 -> 46}, {x1 -> 6, x2 -> 7, x3 -> 7, x4 -> 27, x5 -> 42, 
  x6 -> 42}, {x1 -> 6, x2 -> 8, x3 -> 11, x4 -> 20, x5 -> 27, 
  x6 -> 51}, {x1 -> 6, x2 -> 8, x3 -> 15, x4 -> 20, x5 -> 30, 
  x6 -> 49}, {x1 -> 6, x2 -> 8, x3 -> 19, x4 -> 20, x5 -> 33, 
  x6 -> 47}, {x1 -> 6, x2 -> 12, x3 -> 35, x4 -> 37, x5 -> 37, 
  x6 -> 39}, {x1 -> 6, x2 -> 14, x3 -> 15, x4 -> 23, x5 -> 34, 
  x6 -> 46}, {x1 -> 6, x2 -> 14, x3 -> 19, x4 -> 23, x5 -> 37, 
  x6 -> 44}, {x1 -> 6, x2 -> 14, x3 -> 23, x4 -> 23, x5 -> 40, 
  x6 -> 42}, {x1 -> 6, x2 -> 15, x3 -> 15, x4 -> 16, x5 -> 16, 
  x6 -> 57}, {x1 -> 7, x2 -> 7, x3 -> 27, x4 -> 37, x5 -> 39, 
  x6 -> 39}, {x1 -> 7, x2 -> 9, x3 -> 11, x4 -> 23, x5 -> 39, 
  x6 -> 44}, {x1 -> 7, x2 -> 9, x3 -> 15, x4 -> 23, x5 -> 42, 
  x6 -> 42}, {x1 -> 7, x2 -> 10, x3 -> 11, x4 -> 16, x5 -> 21, 
  x6 -> 55}, {x1 -> 7, x2 -> 10, x3 -> 15, x4 -> 16, x5 -> 24, 
  x6 -> 53}, {x1 -> 7, x2 -> 16, x3 -> 19, x4 -> 19, x5 -> 31, 
  x6 -> 48}, {x1 -> 8, x2 -> 9, x3 -> 27, x4 -> 33, x5 -> 33, 
  x6 -> 43}, {x1 -> 8, x2 -> 9, x3 -> 31, x4 -> 33, x5 -> 36, 
  x6 -> 41}, {x1 -> 8, x2 -> 11, x3 -> 11, x4 -> 19, x5 -> 33, 
  x6 -> 48}, {x1 -> 8, x2 -> 11, x3 -> 15, x4 -> 19, x5 -> 36, 
  x6 -> 46}, {x1 -> 8, x2 -> 11, x3 -> 19, x4 -> 19, x5 -> 39, 
  x6 -> 44}, {x1 -> 8, x2 -> 15, x3 -> 27, x4 -> 36, x5 -> 37, 
  x6 -> 40}, {x1 -> 9, x2 -> 10, x3 -> 15, x4 -> 36, x5 -> 36, 
  x6 -> 42}, {x1 -> 9, x2 -> 10, x3 -> 19, x4 -> 36, x5 -> 39, 
  x6 -> 40}, {x1 -> 9, x2 -> 13, x3 -> 15, x4 -> 15, x5 -> 30, 
  x6 -> 50}, {x1 -> 9, x2 -> 17, x3 -> 31, x4 -> 32, x5 -> 34, 
  x6 -> 42}, {x1 -> 9, x2 -> 23, x3 -> 27, x4 -> 35, x5 -> 35, 
  x6 -> 41}, {x1 -> 9, x2 -> 23, x3 -> 31, x4 -> 35, x5 -> 38, 
  x6 -> 39}, {x1 -> 10, x2 -> 12, x3 -> 19, x4 -> 32, x5 -> 33, 
  x6 -> 44}, {x1 -> 10, x2 -> 12, x3 -> 23, x4 -> 32, x5 -> 36, 
  x6 -> 42}, {x1 -> 10, x2 -> 12, x3 -> 27, x4 -> 32, x5 -> 39, 
  x6 -> 40}, {x1 -> 10, x2 -> 14, x3 -> 15, x4 -> 18, x5 -> 42, 
  x6 -> 43}, {x1 -> 10, x2 -> 18, x3 -> 19, x4 -> 35, x5 -> 37, 
  x6 -> 41}, {x1 -> 10, x2 -> 25, x3 -> 31, x4 -> 31, x5 -> 32, 
  x6 -> 43}, {x1 -> 10, x2 -> 31, x3 -> 31, x4 -> 34, x5 -> 36, 
  x6 -> 40}, {x1 -> 11, x2 -> 14, x3 -> 23, x4 -> 28, x5 -> 30, 
  x6 -> 46}, {x1 -> 11, x2 -> 14, x3 -> 27, x4 -> 28, x5 -> 33, 
  x6 -> 44}, {x1 -> 11, x2 -> 20, x3 -> 23, x4 -> 31, x5 -> 34, 
  x6 -> 43}, {x1 -> 11, x2 -> 20, x3 -> 27, x4 -> 31, x5 -> 37, 
  x6 -> 41}, {x1 -> 12, x2 -> 15, x3 -> 15, x4 -> 31, x5 -> 36, 
  x6 -> 43}, {x1 -> 12, x2 -> 15, x3 -> 19, x4 -> 31, x5 -> 39, 
  x6 -> 41}, {x1 -> 12, x2 -> 16, x3 -> 23, x4 -> 24, x5 -> 24, 
  x6 -> 50}, {x1 -> 12, x2 -> 22, x3 -> 23, x4 -> 27, x5 -> 28, 
  x6 -> 47}, {x1 -> 12, x2 -> 22, x3 -> 27, x4 -> 27, x5 -> 31, 
  x6 -> 45}, {x1 -> 13, x2 -> 17, x3 -> 19, x4 -> 27, x5 -> 33, 
  x6 -> 45}, {x1 -> 13, x2 -> 17, x3 -> 23, x4 -> 27, x5 -> 36, 
  x6 -> 43}, {x1 -> 13, x2 -> 17, x3 -> 27, x4 -> 27, x5 -> 39, 
  x6 -> 41}, {x1 -> 13, x2 -> 23, x3 -> 23, x4 -> 30, x5 -> 40, 
  x6 -> 40}, {x1 -> 14, x2 -> 19, x3 -> 19, x4 -> 23, x5 -> 27, 
  x6 -> 49}, {x1 -> 14, x2 -> 19, x3 -> 23, x4 -> 23, x5 -> 30, 
  x6 -> 47}, {x1 -> 16, x2 -> 16, x3 -> 19, x4 -> 19, x5 -> 29, 
  x6 -> 49}, {x1 -> 17, x2 -> 17, x3 -> 19, x4 -> 22, x5 -> 41, 
  x6 -> 42}, {x1 -> 18, x2 -> 23, x3 -> 31, x4 -> 35, x5 -> 36, 
  x6 -> 40}, {x1 -> 19, x2 -> 31, x3 -> 31, x4 -> 34, x5 -> 34, 
  x6 -> 41}, {x1 -> 20, x2 -> 20, x3 -> 23, x4 -> 31, x5 -> 32, 
  x6 -> 44}, {x1 -> 20, x2 -> 20, x3 -> 27, x4 -> 31, x5 -> 35, 
  x6 -> 42}, {x1 -> 20, x2 -> 20, x3 -> 31, x4 -> 31, x5 -> 38, 
  x6 -> 40}, {x1 -> 20, x2 -> 26, x3 -> 27, x4 -> 34, x5 -> 39, 
  x6 -> 39}, {x1 -> 21, x2 -> 22, x3 -> 27, x4 -> 27, x5 -> 29, 
  x6 -> 46}, {x1 -> 22, x2 -> 23, x3 -> 23, x4 -> 30, x5 -> 38, 
  x6 -> 41}, {x1 -> 27, x2 -> 29, x3 -> 31, x4 -> 38, x5 -> 38, 
  x6 -> 38}}

---

If we, for example, want to extend the search to $10^6$ the number of solutions is given by:

In[2]:=Length[FullSimplify[
  Solve[{40*x1 + 296*x2 + 945*x3 + 2048*x4 + 4500*x5 + 8640*x6 == 
     616103, 1 <= x1 <= x2 <= x3 <= x4 <= x5 <= x6 <= 10^6}, {x1, x2, 
    x3, x4, x5, x6}, PositiveIntegers]]]

Out[2]=128

Answer 2

To find all the answers, I coded my own solver following this algorithm:

1. Find all possible $x_6$ that fits in the constraints and its corresponding $w_6$
2. For each possible $x_6$, rewrite the equation that way:

$$ 40x_1+296x_2+945x_3+2048x_4+4500x_5=𝑔𝑐𝑑(40,296,945,2048,4500)w_6 $$

3. Find all possible $x_5$ that fits in the constraints and its corresponding $w_5$

4. Continue the next steps for all unknown

I found 20926 solutions that satisfy the constraints. My code is available on Gist.