# General technique to find largest number that can't be written as a sum of multiples of a given list of numbers

I am given a set of numbers $(n_1, n_2, ...)$ with $n_1 < n_2 < ...$ and I want to know what the largest number is that can't be written as $a_1*n_1 + a_2*n_2 + ...$ The set of numbers is always finite and all $n_i$ and $a_i$ are positive integers. Is there a general technique to do this, or do you just have to try until you get $n_1$ consecutive numbers?

• Example: n is (3,5), largest number is 7 Commented Nov 4, 2013 at 13:12
• Indeed, since $n_1=3$ and 8, 9 and 10 can be formed, each number larger than 8 can be formed. Commented Nov 4, 2013 at 13:16
• But if n is (10, 100) any number not divisable by 10 will fit. The LCS of the ns must be 1. Commented Nov 4, 2013 at 13:18
• What do you mean by LCS? Commented Nov 4, 2013 at 13:24
• It's the Frobenius coin problem.
– bof
Commented Nov 4, 2013 at 13:33

We want to assume, as the Comments note, that the GCD of values $n_i$ is 1, as otherwise there is no upper bound on numbers that cannot be represented.
Edit: Technically this Question differs from the Coin Problem by requiring the count $a_i$ of each denomination $n_i$ to be "positive", where these coefficients are allowed to be zero in the Coin Problem. Whether or not this was a miswording of the Question, the only effect is to add $n_1 + n_2 + \ldots$ to each possible sum, so the set of representable values is simply shifted upward by this amount.
For general cardinality of $\{n_i\}$, stipulated to be finite, the problem is NP-hard as noted in an on-line paper by D. Beihoffer et al that discusses speed of algorithms. However for fixed number of integers $n_i > 0$ there are algorithms of polynomial complexity in size of input (logarithms of $n_i$'s).
• See also brg.a2hosted.com/?page_id=563 for a Python implementation of frobenius_number. Commented Nov 11, 2019 at 10:07