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

v2 · 2026-09-06 · History

Domain-specific #

1495

Origin domain

mathematics

Subdomain

number theory

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.

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) — more general patterns this builds on

• 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 → Span → Closure

Show alternative path (1)

Neighborhood in Abstraction Space

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

Family — Additive Number Theory & Series Tests (6 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-09-08