A023360 Number of compositions of n into prime parts.

1, 0, 1, 1, 1, 3, 2, 6, 6, 10, 16, 20, 35, 46, 72, 105, 152, 232, 332, 501, 732, 1081, 1604, 2352, 3493, 5136, 7595, 11212, 16534, 24442, 36039, 53243, 78573, 115989, 171264, 252754, 373214, 550863, 813251, 1200554, 1772207, 2616338, 3862121, 5701553

Offset

0,6

References

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 292-295.

Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 501 terms from T. D. Noe)

S. R. Finch, Kalmar's composition constant, June 5, 2003. [Cached copy, with permission of the author]

Philippe Flajolet, More information including asymptotic form (1995). [Broken link]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 43, 298

Formula

a(n) = Sum_{prime p<=n} a(n-p) with a(0)=1. - Henry Bottomley, Dec 15 2000

G.f.: 1/(1 - Sum_{k>=1} x^A000040(k)). - Andrew Howroyd, Dec 28 2017

Example

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.

Maple

a:= proc(n) option remember; `if`(n=0, 1, add(
     `if`(isprime(j), a(n-j), 0), j=1..n))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 12 2021

Mathematica

CoefficientList[ Series[1 / (1 - Sum[ x^Prime[i], {i, 15}]), {x, 0, 45}], x]

Prog

(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

Crossrefs

Cf. A000607 for the unordered (partition) version.

Sequence in context: A347742 A286970 A347743 * A154028 A157793 A096375

Adjacent sequences: A023357 A023358 A023359 * A023361 A023362 A023363

Keyword

nonn

Author

David W. Wilson

Status

approved