A089819 Number of subsets of {1,2,...,n} containing no primes.

2, 2, 2, 4, 4, 8, 8, 16, 32, 64, 64, 128, 128, 256, 512, 1024, 1024, 2048, 2048, 4096, 8192, 16384, 16384, 32768, 65536, 131072, 262144, 524288, 524288, 1048576, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 33554432, 67108864

Offset

1,1

Comments

Equivalently, the number of subsets of {1,2,...,n} such that the product of the elements is square, where the empty set is defined to have a product of 1. - Peter Kagey, Nov 18 2017

Links

Robert Israel, Table of n, a(n) for n = 1..3853

Index to divisibility sequences

Formula

a(n) = 2^(n-PrimePi(n)), with PrimePi = A000720.

a(n) = Product_{k=1..n} (2-A010051(k)) = A089818(n,0) = A000079(n) - A089820(n).

a(n) = 2^(1-A010051(n))*a(n-1). - Robert Israel, Nov 22 2017

Example

a(6)=8 subsets of {1,2,3,4,5,6} contain no prime: {1,4,6}, {4,6}, {1,6}, {1,4}, {6}, {4}, {1} and the empty set.
a(7) = 8 as 2^(7 - PrimePi(7)) = 2^(7-4) = 8.

Maple

A089819:=n->2^(n-numtheory[pi](n)): seq(A089819(n), n=1..50); # Wesley Ivan Hurt, Nov 21 2017

Mathematica

Table[2^(n - PrimePi[n]), {n, 50}] (* Wesley Ivan Hurt, Nov 18 2017 *)

Prog

(PARI) a(n)=2^(n-primepi(n)) \\ Charles R Greathouse IV, Apr 09 2012

Crossrefs

Cf. A000079, A000720, A010051, A089818, A089820, A089821, A089822.

Sequence in context: A010238 A178799 A360360 * A059888 A299204 A230141

Adjacent sequences: A089816 A089817 A089818 * A089820 A089821 A089822

Keyword

nonn,easy

Author

Reinhard Zumkeller, Nov 12 2003

Status

approved