# How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?

Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that $n = \sum_{i=1}^k a_i m_i$?

To make things nontrivial, think of $k$ being in the hundreds, and of $n$ and the $m_i$ having hundreds of decimal digits, each. -- Clearly if we would remove the requirement that the $a_i$ are positive, the Chinese Remainder Theorem would tell us the answer -- but we do require them to be positive.

• MO is intended for topics at the graduate-school level and above. Nov 12, 2013 at 4:10
• I don’t see how this is not at the graduate-school level or above, nevertheless the problem seems to be equivalent to the unbounded subset-sum problem, whose NP-completeness is mentioned in mathoverflow.net/a/144983/12705 . Nov 12, 2013 at 12:39
• The question sounds perfectly legitimate to me (and Emil Jeřábek provided an answer to it -- maybe he wants to post it as an actual answer as opposed to a comment, now that the question is reopened). Nov 12, 2013 at 12:47
• Andy, this is an important question related to the works of Sylvester and Frobenius where much was discovered in recent decades. Nov 12, 2013 at 13:58

## 1 Answer

The problem can be thought of as a coin problem. There are $k$ coins with denominations $m_1,\dots,m_k$ and you want to express an amount $n$ with these coins. As states, the problem is an integer programming question which is NP-complete when $k$ is part of the input. It is in P (with exponential dependence on $k$) when $k$ is fixed by an algorithm by Lenstra.

The problem is closely related the Frobenius/Sylvester coin problem - to find the minimum $n$ so that every larger integer has such a representation. See here and here. A polynomial algorithm when $k$ is bounded was achieved by Ravi Kannan. (The dependence on $k$ is double-exponential.)

These two problems (finding a representation for fixed $n$ and finding the value of $n$ above which a representation always exists) represent the first two levels in Presburger Hierarchy. An important open problem here is to find a P-algorithm for higher order problems in the Presburger Hierarchy.

Of course, another important question is how to solve such questions in practice. I suppose other people can answer that better than me. One method that certainly comes to mind is to consider the linear programming relaxation (i.e. to allow rational $a_i$s) and then apply some rounding and "local" improvement.

The range proposed by the OP where $k$ - (the number of coins) is in the hunderds is interesting. I don't know if current algorithms can scratch this value.

• the coin problem is to find the least integer which is not in the submonoid generated by some natural numbers (assuming the gcd is 1). The problem of the OP is the unbounded subset problem, as mentioned by Emil in his comment, and is NP complete. Nov 12, 2013 at 14:19