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