2

The Frobenius Coin Problem, named after Ferdinand Frobenius is a math problem that asks for the largest monetary amount that cannot be represented using only a specific number of coin denominations.

Let $m=1, a \geq 1!, N_m(x) = N_1(a) = a-1 +0 = a-1$, and there will be an infinite number of non-representable numbers using only one denomination. NOTE: the plus zero in the equation is important to remember.

Let $m=2, a \geq 2!, b \geq 2!, \gcd(a,b) = 1$, and the 'a' and 'b' must be at least two units apart. $N_m(x,y) = N_2(a,b) = (a-1)*(b-1) -1= (a-1)*(b-1) -1 = a*b -a -b$, and there will be a largest number which cannot be represented using only two denominations. All numbers after that maximum number can be represented using multiples of 'a's and 'b's. This result is well-known and has been proved.

Finally, Let $m=3, a \geq 3!, b \geq 3!, c \geq 3!, \gcd(a,b,c) = 1$, and the 'a's, 'b's and 'c's must be at least three units apart, respectively. $N_m(x,y,z) = N_3(a,b,c) = 1*[(a-2)*(b-2)*(c-2)] -2*[(a-1)*(b-1) -1 + (a-1)*(c-1) -1 + (b-1)*(c-1) -1] +3*[a+b+c] -1*\gcd(b,c) -2*\gcd(a,c) +1$, and there will be a largest number which cannot be represented using only three denominations. All numbers after that maximum number can be represented using multiples of 'a's, 'b's, and 'c's.

I've tried it for 6, 10, 15, and 6, 9, 20. It works for those entries, and should work for others, based on the restrictions presented. Let me know what you think.

Bill Bouris
  • 27
  • See here: https://arxiv.org/abs/1007.1840 – Christian Blatter Nov 17 '16 at 19:13
  • I skimmed through your paper, but haven't had time to fully comprehend it. The example 7, 11, 17 yields a result 152, incorrectly. But, I believe that all 3-tuples will always have an odd solution. Interestingly, 152/2/2-1 = 37 is the answer! I like my 'algebraic-type' solution, if it eventually works out. – Bill Bouris Nov 18 '16 at 07:29
  • The example ${\bf a}=(7,11,17)$ leads to $l_1=4$, $l_2=5$, $l_3=3$, and then to $g({\bf a})=37$ and $N({\bf a})=20$. – Christian Blatter Nov 18 '16 at 09:10
  • @ChristianBlatter What answer do you get for 8, 12, 19? It must be more involved, right? I have reformulated my calculations to be different from the above algebraic statements, and because of that, I can show that one denomination is infinite, and two denominations yield the value a*b -a -b, etc. – Bill Bouris Nov 26 '16 at 22:15

0 Answers0