20210618, 02:11  #1 
"Matthew Anderson"
Dec 2010
Oregon, USA
3·367 Posts 
Frobenius number
Today I learned,
about the 'coin problem'. "With only a 2 pence and 5 pence coins, one cannot make 3 pence, but one can make any higher integral amount. Very interesting Similarly, with only an unlimited number of 2 pence ant 10 pence coins, you can only make positive even amounts of pence amounts. So there is no Frobenius number for the set (2,10) and GCD(2,10) = 2. If (greatest common divisor) GCD(x,y) = 1 then there will be a Frobenius number , that is an amount for which any higher integral amount is possible. For chicken McNuggets in quantities of 9 and 20, the Frobenius number is 151. generally, this is my notation, Frobenius(a,b) = a*b  a  b. Now I cite sources before I get something wrong. Wikipedia Coin_problem and another link from Art of Problem Solving Online Chicken McNugget Theorem enjoy Matt Last fiddled with by MattcAnderson on 20210826 at 00:37 Reason: added Frobenius(a,b) 
20210618, 04:07  #2 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×19×59 Posts 

20210618, 12:57  #3 
Feb 2017
Nowhere
53×109 Posts 
The Frobenius or coin problem is tantalizing because it has a closedform solution for two variables  if gcd(a,b) = 1 the largest nonrepresentable number is
a*b  a  b. For a = 9, b = 20, this evaluates to 151. For more than two variables, there is no such formula. For three variables, however, there is an efficient computational method. The fact that this and other results about the problem were published in the prestigious Journal für die reine und angewandte Mathematik (AKA Crelle's Journal) is IMO some indication of their significance. 
20210618, 14:34  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×19×59 Posts 
An interesting question for me is if for the 2 coprime varieties (neither bring 1), all solutions are unique or not.
I assume the answer is yes and a counter example if present should be easy to find. ETA Perhaps more interesting would be the uniqueness of solutions for the all coprime more than 2 varieties (non being 1). ETA II  In either case a multiple coin variety could be the basis for a Pomderthis style puzzle. Last fiddled with by a1call on 20210618 at 14:46 
20210618, 20:43  #5  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·19·59 Posts 
Of course what I failed to realize that if set of coins a & b has a unique solution and b & c another sand a & c yet another, then the more than 2 coins variations can't be unique unless the total value is beyond the minimum for one pair and below the minimum for the other 2 pairs.
ETA: Unless that is, you are obliged to use at least on of each type of coins. So there are plenty of potential solutions for each pair: PARI=GP Code: Code:
theTotal =95 coin1 =2 coin2 =3 for(i=1,theTotal \coin1 ,{ for(j=1,theTotal \coin2, if(i*coin1 +j*coin2 ==theTotal , print("**** ",theTotal ," = ",i,"*",coin1," + ",j, " * ",coin2); ); ); }) Quote:
Last fiddled with by a1call on 20210618 at 21:03 

20210619, 00:20  #6 
"Matthew Anderson"
Dec 2010
Oregon, USA
3×367 Posts 
more Frobenius
Thank you a1call and Dr.Sardonicus for your enthusiastic and helpful comments.
Another example of a two coin problem would be with a=3 pence and b=4 pence. Then since Frobenius(a,b) = a*b  a  b, we have Frobenius(3,4) = 3*4  3  4 so Frobenius(3,4) = 12  7 finally Frobenius(3,4) = 5 pence This means, with only 3 pence coins and 4 pence coins, You cannot produce a 5 pence amount. However, you can produce amounts in {6, 7, 8, ...}. Frobenius is sure of this. This is a unique solution. Good fun. Matt Last fiddled with by MattcAnderson on 20210619 at 18:32 Reason: added Frobenius(a,b) 
20210708, 08:49  #7 
"Matthew Anderson"
Dec 2010
Oregon, USA
10001001101_{2} Posts 
Hi again all,
I haven’t read any references about Frobenius numbers. But here is my thought. Suppose you have two coins, and the value of one is an integer multiple of the other. Then the possible values of money is just the multiples of the smaller coin value. For example, if there were a kingdom with two pence and eight pence coins, and no others, then only even amounts of pence could be given as change. And more, every even value of pence could be produced given an infinite supply of these two coins. I believe I am right Matt 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
RSA on Frobenius  paulunderwood  Number Theory Discussion Group  10  20190416 10:14 
Frobenius and semiprime testing  paulunderwood  Number Theory Discussion Group  12  20181109 07:07 
Estimating the number of primes in a partiallyfactored number  CRGreathouse  Probability & Probabilistic Number Theory  15  20140813 18:46 
Number of distinct prime factors of a Double Mersenne number  aketilander  Operazione Doppi Mersennes  1  20121109 21:16 
Fermat number F6=18446744073709551617 is a composite number. Proof.  literka  Factoring  5  20120130 12:28 