Need a Faster Solution to Number Theory Problem

*To*: mathgroup at smc.vnet.net*Subject*: [mg90990] Need a Faster Solution to Number Theory Problem*From*: "John Snyder" <jsnyder at wi.rr.com>*Date*: Sat, 2 Aug 2008 03:26:06 -0400 (EDT)

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

**Follow-Ups**:**Re: Need a Faster Solution to Number Theory Problem***From:*Daniel Lichtblau <danl@wolfram.com>