I realize that such a question may have already been asked, and having looked at a few, I didn't really understand how to calculate a frobenius number.
So, is there a general equation that can be used, such as when you are dealing with a series of 2 numbers AND a series of 7 numbers?
Or do we just take a certain number and iterate downwards until we come to a number that can't be made?
If so, how do we calculate this number.
Thank you.
$\endgroup$2 Answers
$\begingroup$A simple straightforward algorithm starts from $0$ and repeatedly adds numbers onto pre-made numbers until a streak is found. For example, consider $3$ and $5$.
We start off with $\{0\}$.
Taking the minimum of $0+3$ and $0+5$ gives us $\{0,3\}$.
Taking the minimum of $0+5,3+3,$ and $3+5$, we get $\{0,3,5\}$.
The next few steps are:
$\{0,3,5,6\}$
$\{0,3,5,6,8\}$
$\{0,3,5,6,8,9\}$
$\{0,3,5,6,\color{red}{8,9,10}\}$
From which we can see the Frobenius number of $\{3,5\}$ is $7$.
As it would turn out, an asymptotically faster algorithm would be to rewrite this into a linear recurrence:
$$a_n=\begin{cases}0,&n<0\\1,&n=0\\a_{n-3}+a_{n-5},&n>0\end{cases}$$
We seek to find the largest $n$ s.t. $a_n=0$. The computation of linear recurrences is well studied and you can compute $(a_n,a_{n-1},a_{n-2},a_{n-3},a_{n-5})$ in $\mathcal O(\log(n))$ steps by rewriting it as:
$$\begin{bmatrix}a_n\\a_{n-1}\\a_{n-2}\\a_{n-3}\\a_{n-4}\end{bmatrix}=A^n\begin{bmatrix}1\\0\\0\\0\\0\end{bmatrix}\tag{$n\ge0$}\\A=\begin{bmatrix}0&0&1&0&1\\1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\end{bmatrix}$$
and applying exponentiation by squaring. Once a streak is found, we work backwards with a binary search, using our previously computed $A^k$ and their inverses as needed. Note that this isn't super helpful on very small values, but can be more useful for finding the Frobenius number of something like $\{2000,3001,4567\}$.
$\endgroup$ $\begingroup$The Frobenius problem in general is hard to solve (the 2 number case is easy, see e.g. here for an instructive technique). I believe the (to date) definitive summary of what is known to be Ramírez-Alfonsín's "The Diophantine Frobenius Problem" (Oxford University Press, 2006). The problem itself pops up all over the place, so it has been well-studied, a web search should turn up lots of references.
$\endgroup$ 1
