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?
Best Answer
I wrote and ran some Mathematica code:
Running the code gives:
If we, for example, want to extend the search to $10^6$ the number of solutions is given by: