Variations of the Frobenius coin problem


by richardfrobey
Tags: coin, frobenius, variations
richardfrobey
richardfrobey is offline
#1
Apr3-12, 02:50 PM
P: 1
I wasn't sure if this should go in the number theory section, but here goes:

Is there a formula for solving problems such as: If there are n coin denominations [itex]x_{1}[/itex],[itex]x_{2}[/itex]...[itex]x_{n}[/itex] that total p cents, how many combinations are possible? n and p are positive real numbers, of course.


On a side note, wikipedia says: "There is an explicit formula for the Frobenius number when there are only two different coin denominations. If the number of coin denominations is three or more, no explicit formula is known; but, for any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time (in the logarithms of the coin denominations forming an input)."

Does anyone know what the algorithm that wikipedia mentions is? I know it cannot be written explicitly and mathematically (as per wikipedia), but can anyone write it in another format?


Feel free to repost this question on mathstackexchange, mathoverflow, yahoo! answers, etc. if it will help to get the answer.

Thanks in advance.
Phys.Org News Partner Mathematics news on Phys.org
Hyperbolic homogeneous polynomials, oh my!
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Stephen Tashi
Stephen Tashi is offline
#2
Apr4-12, 09:25 PM
Sci Advisor
P: 3,175
Quote Quote by richardfrobey View Post
If there are n coin denominations [itex]x_{1}[/itex],[itex]x_{2}[/itex]...[itex]x_{n}[/itex] that total p cents, how many combinations are possible?
Combinations of what? - you haven't stated a problem clearly.
tyro23
tyro23 is offline
#3
Apr6-12, 10:15 AM
P: 1
Quote Quote by Stephen Tashi View Post
Combinations of what? - you haven't stated a problem clearly.
I think this is asking about the number of combinations of coins that total less than or equal to p. I have seen similar problems, and even if this isn't what the TC meant (which I'm pretty sure it is), this should generate some interesting discussion.


Register to reply

Related Discussions
Calculus of variations problem Calculus 0
A proof needed, problem in Perron-frobenius theory Calculus & Beyond Homework 1
Frobenius problem Calculus & Beyond Homework 0
problem in ode with frobenius Calculus & Beyond Homework 1
frobenius problem General Math 3