cp's OEIS Frontend

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

%I A219107 #23 Jan 30 2020 18:32:06
%S A219107 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,
%T A219107 160,91,138,99,70,122,306,126,314,151,362,278,588,901,602,303,654,
%U A219107 1142,888,1759,892,1226,950,2160,1230,3379,1444,2372,2100,4644,7416
%N A219107 Number of compositions (ordered partitions) of n into distinct prime parts.
%C A219107 a(0) = 0 iff n in {1,4,6}.
%H A219107 Alois P. Heinz, <a href="/A219107/b219107.txt">Table of n, a(n) for n = 0..10000</a>
%F A219107 a(n) = Sum_{k=0..A024936(n)} A219180(n,k)*k!.
%e A219107 a(5) = 3: [2,3], [3,2], [5].
%e A219107 a(7) = 3: [2,5], [5,2], [7].
%e A219107 a(8) = 2: [3,5], [5,3].
%e A219107 a(9) = 2: [2,7], [7,2].
%e A219107 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].
%p A219107 with(numtheory):
%p A219107 b:= proc(n, i) b(n, i):=
%p A219107       `if`(n=0, [1], `if`(i<1, [], zip((x, y)->x+y, b(n, i-1),
%p A219107        [0, `if`(ithprime(i)>n, [], b(n-ithprime(i), i-1))[]], 0)))
%p A219107     end:
%p A219107 a:= proc(n) local l; l:= b(n, pi(n));
%p A219107       a(n):= add(l[i]*(i-1)!, i=1..nops(l))
%p A219107     end:
%p A219107 seq(a(n), n=0..70);
%p A219107 # second Maple program:
%p A219107 s:= proc(n) option remember; `if`(n<1, 0, ithprime(n)+s(n-1)) end:
%p A219107 b:= proc(n, i, t) option remember; `if`(s(i)<n, 0, `if`(n=0, t!, (p
%p A219107       ->`if`(p>n, 0, b(n-p, i-1, t+1)))(ithprime(i))+b(n, i-1, t)))
%p A219107     end:
%p A219107 a:= n-> b(n, numtheory[pi](n), 0):
%p A219107 seq(a(n), n=0..70);  # _Alois P. Heinz_, Jan 30 2020
%t A219107 zip = With[{m=Max[Length[#1], Length[#2]]}, PadRight[#1, m]+PadRight[#2, m] ]&;
%t A219107 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}]];
%t A219107 a[n_] := Module[{l}, l = b[n, PrimePi[n]]; Sum[l[[i]]*(i-1)!, {i, 1, Length[l]}]];
%t A219107 Table[a[n], {n, 0, 70}] (* _Jean-François Alcover_, Mar 24 2017, adapted from Maple *)
%Y A219107 Cf. A000142, A000586, A032021, A218396.
%K A219107 nonn
%O A219107 0,6
%A A219107 _Alois P. Heinz_, Nov 11 2012