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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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