Re: a question of counting
From: Ed Beroset (beroset_at_mindspring.com)
Date: 03/14/05
- Next message: aeo6: "Re: Epistemology 201: The Science of Science"
- Previous message: Benjamin: "Is V bounded almost everywhere?"
- In reply to: David Einstein: "Re: a question of counting"
- Next in thread: David Einstein: "Re: a question of counting"
- Reply: David Einstein: "Re: a question of counting"
- Messages sorted by: [ date ] [ thread ]
Date: Mon, 14 Mar 2005 22:18:40 GMT
David Einstein wrote:
> Ed Beroset wrote:
>
>> Here's the problem: suppose you have coins that are worth 7, 11 and
>> 16 units. Assuming that you have an unlimited supply of each
>> denomination, what is the algorithm by which you can enumerate, in
>> order, each of the possible sums?
[...]
> Well, it depends on exactly what you are trying to do. If all you want
> to do is to write a program that enumerates the values, that is easy to
> do, but I'd need to know how and why you want to do this to give you
> advice on how to proceed.
That's one thing I'd like to have as a result, but I already have a
brute force program that does this by simply trying all combinations of
coins and sorting the results by value. I was inspired to look at this
by a problem (and solutions) given in a relatively recent issue of C/C++
Users Journal. The problem (paraphrased) was creating a program to
produce the series of all numbers which are of the form 2^x*3^y*5^z
where x,y,z are nonnegative integers, in numerical order. It's easy to
see that this is the same as the problem of x*log(2) + y*log(3) +
z*log(5) which, for some reason struck me as possibly easier to solve.
You'll note that my numbers (7,11,16) are scaled integer approximations
of those logarithms. The longer I pondered, the more I was intrigued by
the class of problems and their solutions, hence my posting here.
> If you are asking the more interesting question of describing the set of
> representable values, then you are venturing into the realm of the
> "Frobenius Problem".
Yes, that's exactly what I'm talking about! (I didn't know it by that
name, but looked it up.) Having a name helps the search process immensely.
> Most papers on the Frobenius problem concern
> themselves only with finding the largest number not representable, and
> maybe the number of values not representable. This is more difficult
> than it looks, with two coins it is simple, with 3 coins there is an
> algorithm consisting of two applications of the Euclidean algorithm. For
> n=4 or more coins there is an algorithm of Kannan which will run in
> polynomial time for fixed n, but is complicated and as far as I know has
> never been implimented.
Very interesting. I'm also interested in knowing if there is a
generating function for the set of numbers which is representable (or
conversely for the set of numbers which is not.)
> There is a paper by A. Barvinok and Kevin Woods available on the arXiv
> that shows that if one creates a power series f(x)=sum_{t is
> representable} x^t then f(x) has a simple description as a sum of
> rational functions.
Thanks for the specific and helpful reply. As for the name of the field
to which this problem belongs, it looks like Wolfram classifies this as
the realm of number theory involving Diophantine equations. Looks
like I need to find a book on basic number theory and educate myself.
Thanks for the pointers.
Ed
- Next message: aeo6: "Re: Epistemology 201: The Science of Science"
- Previous message: Benjamin: "Is V bounded almost everywhere?"
- In reply to: David Einstein: "Re: a question of counting"
- Next in thread: David Einstein: "Re: a question of counting"
- Reply: David Einstein: "Re: a question of counting"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
