A262699 List of currency denominations such that any value x > 0 is represented in exactly x ways as a sum of distinct denominations, where a repeated value represents a bill and a coin which count as distinct denominations.

1, 2, 2, 3, 4, 4, 8, 8, 16, 16, 32, 32, 64, 64, 128, 128, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 8192, 8192, 16384, 16384, 32768, 32768, 65536, 65536, 131072, 131072, 262144, 262144, 524288, 524288, 1048576, 1048576

Offset

1,2

Links

Table of n, a(n) for n=1..42.

David Wilson, Currency puzzle, SeqFan list, Sept. 25, 2015.

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

Formula

a(n) = 2^ceiling(n/2-1) for n>4.

G.f.: x*(1 - x)*(1 + 3*x + 3*x^2 + 2*x^3 + 2*x^4)/(1 - 2*x^2). [Bruno Berselli, Sep 28 2015]

Mathematica

LinearRecurrence[{0, 2}, {1, 2, 2, 3, 4, 4}, 60] (* Harvey P. Dale, Jul 10 2023 *)

Prog

(PARI) a(n)=2^((n-1)\2)+if(n<5, !bittest(n, 0))
(Magma)  [n le 4 select Floor(n/2+1) else 2^Ceiling(n/2-1): n in [1..45]]; // Vincenzo Librandi, Sep 28 2015

Crossrefs

Sequence in context: A036813 A036814 A137776 * A153946 A036810 A036809

Adjacent sequences: A262696 A262697 A262698 * A262700 A262701 A262702

Keyword

nonn,easy

Author

M. F. Hasler, Sep 27 2015

Status

approved