A little Python

Two filler photos for today. Neither of them contain pythons.

I had thought of starting today’s post with a picture of a snake, but I think yesterday featured enough unpleasantness.  We had two colloquia today, including a great talk by Luis Caffarelli on diffusion equations which had some great insights into regularity for these solutions.  But I’d like to talk about the second one, which was on the Frobenius coin problem, asking what the largest number  a certain number of coins could not make change for.  The idea is that if you lived in a (rather silly) country with only 3 and 5 cent pieces, you would be at a loss to give someone 7 cents.

But this is not the problem I want to talk about.  I want to think about countries that are moderately less silly.  They will always have coins to make any amount of change (this is equivalent to always having 1 cent pieces).  But the observation I seek to generalize is the following:

With [common] US coins, it is possible to have $1.19 in change, but not be able to make change for a dollar (i.e., 3 quarters, 4 dimes, and 4 pennies).

Houston, looking positively bucolic.

I want to imagine a country where a dollar is worth d pennies, and to investigate the worst choice of denominations for coins, so that a person can have a lot of money in coins, but not make change for a dollar.  I also impose the following restrictions:

1. The country has at most 4 denominations of coin.
2. Each denomination of coin divides the value of a dollar.

I wrote a short Python script to solve this.  It turns out that as long as you have 4cent and 25cent pieces, you can hold $1.71 without being able to make change for a dollar.

The first time you get over $5 in coins is when 1 dollar = 210 cents, then if you have pennies, 30, 35, and 42 cent pieces, you can have $5.23 in coins without being able to break a dollar.  Similarly, if 1 dollar = 396 cents, you can have $10.09 in coins, if coins have value 1,36,44 and 99.

I have put a plot below.  It reminds me vaguely of the plot of Euler’s totient function, and certainly a thorough description of a solution to this should have to do with how many factors the denominations of coins have, but I certainly do not have a rigorous explanation for why these two plots look similar.  The points along the bottom correspond to prime numbers, where condition 2 requires that we only have pennies.

A plot for value of a dollar, and the most change you can have without being able to break a dollar (assuming a really bad choice of denominations of coins).

Euler's phi function, for comparison.


One comment on “A little Python

  1. Leonid Kovalev says:

    Ah yes, I visited the bucolic Houston a couple of times… even in the picture there’s too much concrete.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s