```> I still can't manage
>   make_change(p**10-1, (1..20).map{|n|p**n})
> for any prime p (and who can?)

Actually, if I'm not totally mistaken, handling primes is a
generalization of the even/odd optimization. The enclosed code
(ruby19)
includes such checks. Unfortunately, this optimization takes some
time
and makes the code about 2-3 times slower than my first submission (I
assume the optimization could be further optimized :-).

Regards,
Thomas.

require 'mathn'

def make_change(amount, coins = [25, 10, 5, 1])
return nil if coins.empty? or !amount.kind_of?(Integer)
# Collect the coins' prime factors.
factors = Hash.new {|h, c| h[c] = Hash[c.prime_division]}

changer = ->(amount, coins, max_size) do
return [] if amount == 0
return nil if coins.empty? or max_size <= 0
cf = Hash.new(0)
coins.each {|c| c != 0 && factors[c].each {|f, n| cf[f] += 1}}
# If all coins have a common prime factor but this prime is
no
# factor of amount, then we cannot build a sum equal the
amount
# with these coins.
return nil if cf.any? {|f, n| n == coins.size && amount % f !=
0}
set = nil
coins = coins.dup
until coins.empty?
coin = coins.shift
next if amount < coin
n_coins = amount.div(coin)
break if n_coins > max_size
n_coins.downto(1) do |j|
other = changer.call(amount - coin * j, coins,
max_size - j)
if other
set = ([coin] * j) + other
max_size = set.size - 1
end
end
end
return set
end

coins = coins.sort_by {|a| -a}
coins.reject! {|c| c == 0 || c > amount}
changer.call(amount, coins, amount)
end

```