A057536 Minimal number of coins needed to pay n Euro-cents using the Euro currency.

0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 2, 3, 3, 4, 4, 3, 4, 4, 5, 5, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 3, 4, 4, 5, 5, 4, 5, 5, 6, 6, 1, 2, 2, 3, 3, 2

Offset: 0

Author

Thomas Brendan Murphy (murphybt(AT)tcd.ie), Sep 06 2000

Keywords

• easy
• nonn

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.

Examples

			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.
		

Links

• Joan Ludevid, Table of n, a(n) for n = 0..10000
• Index entries for sequences related to making change.

Crossrefs

Cf. A011542, A001299.

Programs

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 *)

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.

Extensions

a(0)=0 prepended by Alois P. Heinz, May 26 2015