Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.