Re: Re: Need a Faster Solution to Number Theory

```Daniel Lichtblau wrote:
> John Snyder wrote:
>> I got hooked on the following little number theory problem which appears in
>> the August issue of Discovery magazine.  "Susan has more than one dollar in
>> change, but she still can't make exact change for a dollar bill. What is the
>> maximum amount of money that Susan could have in pennies, nickels, dimes and
>> quarters for this to be true?"
>>
>> I solved the problem using the following Mathematica code:
>>
>> coins={1,5,10,25};
>> dollar=FrobeniusSolve[coins,100];
>>
>> Catch[Do[t=Times@@Length/@(Cases[dollar,{p_,n_,d_,q_}/; (p<=#1&&n<=#2 &&
>> d<=#3 && q<=#4)]&@@@FrobeniusSolve[coins,a]);
>> If[t==0,Throw[a]],{a,130,101,-1}]]
>>
>> Starting with a maximum guess of \$1.30 this gives the correct answer of
>> \$1.19 in about 5 seconds.  The problem is that if the problem is made more
>> complicated by adding more possible coin denominations (and/or paper
>> currency) the execution time become very long indeed.
>>
>> Is there a way to speed up the solution to this type of problem so that I
>> can handle more complicated cases in a reasonable time?
>>
>> Thanks,
>>
>> John
>
> Late response, but I didn't get time to look hard at this until now. It
> seems to be a difficult problem in terms of complexity, though I'm not
> certain I have the best possible approach.
> [...]

I forgot a few things. One is that Mathematica already has the
functionality for elbows-to-corners (e2c) conversion built in. It seems
to be maybe 10 x faster than what I had shown.

Another is that one can often use term rewriting methods to bring down
the number of elbows under consideration. This specifically applies in
the case where the first denomination divides all others, and the second
divides all others above it. In our example we can swap 5 pennies for a
nickel and not hurt ourselves. It turns out that this removes most of
the elbows from consideration, thus making the job of e2c easier.

Here is the entire code needed. It assimes the first two denominations
are 1 and 5 respsctively. Were this not the case, one could still have
working code by removing the replacement rule that begins {p_,n_,rest}...

maxNoChange2[coins_List, amount_Integer /; amount >= 1] /;
Not[And @@ Map[IntegerQ, amount/coins]] := Infinity

maxNoChange2[coins_List, amount_Integer /; amount >= 1] :=
Reduce`FarthestCorner[
coins, (FrobeniusSolve[coins,
amount] /. {p_, n_, rest___} /;
p > 5 :> {p - 5*(Floor[p/5] - 1), n + Floor[p/5] - 1, rest})] -
Total[coins]

So here is the example that was taking around 80 seconds. Without the
elbow penny-to-nickel replacement rule it is around 6 seconds, and with
it we are down to 1 second.

In[19]:= coins = {1, 5, 10, 25, 50};

In[20]:= Timing[maxNoChange2[coins, 200]]
Out[20]= {0.992062, 219}

There may well be further improvements to be had. I'm not certain I have
exhausted all possible replacements (though I am certain we need to
retain 5 pennies when there are more than 5). I am not certain there is
anything at the moment.

One resource I will mention, since it is really good for computing
Frobenius numbers, is an article by Bjarke Roune.

http://portal.acm.org/citation.cfm?id=1328333.1328354&coll=&dl=

This and others of relevance can be obtained in pdf form at the URL below.

http://www.broune.com/papers/

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: Re: LaTex to Mathematica
• Next by Date: Mathematica Special Interest Group (Washington DC Area) UPDATED
• Previous by thread: Re: Need a Faster Solution to Number Theory Problem
• Next by thread: Re: Re: Re: Need a Faster Solution