A369780 a(n) = number of subsets of {1,2,...,n} that contain more primes than nonprimes.

0, 0, 1, 4, 5, 16, 22, 64, 93, 130, 176, 562, 794, 2380, 3473, 4944, 6885, 21778, 31180, 94184, 137980, 198440, 280600, 880970, 1271626, 1807781, 2533987, 3505699, 4791323, 16489546, 22964087, 75973189, 107594213, 150676186, 208791332, 286454524, 389329652

Offset: 0

Author

Clark Kimberling, Feb 03 2024

Keywords

• nonn

Examples

			a(4) = 5 enumerates these subsets: {2}, {3}, {2,3}, {1,2,3}, {2,3,4}.
		

Links

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

Crossrefs

Cf. A000040, A000720, A018252, A037031, A369781, A369853, A369854.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, `if`(t>0, 1, 0),
      b(n-1, t)+b(n-1, t+`if`(isprime(n), 1, -1)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..36);  # Alois P. Heinz, Feb 03 2024

Mathematica

Map[Length[Select[Map[Commonest, PrimeQ[Rest[Subsets[Range[#]]]]], # == {True} &]] &, Range[22]]  (* Peter J. C. Moses, Jan 29 2024 *)

Formula

a(n) + A369781(n) = 2^n-1.

a(n) = Sum_{i=1..pi(n)} Sum_{j=0..i-1} binomial(pi(n),i)*binomial(n-pi(n),j). - Alois P. Heinz, Feb 03 2024

Extensions

a(23)-a(36) from Alois P. Heinz, Feb 03 2024