mersenneforum.org Frobenius number
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-06-18, 02:11 #1 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 17008 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 2021-08-26 at 00:37 Reason: added Frobenius(a,b)
 2021-06-18, 04:07 #2 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 1000011111102 Posts
 2021-06-18, 12:57 #3 Dr Sardonicus     Feb 2017 Nowhere 7×733 Posts The Frobenius or coin problem is tantalizing because it has a closed-form solution for two variables - if gcd(a,b) = 1 the largest non-representable 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.
 2021-06-18, 14:34 #4 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,087 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 Pomder-this style puzzle. Last fiddled with by a1call on 2021-06-18 at 14:46
2021-06-18, 20:43   #5
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,087 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:
 **** 95 = 1*2 + 31 * 3 **** 95 = 4*2 + 29 * 3 **** 95 = 7*2 + 27 * 3 **** 95 = 10*2 + 25 * 3 **** 95 = 13*2 + 23 * 3 **** 95 = 16*2 + 21 * 3 **** 95 = 19*2 + 19 * 3 **** 95 = 22*2 + 17 * 3 **** 95 = 25*2 + 15 * 3 **** 95 = 28*2 + 13 * 3 **** 95 = 31*2 + 11 * 3 **** 95 = 34*2 + 9 * 3 **** 95 = 37*2 + 7 * 3 **** 95 = 40*2 + 5 * 3 **** 95 = 43*2 + 3 * 3 **** 95 = 46*2 + 1 * 3

Last fiddled with by a1call on 2021-06-18 at 21:03

 2021-06-19, 00:20 #6 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 26×3×5 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 2021-06-19 at 18:32 Reason: added Frobenius(a,b)
 2021-07-08, 08:49 #7 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 11110000002 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

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Number Theory Discussion Group 10 2019-04-16 10:14 paulunderwood Number Theory Discussion Group 12 2018-11-09 07:07 CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16 literka Factoring 5 2012-01-30 12:28

All times are UTC. The time now is 10:48.

Sat Dec 4 10:48:40 UTC 2021 up 134 days, 5:17, 0 users, load averages: 1.13, 1.12, 1.15