0,3

There is a unique solution to this puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a semiprime number of ways that I can make change for n-1 cents and for n+1 cents." There is a unique solution to this related puzzle: "There are a prime number of ways that I can make change for n cents using coins of 1, 2, 5, 10 cents; but a 3-almost prime number of ways that I can make change for n-1 cents and for n+1 cents." - Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 26 2005

X. Gourdon and B. Salvy, Effective asymptotics of linear recurrences with rational coefficients, Discrete Math., 153 (1996), 145-163.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 316.

G. P\'{o}lya and G. Szeg\"{o}, Problems and Theorems in Analysis, Springer-Verlag, NY, 2 vols., 1972, Vol. 1, p. 1.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 152.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000

H. Bottomley, Initial terms of A000008, A001301, A001302, A001312, A001313

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 174

Index entries for sequences related to making change.

G.f.: 1/((1-x)(1-x^2)(1-x^5)(1-x^10)). a(n)=a(n-2)+a(n-5)-a(n-7)+a(n-10)-a(n-12)-a(n-15)+a(n-17)+1. a(-18-n)=-a(n).

a(n) = term (18,1) in a certain 18x18 matrix (see Maple code). - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 25 2008

1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10));

M := Matrix(18, (i, j)-> if(i=j-1 and i<17) or (j=1 and member(i, [2, 5, 10, 17, 18])) or (i=18 and j=18) then 1 elif j=1 and member(i, [7, 12, 15]) then -1 else 0 fi); a := n -> (M^(n+1))[18, 1]; seq (a(n), n=0..51); - Alois P. Heinz (heinz(AT)hs-heilbronn.de), Jul 25 2008

Contribution from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 05 2008: (Start)

# even more efficient:

a:= proc(n) local m, r; m := iquo (n, 10, 'r'); r:= r+1; ([23, 26, 35, 38, 47, 56, 65, 74, 83, 92][r]+ (3*r+ 24+ 10*m) *m) *m/6+ [1, 1, 2, 2, 3, 4, 5, 6, 7, 8][r] end: seq (a(n), n=0..100); (End)

a[n_] := SeriesTerm[1/((1 - x)(1 - x^2)(1 - x^5)(1 - x^10)), {x, 0, n}]

a[n_, d_] := SeriesTerm[1/(Times@@Map[(1-x^#)&, d]), {x, 0, n}] (general case for any set of denominations represented as a list of coin values in cents).

(PARI) a(n)=if(n<-17, -a(-18-n), if(n<0, 0, polcoeff(1/((1-x)*(1-x^2)*(1-x^5)*(1-x^10))+x*O(x^n), n)))

a(n)-a(n-1)=A025810(n).

Sequence in context: A029016 A121385 A029015 this_sequence A001312 A001301 A001302

Adjacent sequences: A000005 A000006 A000007 this_sequence A000009 A000010 A000011

nonn,easy,nice

N. J. A. Sloane (njas(AT)research.att.com).