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

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

• 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\}$$ – Ethan Oct 24 '15 at 20:00
• 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). – ml0105 Oct 24 '15 at 20:25
• @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. – Abstraction Oct 24 '15 at 20:33
• @Abstraction: I have two concrete cases: $c=-200$ and $c=-40$. – vonjd Oct 24 '15 at 20:38
• @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. – vonjd Oct 24 '15 at 20:45

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.

• I have an additional condition, but I thought it would make things more complicated: $$a_1+a_2+\dots+a_{16}+a_{17}=0$$ – vonjd Oct 24 '15 at 21:04
• 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... – vonjd Oct 24 '15 at 21:10
• @vonjd Included that condition. Still way too many solutions, it seems. – Abstraction Oct 24 '15 at 21:39
• 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. – vonjd Oct 25 '15 at 8:38
• @vonjd For $c=-40$ it's 75815500714363776 and for $c=-200$ it's 18155720223502317. – Abstraction Oct 26 '15 at 18:14

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.