3 ms·
I believe the young economist mentioned in the article is simply wrong in his analysis. The most efficient 4-denomination set is {1,5,18,25} (tied with {1,5,18,
by iconjack 2y ago
I believe the young economist mentioned in the article is simply wrong in his analysis. The most efficient 4-denomination set is {1,5,18,25} (tied with {1,5,18,29}) at 3.89 coins per transaction, better than the economist's {1,3,11,38} at 4.10. This result is from a 2003 paper by Jeffrey Shallit called "What's This Country Needs is an 18¢ Piece". Just before posting, I verified Shallit's result with a Python program.
[1] https://graal.ens-lyon.fr/~abenoit/algo09/coins1.pdf https://graal.ens-lyon.fr/~abenoit/algo09/coins1.pdf