# 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. – Andy Putman Nov 12 '13 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 . – Emil Jeřábek Nov 12 '13 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). – André Henriques Nov 12 '13 at 12:47
Andy, this is an important question related to the works of Sylvester and Frobenius where much was discovered in recent decades. – Gil Kalai Nov 12 '13 at 13:58

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.