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

Author

Clark Kimberling, Feb 03 2024

Keywords

• nonn

Examples

			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}.
		

Links

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

Crossrefs

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

Programs

Mathematica

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

Formula

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

Extensions

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