Fact-checked by Grok 2 weeks ago

Coin problem

The coin problem, also known as the Frobenius coin problem, is a classic problem in number theory that asks for the largest integer that cannot be expressed as a non-negative integer linear combination of a given set of positive integers (coin denominations) whose greatest common divisor is 1.^[1]^[2] This largest non-representable integer is termed the Frobenius number of the set.^[3] For two coprime denominations a and b, the Frobenius number is explicitly given by the formula g(a, b) = ab - a - b.^[1]^[2] The problem was first formulated by the German mathematician Ferdinand Georg Frobenius in the early 20th century, though the explicit solution for two variables was provided earlier by James Joseph Sylvester in 1884.^[2]^[3] Sylvester also proved that the number of positive integers not representable in this way equals \frac{1}{2}(a-1)(b-1).^[2] For more than two denominations, no general closed-form formula exists, and computing the Frobenius number becomes significantly more complex, with research focusing on algorithms, bounds, and special cases.^[3]^[2] Notable contributions include upper bounds by mathematicians such as Issai Schur (1935), Paul Erdős and Ronald Graham (1972), and Ernst Selmer (1976), which help estimate the Frobenius number for larger sets.^[2] The problem has practical interpretations, such as the "Chicken McNugget theorem" for McDonald's packaging sizes (6, 9, and 20 pieces), where the Frobenius number is 43, meaning 43 nuggets cannot be bought exactly but all larger quantities can.^[1]^[2] It extends to broader Diophantine approximation and additive combinatorics, influencing fields like computer science for optimization algorithms.^[3]

Problem Definition

Classical Statement

The classical statement of the coin problem, also known as the Frobenius coin problem, seeks the largest non-negative integer that cannot be expressed as a non-negative integer linear combination of given positive integer denominations a_1, a_2, \dots, a_n.^[3] This largest unrepresentable integer is termed the Frobenius number, denoted g(a_1, \dots, a_n), and is defined precisely as the maximum value k for which there exist no non-negative integers x_1, \dots, x_n satisfying k = \sum_{i=1}^n x_i a_i.^[1] The non-negative integers that can be formed in this manner constitute the numerical semigroup generated by the denominations \{a_1, \dots, a_n\}, which is the set of all finite sums \sum_{i=1}^n x_i a_i with x_i \in \mathbb{N}_0 (where \mathbb{N}_0 includes 0).^[4] For this semigroup to have a finite complement in the non-negative integers—ensuring the existence of a largest unrepresentable number—the denominations must satisfy \gcd(a_1, \dots, a_n) = 1; if the gcd exceeds 1, only multiples of that gcd are representable, rendering the Frobenius number infinite.^[4] The problem derives its name from Ferdinand Georg Frobenius (1849–1917), though it was initially investigated by J. J. Sylvester, who addressed related questions in a 1884 publication in the Educational Times.^[5] When the denominations consist of two coprime positive integers a and b, every integer greater than g(a, b) belongs to the numerical semigroup they generate.^[1]

Key Assumptions and Variants

The coin problem, formally known as the Frobenius coin problem, fundamentally assumes that the denominations a_1, a_2, \dots, a_n are positive integers with greatest common divisor \gcd(a_1, a_2, \dots, a_n) = 1. This coprimality condition is essential, as it guarantees—by an extension of Bézout's identity to non-negative integers—that every sufficiently large positive integer can be expressed as a non-negative integer linear combination \sum_{i=1}^n x_i a_i with x_i \geq 0. Without this assumption, the problem's core question of identifying a finite largest non-representable amount loses meaning.^[6]^[3] For the trivial case of a single denomination (n=1), if a_1 = 1, every non-negative integer is representable using non-negative multiples, rendering the Frobenius number undefined or vacuously zero. However, if a_1 > 1, only multiples of a_1 can be formed, leaving infinitely many non-representable integers and thus an infinite Frobenius number. This case highlights the necessity of multiple denominations and coprimality for the problem's finite solvability.^[6] A key variant arises when the denominations are not coprime, i.e., \gcd(a_1, \dots, a_n) = d > 1; here, all representable amounts are multiples of d, so infinitely many positive integers (those not divisible by d) remain non-representable, and the Frobenius number is infinite. Another variant involves restrictions on coefficients, such as bounded quantities in the local postage stamp problem, where the total number of coins (or stamps) is limited to at most t for some fixed t, altering the set of representable amounts and requiring separate analysis of the largest non-achievable value under this constraint. Allowing negative coefficients transforms the problem into the classical linear Diophantine equation setting, where solutions exist for all integers congruent to 0 modulo the gcd, but without the non-negativity focus that defines the coin problem.^[6]^[5] The problem extends to higher-dimensional or vector variants, where denominations are vectors in \mathbb{Z}^m (for m > 1), and one seeks the "largest" (in some partial order) non-representable vector as a non-negative integer combination; this generalizes the scalar case but introduces greater computational complexity, with no simple closed-form solutions even for small dimensions. In contrast to such abstract extensions, the chicken nugget problem serves as a popularized instance of the standard coin problem, using denominations like 6, 9, and 20 to find exact combinations for purchasing whole boxes (allowing zero coefficients for unused types), emphasizing practical limitations without altering the core non-negative representation mechanics.^[3]^[5]

Computing the Frobenius Number

Two Coprime Denominations

When two positive integers a and b with a < b are coprime (i.e., \gcd(a, b) = 1), the Frobenius coin problem admits an exact closed-form solution for the Frobenius number g(a, b), defined as the largest integer that cannot be expressed as ax + by for nonnegative integers x, y. This solution is given by Sylvester's theorem: g(a, b) = ab - a - b.^[3] The formula was first established by James Joseph Sylvester in 1884.^[3] A key property is that every integer greater than g(a, b) can be represented as a nonnegative integer combination of a and b, while there exist exactly \frac{1}{2}(a-1)(b-1) positive integers that cannot be represented.^[3] This count arises from the symmetry in the residues modulo ab: among the integers from 1 to ab-1 not divisible by a or b, exactly half are non-representable, paired with their complements ab - k.^[3] To derive the formula, consider that any non-representable number can be written as ma - nb for integers $1 \leq m \leq b-1, n \geq 1, since if y \geq a, the representation could be adjusted using the relation a \cdot b - b \cdot a = 0. The largest such value occurs when n=1 and m = b-1: (b-1)a - b = ab - a - b. This number is non-representable, as solving ax + by = ab - a - b leads to a negative coefficient for b (e.g., x = b-1, y = -1). Meanwhile, ab - a - b + 1 is representable, and since the multiples of b modulo a cover all residues, every larger integer is representable. This proof leverages the completeness of the residue coverage and the finiteness of non-representables.^[3]^[7] Examples illustrate the formula effectively. For a=2, b=3, g(2,3) = 2 \cdot 3 - 2 - 3 = 1, as 1 cannot be formed but all larger positives can (e.g., 2=1·2, 3=1·3, 4=2·2). For a=3, b=5, g(3,5) = 3 \cdot 5 - 3 - 5 = 7, where 7 is non-representable but 8=1·3+1·5 and higher values follow. For a=4, b=9, g(4,9) = 4 \cdot 9 - 4 - 9 = 23, with 23 non-representable (no nonnegative solutions) but 24=6·4. These cases highlight how the formula scales with larger coprime pairs.^[3]

Three or More Denominations

Unlike the case of two coprime denominations, no closed-form formula exists for computing the Frobenius number when there are three or more coprime denominations.^[8] The problem of determining this number is NP-hard under Turing reduction, even when the number of denominations is part of the input. To compute the Frobenius number in practice, algorithms rely on enumeration or optimization techniques limited by upper bounds. Brute-force enumeration involves generating all possible non-negative integer combinations of the denominations up to a known upper bound on the Frobenius number, checking which values are representable.^[9] A more efficient approach uses dynamic programming, where a boolean array tracks representable integers starting from 0; for each denomination, the array is updated by marking multiples and additions, ultimately identifying the largest unmarked index below the bound.^[5] Upper bounds are essential for bounding the search space. A classical bound, due to Schur, states that for coprime positive integers p_1 < p_2 < \cdots < p_k with k \geq 3, the Frobenius number g \leq (p_1 - 1)(p_k - 1) - 1.^[2] Tighter bounds have been developed in recent years; for instance, Aliev, De Loera, and Oertel (2019) provide an optimal upper bound on the distance from vertices of knapsack polyhedra to nearest lattice points, which directly informs improved estimates for the Frobenius number in higher dimensions. For example, with denominations 6, 10, and 15 (which are coprime as a set), the Frobenius number is g(6,10,15) = 29, meaning 29 cannot be formed but all larger integers can.^[10] In terms of computational complexity, algorithms for arbitrary numbers of denominations run in exponential time relative to the input size, as the search space grows with the product of the denomination values. However, for a fixed number of denominations, polynomial-time algorithms exist, though the degree of the polynomial increases with the number of denominations.^[11]

Special Forms of Denominations

Arithmetic Progressions

In the coin problem, a significant special case arises when the denominations form an arithmetic progression. Consider the set of k \geq 2 positive integers \{a, a+d, a+2d, \dots, a+(k-1)d\}, where a \geq 2, d \geq 1, and \gcd(a,d)=1. This ensures the set is coprime as a whole, guaranteeing a finite Frobenius number. The structure of this progression allows for an explicit closed-form expression for the largest integer that cannot be expressed as a non-negative integer combination of these denominations.^[12] The Frobenius number for this set is given by

g(a, a+d, \dots, a+(k-1)d) = a \left\lfloor \frac{a-2}{k-1} \right\rfloor + (a-1)d.

This formula, originally derived by Roberts and later presented in simplified form, quantifies how the representable amounts cover all sufficiently large integers, with the threshold determined by the interplay between the starting value a, the spread d, and the length k. As k increases, the floor term decreases, reflecting that longer progressions fill gaps more effectively and thus lower the Frobenius number, though it remains dependent on a and d.^[12]^[13] For the case of three denominations (k=3), the formula simplifies to g(a, a+d, a+2d) = a \left\lfloor \frac{a-2}{2} \right\rfloor + (a-1)d. This depends on the parity of a: if a is odd, \left\lfloor \frac{a-2}{2} \right\rfloor = \frac{a-3}{2}, yielding g = a \cdot \frac{a-3}{2} + (a-1)d; if even, it adjusts accordingly to \frac{a-4}{2}. An illustrative example is the progression $5, 8, 11 (a=5, d=3): \left\lfloor \frac{3}{2} \right\rfloor = 1, so g = 5 \cdot 1 + 4 \cdot 3 = 17. Indeed, 17 cannot be formed (as $17-5=12, $17-8=9, and $17-11=6 are non-representable), while all integers greater than 17 are. Note that if \gcd(a,d)>1, such as $3,6,9 (d=3), the set is not coprime, and the Frobenius number is infinite.^[12]^[14] This closed form highlights the tractability of arithmetic progressions compared to general sets of three or more denominations, where no universal formula exists. The result has been extended to modified arithmetic progressions, but the standard case underscores key properties like the linear growth in d and quadratic potential in a for fixed k.^[12] In the context of the coin problem, geometric sequences of denominations refer to sets of the form A_k(a, b) = \{a^k, a^{k-1}b, \dots, ab^{k-1}, b^k\}, where a and b are coprime positive integers greater than 1 and k \geq 2 is the length of the sequence. Such sets generate numerical semigroups with gcd 1, allowing the Frobenius number to be well-defined. A closed-form expression for the Frobenius number g(A_k(a, b)) is given by g(A_k(a, b)) = \sigma_{k+1}(a, b) - \sigma_k(a, b) - (a^{k+1} + b^{k+1}), where \sigma_m(a, b) denotes the sum of the elements in A_m(a, b).^[15] This formula arises from a recurrence relation g(A_k(a, b)) = b \cdot g(A_{k-1}(a, b)) + a^k (b - 1), derived using apéry sets and properties of numerical semigroups.^[15] For instance, when a = 2, b = 3, and k = 2, the set is {4, 6, 9}, with g = 11, illustrating how the formula captures the largest non-representable integer.^[15] Fibonacci-related sequences in the coin problem often involve numerical semigroups generated by consecutive or selected Fibonacci numbers, leveraging their recursive structure and coprimality properties. For the semigroup generated by three non-consecutive Fibonacci numbers F_i, F_{i+2}, F_{i+k} with i, k \geq 3, the Frobenius number depends on the quotient r = \lfloor (F_i - 1)/F_k \rfloor. Specifically, if r = 0 or if r \geq 1 and F_k - 2 F_i < (F_i - r F_k) F_{i+2}, then g(F_i, F_{i+2}, F_{i+k}) = (F_i - 1) F_{i+2} - F_i (r F_k + 1); otherwise, g(F_i, F_{i+2}, F_{i+k}) = (r F_k - 1) F_{i+2} - F_i ((r - 1) F_k + 1).^[16] This result extends earlier work on Fibonacci semigroups by providing explicit computations for non-consecutive generators. For consecutive Fibonacci numbers, such as {3, 5, 8} (F_4, F_5, F_6), the Frobenius number is 7.^[17] Similarly, for {2, 3, 5} (F_3, F_4, F_5), the Frobenius number is 1.^[17] Recent developments have extended the Frobenius problem to r-Fibonacci sequences, defined by the recurrence p_{n+2} = r p_{n+1} + p_n with p_0 = 0, p_1 = 1, and r \geq 2. For the numerical semigroup S_r(a) generated by {p_a + p_n \mid n \in \mathbb{N}}, where p_a is an r-Fibonacci number, the minimal generators are {p_a + p_0, \dots, p_a + p_{a-1}}. The Frobenius number is \mathrm{F}(S_r(a)) = (a-1) p_a - 1 when r = 2, and \mathrm{F}(S_r(a)) = (r-1) \left( \sum_{i=1}^{a-1} p_i + (a-1) p_a \right) - p_a for r \geq 3.^[18] These results utilize generalized Zeckendorf decompositions to characterize representable numbers. In 2025, explicit formulas were also computed for the Frobenius number of semigroups generated by the squares of three consecutive Fibonacci numbers.^[19] In parallel, generalizations to p-Frobenius numbers—the largest integer expressible in at most p ways—have been explored for Diophantine triples satisfying equations like x^2 + 3 y^2 = z^3. For such triples (x, y, z), an explicit formula for the p-Frobenius number is derived, providing closed-form expressions that reduce the problem to analyzing solution counts in the associated numerical semigroup.^[20] Combinatorial methods have also advanced the computation of Frobenius numbers for these sequences by reformulating the problem as an optimization task over lattice points. Specifically, the Frobenius number can be linked to the covering radius of a geometric configuration, allowing polynomial-time algorithms for special cases like Fibonacci-generated sets through integer linear programming reductions.^[21] This approach emphasizes minimal representations and has been applied to optimize bounds for geometric and recursive sequences, highlighting connections to covering problems in combinatorial geometry.^[21]

Theoretical Advances and Conjectures

Wilf's Conjecture

Wilf's conjecture, posed in 1978, concerns numerical semigroups and their invariants. For a numerical semigroup S with multiplicity e(S) (the smallest positive element in S), Frobenius number g(S) (the largest integer not in S), and genus n(S) (the number of positive integers not in S), the conjecture states that e(S) + n(S) \leq g(S) + 1.^[22] Equivalently, the number of elements of S in the interval [0, g(S)] is at least e(S). This inequality provides a bound on the genus n(S), which represents the size of the gap set (the positive integers up to g(S) not in S), limiting how sparse S can be near its Frobenius number.^[23] The conjecture has been proven for irreducible numerical semigroups, which include symmetric and pseudo-symmetric cases. For symmetric semigroups, where g(S) = 2n(S) - 1, the inequality holds as a direct consequence of the structural properties.^[24] Computationally, it has been verified for all numerical semigroups of genus up to 100. No counterexamples have been found despite extensive searches, and partial proofs exist for semigroups with low embedding dimension (the minimal number of generators), such as embedding dimension at most 3.^[23]^[25] In the context of the coin problem, Wilf's conjecture applies to numerical semigroups generated by the coin denominations, offering insights into the density of representable amounts below the Frobenius number.^[22]

Bounds and Recent Developments

Classical bounds on the Frobenius number g(a, b) for two coprime positive integers a < b include the exact value g(a, b) = ab - a - b, providing the precise limit.^[2] For the general case with n \geq 3 coprime denominations A = \{a_1 < a_2 < \cdots < a_n\}, a standard upper bound is g(A) \leq (\min A)^2 \left( \sum_{j=1}^n \frac{a_j}{\min A} - 1 \right) / 2, which scales with the sum of the denominations relative to the minimum.^[2] Recent improvements have refined these estimates for numerical semigroups. In 2019, Aliev and colleagues established sharper upper bounds on the Frobenius number by leveraging covering radius techniques in convex geometry, reducing the dependency on higher-dimensional generators.^[26] These results were extended in 2024 through analyses of stretched numerical semigroups, yielding new upper bounds g(H) \leq n_i n_j - n_i - n_j for relatively prime generators n_i, n_j in specific structures, enhancing applicability to larger sets.^[27] Additionally, a 2025 study introduced linear regression models to estimate the Frobenius number for semigroups generated by binomial coefficients, approximating asymptotic behavior with high accuracy for sets like \{ \binom{k}{2}, \binom{k}{3}, \dots \}, where exact computation is intractable.^[28] Key developments since 2020 include short proofs for finite variants of the problem. A 2025 arXiv preprint provides an exact solution to the finite Frobenius coin problem—where a maximum number of coins is restricted—using dynamic programming reductions that yield closed-form expressions in O(n \log m) time for denominations up to m.^[29] Combinatorial optimization has also advanced the field; a 2024 approach reformulates the Frobenius number as an integer linear programming problem over special sequences, solvable via generating functions and Lagrange's four-square theorem for efficient bounds.^[21] Further progress addresses specific generators, such as a 2025 computation of Frobenius numbers for triplets of centered triangular and square numbers, deriving explicit formulas like g(3k^2 + 3k + 1, 3(k+1)^2 + 3(k+1) + 1, 3(k+2)^2 + 3(k+2) + 1) = 9k^4 + 18k^3 + 15k^2 + 4k - 1 for centered triangular cases.^[30] Despite these advances, open problems persist, particularly the exact computation of g(a, b, c) for three coprime integers, which remains NP-hard under Turing reductions and lacks a closed-form formula, though algorithmic approximations continue to improve.^[31] Extensions of Wilf's conjecture to affine semigroups—higher-dimensional analogues—have been explored in 2025 conference talks, verifying the inequality e(S) + g(S) \leq n (where e(S) is the embedding dimension and n the multiplicity) for various \mathbb{C}^d-semigroups but leaving the general case unresolved.^[32] Wilf's original conjecture for numerical semigroups remains open, with ongoing verifications for semigroups up to multiplicity 100 but no full proof as of 2025.^[32]

Applications and Examples

McNugget Numbers

The Chicken McNugget theorem illustrates the coin problem using historical McDonald's Chicken McNugget pack sizes of 6, 9, and 20 pieces, available in the 1980s and 1990s. The Frobenius number for this set is 43, meaning 43 nuggets cannot be purchased exactly, but all larger quantities can.^[33] The positive integers that cannot be expressed as non-negative integer combinations of 6, 9, and 20—known as non-McNugget numbers—are: 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43.^[34] As of 2025, McDonald's offers McNuggets in packs of 4, 6, 10, 20, 40, and 50 pieces, altering the applicable Frobenius number.^[35]

Algorithmic and Mathematical Uses

The coin problem finds significant application in the analysis of sorting algorithms, particularly Shellsort, where the increment sequence determines the efficiency of resolving inversions. In Shellsort, an increment sequence h_1 > h_2 > \cdots > h_k = 1 with \gcd(h_1, \dots, h_k) = 1 leads to a worst-case input size and number of comparisons bounded by quantities involving the Frobenius number g(h_1, \dots, h_k) + 1, as this represents the largest distance between elements that cannot be directly compared across increments.^[36] This connection allows derivation of upper bounds on the algorithm's time complexity; for instance, sequences yielding small Frobenius numbers result in improved performance, such as O(N^{3/2}) in certain cases.^[37] A concrete example is the increment sequence 6, 9, 20, for which the Frobenius number is 43, directly influencing the bound on unresolved inversions in the worst case.^[5] In optimization, the coin problem underpins solutions to the unbounded knapsack problem, especially variants like the change-making problem, which seeks the minimum number of coins (or items) summing to a target value with unlimited availability. Algorithms for this NP-hard problem leverage Frobenius theory to bound the search space; for example, a dynamic programming approach achieves \tilde{O}(n u) time for target u and n denominations by using the Erdős–Graham theorem, which estimates the Frobenius number to limit computations in the "tail" of non-representable values.^[38] This extends to the all-capacities version, solving multiple targets efficiently without recomputing full tables.^[39] Mathematically, the coin problem arises in the analysis of Petri nets, particularly in determining the least live weight for conservative weighted circuits, which models resource allocation in distributed systems. The least live weight is the minimal total token weight ensuring all markings are live (reachable and enabling all transitions indefinitely), and for a circuit with arc weights forming a coprime set, it equals the Frobenius number plus the sum of the weights.^[40] This equivalence provides a closed-form solution via Frobenius computations, aiding verification of liveness in weighted T-systems.^[41] In number theory, the two-denomination coin problem connects to Diophantine approximations through continued fraction expansions of the ratio a/b, enabling efficient computation of the Frobenius number g(a,b) = ab - a - b. The convergents of the continued fraction yield the minimal non-negative solutions to the equation ax + by = n, identifying the boundary between representable and non-representable integers without exhaustive search.^[42] This method, dating to the 1970s, exploits the quality of rational approximations to bound the search for the largest non-representable value.

References

[1]
Frobenius Number -- from Wolfram MathWorld
Finding the Frobenius number of a given problem is known as the coin problem. Computation of the Frobenius number g(a_1,a_2,...) is implemented in the ...
[2]
[PDF] The Frobenius Coin Problem Upper Bounds on The ... - UPenn CIS
In its simplest form, the coin problem is this: what is the largest positive amount of money that cannot be obtained using two coins of specified distinct ...
[3]
[PDF] The linear Diophantine problem of Frobenius - matthias beck
The next set of problems assumes some basic number theory, in particular, knowledge about the greatest-integer function and inverses in Zn. The different ...
[4]
[PDF] A Note on Numerical Semigroups Generated by k-th Powers
Feb 21, 2025 · It is known that. ⟨A⟩ is a numerical semigroup (that is, N \ ⟨A⟩ is finite) if and only if gcd(A) = 1. If S is a numerical semigroup and ...
[5]
[PDF] The Frobenius Problem and Its Generalizations
As we already have seen, Sylvester published a paper in 1882 where he defined h(x1,x2,...,xn) to be the total number of integers not representable as an integer ...
[6]
https://global.oup.com/academic/product/the-diophantine-frobenius-problem-9780198568209
[7]
AMS :: Feature Column :: The Frobenius Problem
This article presents a solution to the Frobenius problem in the simplest case that there are two denominations of currency.
[8]
Formulae for the Frobenius number in three variables - ScienceDirect
The Frobenius number of a, b, c, denoted by , is the largest integer that is not expressible by the form with x, y, z nonnegative integers.
[9]
Routines for the Frobenius Problem
However, the case of three denominations is hard, and for general N, the problem is NP-hard! In an example inspired by the "denominations" of McDonald's ...
[10]
Frobenius number for three numbers - MathOverflow
May 1, 2010 · First of all you must use Johnson's formula. For modified Frobenius number f(a,b,c)=g(a,b,c)+a+b+c it gives f(a,b,c)=df(a/d,b/d,c). It allows to ...A formula for Frobenius number of certain numerical semigroupsTripathi's formulas for Frobenius number in three variablesMore results from mathoverflow.net
[11]
[PDF] solution of the frobenius problem and its generalization
Nov 27, 1989 · The simple statement of the Frobenius problem makes it attractive. Not surprisingly, the Frobenius problem is NP-hard in general. This is ...
[12]
None
### Extracted Formula for Frobenius Number g(A)
[13]
[PDF] Sylvester sums on the Frobenius set in arithmetic progression - arXiv
Mar 23, 2022 · Roberts [18] found the Frobenius number for arithmetic sequences. g(a, a + d,...,a + (k − 1)d) = a − 2 k − 1 a + (a − 1)d.
[14]
[PDF] Formulae for the Frobenius number in three variables - IIT Delhi
In this section, we discuss the Frobenius Problem specifically in the case of three variables. There are several algorithms for computing g(a1,a2,a3), none of ...<|control11|><|separator|>
[15]
[PDF] ON THE FROBENIUS PROBLEM FOR GEOMETRIC SEQUENCES ...
INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 8 (2008), #A43. ON THE FROBENIUS PROBLEM FOR GEOMETRIC SEQUENCES. Amitabha Tripathi. Department of ...
[16]
None
**Summary of arXiv:math/0606717**
[17]
(PDF) On the Frobenius Number of Fibonacci Numerical Semigroups
In this paper we compute the Frobenius number of certain {\em Fibonacci numerical semigroups}, that is, numerical semigroups generated by a set of Fibonacci ...
[18]
The extended Frobenius problem for r-Fibonacci sequences shifted ...
May 18, 2025 · We study the extended Frobenius problem for sequences of the form , where is an r-Fibonacci sequence and is an r-Fibonacci number.
[19]
Frobenius numbers associated with Diophantine triples of x2 + 3y2 ...
Apr 25, 2025 · ... 2025. Abstract. We give an explicit formula for the p-Frobenius number of triples associated with Diophantine equations x2 +3y2 = z3, that is ...
[20]
A combinatorial approach to Frobenius numbers of some special ...
We present a combinatorial approach to the Frobenius problem. Basically, we transform the problem into an easier optimization problem.
[21]
A Circle-of-Lights Algorithm for the “Money-Changing Problem”
Apr 11, 2018 · (1978). A Circle-of-Lights Algorithm for the “Money-Changing Problem”. The American Mathematical Monthly: Vol. 85, No. 7, pp. 562-565.
[22]
[1610.08726] Wilf's conjecture for numerical semigroups - arXiv
Oct 27, 2016 · Let S\subseteq \mathbb{N} be a numerical semigroup with multiplicity m, embedding dimension \nu and conductor c=f+1=qm-\rho for some q,\rho\in\ ...Missing: statement | Show results with:statement
[23]
Bounds for invariants of numerical semigroups and Wilf's conjecture
May 31, 2023 · We provide bounds for and for the type of the numerical semigroup in function of e and n, and use these bounds to prove that
[24]
https://link.springer.com/article/10.1007/s00209-023-03295-6
[25]
On the linear diophantine problem of Frobenius. - Semantic Scholar
The problem of Frobenius consists in determining the largest integer g(a1,a2,...,ak) with no such representation. To the author, a particularly nice aspect ...
[26]
An optimal lower bound for the Frobenius problem | Request PDF
The objective of this paper is to produce new upper bounds for the Frobenius number when N ≥ 3. ... Aliev ... Positive semigroups and generalized Frobenius numbers ...
[27]
An upper bound for the Frobenius number and stretched numerical ...
We give a new upper bound for the Frobenius number 𝐹 ⁡ ( 𝐻 ) of H with respect to a pair of relatively prime generators ( 𝑛 𝑖 , 𝑛 𝑗 ) of H. Then we will ...
[28]
A Study on the Estimation of the Frobenius Numbers Generated by ...
Apr 27, 2025 · In this paper, we study the approximation of Asymptotic behavior using Linear Regression to get a Frobenius Number for one existing and a new result.
[29]
Short Proof: Exact Solution to the Finite Frobenius Coin Problem
Abstract page for arXiv paper 2508.08464: Short Proof: Exact Solution to the Finite Frobenius Coin Problem.
[30]
Frobenius numbers for the triplets of the centered triangular ...
May 8, 2025 · Frobenius numbers for the triplets of the centered triangular numbers and centered square numbers. May 2025. Authors: Tapas Chatterjee at ...
[31]
[PDF] The Computational Complexity of the Frobenius Problem - arXiv
Nov 15, 2016 · Then, we say that L is strongly C-hard if there is no pseudopolynomial algorithm for solving L; otherwise, we say that it is weakly C-hard. 3 ΠP.
[32]
<p>Wilf's Conjecture for Numerical and Affine Semigroups</p>
Wilf's conjecture establishes an inequality that relates three fundamental invariants of a numerical semigroup: the minimal number of generators (or the ...
[33]
[PDF] the worst case in shellsort and related algorithms - MIT Mathematics
In Section 3, we describe the Frobenius problem, and prove a result showing its connection with Shellsort. This result is used in Section 4 to obtain upper.
[34]
[PDF] A New Upper Bound for Shellsort - Robert Sedgewick
A direct relationship between Shellsort and the classical “problem of Frobenius” from additive number theory is used to derive a sequence of O(log N) ...
[35]
[2110.02503] More on Change-Making and Related Problems - arXiv
Oct 6, 2021 · The analysis of the algorithm uses a theorem of Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the ...
[36]
[PDF] More on Change-Making and Related Problems - DROPS
The analysis of the algorithm uses a theorem of. Erdős and Graham (1972) on the Frobenius problem. This algorithm can be extended to solve the all-capacities ...
[37]
Liveness of weighted circuits and the diophantine problem of ...
The diophantine problem of Frobenius is used to determine a formula for the least live weight. Download to read the full chapter text. Chapter PDF. Similar ...
[38]
On the Reversibility of Circular Conservative Petri Nets
The diophantine problem of Frobenius is used to determine a formula for the least live weight. View. Show abstract. On Weighted T-Systems. Chapter. Jun 1992 ...
[39]
https://drops.dagstuhl.de/storage/00lipics/lipics-vol173-esa2020/LIPIcs.ESA.2020.29/LIPIcs.ESA.2020.29.pdf
[40]
What progress has been made till date on the Frobenius coin ...
Jun 11, 2014 · The Frobenius Coin Exchange Problem (FP) goes back to J. J. Sylvester in the mid 1880s. Let N0 N 0 denote the set of non negative integers: ...