FrobeniusNumber

The largest integer that is not a non-negative integer combination of the given positive integers.

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageFrobeniusNumber✓

FrobeniusNumber(list)the coin problem's answer for these denominations

Typed signatures

Type	Package	Applies
`(list<integer>) -> integer`	`number-theory`	always

Domain: Number theory

Details

By the round-robin shortest-path algorithm over $\mathbb{Z}/a_0$ for the smallest generator $a_0$ , not by searching FrobeniusSolve upward.
Requires the generators' $\gcd$ to be 1 — otherwise every multiple of that gcd past it is still unreachable, so the answer is $+\infty$ .

Examples

Basic #

The McNugget number

\mathrm{FrobeniusNumber}(\bigl\lbrack6, 9, 20\bigr\rbrack)

Out

43

\mathrm{FrobeniusNumber}(\bigl\lbrack3, 5\bigr\rbrack)

Out

7

Scope #

\mathrm{FrobeniusNumber}(\bigl\lbrack12, 16, 20, 27\bigr\rbrack)

Out

89

Properties #

Two generators: $ab-a-b$

\mathrm{FrobeniusNumber}(\bigl\lbrack4, 7\bigr\rbrack)

Out

17

Possible issues #

Not coprime: infinitely many numbers are unreachable

\mathrm{FrobeniusNumber}(\bigl\lbrack2, 4\bigr\rbrack)

Out

∞

About