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.^[1]

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.

Structural Signature

• The positive integer generators. A finite denomination set supplies allowed additive pieces.
• The nonnegative coefficients. Each generator can be used zero or more times; subtraction is forbidden.
• The additive semigroup. All reachable totals are finite nonnegative combinations.
• The gcd gate. A common divisor greater than one leaves infinitely many unreachable totals.
• The finite gap set. Under gcd one, only finitely many nonnegative integers are unreachable.
• The extremal gap. The largest missing total is the Frobenius number.
• The arity boundary. Two generators admit a closed formula; higher arity requires algorithms, bounds, or special structure.
• The witness decomposition. Representability claims require explicit coefficients or semigroup reasoning.

What It Is Not

• Not change-making with a limited wallet. Coin counts are unbounded in the classical problem.
• Not subset sum. A denomination may be reused and the target extremum ranges over all totals.
• Not arbitrary integer linear combination. Coefficients must be nonnegative.
• Not guaranteed to have a finite answer without gcd one. A shared divisor leaves arbitrarily large gaps.
• Not the number of missing values. That separate invariant is the genus of the numerical semigroup.
• Not solved for all arities by ab−a−b. The formula is the coprime two-generator case.

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.

Fix positive integer denominations and require nonnegative integer coefficients. If their greatest common divisor exceeds one, infinitely many integers are unrepresentable and no largest missing integer exists in the ordinary formulation. For two coprime denominations the closed formula applies, but it must not be extrapolated to arbitrary dimension. Distinguish the Frobenius number from the number of gaps, the conductor, and the smallest representation count. A representation may use a denomination repeatedly and may use none of another, unlike subset sum. Monetary language is mnemonic; no assumption about prices, making change optimally, or minimizing coin count belongs to the identity. When a bound or algorithm is given for several denominations, state whether the dimension is fixed, whether denominations are binary encoded, and whether the result computes the exact Frobenius number or only decides representability.

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.

The nonnegative integer combinations form an additive semigroup with a finite complement after coprimality is imposed. This converts infinitely many representation questions into a finite frontier problem: beyond the conductor every integer is reachable, so attention can shift to residues and minimal representatives. Choosing one denomination as a modulus yields an Apéry-set view in which each residue class has a least representable element; the largest of those thresholds determines the final gap. This structure explains both eventual coverage and why local failures do not persist forever. With more generators, interactions among residue classes become combinatorial and no universal formula like the two-generator case survives. The abstraction manages that complexity by preserving generator set, nonnegative span, residue structure, and maximal gap as separate roles.

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. Linear span over a field allows subtraction and arbitrary scalars, eliminating the gap phenomenon; integer lattice span allows negative coefficients, invoking Bézout without proving nonnegative representability. The transferable skeleton is restricted generators → reachable subset → frontier of nonreachability. It applies to scheduling and denomination systems only when repetition and nonnegative integrality are literal. The domain residual is the numerical semigroup and its largest gap, not generic resource allocation or optimization.

Examples

Canonical

With denominations 3 and 5, the coprime two-generator formula gives 3·5−3−5=7. Seven cannot be written 3m+5n with m,n≥0. Every integer from 8 onward is representable: 8=3+5, 9=3+3+3, 10=5+5, and adding another 3 propagates coverage.^[1]

Mapped back: generators {3,5} → nonnegative additive span → last gap 7 → consecutive reachable block → all larger totals.

Applied / In Practice

A packaging system can ship only bundles of two allowed sizes and permits unlimited bundles. Before promising arbitrary large orders, planners compute the Frobenius number and construct residue-class decompositions. If inventory limits bundle counts, the model is no longer the classical coin problem and must be replaced by bounded integer programming.

For two coprime denominations, an analyst can classify residues modulo either denomination and show that every sufficiently large total has a nonnegative representation. The largest failure agrees with the two-generator formula, while a direct table verifies smaller gaps. Adding a third denomination can fill many gaps but does not justify applying a pairwise formula to the new set. In a scheduling analogy, tasks of fixed integer lengths can tile sufficiently long horizons, yet the model fails if tasks overlap continuously, can be shortened, or must each be used at most once. The example exposes the exact modeling assumptions rather than treating every integer-combination problem as the coin problem.

Mapped back: unlimited indivisible bundle sizes → reachable totals → last infeasible total → model-boundary check.

Structural Tensions

• Infinite target range vs. finite certificate. One extremal gap summarizes all later reachability. Diagnostic: Has the conductor property been proved?
• Simple two-generator formula vs. higher-arity complexity. Adding one denomination changes the computational landscape. Diagnostic: Is the formula being overextended?
• Coin intuition vs. algebraic identity. Currency language helps but can import limited supply or optimal-change assumptions. Diagnostic: Are coefficients truly unlimited and nonnegative?
• Scalar Frobenius number vs. gap structure. The maximum omits genus and decomposition behavior. Diagnostic: Does the application need more than the last gap?
• Autonomous problem vs. generic span. Span travels; integer semigroup gaps create the coin problem. Diagnostic: Is the object a nonnegative integer additive span with an extremal omission?

Structural–Framed Character

The coin problem is structural-leaning. Its result is formal and independent of coin culture once generators are fixed; the monetary story and notation are conventional. It is evaluatively neutral and observer-independent. Domain specificity comes from positive integer semigroups and the largest-gap question rather than span in general.

Positive generators, nonnegative integer coefficients, greatest-common-divisor gate, eventual finite complement, and largest missing value are structural. Currency names, order of generators, chosen modulus, proof technique, and a real-world interpretation are framed. Scaling all generators by a common factor changes the ordinary problem by destroying coprimality rather than simply rescaling an answer. Redundant generators can leave the semigroup unchanged, so an input list and its minimal generating set need not coincide. These distinctions explain why the identity belongs to a semigroup's reachability frontier and not to a particular coin story or one closed formula. They also require the zero value to be recognized as representable by using every generator zero times, preventing an avoidable boundary error.

Structural Core vs. Domain Accent

The skeleton is finite generators + admissible composition → reachable set → largest omitted value. The accent is positive integers, nonnegative multiplicities, gcd-one cofinality, and numerical-semigroup gaps. Removing them yields generic span or reachability.

Instantiates / Related Primes

Span is the strict parent because representable totals are precisely those generated from the denominations under the admissible nonnegative-integer combination rule. Complete Enumeration is not required, since algebraic proofs can avoid listing all totals.

The prospective workspace queue contains one strict upward edge to prime:span. No live DAG mutation is authorized.

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

Not to Be Confused With

• Change-making problem. Usually optimizes the number of coins for a fixed amount.
• Subset-sum problem. Each listed item is used at most once.
• Unbounded knapsack. Optimizes value or cost rather than the largest unreachable total.
• Bézout identity. Allows negative integer coefficients.
• Numerical-semigroup genus. Counts gaps rather than selecting the largest one.

References

[1] Jorge L. Ramírez Alfonsín, The Diophantine Frobenius Problem (Oxford University Press, 2005). registry ↩a ↩b