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,2

Links

Table of n, a(n) for n=1..37.

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.

Example

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}.

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 *)

Prog

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

Crossrefs

Cf. A000720, A089818, A089819, A089822.

Sequence in context: A175841 A293601 A171647 * A343419 A353796 A294067

Adjacent sequences: A089818 A089819 A089820 * A089822 A089823 A089824

Keyword

nonn

Author

Reinhard Zumkeller, Nov 12 2003

Status

approved