Algorithm for determining non-negative values ​​of a solution for a 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 solve the equation k1n1 + k2n2 + k3n3 ... = m where k1, k2, k3 ..., m are positive integers.

I do not need to find a solution - just determine if a solution exists.

Edit:

Regarding the practical use of this algorithm:

In the communication library, I want to decide whether the given message is valid according to its size, before processing the message. For example: I know that a message contains zero or more 3-byte elements, zero or more 4-byte elements, and zero or more 5-byte elements. I received a message of 456 bytes, and I want to determine its authenticity before checking its contents. Of course, the message header contains the number of elements of each type, but I want to do the first check at the message library level, passing something like pair<MsgType,vector<3,4,5>> .

Answer 1

You ask if regex exists

(xxx | xxxx | xxxxx) *

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

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

Suppose your numbers are 6,7,15. I will call the number, expressed as 6x + 7y + 15z "available." You should check if this number is available.

If you can get some number n, then, of course, you can get n + 6, n + 12, n + 18 - in the general case, n + 6k for all k> = 0. On the other hand, if you cannot get some the number n, then n-6 will not be available either (if you can get (n-6), then (n-6) + 6 = n will be available), which means that n -12, n-18, n- 6k is also not available.

Suppose you have determined that 15 is available, but 9 is not. In our case, 15 = 6 * 0 + 7 * 0 + 15 * 1, but it can’t get 9. So, according to our previous considerations, 15 + 6k is available for all k> = 0 and 9-6k for all k> = 0. If you have some number divided by 6, you get 3 as the remainder (3, 9, 15, 21, ...), you can quickly answer: digits <= 9 are not available, digits> = 15.

It is enough to determine for all possible residuals of dividing by 6 (i.e., 0,1,2,3,4,5), which is the smallest number that is available. (I just showed that this number for remainder 3 is 15).

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

In our case (6,7,15), the number 7 leads 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. Thus, 6 * 2 + 3 = 15 is the smallest number that gives 3 as the remainder. 6 * 1 + 3 = 9 is not available (well, we checked it earlier manually).

And what is the relationship with regular expressions? Well, every regex has an equivalent finite state machine, and I built one of them.

This problem, resolved by several requests, appeared at the Polish Olympiad, and I translated the solution. Now, if you hear now that a person speaking in computer science is not useful for real programmers, hit him in the face.

Answer 2

According to this , if the greatest common coefficient {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. A new problem is to write an algorithm to find the greatest common factor, but trivial in the light of the original problem.

So, part of your algorithm will find gcf ({n1, n2, ...}), then see if it is a factor of m. If this is not so, then there is no solution. This does not fully show that the solution exists, but it can quickly show you that nothing exists, which is still useful.

Answer 3

It sounds like you are talking about a system of inequalities with whole limitations. The reality is that you are solving this system:

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

And the additional restriction that n1, n2, n3 are integers. This is a linear programming problem. Unfortunately, for you the general case of solving such a system with complete restrictions is NP-complete . However, there are many algorithms that will solve this for you.

Answer 4

This is due to the problem of the Frobenius coin , which was not solved for n> 3.

Answer 5

Brute force approach (pseudo-code):

 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: This does not make sense in the communication library, since it should work immediately. In the OP application, I would probably use some kind of hash, but its approach sounds interesting.

Answer 6

Here is something in the case of 2 numbers. I have not figured out how to scale it yet:

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

Basically, this works because if you take x<y , you can express all integers mod x with (0, y, 2y, 3y, ..., (x-1) y). Now by adding a few positive multiples of x, you can achieve all the integers between [(x-1) (y-1), (x-1) y], since all the integers are between (x-1) (y-1 ) and (x-1) y-1 were expressed earlier.

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

And for brute force:

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

Answer 7

Perhaps the following information does not matter since it does not handle the general situation, but ...

If the task is to determine if a given positive integer K can be expressed as the sum 3*n1 + 4*n2 + 5*n3 , for non-negative integers n1, n2, n3, the answer is yes, for K > = 3.

The well-known textbook of Rosen "Discrete mathematics and its applications", p. 287 of the sixth edition, proves that "each amount of postage of 12 cents or more can be formed using only 4-cent and 5-cent marks" using induction.

The fundamental step is that postage of 12 cents can be formed using 3 four-cent marks.

The induction step considers that if P (k) is true using four-cent marks, then simply replace the four-cent seal with a five percent stamp to show that P (k + 1) is true. If P (k) is true without four-cent marks, then, since k> = 12, we need at least 3 five-meter marks to form our sum, and 3 five-percent marks can be replaced by 4 four-cent stamps to achieve k + 1.

To extend the above solution to this problem, you just need to consider only a few cases.