Alright, I've had too much caffeine, let's try to make an algorithm. (Thanks to everyone who pointed out that it's an algorithm, not a logarithm.)

First step seems like you'd take the largest possible number of your largest subunit that adds up to less than the target.

Second, take your next largest subunit and add the largest possible amount that doesn't add up to the target when combined with any possible quantity of the largest subunit.

Then, repeat for each successively smaller subunit, but comparing each one to every possible permutation of quantities of the larger subunits.

Sounds simple to do in your head, but like a pain in the rear to code. So let's write a Perl script to do it. Forgive this for being ugly, but I'm really too wired to be doing this right now. (This defaults to the US test case, you can switch the commenting on the two "my @subunits" lines for the UK test case, or play with $target and $subunits for fun, as long as the assumptions at the top hold true.) Yes, this works. You might have to change the first line if your perl isn't in /usr/bin/perl.

(Thanks to e-troon for pointing out I missed a couple of UK coins in the first version. They don't effect the output unless you change the target.)

#!/usr/bin/perl -w # # Assumptions: # $target is amount to subdivide, integer # @subunits is a list of all possible subunits, all # integers, in order from largest to smallest # $target is even divisble by every item in @subunits my $target = 100; my @subunits = (25, 10, 5, 1); # Standard US coins #my @subunits = (50, 20, 10, 5, 2, 1); # Standard UK coins my %units_so_far; my @permutations = (0); foreach $unit (@subunits) { my $highestquantity = $target / $unit; foreach $perm (@permutations) { QLOOP: for $quantity (1 .. $highestquantity) { if ($unit * $quantity + $perm == $target) { $highestquantity = $quantity - 1; last QLOOP; } } } my @newperms = @permutations; if ($highestquantity) { foreach $perm (@permutations) { for (1 .. $highestquantity) { push @newperms, $_ * $unit + $perm; } } } @permutations = @newperms; $units_so_far{$unit} = $highestquantity; } my $outbuff = ""; my $total = 0; foreach (keys(%units_so_far)) { $total += $_ * $units_so_far{$_}; if ($units_so_far{$_}) { $outbuff .= "$units_so_far{$_} of denomination $_, "; } } print "You can have up to $total without making change for $target.\n"; print "(That's " . $outbuff . "if you care.)\n";

10/31/2001: Addendum: Yes, if you add 3 or 200 (or any other quantity that $target won't divide evenly into) to the subunits list, this program will happily use all your CPU power and memory until you kill it or your system crashes, in attempt to calculate infinity in a rather inefficient manner.