Cents and Cents-Ability

A late post this week, since I'm currently traveling in Italy with my parents! Going between EU countries and using cash more often than usual has reminded me of how inept I feel making change in euros after 30 years of using the US denominations. I thought I'd take a look at the relationship between the different coin/bill values and the ways to get a certain amount of money.

Here are the US denominations less than $5 (not including $1):

Wikipedia

And the EU denominations less than 5€:

Wikipedia

We're looking for ways to get a total value using some number of each of these coins. We can write this as an equation, for example

where p, n, d, q, and D are the numbers of pennies, nickels, dimes, quarters, and dollars. Since we no longer cut coins to make change, all these values must be integers, which makes this a Diophantine equation. These can be difficult to solve; the Python package SymPy has tools for it, but I couldn't find a way to restrict it to only positive integers (handling anti-pennies is far too dangerous). I was able to make my own though, which uses a simple brute-force technique.

Since it slows down exponentially as the total value gets larger, I was only able to run it for values up to 4 dollars/euros. The results are still interesting though. Here's the minimum number of coins needed to make a total:

As each larger denomination becomes available, there's a sudden drop in the number of coins needed. Since euros include many more denominations, they're able to use fewer.

We won't always get the minimum in change though, so it's useful to look at the different ways to make a value, and find out what the average number of coins is:

These are going to include many sets with mostly pennies though, so we can also look at the median:

At the very beginning of each of these, you can see there are a few cases where the US uses more coins, probably due to the euro having a 2 cent coin, but in the end, more denominations means more coins on average.

There are many things I'll need to unlearn when I return to the US next month (like saying "merci" instead of "thanks"), but since I never really got the hang of euros I suppose making change won't be one of them.