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

Author

David W. Wilson

Keywords

• nonn

Examples

			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.
		

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

Crossrefs

Cf. A000607 for the unordered (partition) version.

Programs

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]

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

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