|
%I #21 Jul 10 2023 12:47:06
%S 1,2,2,3,4,4,8,8,16,16,32,32,64,64,128,128,256,256,512,512,1024,1024,
%T 2048,2048,4096,4096,8192,8192,16384,16384,32768,32768,65536,65536,
%U 131072,131072,262144,262144,524288,524288,1048576,1048576
%N 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.
%H David Wilson, <a href="http://list.seqfan.eu/oldermail/seqfan/2015-September/015391.html">Currency puzzle</a>, SeqFan list, Sept. 25, 2015.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (0,2).
%F a(n) = 2^ceiling(n/2-1) for n>4.
%F 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]
%t LinearRecurrence[{0,2},{1,2,2,3,4,4},60] (* _Harvey P. Dale_, Jul 10 2023 *)
%o (PARI) a(n)=2^((n-1)\2)+if(n<5,!bittest(n,0))
%o (Magma) [n le 4 select Floor(n/2+1) else 2^Ceiling(n/2-1): n in [1..45]]; // _Vincenzo Librandi_, Sep 28 2015
%K nonn,easy
%O 1,2
%A _M. F. Hasler_, Sep 27 2015
|
