0
$\begingroup$

I have the following Diophantine equation:

$$17a_1+16a_2+\dots+2a_{16}+a_{17}+c=0$$

with $c$ being a constant integer value, where I have two concrete cases: $c=-200$ and $c=-40$.

I am looking for an algorithm that finds all solutions (roots) under the following condition: $$a_n\in\{-10,-9,\dots,-1,0,1,\dots,9,10\}.$$

So the solution space must be finite.

What I tried so far
I thought about a brute force approach but the solutions space is too big ($\sim3\times10^{22}$). The other idea I had was starting from one solution and finding an algorithm which changes one $a_n$ at a time and counterbalance that by systematically changing other $a_n$'s but I haven't discovered a good system yet to really find all solutions.

My question
Could you give me that algorithm (e.g. in pseudocode) or at least some ideas where to look for a solution?

Edit
I have an additional condition but I don't know if it makes things worse (in the sense of more complicated finding solutions) because we now have a system of linear Diophantine equations:

$$a_1+a_2+\dots+a_{16}+a_{17}=0$$

I thought that it would be easier to use this additional condition to prune the solutions to the first equation but I didn't imagine that there were so many solutions to it...

$\endgroup$
  • $\begingroup$ I'd first make the substitution $b_n-10=a_n$ so that your problem reduces to finding solutions to: $$17b_1+16b_2+\dots+2b_{16}+b_{17}=1530-c$$ $$b_n\in\{0,1,2,3,\cdots 18,19,20\}$$ $\endgroup$ – Ethan Oct 24 '15 at 20:00
  • $\begingroup$ Are you familiar with the Knapsack problem? It's NP-Complete. So you won't likely find a useful characterization for solutions, nor a useful way to enumerate them. Even restricting to the case of 0 and 1 for your domain, it's still computationally difficult (see SAT for example). $\endgroup$ – ml0105 Oct 24 '15 at 20:25
  • $\begingroup$ @ml0105 Here we have fixed size of a problem (17), so solving for domain $\{0,1\}$ would be trivial. But the major problem is that this problem is not even of NP class, because in general case (when c isn't close to 1530) we have too many solutions, so outputting them is already a challenge. I'm running an estimate now for c=0, but it seems that there will be more than $10^{17}$ solutions, which we can't output within reasonable time. $\endgroup$ – Abstraction Oct 24 '15 at 20:33
  • $\begingroup$ @Abstraction: I have two concrete cases: $c=-200$ and $c=-40$. $\endgroup$ – vonjd Oct 24 '15 at 20:38
  • $\begingroup$ @Abstraction: I can't imagine that there are $10^{17}$ solutions because the equation seems quite "rigid". My "feeling" is that there must be a lot less. But perhaps I am wrong. $\endgroup$ – vonjd Oct 24 '15 at 20:45
1
$\begingroup$

Here is code in C# for calculating a number of solutions. Upd: now code includes condition $\sum_ia_i = 0$, and now number of solutions fits into long type:

class Program {
  const int bound = 10;
  const int Num = 17;

  static int[] limit = new int[Num+1];
  static long[,,] memoize = new long[Num * (Num + 1) * bound + 1, Num, Num * bound * 2 + 1];

  static long CountSums(int acc, int i, int valAcc) {
    if (acc > limit[i] || acc < -limit[i]) return 0;
    if (valAcc > (Num - i) * bound || valAcc < -(Num - i) * bound) return 0;
    if (i == Num) return 1;
    if (memoize[acc + (Num * (Num + 1) * bound) / 2, i, valAcc + Num*bound] != -1)
      return memoize[acc + (Num * (Num + 1) * bound) / 2, i, valAcc + Num*bound];
    long ret = 0;
    for (int v = -bound; v <= bound; ++v) {
      //if (i == 0) Console.WriteLine("Checking a[0] = " + v);
      ret += CountSums(acc + (Num - i) * v, i + 1, valAcc+v);
            if(i==0) Console.WriteLine(ret);
    }
    memoize[acc + (Num * (Num + 1) * bound) / 2, i, valAcc + Num*bound] = ret;
    return ret;
  }

  static void Main(string[] args) {
    int c = -200;

    int[] a = new int[17];
    for (int i = 0; i < Num; ++i) limit[Num - i - 1] = limit[Num - i] + (i+1) * bound;
    for (int i = 0; i < memoize.GetLength(0); ++i)
      for (int j = 0; j < memoize.GetLength(1); ++j)
        for (int k = 0; k < memoize.GetLength(2); ++k)
          memoize[i, j, k] = -1;

    Console.WriteLine(CountSums(c,0,0));
  }        
}

Bad news: for $c=-200$ there are 434464777059469959 solutions and for $c = -40$ there are 1427251637075119231 solutions. Finding them is similar to counting, but memoizing solutions themselves all the way is out of question. Possibly solution memoization should be limited to ~6 last members. The main problem is that any enumeration of this many solutions won't be done in reasonable time.

$\endgroup$
  • $\begingroup$ I have an additional condition, but I thought it would make things more complicated: $$a_1+a_2+\dots+a_{16}+a_{17}=0$$ $\endgroup$ – vonjd Oct 24 '15 at 21:04
  • $\begingroup$ I thought that it would be easier to use this additional condition to prune the solutions to the first equation but I didn't imagine that there were so many solutions to it... $\endgroup$ – vonjd Oct 24 '15 at 21:10
  • $\begingroup$ @vonjd Included that condition. Still way too many solutions, it seems. $\endgroup$ – Abstraction Oct 24 '15 at 21:39
  • $\begingroup$ Thank you, I upvoted and accepted your answer. Well, too bad... Could you do me a favour a let the program run not for $17$ but for $16$ $a$-terms, all else being equal (i.e. starting from $16a_1$ up to $a_{16}$) - Thank you again. $\endgroup$ – vonjd Oct 25 '15 at 8:38
  • 1
    $\begingroup$ @vonjd For $c=-40$ it's 75815500714363776 and for $c=-200$ it's 18155720223502317. $\endgroup$ – Abstraction Oct 26 '15 at 18:14
1
$\begingroup$

I would suggest the following:

Use 17 different hash tables. The $i$-th hash table has keys of the values that $ia_{18-i}+\cdots+a_{17}+c$ can take, while the value is the number of occurrences of that value. These hash tables can be updated easily because $$ia_{18-i}+\cdots+a_{17}+c=ia_{18-i}+((i-1)a_{17-i}+\cdots+a_{17}+c).$$ Therefore, take each value of $a_{18-i}$, compute $ia_{18-i}$ add this value to each key for the $i-1$-th hash table; update the $i$-th hash table with the sums and their multiplicity.

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