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

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?

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


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$$

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

2. Continue the next steps for all unknown

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