Roland Piquepaille writes "There are mostly four kinds of coins in circulation in the U.S: 1 cent, 5 cents, 10 cents, and 25 cents. But is it the most efficient way to give back change? This Science News article says that a computer scientist has found an answer. "For the current four-denomination system, [Jeffrey Shallit of the University of Waterloo] found that, on average, a change-maker must return 4.70 coins with every transaction. He discovered two sets of four denominations that minimize the transaction cost. The combination of 1 cent, 5 cents, 18 cents, and 25 cents requires only 3.89 coins in change per transaction, as does the combination of 1 cent, 5 cents, 18 cents, and 29 cents." He also found that change could be done more efficiently in Canada with the introduction of an 83-cent coin and in Europe with the addition of a 1.33- or 1.37-Euro coin. Check this column for more details and references." The paper (postscript) is online.