A053344 Minimal number of coins needed to pay n cents using coins of denominations 1, 5, 10, 25 cents.

1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 2, 3, 4, 5, 6, 3, 4, 5, 6, 7, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 5, 6, 7, 8, 9, 5, 6, 7, 8, 9, 4

Offset

1,2

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for sequences related to making change.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,-1).

Formula

a(n) = floor(n/25) + floor([n mod 25]/10) + floor([{n mod 25} mod 10]/5) + ([n mod 25] mod 10) mod 5.

G.f.: -x*(5*x^24 -x^23 -x^22 -x^21 -x^20 +4*x^19 -x^18 -x^17 -x^16 -x^15 +3*x^14 -x^13 -x^12 -x^11 -x^10 +4*x^9 -x^8 -x^7 -x^6 -x^5 +3*x^4 -x^3 -x^2 -x -1) / ((x -1)^2*(x^4 +x^3 +x^2 +x +1)*(x^20 +x^15 +x^10 +x^5 +1)). - Colin Barker, Jan 10 2015

Example

a(57) = 5 because to pay 57 cents at least 5 coins are needed: 2 of 25 cents, 1 of 5 cents and 2 of 1 cent.

Mathematica

f[n_]:=Floor[n/25]+Floor[Mod[n, 25]/10]+Floor[Mod[Mod[n, 25], 10]/5]+Mod[Mod[Mod[n, 25], 10], 5]; lst={}; Do[AppendTo[lst, f[n]], {n, 6!}]; lst (* Vladimir Joseph Stephan Orlovsky, Sep 28 2009 *)
Table[Min[Total/@FrobeniusSolve[{1, 5, 10, 25}, n]], {n, 100}] (* or *) LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1}, {1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2}, 100] (* Harvey P. Dale, Aug 14 2014 *)

Prog

(PARI) Vec(-x*(5*x^24 -x^23 -x^22 -x^21 -x^20 +4*x^19 -x^18 -x^17 -x^16 -x^15 +3*x^14 -x^13 -x^12 -x^11 -x^10 +4*x^9 -x^8 -x^7 -x^6 -x^5 +3*x^4 -x^3 -x^2 -x -1) / ((x -1)^2*(x^4 +x^3 +x^2 +x +1)*(x^20 +x^15 +x^10 +x^5 +1)) + O(x^100)) \\ Colin Barker, Jan 10 2015
(Magma) I:=[1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 4, 5, 6, 2, 3, 4, 5, 6, 1, 2]; [n le 26 select I[n] else Self(n-1) +Self(n-25) - Self(n-26): n in [1..70]]; // G. C. Greubel, May 31 2018
(Python)
def A053344(n):
    a, b = divmod(n, 25)
    c, d = divmod(b, 10)
    return a+c+sum(divmod(d, 5)) # Chai Wah Wu, Nov 08 2022

Crossrefs

Cf. A011542, A001299.

Sequence in context: A010883 A011542 A260688 * A092196 A100878 A145172

Adjacent sequences: A053341 A053342 A053343 * A053345 A053346 A053347

Keyword

easy,nonn

Author

Jean Fontaine (jfontain(AT)odyssee.net), Jan 06 2000

Status

approved