A219107 Number of compositions (ordered partitions) of n into distinct prime parts.

1, 0, 1, 1, 0, 3, 0, 3, 2, 2, 8, 1, 8, 3, 8, 8, 10, 25, 16, 9, 16, 38, 16, 61, 18, 62, 46, 66, 160, 91, 138, 99, 70, 122, 306, 126, 314, 151, 362, 278, 588, 901, 602, 303, 654, 1142, 888, 1759, 892, 1226, 950, 2160, 1230, 3379, 1444, 2372, 2100, 4644, 7416

Offset: 0

Author

Alois P. Heinz, Nov 11 2012

Keywords

• nonn

Comments

a(0) = 0 iff n in {1,4,6}.

Examples

			a(5) = 3: [2,3], [3,2], [5].
a(7) = 3: [2,5], [5,2], [7].
a(8) = 2: [3,5], [5,3].
a(9) = 2: [2,7], [7,2].
a(10) = 8: [2,3,5], [2,5,3], [3,2,5], [3,5,2], [5,2,3], [5,3,2], [3,7], [7,3].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A000142, A000586, A032021, A218396.

Programs

Maple

with(numtheory):
b:= proc(n, i) b(n, i):=
      `if`(n=0, [1], `if`(i<1, [], zip((x, y)->x+y, b(n, i-1),
       [0, `if`(ithprime(i)>n, [], b(n-ithprime(i), i-1))[]], 0)))
    end:
a:= proc(n) local l; l:= b(n, pi(n));
      a(n):= add(l[i]*(i-1)!, i=1..nops(l))
    end:
seq(a(n), n=0..70);
# second Maple program:
s:= proc(n) option remember; `if`(n<1, 0, ithprime(n)+s(n-1)) end:
b:= proc(n, i, t) option remember; `if`(s(i)`if`(p>n, 0, b(n-p, i-1, t+1)))(ithprime(i))+b(n, i-1, t)))
    end:
a:= n-> b(n, numtheory[pi](n), 0):
seq(a(n), n=0..70);  # Alois P. Heinz, Jan 30 2020

Mathematica

zip = With[{m=Max[Length[#1], Length[#2]]}, PadRight[#1, m]+PadRight[#2, m] ]&;
b[n_, i_] := b[n, i] = If[n==0, {1}, If[i<1, {}, b[n, i-1] ~zip~ Join[{0}, If[Prime[i] > n, {}, b[n - Prime[i], i-1]]], {0}]];
a[n_] := Module[{l}, l = b[n, PrimePi[n]]; Sum[l[[i]]*(i-1)!, {i, 1, Length[l]}]];
Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Mar 24 2017, adapted from Maple *)

Formula

a(n) = Sum_{k=0..A024936(n)} A219180(n,k)*k!.