Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>