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.

  • 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$?2012-05-10

2 Answers 2

4

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.

6

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

  • 0
    @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.2012-05-10