1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.