OFFSET
0,4
COMMENTS
Euro currency has coins and bills of size 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000 cents.
LINKS
FORMULA
a(n) = floor(n/50000) + floor((n mod 50000)/20000) + floor(((n mod 50000) mod 20000)/10000) + ... + floor(((n mod 50000) mod 20000 ... mod 5)/2) + ((n mod 50000) mod 20000)... mod 2.
EXAMPLE
a(57) = 3 because to pay 57 cents at least 3 coins are needed: 1 of 50 cents, 1 of 5 cents and 1 of 2 cents.
MATHEMATICA
Table[Min[Map[Total, FrobeniusSolve[{1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000}, n]]], {n, 0, 105}] (* Joan Ludevid, Jun 15 2022 *)
numCoins[n_]:=(amount = n; coins = {50000, 20000, 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1}; total=0; For[i = 1, i <= Length[coins], i++, total+=Quotient[amount, coins[[i]]]; amount = Mod[amount, coins[[i]]]]; total);
Table[numCoins[n], {n, 0, 105}] (* Joan Ludevid, Jun 16 2022 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Thomas Brendan Murphy (murphybt(AT)tcd.ie), Sep 06 2000
EXTENSIONS
a(0)=0 prepended by Alois P. Heinz, May 26 2015
STATUS
approved