3
$\begingroup$

Say I wanted to be able to carry enough coins in my pocket such that at any time, I could count out exact change totaling any of the prime numbers less than 100. How would I determine the minimum set of coins I would need to carry? I don't care about being able to count out multiple primes - meaning the set does not have to remain useful after one number has been counted out.

So, given the standard US coins: penny, nickel, dime, and quarter - what would be the minimum number of each coin that I would need to be able to count out exactly $3, 5, 7, 11$ up to $97$ cents.

$\endgroup$
  • 1
    $\begingroup$ Are you asking for the minimum for each prime separately, or are you asking for the minimum collection that suffices to make every prime amount less than $100$? $\endgroup$ – Brian M. Scott May 10 '12 at 3:17
4
$\begingroup$

If you want one set of coins that can add to all primes, you need 4 pennies so you can do 19. You also need a nickel for 19. Two nickels are dominated by dime+nickel, so you only want one. You clearly want three quarters to get close to 97. As three quarters, one dime, one nickel, and four pennies can't do 97 you need two dimes. So: three quarters, two dimes, one nickel, and four pennies makes ten coins.

$\endgroup$
6
$\begingroup$

See the Encyclopedia of Integer Sequences: https://oeis.org/A053344

$\endgroup$
  • $\begingroup$ Very ...... nice. $\endgroup$ – copper.hat May 10 '12 at 3:53
  • $\begingroup$ Might be even easier to read it off from oeis.org/A053344/b053344.txt $\endgroup$ – Gerry Myerson May 10 '12 at 4:11
  • $\begingroup$ While the formula provided there is useful, it destroys any knowledge about which specific coins are needed to get each sum. You get a count, but only of how many coins total. Good starting point though. I'll see if I can adapt that to get what I'm looking for. $\endgroup$ – Nate Kennedy May 10 '12 at 12:33
  • $\begingroup$ @CoreyKennedy: The formula actually provides the coins. Each addend is the number of a specific type of coin; I believe they're arranged from highest to lowest. $\endgroup$ – Charles May 10 '12 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.