Are 2c and 3c coins still legal tender?
1 Like
Iām too lazy to try and find a solution using this ideaā¦ but would including any number of coins using decimal values (EG: A 1.5Ā¢ coin) allow for a smaller set?
Tell your nation that second decimal place precision is decadent and that nothing smaller than a tenth will be minted. 
2 Likes
Iām not going to waste time on this, but I will say itās delightful to visit Canada, where $5 is three coins.
1 Like
Two bits, four bits, six bits, a dollarā¦
5 Likes
I love that the $ symbol ultimately derives from The Pillars of Heracles.
blarg. I wrote a program to brute force all solutions with 16 or fewer coins. there are no 15 coin solutions.
I wish there was some kind of, like, clever way to come up with a solution to this, rather than just brute forcing it, but if there is a smarter approach, I havenāt thought of it. As it stands, I thought of it as an optimization problem, which was kind of interesting - i suspect I could still get the run time down quite a bit lower than it is.
Anyway, 16 coin solutions
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 45, 47, 48, 49, 52
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 47, 48, 49, 51
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 46, 48, 49, 51, 53
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52 -> best value! does all values up to 104
ETA:
sometimes, you get some right answers, and so you think you got them all. but I actually had a silly bug in the logic for finding the first gap in the combinations that would fail if the gap was in the high 64 bits, so hereās the answers I missed the first time around
1, 2, 3, 7, 11, 15, 19, 23, 27, 28, 29, 30, 61, 64, 67, 70
1, 3, 4, 7, 8, 9, 16, 17, 21, 24, 35, 46, 57, 68, 79, 90
1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50
8 Likes
I looked into brute force approaches, only to abandon when I concluded there are 2x10^27 cases to be checked to find 15-coin solutions. (That includes the shortcut that a 1-cent coin is a given.) What method did you use, what shortcuts were you able to apply, and how long did it take?
I was closing in on one of those solutions last night, working by hand. Unfortunately, instead of 5 and 8 Iād jumped to 9 and 11, so I was ending up with holes that werenāt quite closing up.
I have to wonder if thereās a logical method to derive the answers. Iād decided that there would have to be a nearly sequential cluster around 44 - 52 in order to manage it, but that was more of an intuitive leap from all the playing around with the numbers rather than a logical decision.
1 Like
I wonder if this is fundamentally a brute-force problem? If not, perhaps solving a smaller problem via brute force would start to display a pattern? What is the smallest set of coins to make change for 10 or less with two coins?
1,3,4,6:
Ā 1 (0,1)
Ā 2 (1,1)
Ā 3 (0,3)
Ā 4 (0,4) (1,3)
Ā 5 (1,4)
Ā 6 (0,6) (3,3)
Ā 7 (3,4)
Ā 8 (4,4)
Ā 9 (3,6)
10(4,6)
1,3,4,5:
Ā 1 (0,1)
Ā 2 (1,1)
Ā 3 (0,3)
Ā 4 (0,4) (1,3)
Ā 5 (0,5)
Ā 6 (1,5) (3,3)
Ā 7 (3,4)
Ā 8 (4,4)
Ā 9 (4,5)
10(5,5)
I donāt know, donāt see much, and I see that 5, not 6 is part of all listed 16 coin solutions for 100.
The fact that there are multiple solutions, but that the lower numbers seem fixed (1,3,4 for these two, 1,3,4,5,8,14,20,26,32,38,44 for the four solutions for 100) might mean something.
1 Like
So, yeah, the 1 cent is a given.
You never need to check for a coin unless itās higher than all the other coins in your set. And you never need to check a value thatās higher than the smallest gap in your combinations. So, you start with 1, then you donāt need to check 1 again, and you donāt need to check anything higher than 3. the only possible values for the second coin are 2 & 3.
For the third coin, if you already have 1 & 2, then you need to check 3,4,5. You donāt have to check 6 or greater, because 1,2,6 canāt make 5, so thatās a bad combination.
I store the values of the coins Iām testing as a pair of 64 bit integers - one bit per coin. And I store all the combinations that Iāve covered as another pair of 64 bit integers. The code would have been cleaner with 128 bit ints, but my hardware doesnāt support that. I thought about using the bigint library, but felt like I could probably do better by hand coding the low/high bitfields in this specific case.
The nice thing about storing things as bit fields is that when I add a new coin, I can find all the new combinations by shifting the field with all my coins by the new coin value (to make this work, I also act as though I have a zero value coin). Iām thinking of it as a shift, but I actually multiply to do the shift, so I can use _umul128
The whole thing runs in something like 20 or 30 minutes, on an AMD Athlon II chip at 3ghz. Thereās very little memory access while itās running. The first thing i would do if I were going to make it faster would be to run it on multiple threads. I can post the source code (somewhere?) if anyone is interested
3 Likes
Itās a good question. I tried running the program on some smaller sets - for example, the possible combinations for making the values from 1-80 with 14 coins are
1, 2, 5, 8, 11, 14, 17, 20, 23, 24, 25, 51, 53, 55
1, 3, 4, 5, 8, 14, 20, 26, 32, 35, 36, 37, 39, 40
1, 3, 4, 9, 10, 15, 16, 21, 22, 24, 25, 51, 53, 55
Out of the three results, only one would start you in a good direction. I donāt have enough math to say when a given solution for 1-X is going to be a good starting point on a solution to a larger set. itās possible that patterns would become more obvious as we go bigger, but that starts getting into execution times that arenāt fun. 14 coins is done in 7 seconds. 16 coins took 805. 17 coins could be up to 8 hours of runtime (unless I multithread it and run it on a 16 core machine - then we might be back to reasonable times)
3 Likes
So, doing it by hand for 10 I got 1,3,4,5 and 1,3,4,6ā¦then I tried taking both to 20, and quickly 1,3,4,5 was better. And as I went on to 32 I was looking at your numbers to check, and it seems that if I just try to make numbers from previous numbers, and if I canāt, add the number I couldnāt make, so far Iām getting the same values. I could probably continue the process manually to see if it holds up faster than writing a program to follow that operationā¦
I also wondered if there was anything to the number distribution, but I see for your solutions we have 5 numbers clustered between 1 and 10 and five clustered between 40 and 50, and a pretty random distribution outside of that. Iām not sure what that means, but I guess having a bunch of numbers around 50 is probably the most efficient way to get all the numbers between 50 and 100, and having a bunch of numbers under 10 helps with smaller gradients.
UPDATE:
Okay, that doesnāt work: If you just start with that process from 0, then for 10 you get: 0,1,3,5,7,9. If I seed it to 8, however, then it carries on to 44 before going off the rails again:
0,1,3,4,5,8,14,20,26,32,38,44,50,56,62,68,74,80,86,92,98
After a little experimentation it appears I can solve 14 (technically 9) through 44, but all the numbers on either side I have to pre-seed (so, five on either side, then I can solve the middle six).
1 Like
Yeah, you canāt do it iteratively, you have to look at it holistically.
The main insight for me was modulo is a critical path because it allows you to use larger numbers for gradients. And the modulo has to be even to take advantage of doubling.
Ex. naively take 1, 2, 3, 4, 5, 11, 17 gets you to 22, whereas 1, 3, 4, 5, 8 , 14, 20 gets you all the way to 31 because 8 mod 6 is 2.
And then once you hit 44 all you have left to do is fill in the 5 remaining spots with other numbers in the 45-55 range to satisfy the values above 88.
2 Likes
Since 1+1 is 2 they donāt need a 2, but to generate gradients, they need some number to represent 2, the innovate solution is to use 8 mod 6, hence why they donāt need a 6, since the subsequent chain after 8 is 8 + 6, 8 + 6 + 6, 8 + 6 + 6 + 6, etc.
Itās intuitive but not obvious.
1 Like
It is possible with to solve this with 17 coins where two coins of the same value are never used. (I had a bug that imposed this requirement.)
3 Likes
Thatās actually really interesting, might be a key to the trick ā¦
I donāt know about this 16 number business but I got 17 with: 1, 2, 3, 4, 5, 9, 15, 21, 27, 33, 39, 45, 46, 47, 48, 49, 50
If it has an amount and stamped by the Mint, it is legal tender in the US. You can pay your taxes in half pennies if you want (assuming they take cash I suppose).
Private businesses however are not required to accept it (though they would be foolish not to considering the value is well over their stated price).
