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$
9
  • $\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$ Oct 24, 2015 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, 2015 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$ Oct 24, 2015 at 20:33
  • $\begingroup$ @Abstraction: I have two concrete cases: $c=-200$ and $c=-40$. $\endgroup$
    – vonjd
    Oct 24, 2015 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, 2015 at 20:45

2 Answers 2

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$
5
  • $\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, 2015 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, 2015 at 21:10
  • $\begingroup$ @vonjd Included that condition. Still way too many solutions, it seems. $\endgroup$ Oct 24, 2015 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, 2015 at 8:38
  • 1
    $\begingroup$ @vonjd For $c=-40$ it's 75815500714363776 and for $c=-200$ it's 18155720223502317. $\endgroup$ Oct 26, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .