Algorithm to determine non-negative-values solution existance for linear diophantine equation

Question

I am looking for a method to determine if there is a solution to equations such as: 3n1+4n2+5n3=456, where n1,n2,n3 are positive integers.

Or more general: are there zero or positive integers n1,n2,n3... that solves the equation k1n1+k2n2+k3n3...=m where k1,k2,k3... and m are known positive integers.

I don't need to find a solution - just to determine if a solution exist.

Edit:

Concerning the practical use of this algorithm:

In a communication library, I want to decide if a given message is valid according to its size, before handling the message. For example: I know that a message contains zero-or-more 3-bytes elements, zero-or-more 4-bytes elements, and zero-or-more 5-bytes elements. I received a message of 456 bytes, and I want to determine its validity before further inspecting its content. Of course the header of the message contains the number of elements of each type, but I want to make a first-inspection in the communication-library level by passing something like pair<MsgType,vector<3,4,5>>.

Answer 1

You're asking if the regular expression

(xxx|xxxx|xxxxx)*

matches xx...x, where x occurs 456 times.

Here's a solution in O(n+a^2), where a is the smallest of the numbers on the left side (in this case 3).

Suppose your numbers are 6,7,15. I'll call a number expressible in the form 6x+7y+15z "available". You are to check if a given number is available.

If you're able to get some number n, then surely you will be able to get n+6, n+12, n+18 - in general, n+6k for all k >= 0. On the other side, if you are unable to get some number n, then n-6 is surely not available too (if you could get (n-6), then (n-6)+6=n would be available), this means n-12, n-18, n-6k are not available neither.

Suppose you have determined that 15 is available but 9 is not. In our case, 15=6*0+7*0+15*1 but won't be able to get 9 in any way. So, by our previous reasoning, 15+6k is available for all k >= 0 and 9-6k for all k >= 0 is not. If you've got some number that divided by 6 gives 3 as remainder (3, 9, 15, 21, ...) you can quickly answer: numbers <= 9 are not available, numbers >= 15 are.

It is enough to determine for all possible remainders of division by 6 (that is 0,1,2,3,4,5) what is the smallest number that is available. (I just have shown that this number for the remainder 3 is 15).

How to do it: Create a graph with vertices 0,1,2,3,4,5. For all numbers k that you are given (7,15 - we disregard 6) add an edge from x to (x + k) mod 6. Give it weight (x + k) div 6. Use Dijkstra's algorithm using 0 as the initial node. The distances found by the algorithm will be exactly those numbers we are searching for.

In our case (6,7,15) the number 7 gives rise to 0 -> 1 (weight 1), 1 -> 2 (weight 1), 2 -> 3 (weight 1), ..., 5 -> 0 (weight 1) and the number 15 gives 0 -> 3 (weight 2), 1 -> 4 (weight 2), ..., 5 -> 1 (weight 2). The shortest path from 0 to 3 has one edge - its weight is 2. So 6*2 + 3 = 15 is the smallest number that gives 3 as remainder. 6*1 + 3 = 9 is not available (well, we checked that previously by hand).

And what is the connection to regular expressions? Well, every regular expression has an equivalent finite automaton, and I constructed one of them.

This problem, with multiple queries allowed, appeared on the Polish Olympiad and I translated the solution. Now, if you hear now a person saying computer science is not useful for real programmers, punch him in face.

Answer 2

According to this, if the greatest common factor of {n1, n2, n3, ...} is not a divisor of m then you have no solution. This page shows an example of just {n1, n2} but it extends to larger systems. The new problem is writing an algorithm for finding the greatest common factor, but that's trivial in light of the original problem.

So part of your algorithm would find the gcf({n1,n2,...}) then see if it's a factor of m. If it isn't, then no solution exists. This doesn't fully show that a solution exists, but it can quickly show you that none exists, which is still useful.