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

Links

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

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

Example

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

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

Crossrefs

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

Sequence in context: A092809 A250254 A293344 * A058622 A196021 A064294

Adjacent sequences: A369777 A369778 A369779 * A369781 A369782 A369783

Keyword

nonn

Author

Clark Kimberling, Feb 03 2024

Extensions

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

Status

approved