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

Author

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

Keywords

• easy
• nonn

Examples

			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.
		

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

Crossrefs

Cf. A011542, A001299.

Programs

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

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

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

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

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