What the U.S. needs is an 18-cent coin

An interesting wrinkle to this is that an 18 cent coin would make it much harder to make change with the fewest coins for certain values.<p>How do we make change in everyday life? The simple algorithm everyone knows, even if they don't know what an algorithm is, is to start with the largest coin and move down, taking as many of each as you can. Thus to make change for 72 cents we: take 2 quarters, leaving us with 22 cents take 2 dimes, leaving us with 2 cents take no nickels take 2 pennies, leaving us with 0 cents and we're done<p>This algorithm as it turns out is only optimal so long as each denomination is at least twice as much as the previous one. So what happens if we have an 18 cent coin? Let's make change for 37 cents. With the simple algorithm we end up with {1 quarter, 1 dime, 2 pennies}. That's four coins. However you can do it with three coins: {2 18 cent pieces, 1 penny}.<p>The algorithm for the case with arbitrary denominations isn't np-complete (it's a fun algorithms question to figure out), but it's way too difficult to be doing in your head all the time.

&#62; Shallit assumed that every amount of change between 0 and 99 cents is equally likely.<p>Fail. He could at least have blagged some transaction data from a retailer that actually does a bunch of small cash transactions. Just getting copies of the receipt roles from his local bodega would be better than this.

The assumption that every possible value from 0 to 99 is equally likely doesn't seem like the best idea. In a country where the cost of items usually ends in .99, .97, or the like, and the sales tax is added after the fact (and usually from 0-10%), is it still the best choice? The post (and cited paper) don't seem to mention this.<p>That said, I don't know where you'd acquire these sorts of statistics.

People can multiply 1, 5, 10, and 25 with zero difficulty. An average person would likely resent being forced to count multiples of a less round number such as 18. For that reason alone, such a change is unlikely to come about.

No. What the U.S. needs is NO coins.<p>(Seriously, does ANYONE use coins anymore? It's either bills or a credit card for me.)

Or, they could get rid of every coin smaller than a quarter. Assuming every amount of change less than a dollar is equally likely, the average number of coins needed to make change now becomes 1.5 - and it's not like anybody really uses anything less than a quarter for anything other than coinstar anyways

Whenever taxation changes it will shift the "average transaction value" by a few cents and invalidate the added usefulness of already minted coins