Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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$? –  Brian M. Scott May 10 '12 at 3:17
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Very ...... nice. –  copper.hat May 10 '12 at 3:53
    
Might be even easier to read it off from oeis.org/A053344/b053344.txt –  Gerry Myerson May 10 '12 at 4:11
    
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. –  Nate Kennedy May 10 '12 at 12:33
    
@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. –  Charles May 10 '12 at 13:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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