The Frobenius problem asks for the largest amount that cannot be obtained by using only coins of specified denominations.

The Frobenius problem asks for the largest amount of money that cannot be obtained by using only coins of specified denominations. Instead of coins, some definitions use stamps or Chicken McNuggets.

Formally, $F(a_1,\ldots,a_n)$ denotes the largest integer that cannot be represented by using only coins of specified denominations $a_1,\ldots,a_n$.

Examples:

  • The largest amount that cannot be represented by coins of denominations $2$ and $3$ is the amount $5$; in other words $F(2,3)=1$. All even numbers can be written as $2+2+\cdots+2$, and all odd numbers (except $1$) can be written as $3+(2+\cdots+2)$.
  • The Chicken McNugget problem asks for $F(6,9,20)$, as McDonald's Chicken McNuggets boxes come with $6$, $9$, and $20$ nuggets. One can show that $F(6,9,20)=43$.
history | excerpt history