mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > MattcAnderson

Reply
 
Thread Tools
Old 2021-06-18, 02:11   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2·3·151 Posts
Default 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)
MattcAnderson is offline   Reply With Quote
Old 2021-06-18, 04:07   #2
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32·239 Posts
Default

a1call is offline   Reply With Quote
Old 2021-06-18, 12:57   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

7×23×31 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-06-18, 14:34   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

41478 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-06-18, 20:43   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

32·239 Posts
Default

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
a1call is offline   Reply With Quote
Old 2021-06-19, 00:20   #6
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2·3·151 Posts
Thumbs up 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)
MattcAnderson is offline   Reply With Quote
Old 2021-07-08, 08:49   #7
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

2×3×151 Posts
Default

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
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA on Frobenius paulunderwood Number Theory Discussion Group 10 2019-04-16 10:14
Frobenius and semi-prime testing paulunderwood Number Theory Discussion Group 12 2018-11-09 07:07
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Fermat number F6=18446744073709551617 is a composite number. Proof. literka Factoring 5 2012-01-30 12:28

All times are UTC. The time now is 17:46.


Fri Oct 22 17:46:47 UTC 2021 up 91 days, 12:15, 0 users, load averages: 1.68, 1.55, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.