> Probability of a transaction resulting in value v is uniform from [0,99].<p>in reality, most of the transactions that use coins end up conforming to common existing coin combinations e.g. laundromats in US mostly price as multiples of quarters ($0.25)
We should better introduce $50, $100, $500, $1000 and $5000 coins. I'd love my entire salary to come in coins and to be able to pay for any purchase in coins conveniently.
Iportant first comment in the blog:<p>> <i>Just to summarize how commenter, Jeffrey Shallit, addresses the (1, 3, 11, 37) solution: this is the best way to use the Greedy algorithm to select coins. However, (1, 5, 18, 25) and (1, 5, 18, 29) are tied for the actual solutions. [...]</i>
I thought it was going to be about how there was 3700% inflation since coins were actually a useful concept.<p>It's probably just better to go for eliminating the cent and the nickel and making a 2.5$ coin.
Most efficient would be to start rounding purchases to the nearest five cents (if is isn't electronic) and get rid of the penny which costs more to produce than the penny is worth.
People need to be able to quickly do the math in their heads to make change. More efficient use of coins but harder for everyone involved is not a functional improvement.
I love thinking about problems like that. Yes it is impractical and unlikely to result in any change but it also helps illuminate relationships (like # of coins in your change) that you might not otherwise see.<p>Of course, as an economist Patrick (the person asking the question in the article not the author) ignores what is most important about choosing coins "Can the teller give you change quickly and accurately?" That is the important question because GDP depends on transaction flow, and anything that hinders transaction flow is a net negative on GDP[1].<p>Using the Suica card in Japan I was reminded again of how useful it would be if the government would just bless a pure stored value cash card. Yes, I understand the arguments against it (mostly based on surveillance IMHO) but still it would be a useful thing in terms of getting us to 0 coins per transaction. :-)<p>[1] Yes, I subscribe to the theory that GDP is inherently a time based numbers "value per unit time"
In ideal world, I would prefer coins to be powers of 2.<p>It requires 7 coins in [ 1 .. 64 ] range to reach 100, but the average of popcnt( 1 .. 99 ) is only 3.19 coins per transaction, way better than 4.1 coins.
Two obvious problems: the fractional part of the price is not uniform over [00..99] and the system has 5 coins, since in 2021 minting for the half-dollar coin was restarted.
At some point, that we are possibly near to, doesn’t the value of a dollar become so small that the fractions of a dollar that coins represent aren’t even worth dealing with?<p>If so, and transactions just rounds to nearest dollar the we are basically expecting that over our lifetime it will nearly balance out without the need to think about it too much.
I currently have 0 coins and 0 bills on me. I had to borrow $10 from my wife to tip the bartenders at a wedding this past Saturday since I didn't want to go to an ATM. Cash (and coins) have their place but it's not worth the effort to make them more efficient anymore.
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.<p>[1] <a href="https://graal.ens-lyon.fr/~abenoit/algo09/coins1.pdf" rel="nofollow">https://graal.ens-lyon.fr/~abenoit/algo09/coins1.pdf</a>
> The chance you have 43 cents in your pocket is equal to the probability that you have 29 or 99 cents in your pocket (in addition to any bills).<p>This was something I found fascinating when I first visited the US. I'm not sure if it's common across the entire country, but it definitely happened everywhere I shopped: I always received the exact change. If something cost $1.97 and I paid $2 in cash, I would get 3 cents back. And so on, no matter how many coins would be necessary. How thoughtful. I'm more used to rounding off and leaving the change behind, no questions asked.
I was curious what the theoretical distribution of digits might be, did not know that there is an extension of Benford's law for later digits which suggests the uniform assumption is quite nearly right:
<a href="https://en.wikipedia.org/wiki/Benford%27s_law#Generalization_to_digits_beyond_the_first" rel="nofollow">https://en.wikipedia.org/wiki/Benford%27s_law#Generalization...</a><p>Of course in real life, 50 cents and 99 cents are way more common.
Related:<p><i>Do We Need a 37-Cent Coin?</i> - <a href="https://news.ycombinator.com/item?id=1694075">https://news.ycombinator.com/item?id=1694075</a> - Sept 2010 (137 comments)<p><i>Freakonomics: Do We Need a 37-Cent Coin?</i> - <a href="https://news.ycombinator.com/item?id=864838">https://news.ycombinator.com/item?id=864838</a> - Oct 2009 (50 comments)
There's a question on SE cstheory site that addresses the more general problem [0]. I wonder if this problem is still open.<p>[0] <a href="https://cstheory.stackexchange.com/questions/5861/asymptotics-for-coin-changing" rel="nofollow">https://cstheory.stackexchange.com/questions/5861/asymptotic...</a>
The coins proposed are all prime, which makes sense to me intuitively. You'll always need a 1 coin. I'm curious if it's generally true that optimal coins for any given range starting at 0 will be primes?
not anymore :)<p>Personally, in the US, pennies, nickles and dimes should be eliminated.<p>I think we are at the point were paper money $1, $2 and $5 should be replaced by coins. But that would cause a huge uproar in this country.