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,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

Joan Ludevid, Table of n, a(n) for n = 0..10000

Index entries for sequences related to making change.

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

Cf. A011542, A001299.

Sequence in context: A271775 A143999 A137419 * A245574 A245573 A236968

Adjacent sequences: A057533 A057534 A057535 * A057537 A057538 A057539

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