A089822 Number of subsets of {1,.., n} containing exactly two primes.

0, 0, 2, 4, 12, 24, 48, 96, 192, 384, 640, 1280, 1920, 3840, 7680, 15360, 21504, 43008, 57344, 114688, 229376, 458752, 589824, 1179648, 2359296, 4718592, 9437184, 18874368, 23592960, 47185920, 57671680, 115343360, 230686720

Offset: 1

Author

Reinhard Zumkeller, Nov 12 2003

Keywords

• nonn

Examples

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

Links

• Robert Israel, Table of n, a(n) for n = 1..3830

Crossrefs

Cf. A000217, A000720, A089818, A089819, A089821.

Programs

Maple

N:= 100: # for a(1)..a(N)
V:= Vector(N):
p:= 1: n:= 1: pi:= 0:
while n <= N do
  p:= nextprime(p);
  for n from n to min(N,p-1) do
    V[n]:= pi*(pi-1)*2^(n-pi)/2;
  od;
  pi:= pi+1;
  n:= p;
od:
convert(V,list); # Robert Israel, Jul 14 2019
# second Maple program:
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, 2):
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, 2];
Array[a, 42] (* Jean-François Alcover, May 30 2020, after Alois P. Heinz *)

Formula

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

a(n) = A000217(A000720(n)-1)*A089819(n);

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