login
A369780
a(n) = number of subsets of {1,2,...,n} that contain more primes than nonprimes.
4
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
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 *)
KEYWORD
nonn
AUTHOR
Clark Kimberling, Feb 03 2024
EXTENSIONS
a(23)-a(36) from Alois P. Heinz, Feb 03 2024
STATUS
approved