# Generating integers from a linear combination of integers

Given are some positive integers $t_1, ..., t_n$ such that $\mathrm{gcd}(t_1, ..., t_n) = 1$. Now we create a linear combination of these: $k_1 t_1 + ... + k_n t_n$ where $k_1, ..., k_n$ are nonnegative integers that you can choose to generate different integers.

What is the smallest $N$ such that all integers greater than or equal to $N$ can be generated by the linear combination?

Example: $k_1 3 + k_2 4$ can generate $0, 3, 4, 6, 7, 8, 9, ...$. So here $N = 6$ and $k_1 = 2, k_2 = 0$.

-

This is a famous problem, sometimes called the coin problem of Frobenius.

If $n=2$ the answer to your question is known to be $N = t_1 t_2 - (t_1 + t_2) + 1$. A proof of this can be found in the answer to this recent question.

For three or more integers, there is no known closed-form solution for $N$. There are some bounds on the values of $N$ in the $n = 3$ case, as well as some algorithms for determining $N$. For more information and references, see the Wikipedia and MathWorld pages on the Frobenius coin problem.

Basically, the problem is considered solved when $n = 2$, partially solved (because of the bounds and algorithms) when $n = 3$, and unsolved when $n \geq 4$.

Update: Guy's Unsolved Problems in Number Theory says, "The case $n = 3$ was first solved explicitly by Selmer and Beyer, using a continued fraction algorithm." So I guess the $n=3$ case has been solved. I suppose you have would have to dig up their paper (it's in the MathWorld references) to see their solution.

-
Thanks! I am glad I finally gave up and asked here :-) – hakos Oct 29 '10 at 5:16
PS: You might want to change the k's to t's to match the question. – hakos Oct 29 '10 at 5:51
@hakos: Thanks. Fixed. – Mike Spivey Oct 29 '10 at 15:47
@hakos: Here is the Selmer/Beyer paper, and here are two other papers you might be interested in. – J. M. Oct 29 '10 at 15:54