Algorithm for finding all roots of linear Diophantine equation with finite solution space

Question

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

Answer 1

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.

Answer 2

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.