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

Question

Hello, 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

Looks like you're talking about a system of inequalities with integer constraints. The reality is you're solving for this system:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

And the additional constraint that n1, n2, n3 are integers. That's a linear programming problem. Unfortunately for you, the general case of solving such a system with integer constraints is NP-complete. However, there are many algorithms that will solve it for you.

Answer 2

A brute-force approach (pseudocode):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

See also http://mail.python.org/pipermail/python-list/2000-April/031714.html

EDIT: In a communications library this would make no sense, since it needs to work immediately. In the OP's application I would probably use some sort of hash, but his approach sounds interesting.

Answer 3

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.

Answer 4

Here's something on the 2 number case. I haven't figured out yet how to scale it:

Given 2 relatively prime integers x and y, there exist positive integers a and b such that ax+by=c for all c>=(x-1)(y-1)

Basically, this works because, if you assume x<y, you can express all integers mod x with (0, y, 2y, 3y, ..., (x-1)y). Now, by adding some positive multiple of x, you can reach all integers between [(x-1)(y-1),(x-1)y], as all of the integers between (x-1)(y-1) and (x-1)y-1 had been expressed previously.

1. GCD(x,y). If c is not a multiple, return false.
2. if GCD(x,y) > 1, divide x,y,c by GCD
3. If c > (x-1)(y-1), return true
4. Else brute force

And for the brute force:

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 5

This is related to the Frobenius coin problem, which hasn't been solved for n>3.

Answer 6

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 7

Perhaps the following info is irrelevant, because it doesn't handle the general situation, but...

If the problem is to determine whether a given positive integer K can be formed as a sum 3*n1 + 4*n2 + 5*n3, for nonnegative integers n1, n2, n3, then the answer is "yes", for K >= 3.

Rosen's well-known textbook Discrete Mathematics and its Applications, p. 287 of the sixth edition, proves that "every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps," using induction.

The basis step is that postage of 12 cents can be formed with 3 four-cent stamps.

The induction step considers that if P(k) is true using four-cent stamps, then simply substitute a four-cent stamp with a five-cent stamp to show that P(k+1) is true. If P(k) is true using no four-cent stamps, then, because k>=12, we need at least 3 five-cent stamps to form our sum, and 3 five-cent stamps can be replaced with 4 four-cent stamps to achieve k+1.

To extend the above solution for this problem requires just considering just a few more cases.