cp's OEIS Frontend

A023360 Number of compositions of n into prime parts.

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