Coin Problem

Find the largest nonnegative integer not representable as a nonnegative integer combination of given coprime positive denominations—the Frobenius number of their numerical semigroup.

Version

v3 · 2026-09-19 · History

Domain-specific #

1495

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Number Theory → Mathematics

Aliases

Frobenius coin problem, Frobenius problem, Postage-stamp coin problem

Core Idea

Given positive integers a₁,…,a_k with greatest common divisor one, the coin problem asks for the largest nonnegative integer that cannot be expressed as n₁a₁+⋯+n_ka_k with every n_i a nonnegative integer. The representable values form a numerical semigroup, and its largest missing value is the Frobenius number. Coprimality ensures only finitely many nonnegative integers are missing.

For two coprime denominations a and b, the Frobenius number is ab−a−b. For three or more generators there is no analogous universal closed form, and computation and complexity depend strongly on whether the number of denominations is fixed. The coin story is mnemonic; the mathematical identity is an extremal gap in the additive span of positive integer generators.

How would you explain it like I'm…

The Can't-Pay Amount

Pretend you only have 3-cent coins and 5-cent coins, as many as you want. You can make 8 cents, or 9, or 10, but you can't make 7 cents at all. The Coin Problem asks: what is the biggest amount you can never make? With 3s and 5s, it's 7, and every amount after that works.

Biggest Impossible Amount

Suppose you only have coins of certain sizes, as many as you want of each, and you must pay exact amounts. With 3-cent and 5-cent coins you can't make 7 cents, but you can make 8, 9, 10 and every amount after that. The Coin Problem asks for the largest amount you can never make. This only has an answer if the coin sizes don't all share a common factor; with only 2-cent and 4-cent coins, every odd amount is impossible forever. The biggest impossible amount is called the Frobenius number.

Largest Unreachable Sum

The Coin Problem starts with positive whole numbers a₁, …, a_k whose greatest common divisor is 1. It asks for the largest whole number that cannot be written as a sum of these numbers, each used a nonnegative whole number of times. That largest missing value is called the Frobenius number. The condition that the numbers share no common factor guarantees only finitely many values are missing, so a largest one exists. For two numbers a and b with no common factor, there is a neat formula: the answer is ab − a − b (for 3 and 5, that is 7). For three or more numbers, there is no similar general formula.

 

Given positive integers a₁, …, a_k with gcd 1, the Coin Problem (Frobenius problem) asks for the largest nonnegative integer not expressible as n₁a₁ + ⋯ + n_ka_k with all n_i nonnegative integers. The set of representable values is closed under addition and contains 0, forming a numerical semigroup; its largest gap is the Frobenius number. Coprimality is what ensures the complement of the semigroup in the nonnegative integers is finite, so the Frobenius number exists. For two coprime generators a and b, it equals ab − a − b. For three or more generators, no analogous universal closed form exists, and how hard the computation is depends heavily on whether the number of generators is held fixed. The coin framing is only a mnemonic: the object is the extremal gap in the additive span of positive integer generators.

Scope of Application

The construct is literal in additive number theory and discrete optimization whenever reachability uses unlimited nonnegative integer combinations.

• Numerical semigroups. Studying gaps, conductors, genus, and generators.
• Diophantine analysis. Deciding nonnegative representability.
• Algorithm design. Computing Frobenius numbers for fixed or variable generator counts.
• Integer programming. Examining one-row nonnegative feasibility and bounds.
• Scheduling and batching analogues. Modeling totals constructed from indivisible allowed sizes when unlimited reuse is accurate.
• Coding and algebraic applications. Using numerical-semigroup invariants in specialized constructions.

Clarity

List positive generators, require nonnegative integer coefficients, state the gcd, and distinguish representability, largest gap, conductor, and number of gaps. Say whether denominations are minimal and whether generator count is fixed for a complexity claim. Verify proposed answers by proving both nonrepresentability of the gap and representability of every larger value.

Manages Complexity

The Frobenius number compresses an infinite reachability pattern into its last failure. Once it is known, all larger totals are guaranteed reachable. The scalar hides how gaps are distributed and how decompositions are found; algorithms often use residues modulo a generator, Apéry sets, or shortest paths to retain the missing structure.

Abstract Reasoning

1. Normalize the positive integer generator set.
2. Compute the gcd and stop if a finite largest gap cannot exist.
3. Construct the nonnegative additive semigroup or a residue representation.
4. Identify unreachable residue minima and implied gaps.
5. Propose the largest missing integer.
6. Prove it lacks a nonnegative decomposition.
7. Prove every larger integer is representable.
8. Use the two-generator formula only when its hypotheses hold.

Knowledge Transfer

The strict parent is Span: allowed generators and nonnegative integer coefficients define the set of reachable totals. The coin problem adds discreteness, positivity, a coprimality gate, and the largest omitted point. Generic resource-combination problems are analogues unless unlimited integer reuse and extremal nonrepresentability are preserved.

Span is the strict parent because representable integers are generated by nonnegative integer combinations, but the coefficient domain and order structure are essential.

Relationships to Other Abstractions

Current abstraction Coin Problem Domain-specific

Parents (1) — outgoing typed relations

• Coin Problem is a kind of Span Prime

  Span is the strict parent because representable totals are precisely those generated from the denominations under the admissible nonnegative-integer combination rule.

Hierarchy paths (2) — routes to 2 parentless roots

• Coin Problem → is a kind of Span → is a kind of, typical Closure

Show alternative path (1)

Neighborhood in Abstraction Space

Coin Problem sits in a sparse region of the domain-specific corpus (86^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Integer Properties & Number-Theoretic Sets (15 abstractions)

Nearest neighbors

• Fundamental Theorem of Arithmetic — 0.82
• Pillai's Arithmetical Function — 0.81
• Mordell–Weil Theorem — 0.81
• Primefree Sequence — 0.80
• Factorial Number System — 0.80

Computed from structural-signature embeddings · 2026-10-25