A369781 a(n) = number of nonempty subsets S of {1,2,...,n} such that (number of primes in S) <= (number of nonprimes in S).

0, 1, 2, 3, 10, 15, 41, 63, 162, 381, 847, 1485, 3301, 5811, 12910, 27823, 58650, 109293, 230963, 430103, 910595, 1898711, 3913703, 7507637, 15505589, 31746650, 64574876, 130712028, 263644132, 520381365, 1050777736, 2071510458, 4187373082, 8439258405, 16971077851

Offset

0,3

Links

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

Formula

a(n) + A369780(n) = 2^n-1 = A369853(n) + A369854(n).

Example

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

Mathematica

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

Crossrefs

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

Sequence in context: A108065 A187767 A226881 * A026336 A027913 A081204

Adjacent sequences: A369778 A369779 A369780 * A369782 A369783 A369784

Keyword

nonn

Author

Clark Kimberling, Feb 03 2024

Extensions

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

Status

approved