A089821 Number of subsets of {1,.., n} containing exactly one prime.

0, 2, 4, 8, 12, 24, 32, 64, 128, 256, 320, 640, 768, 1536, 3072, 6144, 7168, 14336, 16384, 32768, 65536, 131072, 147456, 294912, 589824, 1179648, 2359296, 4718592, 5242880, 10485760, 11534336, 23068672, 46137344, 92274688, 184549376, 369098752, 402653184

Offset: 1

Author

Reinhard Zumkeller, Nov 12 2003

Keywords

• nonn

Examples

			a(5)=12 subsets of {1,2,3,4,5} contain exactly one prime: {2}, {3}, {5}, {1,2}, {1,3}, {1,5}, {2,4}, {3,4}, {4,5}, {1,2,4}, {1,3,4} and {1,4,5}.
		

Crossrefs

Cf. A000720, A089818, A089819, A089822.

Programs

Maple

b:= proc(n, c) option remember; `if`(n=0, `if`(c=0, 1, 0),
     `if`(c<0, 0, b(n-1, c)+b(n-1, c-`if`(isprime(n), 1, 0))))
    end:
a:= n-> b(n, 1):
seq(a(n), n=1..42);  # Alois P. Heinz, Dec 19 2019

Mathematica

b[n_, c_] := b[n, c] = If[n == 0, If[c == 0, 1, 0], If[c < 0, 0, b[n - 1, c] + b[n - 1, c - If[PrimeQ[n], 1, 0]]]];
a[n_] := b[n, 1];
Array[a, 42] (* Jean-François Alcover, Nov 07 2020, after Alois P. Heinz *)

PARI

a(n) = primepi(n) * 2^(n-primepi(n)); \\ Michel Marcus, Nov 07 2020

Formula

a(n) = A000720(n)*A089819(n);

for n>1: a(n) = A089818(n,1).

a(n) = pi(n) * 2^(n-pi(n)), with pi = A000720.