|
%I #39 Feb 12 2021 19:40:36
%S 1,0,1,1,1,3,2,6,6,10,16,20,35,46,72,105,152,232,332,501,732,1081,
%T 1604,2352,3493,5136,7595,11212,16534,24442,36039,53243,78573,115989,
%U 171264,252754,373214,550863,813251,1200554,1772207,2616338,3862121,5701553
%N Number of compositions of n into prime parts.
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 292-295.
%D Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
%H Alois P. Heinz, <a href="/A023360/b023360.txt">Table of n, a(n) for n = 0..2000</a> (first 501 terms from T. D. Noe)
%H S. R. Finch, <a href="/A001055/a001055.pdf">Kalmar's composition constant</a>, June 5, 2003. [Cached copy, with permission of the author]
%H Philippe Flajolet, <a href="http://www.people.fas.harvard.edu/~sfinch/constant/backhous/flajolet.html">More information including asymptotic form</a> (1995). [Broken link]
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 43, 298
%F a(n) = Sum_{prime p<=n} a(n-p) with a(0)=1. - _Henry Bottomley_, Dec 15 2000
%F G.f.: 1/(1 - Sum_{k>=1} x^A000040(k)). - _Andrew Howroyd_, Dec 28 2017
%e 2; 3; 4 = 2+2; 5 = 2+3 = 3+2; 6 = 2+2+2 = 3+3; 7 = 2+2+3 = 2+3+2 = 3+2+2 = 2+5 = 5+2; etc.
%p a:= proc(n) option remember; `if`(n=0, 1, add(
%p `if`(isprime(j), a(n-j), 0), j=1..n))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Feb 12 2021
%t CoefficientList[ Series[1 / (1 - Sum[ x^Prime[i], {i, 15}]), {x, 0, 45}], x]
%o (PARI) {my(n=60); Vec(1/(1-sum(k=1, n, if(isprime(k), x^k, 0))) + O(x*x^n))} \\ _Andrew Howroyd_, Dec 28 2017
%Y Cf. A000607 for the unordered (partition) version.
%K nonn
%O 0,6
%A _David W. Wilson_
|
