Optimal denominations to split a dollar

bl.ocks.org

3 pointszjonsson3 comments

Recently, I learned (via HN) that prime numbers are the magical building blocks of numbers.

By using that fact (without understanding it), I was able to beat the author's scores slightly by only including prime coins in the list of candidates.

http://jsfiddle.net/JY648/

Oh, the author still wins on the 4- and 5-coin variations.

When I try to include more than X candidates, it crashes. Help?

Oh, after some thought, I think I understand my intuition: prime coins are good choices for the same reason prime numbers are good choices when you are resizing images or changing the sample rate on audio. What do you call that, when you avoid Moiré patterns (or something like that) by using primes?

Brilliant, thank you! My initial approach was simplistic (to avoid combinatory explosion) but prime numbers seem obvious in hindsight!

Reply on news.ycombinator.com